Short: TLSFMem O(1) Memory Allocator Author: Chris Hodges Uploader: polluks+aminet sdf lonestar org (Stefan Haubenthal) Type: util/boot Version: 1.6 (19-Aug-08) Requires: 68020+ Architecture: m68k-amigaos >= 3.0 Introduction ~~~~~~~~~~~~ TLSFMem is an implementation of a very new memory allocation system called TLSF (two level segregated fit). TLSF was described in a paper by the three spanish researchers M. Masmano, I. Ripoll, A. Crespo. Originally designed for Realtime Operating Systems, all allocation and free operations run with constant time complexity (O(1)). This is a major improvement over the original AmigaOS memory system, which gets slower while memory gets fragmented (O(m) where m is the number of fragments). Moreover, the old AmigaOS allocator uses a first fit strategy, which causes the memory to fragment pretty quickly. TLSF is an exact fit allocator for memory blocks smaller than 512 bytes and a good fit allocator for all other sizes: It will always find a free block which is always smaller than 103% of the requested block. *************************************************************************** TLSFMem is blindly fast and will reduce memory fragmentation significantly! *************************************************************************** TLSFMem was written in optimized assembly language, but more importantly, it uses these clever constant time algorithms. (There is really no use in programs that are written in assembly, when the algorithm sucks (e.g. naïve pattern matching algorithm, like in SearchStar vs. sub-linear Rabin-Karp).) This software comes as freeware, but as I spent a lot of time in developing it, you are welcome to donate something. Audio CDs are welcome and there's an Amazon.de wishlist aswell. No PayPal. FAQ ~~~ Q: Does this 103% stuff mean it wastes memory (internal fragmentation)? A: No. It only needs four extra bytes per allocation. The only internal fragmentation happening is for its alignment of 16 bytes per allocation. Q: Does it run on WarpOS / PowerUP? A: The last version V1.3 didn't due to a bug in AllocAbs. The new one should run under PowerUP, because according to Laire, PowerUP calls the exec functions. I suspect WarpOS still not to work because it's said to have its own PPC native implementation of the exec memory functions, which will cause WarpOS to run out of memory. This is due to TLSFMem allocating its memory from the normal memory lists and pouring each into TLSF mem headers, which would appear empty to the standard exec routines. Q: There was another question here before. Where did this important question go? A: A fascist idiot and troll blackmailed me for mentioning his realname here. Q: Will it speed up any program or just those written for it in mind? A: It will speed up all programs using the standard exec memory functions. It will not speed up programs that use their own allocators (but these are scarce). Q: Will TLSFMem (not TLSFMemPool) also speed up Memory Pools? A: Yes, as memory pools also depend on AllocMem() allocations when building new puddles. However, memory allocations within a puddle remain unchanged (I think exec from 3.9 BB2 uses AVL trees which have amortized O(log n) complexity, which is "good enough" -- but I don't know how exec