Lock free Queue and Lock free Allocator

Discussion in 'Automated Trading' started by nitro, Oct 27, 2009.

  1. nitro


    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:

    LockFreeQueue< array < Byte > ^ > ^ transmitQueue;
    Thanks in advance
  2. rosy2


    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
  3. wenzi


  4. KGTrader


    Hi Rosy2,

    Does fixed size block allocator satisfy
    your requirements? if yes, this might
    work for you


    I have not used it yet. I am about to use
    it. The default operation mode is:
    lock free, non-thread-safe
  5. 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).


    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.
  6. nitro



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


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

  8. nitro


    I have used APPIA before. It is very average.
  9. 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).
  10. 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.
    #10     Oct 29, 2009