Best and fast way to AllocMem within an interrupt :Semaphores ?

[Piru]

They're all based on Allocate()/Deallocate(), so they're quite fast while memory is not fragmented.

However, FreePooled() is a bit special: It gets really slow due to the puddle scanning to find the proper memory header to call Deallocate() on. This gets exponentally slow.

AmigaOS 3.9 BB2 fixed this by using the new AVL tree binary balanced tree instead of simple linked list for the puddles.

[Karlos]

Presumably then, they all have at least O(N) cost as a function of the number of nodes in the free memory list?

[Piru]

In the worst case every 8 bytes is allocated and free. This way it's the (memory_area_size / 8 / 2) nodes to walk thru before you find the correct chunk.

At Allocate(), if the large enough free memory chunk is after such alteration of allocated and free chunks, it needs to walk thru all of them to find the large enough one.

At Deallocate() it needs to walk all free chunks until it finds chunk to merge with (or to insert after).

Needless to say, fragmentation is bad. If you need absolute speed, I suggest using object cache for the time critical things, or other similar methods.

[Karlos]

I'm interested in all of this as I weigh up the cost of writing my own custom allocator routines versus a basic wrapper for the memory pool allocation scheme.