TLSFMem O(1) Memory Allocator

[ChrisH]

The OS4 memory system claims O(1) performance (*), and an inefficiency of under 112.5%.  So this new memory system is seemingly a little more efficient (103%), but not enough to be worth rewriting the whole OS4 memory subsystem for.

(* = I disagree with this, and most likely would disagree with the magical O(1) claim of this new allocator too (once I get around to reading how it works).  In OS4's case, you only get O(1) performance if there is a mix of allocations & deallocations, otherwise you'll likely get O(n) performance (but should get O(log(n)) performance if they changed the implementation).)

Still, this is a great thing to see for OS3.x!  :-)

[ChrisH]

@platon42

Regarding the "inefficiency" of 103% is about the good fit properties, it
doesn't waste memory (but I don't know about the OS4 allocator).

But the "good fit properties" of 103% means that it uses (up to) 3% more memory than necessary, so it *is* an inefficiency.  OS4 has a similar wastage of (up to) 12.5%.  BTW, the proper name for this is "internal fragmentation", unless I misunderstand you.

[ChrisH]

@motorollin

Forgive me for being a bit dense, but I don't quite get it. What does this do to my system?

For some programs it will make NO difference, but for those that allocate lots of (usually small) chunks of memory, it could make a massive difference:

For my own (very old) FolderSync program, I was able to gain a 70 times speed-up by writing my own custom memory allocation system.  The reason is that (a) AmigaOS 3.x has a very old & slow memory allocation system, and (b) FolderSync made very many (small) memory allocations.

[ChrisH]

Isn't that what memory pools, introduced with OS 2.0 is for? Small allocations, pooled into puddles? Unfortunately, there are still programs, that don't use them, way past the OS 2.0 release date...

Bleugh, memory pools are disgusting!  You have to manually manage them, rather than having it automatically allocate/choose automatically sized 'pools' for you.  i.e. mine simply replaced the existing AllocMem() routines, like yours does (but only for my program) - no hassle.

If the OS4 allocator has internal fragmentation and if it's really up to 12,5%, it sucks.

Well, that is a lot better than all previous memory allocators, the fragmentation can never exceed 12.5%, and it is apparently used by Linux & other modern OSes.

P.S.  Yes, I will look at the TLSF papers when I have time (already downloaded).  Pity you didn't link to the paper, as it took a while to find (most places wanted payment!).

[ChrisH]

I finally got around to trying TLSFMem on my OS3.9.2 WinUAE system, and sadly it crashes my system *immediately*, even when I disable User-Startup (which has a lot of patches).  Which is a pity, because I was hoping it would have been a superior alternative to my own (program specific) fast memory allocator...