Lock free Queue and Lock free Allocator

Does anyone know of a combination generic implementation of a LFQ and LFA that would work in C++.Net?

For example, I need to be able to say this:

Code:

LockFreeQueue< array < Byte > ^ > ^ transmitQueue;

Thanks in advance

 

i would also be interested to know about a lock free allocator.
i havent used c++ in a while but we used hoard; i dont think it was lock free though

 

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

 

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.

 

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.

 

rufus, if your FIX engine and this code was available for purchase, you would have a customer.

 

I have used APPIA before. It is very average.

 

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.