[Discussion] - LockFree ThreadSafe Dynamic Memory Allocation

[clintonselke]

I thought this might be an interesting discussion,

Has anyone heard of this being possible?, (from the title "LockFree ThreadSafe Dynamic Memory Allocation")

I only just learned recently that dynamic memory allocation isn't thread safe (for native code anyways). Have not really been a big fan of using threads until recently, starts to change as computers get more CPUs. If you only have 1 CPU, then its more efficient to find a way to do something with just 1 thread (if possible).

One thing I did find that was very interesting was a LockFree Queue, which allows 1 reader thread, and 1 writer thread to work on the one queue simultaneously without corruption. It improves performance over locking a regular queue by over a factor of 10 times (for just reading/writing to/from queue, w/o doing work on the data itself). Using Mutexes generally causes bottlenecks in programs, making threads compete for the one resource... where as, using lockfree algorithms by the use of atomic operations, the structs are never in an invalid state during modification which means multiple threads can use them at the same time w/o causing corruption.

Imagine a intersection on the road with traffic lights... Locking is the use of the traffic lights to allow cars to share the resource (the section of road in the middle of the intersection, to reach the other side).

Now what Lock-Free algorithms using atomic operations introduces is, a new road where cars don't have to stop, they can just pass through each other like ghosts... spooky xD, but freaky cool, and improves performance so much.

Now Time For Some Inspiration the LockFree Queue



Now next thing is, I believe this can also be done with a Heap Algorithm, through the use of atomic operations. To have multiple threads allocating / de-allocating memory without the need to lock.

Sure a LockFree Queue is only 1 reader and 1 writer but...

If every thread had its own lockfree queue, then you can mimic the effect of a single LockFree Queue (by join several queues in parallel) to allow many writers and 1 reader (I've done that b4 and it works well).

Now for those that don't know already, a Heap structure is one that efficiently stores values by some size, and its very efficent to get the smallest or largest value (or object by some key).

What I'd want for the Heap structure is multiple readers and multiple writers (I think, still working it out). Every allocation of memory (malloc / new) would do a read on the heap object. Every deallocation of memory (free / delete) would do a write to the heap object. The heap object would essentially hold blocks of free space.

Joining back together two adjacent blocks of free space into 1 chunk, I'm really not concerned about at this state, as each bit of memory allocated is roughly the same size. And if i need smaller memory than available, I can always pass over a chunk that is slightly larger than required, then when its freed, that chunk goes back on the heap again.

This plan is only to work around the Dynamic Memory Allocation not being thread safe... last resort is locking, sigh :P

If anyone has anything to add, or anything they've discovered online or somewhere, feel free to post it below.

[InfamousNoone]

Me and Saint both face-palmed at this.

[clintonselke]

Originally Posted by InfamousNoone

Me and Saint both face-palmed at this.

Feel like writing me a lock free memory pool?

[gabrola]

Ever heard of pthreads?

[DragonHeart]

Originally Posted by gabrola

Ever heard of pthreads?

***** threads 0.o?

[bone-you]

From skimming it, it looks like what I did in my socket system for c++.

[gabrola]

[clintonselke]

Originally Posted by gabrola

lol, exactly what im after, thx.