Is there any book about memory allocators ?

[gilesgoat]

If you used Unreal Engine, the codecs are all in there...

coat->get();

Wait until Unreal/Unity will come knocking to your doors saying "and now you do what WE tell you to do, if we say 'jump', you jump !".

When a video card won't be any more "a video card" but "a thing to run the UE/Unity Engine" ..

( or wait, is that already happening ? )

[KlaxonCow]

Just reading this from giles' original post:

Then you have the "free" someone says "I don't need X any more", you can mark that block as "Free" ..

And there starts where I started to go into "bananez territory", first of all even this "list of blocks" cannot be "infinite" and/or "expand all time" becuase it would mean that then you have "a mem allocator" for the list itself but still in any case "can't expand to infinite".

It may get to a point you still in theory have free mem in "Pool A" but you exhausted all mem to keep track of it.

So, basically, the issue that's bothering you is the memory you need - the "overhead" - to keep track of what's free and used?

The approach I took with my "Pool" class is a consolidating free list. The free list is a list of blocks, not individual elements. There's a tiny bit more fiddling involved, granted, but it ensures that the memory for keeping track of things is always minimal.

For example, the free list for an empty pool would be one entry. A block that starts at index 0 and has a size of the entire pool.

If you then allocate from the pool, it'll find a block that's got a "size" big enough to satisfy the request and simply shifts the "index" of the block forward by the amount of items being allocated, and reduces its size by that amount too.

By doing things in blocks like this, it's not just minimal storage but it's easy to find a block of available slots big enough to satisfy a request. I'm just looking for a block size that's greater than or equal to the amount of items that need to be allocated. Allocating them, in terms of the free list, is only adding to the index and subtracting from the size of that block.

The price that's paid for this, though, is deallocation is a bit more fiddly. Because when you give it back, you've either got to add it back to an already existing block - if the item is before or after an existing block, add it to that block - or you create a new block in the free list, if there are "used" slots either side of it, so it can't be consolidated into an existing block.

Then - oh, it gets better - there's the idea of a free block, one allocated item, then another free block. In giving that item back, it's not just adding it onto the end of the first free block. It's also that both free blocks now meet, so we want to consolidate that into one big contiguous free block.

This is why I call it a "consolidating" free list. And the way I do it is that there's a routine within it that consolidates free blocks together. So a dellocation is actually just adding a new free block to the list, then I run "consolidate", which joins blocks together in the free list until we've got the minimal consolidated list.

This is more faff. But it's only paid on deallocation. And it's only an "admin" thing - none of the actual data is moved or anything, it's just re-arranging the free list only. And it does mean that your worry - that the amount of memory used on simply keeping track of things would itself become quite substantial - is reduced to the minimum.

There are other ways to do it. There's the "bitmap" approach where you just have a bit for every slot - 0 means it's free, 1 means it's empty - and so allocation / deallocation is just flipping bits on and off. Which is faster for that aspect, but it's slower to find available contiguous slots to meet an allocation, as you'd have to scan through the "bitmap", looking for enough zero bits in a row to meet your allocation.

And the thing with the "bitmap" approach is that the size of your "bitmap" is proportional to how many items you've got, so that's the kind of data structure that might have you worried - that the "bitmap" ends up taking up quite a bit of space itself (you see this with page tables in the OS, that the page tables themselves actually become a beefy data structure in themselves, just to keep track of all the pages - and that's why CPUs do have things like "huge pages", as maybe dividing things up into 4K pages is a bit too small a division, leading to some quite massive "page tables" to track it all).

Mind you, if you only ever allocate / deallocate one item at a time, then that's not a problem. But allocating / deallocating one at a time is also just generally slower overall, as you're paying the "overhead" price every time.

Basically, this stuff is always a trade-off.

You make this bit faster, but it usually means something else gets slower. And, of course, just the general "memory vs. CPU time" trade-off. My consolidating list uses less memory than a bitmap, but I use up some CPU time on doing that consolidation.

I've gone for this scheme - which is "fast allocate, slower deallocate" - because, you know, it's possible to be "lazy" with deallocation. I can leave "dead" objects in the pool for a bit - it's a waste of memory, but it's otherwise harmless. And there's the possibility of waiting until there's a bunch of them to deallocate and doing them all en masse in one go (because my "insert" and "remove" procedures do allow for allocating / deallocating multiple items in one call).

In a sense, it's one of those "there is no right answer" things. I mean, there objectively are ways that work better / faster than others. But you do reach that "trade-off" point, where it's, like, "do you care more about less RAM or less CPU?". I feel my consolidating free list balances it nicely enough, in a way that I reckon it'll actually be used.

Indeed, I know - because I wrote it - where it's strong and where it's weak, so I'll use it in a way that'll avoid its weaknesses and play to its strengths. And that, of course, can be added to the list of reasons why "someone else's code" can be an issue - if I don't know how someone else's "pool" or "vector" class works, then I might end up using it in a way that emphasises its "worst case scenario". I don't know. I've not seen the code.

To that end, generic libraries will therefore tend to try to be "everything to all people" and balance to all cases. So however someone uses it, it'll be at least okay on the memory / performance. But that could be leaving stuff on the table. It might be possible to have it be faster or use less memory by doing it a certain way - but, yes, that certain way insists you've got to use the class in a particular way to really exploit that.

I can't remember who said it - probably Knuth? - but it's along the lines of "all coding is trading one thing off against another".

[tufty]

Allocation is cheap, and in most cases you aren't allocating and deallocating all the time. Deallocation is cheap, and can usually be put off until it's convenient. But if you haven't specifically designed your allocator to not shit over cache coherency, you're almost certainly killing performance on all your memory accesses. And then there's thread safety. and, and, and... We're not on the 8 or 16 bit processors any more, Dorothy.

As Dio said before, writing a good memory allocator is not trivial, it's not easy, and takes an enormous amount of time and effort. The chances that you are going to do a better job than the "generic" allocator you have available to you is close to zero, unless you have an extremely specific memory access pattern, and even then, you are going to waste time and kill performance in the process.

Writing a high performance allocator is an interesting project, for sure. It's a research paper, even. But if you're trying to get software out of the door, it's a total waste of time. It's like starting to plumb in a radiator, and deciding to make your own copper tube to feed it.

[Dio]

Wait until Unreal/Unity will come knocking to your doors saying "and now you do what WE tell you to do, if we say 'jump', you jump !".

When a video card won't be any more "a video card" but "a thing to run the UE/Unity Engine" ..

( or wait, is that already happening ? )

Hell yes, this is a couple of days of my month. I have good friends in both engine teams.

[GoatFoam]

It's not strictly about allocators, but I have a very good book about garbage collection strategies.

https://www.amazon.co.uk/Garbage-Collec ... 0471941484

It's getting on a bit now but I doubt much has changed.

[tufty]

The interesting and up to date stuff is gonna be found in academic papers and patents, rather than books.

This sort of search could be useful on a purely "for interest" basis. https://scholar.google.co.uk/scholar?hl ... +algorithm

[gilesgoat]

Wait until Unreal/Unity will come knocking to your doors saying "and now you do what WE tell you to do, if we say 'jump', you jump !".

When a video card won't be any more "a video card" but "a thing to run the UE/Unity Engine" ..

( or wait, is that already happening ? )

Hell yes, this is a couple of days of my month. I have good friends in both engine teams.

As long as they don't start saying " .. and you won't distribute any more documentation ( DOES IT EXIST ? ) / code samples / anything to anyone so NO ONE ELSE BUT US will know how to use/code for GPUs ? " ...

They are trying that aren't they ?

[Dio]

No, they want more of that stuff, because fundamentally they're in very much the same position as you. And hiring is a big thing for them, it's tough to hire into core engine positions, so they're big on developer education, particularly in universities.

[KlaxonCow]

No, they want more of that stuff [...] so they're big on developer education, particularly in universities.

And this is the logical contradiction.

On the one hand, if someone shows interest, they're immediately put off the concept: "use someone else's code", "you'll fail, so give up", "it's way too hard for anyone to understand" and that general sense of "pay no attention to the man behind the curtain".

But, on the other hand, they want more of this stuff and they're big on developer education, as there's not enough of it about and it's needed.

I think that folks don't connect these two things in their minds, and don't realise that maybe they're actually creating the shortage. Because, if anyone tries, then "no! Don't do that!". Umm, okay, then. If you say so. But then "why can we not find anyone with the expertise?" later on. Well, exactly because you told them never ever to try. And they believed you.

But if you haven't specifically designed your allocator to not shit over cache coherency, you're almost certainly killing performance on all your memory accesses. And then there's thread safety. and, and, and... We're not on the 8 or 16 bit processors any more, Dorothy.

Here's the problem.

You speak too eloquently on the matter.

So I know you've had a go at it. Only someone with experience jumps immediately to the pain points like that.

Thus, you advise that which, at some point, you defied.

This is fine. There is no hypocrisy there, as you've simply learnt your lessons. But it changes the weight by which your words should be interpreted.


I still refer to the point that, unless someone defies the advice, then we'd have no-one actually writing all that "someone else's code" that we all depend on.

Yes, use Unreal Engine. But Epic implicitly must defy the advice to have created Unreal in the first place.

And that was a hint I was giving with my earlier examples. Notch defied advice... and is now a billionaire, having written the best-selling game of all time (which is very much based on being a voxel engine, that "someone else's code" wouldn't actually do well back in 2010). Carmack defies the advice... and is a billionaire, who created genre-defining titles that, really, we're all just copying Carmack, even now. Epic defies the advice... and makes a nice little income from their cut of sales. Valve defied the advice... and they're living it large on Steam money.

Of course, this does not mean that defying the advice inherently means you'll succeed and be living it large.

But there's a simple wisdom I hold: "When you copy other people, the very best you can do is match them". You have to stop copying people and doing risky shit that no-one's quite sure will even work, if you want to exceed what everyone else is doing.


Anyway, does it need to be the very best, most perfect, totally optimised memory allocator ever conceived?

No, it doesn't. It just needs to be good enough. With a view to making it better.

Do you think that the first iteration of memory management in, say, the Unreal Engine was 100% perfect?

No, it wasn't. But it worked and it was good enough. And then they made it better with each iteration.


This is a thing. I've worked with a small film company - nominally to do the audio, but I ended up on camera and doing some of the editing too - and films are NOT filmed in chronological sequence. My mother is a writer, and books are never done on the first draft - it's a back-and-forth between author and editor that hones it. I do - or have experience of - many different arts and crafts, and the rule is that NOTHING is ever perfect on the first go.

We only generally ever see the end result, so you can be tricked into thinking it emerged from the Ether in perfect form, just like that, on the first attempt. But, if it's any good, then it absolutely never did that.

I think it's a Knuth-ism: "all good code is written at least twice". Bill Gates, for sure, had a "rule of three" that nothing's any good until the third iteration - because I'm sure that Valve's refusal to do threes boils down to ex-Microsoft employee Gabe Newell's refusal to agree with Bill over that.

Bill's formulation was along the lines of: "the first time, you're learning what the fuck you're doing, so it'll suck. The second time, you now know how to do it, so it'll work. The third time, you're going beyond 'it works' to 'it works exceedingly well' and you're optimising things. Ergo, things ain't really any good, contends Bill, until "third time's the charm".

This is not the first time I've written these things. Won't be the last. Every time I fuck up, the next version dodges that problem from the off, because I simply know what's coming.

Man, by the 69th iteration, you'll be seriously impressed and wondering how the hell did I get so good at this shit? No other reason than I kept fucking doing it.

"We choose the Moon. Not because it's easy, but because it's hard."

[Dio]

I don't get this. I specifically said, write a memory allocator if you want to learn about one. I didn't say anywhere that that wasn't an interesting or useful thing to do.

But what we certainly are saying that in production code you probably shouldn't use your own because it will almost certainly be much worse than one you don't write unless you spend a disproportionate amount of effort on it (say, a few months of full time effort, and a probably a few weeks a year on maintenance to avoid it going off in the fridge - that's a terrible ROI for a professional programmer working in a small team, who can't afford to do three and certainly not 69 iterations of anything that you can download and plug into your code in five minutes).

What you suggest is dangerously close to saying that everyone else's code is worse than the code you write yourself and / or not to be trusted, which would just be pure not-invented-here. NIH is crippling for productivity and 100% not the attitude of a professional software engineer.

You simply can't live like that today. The majority of things you want to do in a computer program cannot be fiddled with by a single person. Even if you constrain it to a small space, it's simply impractical. For example, go try write a video codec. I know the best performance video codec engineer in the world (we compete on TIS-100) and I think he's the only person who could single-handedly take one to shipping quality. I bet even he would argue he's part of a big team that makes it possible. Every one of us is therefore optimising what we work on for what's achievable and useful every single day and yes, that should include things that are possible by one person. Because there are more interesting and more useful and more fun and more YOU things to do somewhere else than writing a frickin' memory allocator. Use the tools you can find; craft some art. Don't build tools for the sake of it, build them when you need new tools to build the next bit of art - or if you really love building tools of course!

And this is the logical contradiction.

On the one hand, if someone shows interest, they're immediately put off the concept: "use someone else's code", "you'll fail, so give up", "it's way too hard for anyone to understand" and that general sense of "pay no attention to the man behind the curtain".

But, on the other hand, they want more of this stuff and they're big on developer education, as there's not enough of it about and it's needed.

I think that folks don't connect these two things in their minds, and don't realise that maybe they're actually creating the shortage. Because, if anyone tries, then "no! Don't do that!". Umm, okay, then. If you say so. But then "why can we not find anyone with the expertise?" later on. Well, exactly because you told them never ever to try. And they believed you.

This is an entire invention in your own mind, as nobody here said anything remotely similar to what you say, and no software professional in the wider world has this attitude.

[tufty]

So I know you've had a go at it. Only someone with experience jumps immediately to the pain points like that.

Even if I hadn't, I would have jumped to the pain points (and those are only a few of them). Like you, I am someone who has been programming for <mumblety> years, and like you I understand, at least on a conceptual level, the differences between the generation of processors we grew up with, and the the generations of processors that have followed.

As it happens, yes, I have written memory allocators. I write compilers for high level languages, targetting bare metal, for fun, you can't get away from them in that case. Unless you're relying on something like newlib, which is what somebody sane would do. However, I am not sane, and I'm treating memory allocation strategies as a part of the compilation process. Just one more optimisation step. But I'm not an expert, my memory allocators are pretty crap, I would almost certainly be better off using newlib, and there's probably a massive security hole, if not multiple massive security holes, floating around in the middle of my allocation code.

I'm doing it for fun. No project to get out of the door, no requirement for any of this to even work. Wasting time, but it's better than watching the crap on the TV. Or Nukie, as the irc inhabitants found out last night. Admittedly, shoving blunt instruments under your fingernails is better than watching Nukie.

Giles, who started the thread, has software to get out of the door. He has bills to pay with that software. The software is expected to work. It's expected not to have massive security holes in it. It needs to be fast. I would argue that in his case, unless there is a very specific and obvious problem with the standard allocator, he should be using the standard allocator. No ifs, no buts, no maybes.

As for the "if people didn't do it, there would be no advances" - maybe so, but the people doing it and making the advances are in academia, or are employed by the people developing the chipsets. J Random User (i.e. us) is not going to suddenly make an advance that improves matters. We will waste our time, and people will laugh at our inadequate efforts as they use the security flaws we have introduced to hack into the products we produce. If we're lucky, maybe they will fix some of the bugs on the way so that their malware runs properly.

[gilesgoat]

Giles, who started the thread, has software to get out of the door. He has bills to pay with that software. The software is expected to work. It's expected not to have massive security holes in it. It needs to be fast. I would argue that in his case, unless there is a very specific and obvious problem with the standard allocator, he should be using the standard allocator. No ifs, no buts, no maybes.

" he should be using the standard allocator. "

Except that there isn't one available, that's why I had to write one.

As for the "if people didn't do it, there would be no advances" - maybe so, but the people doing it and making the advances are in academia, or are employed by the people developing the chipsets. J Random User (i.e. us) is not going to suddenly make an advance that improves matters. We will waste our time, and people will laugh at our inadequate efforts as they use the security flaws we have introduced to hack into the products we produce. If we're lucky, maybe they will fix some of the bugs on the way so that their malware runs properly.

I disagree with that, I think it's very important that "people do things" the "academia" for what I know "is NOT what used to be" and you may more likely get "serious advances" in the "industry" because they have real problems where they need real working solutions and possibly "in a finite amount of time".

The academia has a problem with "fundings" that lead to "weird shit" to get them.

I believe that "there is still and there always should be a place for bedroom coders" people that do things "because they want to do them" I do believe that "J Random User" CAN make a difference .. maybe more "cause luck" than anything else but it can still happen and you should never "put down" people we could say otherwise "you are totally wasting your life with what you do Tufty, it's completely pointless, stop doing it !" ..

But you still do it because you want to do it.

I don't like at all and "I don't believe it" in "it's too big, it's too complex, it's no point doing" .. YOU FUCK ALL WITH THAT ! "If you want to do something, DO IT !" I don't give a frak if there's UE or Unity or anything else because I don't want to live my life "their way" I want it MY WAY !

That's why I'll never get millionaire, it's never going to be "huge mainstream" it's never (?) going to replace those things .. but it's my thing, our thing of Llamasoft, done "the Llamasoft way".

And one day someone maybe will say "that there are not any more people like us that do 'their own way' " and that day I think it'll be a great loss, not about us, but about the fact that really "there aren't any more those people".

I think "we need" those people "thinking out" "doing somehting out" "doing something that should not be done" because yeah maybe "the academia" will find some things "the academia way" .. "the industry" will find some things "the industry way" but "those nerds" will find things that none of both will find "in other ways".

Anyway "never stop trying shit, even if it's pointless", much worse is NOT trying anything because you think "it's not worth it", you'll die thinking at what you never tried.

[KlaxonCow]

Unless you're relying on something like newlib

https://sourceware.org/newlib/

Looking at the docs for newlib, this seems to just be an alternative C standard library, with some extra goodies provided.

The only routines that seem to deal with memory management are "malloc", "realloc" and "free". And here's what the docs say:

These functions operate by calling the function _sbrk_r or sbrk, which allocates space. You may need to provide one of these functions for your system.

Here's what Wikipedia has to say about "brk /sbrk":

brk and sbrk are basic memory management system calls used in Unix and Unix-like operating systems to control the amount of memory allocated to the data segment of the process.
[...]
sbrk and brk were considered legacy even by 1997 standards (Single UNIX Specification v2 or POSIX.1-1998). They were removed in POSIX.1-2001.

So all "newlib" appears to be doing is moving the program break. For embedded systems, you'll have to supply the "sbrk" call.

Indeed, you also might need to define "_malloc_lock" and "_malloc_unlock" too:

The malloc family of routines call these functions when they need to lock the memory pool. The version of these routines supplied in the library use the lock API defined in sys/lock.h. If multiple threads of execution can call malloc, or if malloc can be called reentrantly, then you need to define your own versions of these functions in order to safely lock the memory pool during a call. If you do not, the memory pool may become corrupted.

A call to malloc may call __malloc_lock recursively; that is, the sequence of calls may go __malloc_lock, __malloc_lock, __malloc_unlock, __malloc_unlock. Any implementation of these routines must be careful to avoid causing a thread to wait for a lock that it already holds.

So, it doesn't really provide concurrency, but is just coded with that in mind - it can hook into "_malloc_lock" and "_malloc_unlock" and you actually supply that.

It also doesn't seem to be at all selective. You're locking and unlocking the whole data segment every single time? That doesn't sound multi-threading friendly to lock out the entire memory pool, and stall everything, when - being selective - you can just lock what's being changed and leave everything else that's nowhere near it continue.

Where are the abstract data types? Vectors, linked lists, binary search trees, stacks, queues, hash maps, etc.? It seems to provide zero assistance with data structures.

I'm sure it's a very nice alternative implementation of the C standard library (plus a few extras). But it's just an alternative implementation of the C standard library (plus a few extras).

It's just using "sbrk" to expand and contract the size of the data segment.

From the Wikipedia article on "sbrk":

In the original Unix system, brk and sbrk were the only ways in which applications could acquire additional data space; later versions allowed this to also be done using the mmap call.

And that's what I'm doing. I'm using "mmap".

I'd also say that my "class library" is more about "abstract data types". Linked lists, trees, binary search, hash tables, stacks, queues, etc. which are data structures.

The only bit that's really "memory allocation", rather than just data management, is that they all sit on top of "Mapping", which is a wrapper for "mmap". And I'm not really doing memory allocation at all, I'm calling the OS to do all that for me.

Indeed, one could argue that coding memory allocation / deallocation routines is just "reinventing the wheel" of what the OS necessarily has already.

"mmap" works in pages. But that's fine. "Mapping" treats it as "reserve", so you can allocate / reallocate / deallocate within that page and it'll just use the reserve, until it really needs a brand new page.

I've looked at this "newlib". It's not particularly impressive, as the docs say that it's just calling "sbrk".

And it's the C standard lib, not the C++ standard lib, so it lacks any useful support for those most basic abstract data types. How's this supposed to help avoid reinventing the wheel again?

Yeah, sorry, I actually peeked behind the curtain, and it's just a man with parlour tricks, it's not really an actual wizard.

"Because, because, because, because, because... because of the wonderful things he does!"



(Well, you did call me "Dorothy" earlier, so it's only fitting.)

[Dio]

newlib's not the best example, I think. I've some experience with jemalloc, which is pretty complete and well tested due to being very widely used, and looked a bit at tcmalloc and mimalloc as well.

[KlaxonCow]

newlib's not the best example, I think.

I agree.

I've some experience with jemalloc, which is pretty complete and well tested due to being very widely used, and looked a bit at tcmalloc and mimalloc as well.

Cool. I'll look into those.

(Like, you see, I'm not against using other people's code. I already said - more than once - that I totally agree with you that you should not unnecessarily reinvent wheels. I added the "unnecessarily" caveat, just because, in reality, it sometimes honestly is necessary. I'm really not the extremist here. My stance is really "it's complicated". Ideally, yes. In practice, maybe. Sometimes no. I'm just trying to be intellectually honest that things aren't really black-and-white in actual reality. There are shades of grey. I'm absolutely not saying "not invented here" - as I say, my code uses "mmap". I like to use the OS API directly - cut out the "middle man" - but I'm totally using someone else's code in the OS itself. Or the OpenGL / Vulkan libraries. Or, if I need compression / decompression, then I'll link ZLIB in there. I'm using plenty of "someone else's code".)

Mind you, I do find the tone here interesting.

Because you say "use someone else's code". I criticise the one example I've been given - newlib - and you agree that, yeah, that's probably not the best example to use. Not that it's a bad library, I don't doubt, but just that it's not making a good example for the point being made here.

And this is what I find interesting. You have some experience with jemalloc. And you've looked a bit at tcmalloc and mimalloc.

Cool. But only "some experience"? Only "looked a bit at..."?

Your tone is interestingly non-committal here. "Maybe". "Looked a bit at...". "I've some experience with...".

If you're always using other people's code, as you advise, then why don't you have a "I always use this, every single time, it's brilliant" suggestion?

When you are using other people's code, whose code is that exactly?

You're advising something. But when we get to the nitty-gritty of providing examples - because, okay, I am genuinely willing to give anything a look, as if you have that perfect library that nails it all, requiring zero effort on my part, then I do want to know about it - it's all a bit fuzzy and nebulous.

For the sake of argument, I am going to take your advice. Let's use someone else's code. Cool.

So name one. Which one should I be using? Not theory - actual names and numbers, please.