Is there any book about memory allocators ?

[Little stoned kiwi]

Just coble it together in Python and bang it in a Docker container for distribution.

[KlaxonCow]

Are you writing your own operating system and video drivers? Filesystem handlers?

Back in the DOS days then, yeah, I played around with such things.

Creating these little bootable floppies. Using the BIOS "int 13h" routines, in a bootsector, to read more sectors into RAM. Using "int 10h" and the memory-mapped I/O on VGA to do graphics.

But, anyway, you're not really addressing my actual point at all.

Someone somewhere out there has to be writing all these libraries that everyone else is using. Someone somewhere out there has to defy that, or there simply isn't any libraries or "someone else's code" to be used by everyone else.


And then I gave a few examples of folks - like the successful billionaires of John Carmack and Notch - who've done very well, thank you, for defying your advice by becoming the mavericks who didn't just use someone else's library, but wrote their own.

And I mentioned that just to emphasise the essence of that JFK quote: "We choose the Moon, not because it's easy, but because it's hard".

The President's point being that, yes, choosing the Moon is way harder than not choosing the Moon... but you sometimes choose the hard path, quite purposefully, as the rewards - the learning experience, the pay back, etc. - absolutely justify the pain of getting there.

There's also another reason to mention Notch's Minecraft, in that the voxel engine he created essentially is the game. And Carmack's engines for DOOM and Quake, particularly, were also genre-defining.

That is, those games are their engines. You can't decouple the one from the other, and you couldn't have those games without their respective engines.

Those games can only exist - and went on to be successful - because they didn't just use someone else's code and do what everyone else was doing.

I mean, we could extend this to the "reductio ad absurdum". Why bother coding at all? Let's just ask CHAT-GPT to write all the code for us. Using AI to automate the process - which you could also do manually - of stitching together other people's code. And, there you go, "no code" coding the whole lot.

This is a philosophical thing.

Are you doing this because you enjoy it and are passionate about it? Or is it literally just a case of always looking for the fastest possible route to money, as the only overriding concern?

Okay, I'm being unfair to make that a stark binary choice. In reality, people are ticking both columns, because you do, in this world of ours, need to make a living to be able to afford food and rent and electricity and shit.

To be clear, I would actually agree with you that if there's a good library and there's really no need to "reinvent the wheel" then don't reinvent the wheel. Particularly if you've got a deadline to meet.

But I just have to point out - as a point of intellectual honesty - that "the wheel" has, in fact, been regularly reinvented over and over again. Wooden wheels, metal wheels, spokes, pneumatic tyres, etc. or stick teeth on a wheel and you've got a cog. Put the wheel on a stick and now you've got a valve or a dial.

You're saying "don't reinvent the wheel". But I'm revising that to "don't unnecessarily reinvent the wheel". But, actually, sometimes you do need to reinvent those wheels and can actually make a better wheel than current wheels - and this process has happened innumerable times over the centuries.

The modern wheel, of course, remains round. That fundamental characteristic of a wheel. But, if you think about it, then absolutely nothing else, besides that, is remotely the same between the modern wheel on your car and some neolithic "caveman" wheel. The shape really is the only thing that was not "reinvented" there - absolutely everything else about it was reinvented. Many times.

What matters more to you? To make money in the shortest possible time with the least effort, or to progress the art ("Ars Gratia Artis", as the MGM lion has it, meaning "Art for Art's Sake")?

I'm not saying one is better or worse than the other. Both are most definitely needed at different times (art needs to be paid for, so folks do need to make money at some point, just to fund it all to continue, if nothing else).

Indeed, I think the real mistake here is the belief that there's only one universal "right answer" to the question.


A man goes to an optician's. He tells the optician that he's having trouble seeing distant things, and he must be short-sighted.

So the optician takes her glasses off... and then hands them to the man. "How about these?".

The man puts on the optician's glasses and, no, that prescription's much too strong.

The optician gets upset by this. "You ask me to help you, and you just throw that help back in my face. I was willing to just give you my glasses, for free, out of the kindness of my heart and you just reject this. I'm angry and upset at your ungrateful behaviour, please leave my shop".


And - just to kill the frog - the underlying point with this joke is that we all know that glasses have to be prescription. Crafted to match what's specifically wrong with someone's eyes, to the strength that they require.

So the optician just handing over the glasses she happens to be wearing is perfectly silly. We can immediately see the error she's making, in acting like what's good for her must universally be good for everyone else. Like there's only one type of glasses. Like there's only one "right answer".

If everyone had strictly obeyed "don't reinvent the wheel" then your car would have stone wheels, and it'd be suspension nightmare, which would be quite literally tearing up the motorway, that we're resurfacing the whole lot every other week.

I'm not saying you're wrong. Because you absolutely aren't. Folks should probably have a strong preference for just using a library, if the work has already been done and it's a good library. As I say, "don't unnecessarily reinvent the wheel".

But just recognise that I'm not wrong either. Sometimes, we absolutely have necessarily reinvented the wheel - many times over - and been vastly better off for it.

Your glasses, whilst perfect for you, would be very unlikely to be any good for me. This is not because you're wrong, nor that I'm wrong. It's just because, you know, we have different eyes (indeed, I don't know that you don't, in fact, have 20 / 20 vision and don't even own glasses).

[Dio]

Many of your analogies aren't particularly apposite, including all the game engine ones and the glasses one because - indeed, as you say! - there's a different degree of necessity involved.

Everyone writing code chooses what to write and what to use or reuse. You should be actively making those choices, with some thought, for good reasons. There are very few good reasons to write a memory allocator: it has trivial and mostly universal interfaces, is widely available and is trickier than it looks.

[KlaxonCow]

Many of your analogies aren't particularly apposite, including all the game engine ones and the glasses one because - indeed, as you say! - there's a different degree of necessity involved.

Right back atcha with your writing operating systems and video drivers, filesystem handlers, USB HID processing, audio interfaces, etc.!

Indeed, as the point being made here is that "every case is individual" - no one-size-fits-all universal answer - then ALL analogies now fail, as they will all implicitly have a different degree of necessity / effort involved than the thing they are meant to be analogising.

But, come on, the most extreme leap came from you: Writing an operating system, video drivers, filesystem handlers, audio interfaces, etc. from scratch... as if that's remotely comparable to just implementing a simple "Vector" class in C++. Because, in the end, that's really what my "Pool" class is - a "Vector" with a free list to track availability.

[gilesgoat]

Don't write your own memory allocators if they are any more complex than a basic growing buffer allocator. They are much trickier than they look (especially when threads get involved) and they need a lot of extra work if you're going to get proper debugging information out of them. A robust, well tested basic memory allocator is a multiple month project; a full-featured one much more.

There are hundreds of them out there, and even if none of them exactly fit your needs you would be better taking a well-used working one and customising it. The most likely reason to write one from scratch is to learn how to write one, I suspect.

I see what you say and you are right up to a point "mostly in the sense don't reinvent the wheel" which is "correct" however there's a "small problem" here that "we forget to address".

Because mostly you say "use code that already exists" .. which implies TWO things :

1. that code actually exists

2. it's free of use/license/doesn't have "strings attached".

Now I can't speak too much too many things would be under NDA I can't precisely state the nature of things but to make it short "in certain situations 1 & 2 DO NOT EXIST" ..

Take even Vulkan for example ... "you need mem allocation all over the places" .. OK that "if you plan things in a certain way" COULD be "static buffers allocated once for all and re-used N times" that's what is "the best scenario".

But even Vulkan, correct me if I am wrong they give you "a basic mem allocator that is free BUT IS LIMITED" and then "if you want more, pay me a license" or such ? ( So been told ).

Then there's "consoles" where "I am going to use this OpenSource/free code" is a NO NO NO NO usually "because that free is not really free or has too many strings attached or they simply don't allow you".

So "why are you writing that code" ? Because I HAVE TO ..

In this case I wanted to be "a bit more flexible in case I can re-use it for further uses" but turned out that "actually it wasn't necessary" for the very nature of the problem itself, in reality there are "things" allocating/freeing "blocks" that are "precisely always the same size" and "will be requested more again as before".

So once you get to a certain "max number of simultaneous blocks used" you can guarantee that "it will never be more than those" and that let's say "as soon as 10 are freed maybe 8 of the same are asked again" and so on, so "something too much clever" is not really needed.

But I was curious about "the whole subject of mem allocators".

Also let's not forget "some libs are HUGE" and do "999 other things I don't need I maybe need just 2 of them" ..

And then again "they still need to be ported for the architecture X, which means they could need more debug and such and so on" .. and then "it's still code done by someone else that maybe I understand only 50% and if something goes wrong or it's not as I want I still have to get NUTS to make it work".

So there's a "fine balancing act" between "use what already exists, assuming it really exists" and "do your own".

Let's not forget licensing !! LET'S NOT ..

Because for example "last time I needed some shit that IS actually present in MANY libs EXCEPT where I needed it" turns out SURE, THERE'S A NICE LIB FOR THAT .. ah it's "commercial" use ? I want $2000 .. FUCK OFF !!!

And I should have got the source ( pay first to have them ) port them and maybe they could even not work !

So if you ask me "why you wrote a mini-dsp for that audio shit" there is your answer

1. did not exist for that platform

2. they wanted too much money

And then also let's not forget the situation "I use lib X ( which I don't have sources ), something goes wrong, all I can do is to write to 'X tech support' and hope they'll fix it".

And/or the same time "go nuts trying to find a workaround".

At this point I prefer to "go nuts" on my own code.

But anyway in the end "in a way" I sorted the problem, the thing is working as it should, but I wanted to know "a bit more" about "the world of memory allocators".

Does it make sense ?

[Little stoned kiwi]

Let's not forget licensing !! LET'S NOT ..

Yes, let's not. Licensing is often more relevant than the code itself.
What license have you released you allocator under?

[KlaxonCow]

Does it make sense ?

To me, yes, perfectly so.

As I was already trying to emphasise the "ah, but it's not always so simple" point with Dio myself here.

You really bring up a good issue with licensing. Hadn't considered that one, though it's probably an even bigger issue than anything I've mentioned.

Other people's code comes with strings attached, most often.

A lot of "free" code is not necessarily genuinely free. They might be a stipulation that it cannot be used for commercial purpose, or that it can, but that's when payment or royalties are involved.

Even on the open source end of things, then "copyleft" licensing can be its own kind of millstone around one's neck. The obligation to release source code, particularly if you make any modifications, of the "viral" licences.

Even with something like the LGPL, it can impose some awkward distribution problems.

I remember the "Goldwave" audio editing software on Windows. It makes use of LAME in order to do its MP3 encoding / decoding. But, for various licensing reasons, LAME could not be distributed with the software. Rather there were instructions on how to install LAME separately, as a stand-alone library, and then "Goldwave" would find that library and make use of it.

(Which is a scheme that you can get away with for a creative app like Goldwave, but you really couldn't do with a game. Imagine downloading a game through Steam, but then, sorry, you've got to go to this website and download this library and this library separately. Yeah, that would not work, and folks would be using Steam's "refund" system on your game, without doubt. You can't do this with game software. It wouldn't work and no-one would accept it.)

This little "dance" being mandated by the various licensing rules and regulations. That I can't directly give it to you, but if you happen to have it, then my code will happily make use of it, of course. And here's where you can find it... hint, hint.

Or with emulators, where they can't provide the copyright ROMs out of the box. But here's the emulator and - oh, look - over here on the Internet, someone else (upon whose head this legally falls and not on us, who're providing the emulator to you) happens to have the required ROMs available as a download. We trust you, of course, own the original article and therefore downloading this constitutes a "backup" of a product you already own... and so on and so forth, dancing a merry little dance around the licensing rules and regulations.


Again, it's not that Dio's at all wrong. Don't reinvent wheels that need no reinvention.

But the underlying point here is: "yes, totally... but, in reality, things are not nearly so simple, I'm afraid".

What license have you released you allocator under?

And this point really hits the nail on the head.

It echoes my point that we can't all depend on "someone else's code", if there isn't "someone else" out there creating this code and then releasing it with a permissive enough licence that we're able to take advantage of it.

And, you know, let's indeed reflect it back on ourselves too. Because even when we have written our "own code" for this, are we releasing it as "someone else's code" for other people? I know I haven't with my own code that I've been talking about.

(In fairness, though, this is mostly because it ain't in a form that others would find too usable, I don't feel, because it is, as mentioned, implicitly hooked up to my debugging code, so that would have to be decoupled. Though it does use templating and such, so it's not terrible, it's still not really in a "for public consumption" format. Indeed, creating a good library is more than just having the code, and there's a lot of controlling dependencies, making it sufficiently modular, documenting the thing properly so that someone else can even understand what you've done, making it "bulletproof" and testing all of that, etc. on top of everything.

And, in fairness to Dio, that's also a part of why "use someone else's library" is generally good advice, because it is a lot of effort and testing to get code to that point. So if someone's already done all that before you, take advantage of that, as it really is quite a big slab of work you're avoiding there.

I'd also, in the other direction, point out that it can also be a lot of compromises too. In that, to make my code a library for others to use, I'd really have to remove the debugging code - as that would either mandate others to also go "all in" on my debugging code for all their project, or have a weird thing where these routines are debugged one way, while everything else is debugged some other way. It'd be very awkward. It would have to go, in the name of being usefully "generic" and "modular" for others to use. But, in practice, when I use my code, that debugging stuff is the godsend of why my "own code" is so damned useful. As I say, it effectively acts as a built-in "valgrind", as it tracks all memory to a debug log for me to review and double-check everything is 100% as expected, or immediately see where things are going wrong when they go wrong. In use, that's kind of the best bit. But that's exactly the bit that I would be obliged to "compromise" out of any library I made, in the name of modularity and genericism.)

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

[Dio]

Many of your analogies aren't particularly apposite, including all the game engine ones and the glasses one because - indeed, as you say! - there's a different degree of necessity involved.

Right back atcha with your writing operating systems and video drivers, filesystem handlers, USB HID processing, audio interfaces, etc.!

That was an exaggeration to make the joke about being satisfied with the Moon when you could aim for Mars.

[gilesgoat]

Let's not forget licensing !! LET'S NOT ..

Yes, let's not. Licensing is often more relevant than the code itself.
What license have you released you allocator under?

It's SO stupid ( the allocator ) that I'd feel really ashamed to even have anyone look at the code, let alone release it !

[gilesgoat]

TWO fields where "it's a DEAD WALK AROUND A SUPER TERRIBLE MINEFIELD" .. "Audio" and "Video" ..

You may think that "sure in certain consoles/thing" there is something like "PlayVideo( FILE_NAME ); " ..

Reality is : NO, THERE IS NOT !

It's MUCH more complex than what you'd think or anyone think it should be ...

"Main reason" : CODECs licensing/too many video formats.

"To play that intro video that you see while something else ( hopefully ) is happening" unless you really are using someting like UE/Unity "is a stramassive pain in the arse" usually limited to ONE video format ( cause codecs license issues ).

"The more mental of the mental of all that I've seen so far" is on the Switch, but I can't say anything, NDAs ..

Audio is another "pain in the arse" .. I mean yes at some level like "play simple samples" it's "not too complex" .. but if you start having like "audio streaming and codecs" .. "welcome to the mega shit" ..

How people usually do ? "They pay quite some money for libs" and/or they all use those 2 .. 3 maybe "famous libs" that are around.

But even that, in the case of games, it's "practically true" that 90% ? of games are all made via UE/Unity/maybe something else ... so "only 10% of people deal with such problems". ( and then they pay 2000 pounds or so to have the "made with XXX" removed from the startup ).

Most games "are not even coded" are "blueprinted" I suppose or the fuck it works ..

Most people don't have a REMOTE IDEA about "how the console acutally works" and/or "any of the bits they use" and/or don't even care "what platform they are coding for" because "it does not matter at all".

But then they need "someone else" to fix all the "platform specific stuff" that doesn't work, if they are not "big enough" to have such knowledge in-house I am sure "there's an external company for that".

Then you see why making a video game costs bazillions "pay for this, pay for that, pay for that company, pay for the other, license of this, license of that, pay for that testing, pay for the other one, etc. .. "

I recently made "from total zero" ( HAD to ) this new "DX12 engine for XBOX" because I HAD to .. and I've been looking docs/things/how to/etc. anything I could have found to understand "how to do things" ..

*I* could write ( a probably quite meaningful ) book now .. "because documentation is SO sparse and SO LITTLE you would not believe".

Yes Dio "in the end" I am quite sure I kinda made what you made I BELIEVE "yes it's a graph thing what I've done".

From "A states block" builds "a graph" that builds "pipelines" it's surely "not so generic" as your thing I am sure and makes some "assumptions" like "a restricted number of draw calls per frame" and probably it's not so elegant the way it uses some mem/buffers BUT "it's contained and easy to know how much it needs" and I think "it's simple and fast" in what it does, even if, at the moment, it's not well suited for multi-threading BUT could be EASILY modified for.

But most important "does what it has to", it's not very long, it's not too complex to understand it/modify it, and ( hopefully ) pays the bills and "works".

But I am quite sure that "even the book" and "even this engine" if by absurd "I'd license it" would be "of use only for certain nerds" because 90% "of the real industry/world" would find it "so extremely simple to be totally useless for them".

You CAN NOT "drag and drop things" and make things happen .. no you really have to put C++ code to make it work

Discussing about "mem allocators" is "for super nerds only" that still would like to know "a bit more about for the love of knowing" and also a bit for necessity.

But I'd still discuss about mem allocators, asm, how-that-shit-is-done/how-to-do-it rather than just drag and drop things, that's not "coding" it is "making something" sure but it's NOT "coding" and I do love coding ( and knowing how it works )

[KlaxonCow]

I've not done anything with it, so I can't comment from experience.

But, for video, what about AV1?

https://en.wikipedia.org/wiki/AV1

The whole point of it is that it's an effort - by many big tech companies, like Google and Netflix and Microsoft, who'd benefit greatly from finally ending all this licensing / patents nonsense - to create a genuinely free (licence free, patent free, etc.) video format.

A licensing / patent fee armistice. Because all of them could do with not having to constantly pay fees and licences and shit, so they're working together to make a video format that has no such issues.

As I say, I've not actually done anything with it to confirm by experience, but if it's what it intends to be - what it's cracked up to be - then it would be the video format that finally solves all this nonsense.

Indeed, nVidia's 40 series has hardware AV1. Intel's ARC video card has, in fact, the best AV1 hardware, apparently - beats both AMD and nVidia in performance tests, so Intel really went balls to the wall on their hardware implementation. And the Radeon 7900 also has hardware AV1.

I mean, encoding and decoding can be done in software, of course. But all the video card manufacturers are making the moves for hardware accelerated AV1.

So it looks like the whole industry is making moves towards, you know, using AV1 and bringing all this licensing / patent warfare to an end. And, if it succeeds, then this might hopefully mean we've got a video format, in AV1, that'll end these problems for all of us.

Can't personally confirm that, as I say. But that is the idea of the format, and if it works, then this will be - if not now, then eventually - the way you side-step all the crap to just get a video format that works, and comes with no licensing / patents baggage. And, indeed, the name has a "1" in it - AV1 - so this suggests we might get an "AV2" and "AV3" in the future as well.

[gilesgoat]

I've not done anything with it, so I can't comment from experience.

*SNIP*

It's a fraking mess ... and the thing you'll find it almost IMMEDIATELY is that unless you have "accelerate HW support" and/or at least "special ASM instruction support" doing a real-time decoder in pure SW is "almost impossible" I mean yes you can decode the video but you won't get the required frame rate.

Then every API I've seen so far "it's a mess" does "one bit of the thing" but leaves all to you to do "all the other" almost always ending up in some "mess multi-threaded code" to synchronize disk loading/streaming with video/audio decoding/playback.

And then even the "decoding" ends up in giving you some YCrCB buffer and/or some other weird thing up to you to "display someway" ( usually by expanding it into an RT/Texture via some shaders ) and draw it out.

I don't know why it's like that and there can't be a "PlayVidoIntro( file )" thing, but I never seen anything like that readily available and "the world of video/audio synchronization/codecs is a complete mess".

In fact so much mess I eneded up in creating "my own sort-of Flash Player" where my animations are done via interpreted scripting language and are actually "a composition of this and that" .. believe me or not took me about 4 days to put up "what we needed" VS one week I was messing up with the ONLY "demo code" of a video decompressor I could NOT make it work such mess it was ... (*)

Then got to point "or I do something soon, or I have to tell them I need more weeks to get this working" .. "I got something soon that did what we needed".

(*) actually took me other 3 days of "wear & tears" to make it work Theora/Ogg video decompressor .. was SHIT .. video quality was absolutely crap, almost the point you needed an "uncompressed video to make it look good" and the performance was around 10 fps ...

Audio is so and so, there are " a few ways " you can "get away" with .. video .. is NIGHTMARE ... everywhere I had to deal with it, I tend to avoid it like the pest !

[edit] there is also "another weird side of the story" about "videos".

CAN'T make any names .. but let's say it did happen to me MORE THAN ONCE I had to "fight" with "people" for things like "I am giving you this 15 SECONDS into/logo/anim" .. 2.3Gbytes ...

And it's like .. NO ... NO! .. NO!!! ... "make it smaller!" ..

If it would have been not for me fighting around this stuff and/or finding "alternative solutions" you'd had some games where 99.99% of the whole package size was "the logo" and the remaining 0.01% "the game itself"

[KlaxonCow]

Oh dear. It sounds like I've been lucky that I've never really had to deal with any video.

[gilesgoat]

Oh dear. It sounds like I've been lucky that I've never really had to deal with any video.

If you want "even MORE mess" .. TRY on Windows to CAPTURE video .. I haven't done it on WIN10/11 yet but I THINK "DirectVideo" still works ..

"Welcome to the world of video-graphs, 'input pins' , 'output pins', 'muxes' and other things I can't rememeber" ..

Basically you have to first identify/enumerate "the possible video sources", pick up one and build a sort of "video pipeline", then can't even remember what else shit you need to get the damned video !

But to be honest from what little I remember is EASIER on Windows than on consoles !!

[Dio]

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

coat->get();