Wait-free queueing and ultra-low latency logging

Re:Wait-free queueing and ultra-low latency logging by emerson_clarke on Thursday May 29, 2014 @12:20PM (#7816979)

I think you misunderstand the CAS operation. It performs an atomic compare and swap on a pointer (32 or 64 bits), so obviously it requires no coordination to switch out the head pointer of a stack.

For example, on an LP64 architecure:

  Item * first = writers.first;
  while( CAS((long *)&writers.first,(long)0,*((long*)&first)) != *((long*)&first))
  {
  	first = writers.first;
  }

Here first represents the flush stack, and writers represents the write stack. We just swap the first pointer of the write stack with a null pointer, and this only succeeds if no other threads are currently trying to perform the same operation. This works because pushing to the stack is performed using a similar atomic CAS of the head pointer.

[ Parent | on HN ]

Re:Wait-free queueing and ultra-low latency logging by mortoray on Thursday May 29, 2014 @02:01PM (#7817625)

No, I'm saying you have coordinated the writing to the stack. It's not enough to just swap pointers to the stacks themselves, but you have to know how much data has been written to the stack.

Perhaps your description is incomplete?

[ Parent | on HN ]

Re:Wait-free queueing and ultra-low latency logging by emerson_clarke on Thursday May 29, 2014 @02:56PM (#7817928)

The stack head pointers can be swapped and flushed without knowing how much data is in it.

However, if you need to know the count/size...

Then in general you must accept that the count/size of the write stack is dynamic, so even if you use an integer to track the value (and keep updated with atomic exchange or increment), at the point that you read its value on one thread it may have already changed on another.

So it doesn't really matter if you reset the value to 0 using an interlocked exchange (this cant be done as an atomic unit with respect to the head pointers unless your platform supports a double CAS). Some loss of count/size information will occur.

Alternatively you can safely iterate through the stack to calculate the count/size anytime you need it (provided the next pointers are also treated atomically).

Neither option will give you the exact size since as discussed above its always dynamic, but this i no way impedes the functioning of the write/flush stacks as described. In my solution i just set the value of the count/size to 0, and disregard any loss of information since it is not critical.

[ Parent | on HN ]

Re:Wait-free queueing and ultra-low latency logging by acqq on Friday May 30, 2014 @08:19AM (#7821320)

> disregard any loss of information since it is not critical.

Excuse me but I'd like to have it clearly stated: which information is actually lost in your implementation? Do some of the messages passed to be written actually end not being written? Which part ends up not knowing count/size?

[ Parent | on HN ]