Author Topic: TLSFMem O(1) Memory Allocator (Read 4187 times)

platon42 · « **on:** October 14, 2007, 11:56:41 PM »

TLSFMem is an implementation of a very new memory allocation system called TLSF (two level segregated fit). TLSF was described in a paper in 2005 by the three italian 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.

This software comes as freeware, but as I spent a lot of time in developing it, you are welcome to donate something.

Download it here.

Chris Hodges

sprocket · « **Reply #1 on:** October 15, 2007, 03:38:57 AM »

This sounds great!!!

So Chris, is this useful in any implementation of the AmigaOS?

classic hardware running 3.x? 2.x?

Amiga Forever? UAE?
Amithlon?

or is it mostly useful in only some cases of the above?

JosephC · « **Reply #2 on:** October 15, 2007, 04:08:22 AM »

Hooray!!!

But is it any better than MemOptimizer?
Or Poolmem?

Piru · « **Reply #3 on:** October 15, 2007, 06:34:19 AM »

@JosephC

It should be better than both of those. MemOptimizer and PoolMem don't actually replace the memory allocation routines, they just try to reduce the fragmentation.

Varthall · « **Reply #4 on:** October 15, 2007, 08:24:13 AM »

What about the new memory system in OS4? How does it compare with this new system?

Varthall

ChrisH · « **Reply #5 on:** October 15, 2007, 09:43:30 AM »

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! :-)

JosephC · « **Reply #6 on:** October 15, 2007, 09:50:32 AM »

@Piru

I thought that PoolMem patched AllocMem() to allocate memory in a less fragulated way?

JosephC · « **Reply #7 on:** October 15, 2007, 09:54:12 AM »

Is there any way to rewrite MuForce, MuGuardianAngel, MungWall, etc. to work with the new ChrisHodges(tm) TLSF patch?

itix · « **Reply #8 on:** October 15, 2007, 05:19:26 PM »

Quote

Is there any way to rewrite MuForce, MuGuardianAngel, MungWall, etc. to work with the new ChrisHodges(tm) TLSF patch?

I dont see any reason why MuForce and MungWall wouldnt work with this utility.

MuGuardianAngel is only pointless exercise.

AmigaMance · « **Reply #9 on:** October 15, 2007, 06:42:27 PM »

What a pleasant surprise from Platon42!! :-) Thank you!
I'm using MemOptimizer currently and i will test this patch, asap.

@platon42
From the docs:

Quote

There is a bug in all known version of the scsi.device (both IDE and NCR
SCSI). The devices will allocate an IORequest structure (32 bytes big) and
then use it as IOStdReq structure (which is 48 bytes big), overwriting
innocent memory past the 32 allocated bytes. By chance, this seems to have
no noticable effect on the standard AmigaOS allocator, but immediately
kills TLSFMem, as a vital pointer in its internal structures are
overwritten. Don't get me wrong: This is a bug in the scsi.device and that
TLSFMem triggers it makes it no bug of TLSFMem.

Hey, do you think that this bug could explain the (urg!..) partition trashing experiences that i had with PoolMem and AllocP?? (No problems with MemOptimizer, so far)
What are the expected consequences of this? I do know that you provide a bug-fix, but i still would like to know.

Edit:
Oh, another (important, i believe) question please: Many ppl like me are using the IDEFix package which patches/replaces the standard scsi.device. What's the case with this one? Is there a need for a fix? Which one from the ScsiBugfix directory?

motorollin · « **Reply #10 on:** October 15, 2007, 07:34:57 PM »

Forgive me for being a bit dense, but I don't quite get it. What does this do to my system? Would I be correct in thinking that it makes memory access faster? Significantly?

--
moto

platon42 · « **Reply #11 on:** October 15, 2007, 07:38:21 PM »

@ChrisH

Quote

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).)

You get O(1) guaranteed for each single operation (except for AllocAbs,
which will likely be O(1)). Not O(n), not O(n log n), but O(1). Worst
case. Every case. No mix of operations needed. There are no loops in the
code (except for looping over the existing memory headers, see docs for
detail).

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).

platon42 · « **Reply #12 on:** October 15, 2007, 07:39:09 PM »

> But is it any better than MemOptimizer?
> Or Poolmem?

Yes.

platon42 · « **Reply #13 on:** October 15, 2007, 07:45:50 PM »

> Is there any way to rewrite MuForce, MuGuardianAngel, MungWall, etc. to work with the new ChrisHodges(tm) TLSF patch?

MuForce magically seems to circumvent the patches (calling the original ones (however it gets their pointers)), and thus will immediately cause havok on attempting to free TLSF allocated memory.

> I dont see any reason why MuForce and MungWall wouldnt work with this utility.

MungWall trashes the freed memory, but TLSF stores administration data in the freed memory. I still could add intrinsic MungWall functionality to TLSFMem.

platon42 · « **Reply #14 on:** October 15, 2007, 07:50:00 PM »

> Hey, do you think that this bug could explain the (urg!..) partition trashing experiences that i had with PoolMem and AllocP?? (No problems with MemOptimizer, so far)
> What are the expected consequences of this? I do know that you provide a bug-fix, but i still would like to know.

Could be a result indeed. Whatever application gets access to this memory by allocating it first and using it could cause all kind of weird behaviour -- and as the important pointers (io_Data, io_Offset and io_Length) are in the back part of the structure, partition trashing could occur.

> Oh, another (important, i believe) question please: Many ppl like me are using the IDEFix package which patches/replaces the standard scsi.device. What's the case with this one? Is there a need for a fix? Which one from the ScsiBugfix directory?

I don't think that the idefix drivers are derivates from the Commodore ones, hence they should not have this bug.

Author Topic: TLSFMem O(1) Memory Allocator (Read 4187 times)

platon42

TLSFMem O(1) Memory Allocator

sprocket

Re: TLSFMem O(1) Memory Allocator

JosephC

Re: TLSFMem O(1) Memory Allocator

Piru

Re: TLSFMem O(1) Memory Allocator

Varthall

Re: TLSFMem O(1) Memory Allocator

ChrisH

Re: TLSFMem O(1) Memory Allocator

JosephC

Re: TLSFMem O(1) Memory Allocator

JosephC

Re: TLSFMem O(1) Memory Allocator

itix

Re: TLSFMem O(1) Memory Allocator

AmigaMance

Re: TLSFMem O(1) Memory Allocator

motorollin

Re: TLSFMem O(1) Memory Allocator

platon42

Re: TLSFMem O(1) Memory Allocator

platon42

Re: TLSFMem O(1) Memory Allocator

platon42

Re: TLSFMem O(1) Memory Allocator

platon42

Re: TLSFMem O(1) Memory Allocator