Is there any book about memory allocators ?

[Dio]

In my own projects I've never found a need to go beyond the default malloc lib or growable buffer with bulk discard, but I generally fiddle with areas like emulators where runtime dynamic memory allocation is not a major concern.

Obviously I have restrictions about what I can talk about in my professional career, and my memory for things I did 10+ years ago is imperfect.

But if you really care, I don't think it's problematic to say we intermittently used jemalloc inside performance and quality critical AMD drivers and we also kept up with other MIT-licensed allocators out there in case something better came along. This development arose during our investigation of game stutters where threaded memory allocation did appear to be a potential cause for concern and jemalloc appeared to offer better threaded allocation performance at the time. There were other interesting options and techniques which I can't at this stage remember the names of. I was also a maintainer of a few different varieties of our own allocator or allocator related code (some of which was retired when we added jemalloc as an option). I have also written and maintained other allocators, including - many, many years ago - an "it'll only take a couple of days, it's just an allocator" that ended up wasting months and possibly even a year or more of engineer time in total (and that was way before threaded allocators became a requirement). That experience, although entirely backed up by the others, is probably the main cause of my original post in this thread.

For drop-it-in code I would look at jemalloc first, since I'm aware it has a solid reputation in several big projects and I still hear active conversation about it in the game engine space, but I'm not sure if there's something better that's come along in the many years since I was deep in this area. It is however a pretty big beast, and if you want something less full-featured but more easily customisable or less heavyweight in code footprint I would probably look elsewhere and I have limited advice to offer.

[tufty]

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

It's the first tool you reach for when bootstrapping (relatively) low performance bare metal platforms. Because it's cheap to implement tested code, and it works. If you need a C library, it's pretty much all there, in one hit. It's far from being the highest performance tool out there, but it's a very useful tool, and for 99% of cases, you will not need anything more. And it's what I know from bootstrapping platforms, which is why I mentioned it.

Dio's pointed out some more performance oriented allocators if you do need something more. But do you really need it? Is the potential benefit worth the extra overhead and the investment in time and effort? Is the benefit even there? Is it worth the worry of it not working on a new platform? so on, and so on.

It's not rocket surgery, man. FWIW, the whole "nobody would invent anything new if we all used existing code" argument is bullshit. People don't piss about inventing new shapes of wheel, they're inventing more efficient vehicles using existing wheel shapes.

In a commercial environment, I would consider spending time reinventing the memory allocator, if it's not what you've been explicitly tasked to do, as a potentially sackable misuse of company time. If you were to come to me and say "product X is being measurably held up by memory allocation, here's the figures, can we look into alternatives and maybe inventing our own", then it's potentially a valid thing to do. But you have to get it past the bean counters.

[KlaxonCow]

It's the first tool you reach for when bootstrapping (relatively) low performance bare metal platforms. Because it's cheap to implement tested code, and it works. If you need a C library, it's pretty much all there, in one hit. It's far from being the highest performance tool out there, but it's a very useful tool, and for 99% of cases, you will not need anything more. And it's what I know from bootstrapping platforms, which is why I mentioned it.

To reiterate, I don't doubt it's a good library.

My point was that it was not really a good example of "memory allocation" - the topic of the thread - and doesn't provide any abstract data types / data structures - which is really the focus of my class library (and, really, memory allocation is a very minor part of it - that it's all based on an "mmap" wrapper at the bottom, rather than just "malloc").

But you have to get it past the bean counters.

I agree.

But I consider that to be a lament, not a recommendation.


And the thing is, with my class library, it's implementing the basic data structures - linked lists, vectors, "ordered_map" (sorted array for binary searches), hash tables, etc. - and the idea is that I carry it around with me, from project to project.

When I talked about the 69th iteration, I was not imagining that I'd do all those iterations in one go, on a single project. It was more the notion of using it on the next project, and the next project. And then I work out how to make it better, more secure, more useful and revise it as I go along (with the prospect that I could potentially fold it back onto those previous projects and improve those with the latest version of the library).

There's an argument that always starting from scratch, bootstrapping off "newlib" every single time, could be the greater time sink. When you could bring along your linked list or hash table implementation with you through project to project.

It's the Tony Crowther approach, and he was famed for knocking out the titles at a rate of knots. Basically because he took "the guts" out of one game, transplanted it into another and then revised it into a new game. Then did it again, and again. I coded some good scrolling routines there - copy and paste. Rather than starting with a fresh sheet of paper every time, bootstrapping off the standard library.

Bean counters are often bad at seeing the bigger picture. Having the long-term view. As I say, this is a lament, not a recommendation.

[Dio]

But I consider that to be a lament, not a recommendation.

No, it really isn't. Even taking the money aspect out of it, writing boilerplate most of the time is pretty tedious. There are more interesting things to do than reinvent the wheel again and again unless you really are in the mood to reinvent the wheel.

There's an argument that always starting from scratch, bootstrapping off "newlib" every single time, could be the greater time sink. When you could bring along your linked list or hash table implementation with you through project to project.

"Make sure you reuse your own code, but avoid reusing someone else's code because it may be a time sink" is NIH nonsense. Maybe I'm just confused why the code you import into your codebase once can't then be carried around...?

Bean counters are often bad at seeing the bigger picture.

That's only true in dysfunctional organisations - which we all know exist. But in functional organisations, these cost decisions are made by management and engineering in tandem. And, funnily enough, good engineers usually prefer to spend their time writing interesting code that does new and interesting things, not reinventing the wheel.

[KlaxonCow]

"Make sure you reuse your own code, but avoid reusing someone else's code because it may be a time sink" is NIH nonsense.

This is simply a mischaracterisation of my position.

I've already said that, broadly, I agree with you. That we should not go unnecessarily reinventing wheels - but I added the "unnecessarily" caveat, because sometimes wheels do need to be reinvented (or, more precisely, refined to a particular purpose - as we're not actually reinventing the concept of a wheel).

Indeed, I tried to summarise it here:

Bottom line: Ideally, yes, don't reinvent wheels and use someone else's library. In practice... it's complicated and not nearly so simple.

That, in essence and theory, you're right. But, in practice and reality... ah, things can be shades of grey and not so clear cut.

I feel you're polarising this. That if I don't 100% agree with you to the letter, then I'm characterised as "not invented here" and advocating to always reinvent wheels constantly. Which is just NOT what I've been saying at all. Very much an "you're either with us, or against us" binary attitude.

If I were to similarly mischaracterise your position, in much the same way, then the accusation would be that you're saying we should only ever use someone else's code and never should write a single line of our own code ever. It should be 100% "someone else's code" throughout.

Which, of course, would equally be a gross mischaracterisation of what you're saying, and an equally daft position to take.

100% "not invented here" is daft, but so would 100% "never own code".

Ergo, the truth lies somewhere in the middle. A balance. A trade-off. That it is shades of grey and fuzzy... and that's actually been my position here.

And I notice that it's been conveniently overlooked that when giles was brought up - as the originator of the thread and someone who needs to practically get things done - his position was closer to mine (that it's sometimes necessary, sometimes a bit "shades of grey" what you have to do to get things pragmatically done, etc.).

The "with us or against us" attitude feels almost cult-like, to be honest, when your opponent has not - and will not be - saying that you're in any way wrong.

Only that, in the daily grind - the cut and thrust - then things can be more nuanced and fuzzy. It ain't necessarily so.

[Dio]

I think I'm just confused about what you're saying, which I totally accept may be on my end.

Agreed on shades of grey, but the point is that this is one of the less grey cases.

[KlaxonCow]

I think I'm just confused about what you're saying, which I totally accept may be on my end.

And possibly a little on my end too, as tufty tends to be forthright and, thus, tends to embolden a more bullish response.

So I might be over-defending the opposing argument, but only in the interests of giving it a fair hearing that there is an opposing argument and it's not always illegitimate.

[tufty]

tufty tends to be forthright

I do.

here's an argument that always starting from scratch, bootstrapping off "newlib" every single time, could be the greater time sink

Let's be clear. I'm talking about platforms where there is no underlying anything. So if you want to bring something like a RTOS to it, you need to implement something underneath it. This involves, pretty much, writing sbrk() and a serial port shim layer. Build newlib, buils RTOS. Working system. this is a couple of hours' work, from nothing to a running RTOS. More time reading datasheets beforehand, obviously, but it really is that simple. The only stuff "invented here" is usually ripped direct from the datasheets / programming manual.

And the thing is, with my class library, it's implementing the basic data structures - linked lists, vectors, "ordered_map" (sorted array for binary searches), hash tables, etc. - and the idea is that I carry it around with me, from project to project.

And the benefit over using the existing STL / Boost is ...?

I was in at the start with C++. When the only compiler available was Cfront. At that time, there was a move towards using provided class libraries - after all, why bother writing your own buggy implementation of a linked list when there's an off the shelf one available. Sure, they cost money, but it cheaper to pay for someone else's debugged code than paying to code and debug your own. that was the thinking. I was involved in developing one of these, and it's highly probable that my code is still running out there in the wild. the problem with class libraries is that they enforce a way of writing the code that interfaces with them, and if you have 2 class libraries that enforce different ways of thinking, it gets messy n a hurry. I saw a few projects fail partly because of this. STL changed that. It was free, it was generic, and it was available everywhere. And it's bloody good. It enforces a way of coding, sure. But the cost of ripping out all that oracle class library crap and replacing it with STL was in many cases worth the investment, as it harmonised the codebase. Extending STL is pretty easy, and very performant. These days, you don't even do that. You layer Boost over the STL. Maintaining your own C++ library that isn't based on this is pure NIH.

Whoops, there I go again :)

[KlaxonCow]

The C++ STL just uses "operator new", which typically just uses "malloc".

One of the main reasons for writing a custom allocator is performance. Utilizing a specialized custom allocator may substantially improve the performance or memory usage, or both, of the program. The default allocator uses operator new to allocate memory. This is often implemented as a thin layer around the C heap allocation functions, which are usually optimized for infrequent allocation of large memory blocks. This approach may work well with containers that mostly allocate large chunks of memory, like vector and deque. However, for containers that require frequent allocations of small objects, such as map and list, using the default allocator is generally slow. Other common problems with a malloc-based allocator include poor locality of reference, and excessive memory fragmentation.

Although, of course, I am pulling that from the Wikipedia page about custom allocators, which is the potential solution to these issues.

That you create your own custom allocator - such as a memory pool, based on "mmap" instead of "malloc" (for the reasons I've stated earlier: that pages are fixed size, so are effectively memory-pool-like and that allocation / reallocation / deallocation is often handled by the OS via page tables, so they don't suffer from external fragmentation).

But, sure, write that custom allocator and then use the STL containers. That's a valid approach.

(Mind you, the STL containers are not thread-safe out of the box. An intentional design. But it means that you've got to get involved to make them thread-safe... and the thing is, that's the hard bit that I'd gladly take "someone else's code" to have it done properly for me, but that's the bit that the STL doesn't actually do, so you've got to put that "own code" in anyway.)

But are you spotting the pattern here? You mention "newlib" and when I dig down, it's just "malloc". Okay, what about the STL? Dig down and it's usually just wrappers around "malloc".

Also, with "newlib", we saw that it just had "_malloc_lock" and "_malloc_unlock". That its locking, for multi-threaded code, is not selective and basically just locks everything out en masse. That it uses a big critical section around all of "malloc", rather than selective locking around individual items or even being coded in a lock-less or optimistic fashion.

This is another thing about "someone else's code". There's just the assumption that it's just better, and that whoever coded it solved these problems for you.

There can be deference to its "superiority", and this almost cult-like devotion to that - taken as read to "use someone else's code" and it'll automatically be better for it - but it's just an ordinary man behind the curtain, and the library is, when you dig down, just taking a global lock and doing "operator new / operator delete" as a wrapper around "malloc / free".

BUT the real argument, which is entirely 100% correct, is that you can't do everything. You can and will lean on "other people's code", as it can't pragmatically be done otherwise.

All I'm saying is that this is more of a "tight race" between the two than is often portrayed, and there's more nuance and complication, than simply saying "always use someone else's code" suggests.

Where to draw the line? That's really not as simple a question to answer as it might first appear.

[gilesgoat]

" .. de le umane cose
Tanto sperimentar, quanto ti basti
Per non curarle: .. "


Alessandro Manzoni , "For the death of Carlo Imbonati" 1805 ...

[Dio]

Ha, don't mention Boost in the game programming community. The pitchforks come right out .

[Dio]

Also, with "newlib", we saw that it just had "_malloc_lock" and "_malloc_unlock". That its locking, for multi-threaded code, is not selective and basically just locks everything out en masse. That it uses a big critical section around all of "malloc", rather than selective locking around individual items or even being coded in a lock-less or optimistic fashion.

There's a reason I called out threaded allocators as a cast-iron nightmare, I've worked on them. And as for lockless allocators - these are nearly impossible to write and more than nearly impossible to test. (free on arbitrary threads, in particular, is awesomely hard).

After two of us battled for two months with one particular lockless algorithm I actually changed our coding standard to say "don't do this" because we couldn't envisage any circumstance in which the maintenance and future uncertainty debt of lockless code was outweighed by the benefits.

So while yes, a library using global lock for malloc is 'bad' on some level, that's even less of an argument for doing it yourself, because doing more than global lock is at least one and maybe two orders of magnitude harder than global lock. The barrier you have to cross to DIY gets much higher, not lower.

[GoatFoam]

Lockless anything is a bit hellish. I remember Fredor Pikus talking about a bug in a lockless data structure that manifested so rarely that the first time they saw it the code had been in use for almost a decade and the corrupted structure was many TB in size.

I have some lockless code in my system, and I think it works...

[Dio]

The ones you can do with a single atomic substitution are workable, but frankly I'm done with anything else.

[gilesgoat]

All those discussions apart ... back to the original title .. "is there any book written about ... " ?