Lock free Queue and Lock free Allocator
- Thread starter nitro
- Start date
Hi Rosy2,
Does fixed size block allocator satisfy
your requirements? if yes, this might
work for you
http://warp.povusers.org/FSBAllocator/
I have not used it yet. I am about to use
it. The default operation mode is:
lock free, non-thread-safe
Does fixed size block allocator satisfy
your requirements? if yes, this might
work for you
http://warp.povusers.org/FSBAllocator/
I have not used it yet. I am about to use
it. The default operation mode is:
lock free, non-thread-safe
I wrote a little library that uses the "cmpxchg" (for single processor) and the "lock cmpxchg" (for multi processor) assembler instructions, for both inter thread queuing and thread safe memory pooling (note I didn't say allocation). I wrote the whole thing in C, using a strange "template-like" grammar (using #define ... don't ask), and it scales quite well.
Look at the following paper on RCU (read-compare-update). It is sufficient for any single-producer, multiple consumer situations. The producer, however, may need to "spin-lock" (yield).
http://pdos.csail.mit.edu/6.828/2008/readings/rcu.pdf
Now, if it is just the simple one-producer, one consumer queue, you can play tricks like CPU-affinity, and just use volatile integers (Intel does a good job of putting up memory barriers, in the single processor, one producer / one-consumer case). And I have done exactly that, the performance there is about 25-30% gain from "lock cmpxchg", which does a strict "serialization" of operation on the variable.
Look at the following paper on RCU (read-compare-update). It is sufficient for any single-producer, multiple consumer situations. The producer, however, may need to "spin-lock" (yield).
http://pdos.csail.mit.edu/6.828/2008/readings/rcu.pdf
Now, if it is just the simple one-producer, one consumer queue, you can play tricks like CPU-affinity, and just use volatile integers (Intel does a good job of putting up memory barriers, in the single processor, one producer / one-consumer case). And I have done exactly that, the performance there is about 25-30% gain from "lock cmpxchg", which does a strict "serialization" of operation on the variable.
Thanks.
I am pretty sure hoard is not lock free.
The reason for a lock free allocator in conjunction with the lockfree data structures is the following simple thought experiment: I see some lockfree code online, but what the heck good is it if you then have to call malloc (or gcnew) as a result? It seems to me that all you have done is pushed the inefficiency into the allocator, not really resolving anything.
I may be wrong about this, as all I have done is done a thought experiment and waved my hands in the air, intead of doing real-world testing that gives me actual time comparisons, but I don't see what I could be missing.
Sanity check. You may get around calling malloc, but there is NO way around calling gcnew. If you need a garbage collected .NET object, then you HAVE to call gcnew - because this is the only way to allocate a .NET class instance. Sorry.
That said, I am not even sure why you look for something lock free here. .NET is very efficient if properly configured (server mode) - basically distributing the memory itself and giving every processor core a separate area to allocate from (so they do not block each other).
like rufus said, if you're doing single writer/reader, just use volatiles and an array and wrap it up into a template. i do exactly that for all my messaging.
gets trickier with multi writer/reader, but you can do quite a bit with sw/sr as the linearity of data/model logic really doesn't require anything more complex.
gets trickier with multi writer/reader, but you can do quite a bit with sw/sr as the linearity of data/model logic really doesn't require anything more complex.