Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Wait-free queueing and ultra-low latency logging

mortoray.com

Post reply on HN
Print view View original

41–50 of 56 posts

Re: Wait-free queueing and ultra-low latency logging

#41

Post by emerson_clarke »

mortoray wrote: post #37
emerson_clarke wrote: post #21

Another approach is just to use two stacks, one for writing and one for flushing. User threads write log lines directly to buffers from an allocator usually via a TLS mediated stream. The use of an allocator avoids locking on system calls during memory allocation and minimizes copying between user code and eventual flush to disc/network. Buffers are written to the write stack using atomic CAS, if no buffers are avail…

The problem with this approach is that it requires coordination on when the swap of the two stacks is done. Using CAS doesn't really help. The consumer doesn't know if the producer is currently writing into the stack or not. It still needs another mechanism to determine when it is safe to read from that stack.

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.

Re: Wait-free queueing and ultra-low latency logging

#42

Post by emerson_clarke »

zerd wrote: post #36
emerson_clarke wrote: post #34

Earlier quoted context omitted.

Unfortunately no, thus far i have only implemented it in a commercial context as part of a high frequency trading system.

Do you know of any papers/writeups where you can get more details of the technique?

Im sure im not the first to have done something like this for logging or buffering in general, but im not aware of any writeups.

Information on lock free data structures and the caveats (they are extremely difficult to get right) is freely available though:

  http://www.cs.cmu.edu/~410-s05/lectures/L31_LockFree.pdf

  http://en.wikipedia.org/wiki/ABA_problem

Re: Wait-free queueing and ultra-low latency logging

#43

Post by javert »

zwieback wrote: post #40

Most of my high speed experience is in embedded systems with direct control over HW. Question: for these higher-level systems, is it possible to prevent preemption for a very short time? I'm guessing that a userland app can't do that easily but if it could then that would effectively give you larger atomic operations, which can aid in implementing lock-free solutions.

If I understand your suggestion, that only works when all the threads that share a critical section can only run on the same core.

For instance, if you have a producer on core 0 and a consumer on core 1, even if the producer disables preemptions, the consumer can still enter the critical section (unless you protect it with locks).

Off the top of my head I actually don't know if you can turn off preemptions from userspace in Linux, I've never needed to.

You can give threads sched_fifo or sched_rr priorities that will prevent them from being interrupted by anything of lower priority (but that doesn't include the kernel itself... unless you are on preempt_rt and then there are things you can do).

Re: Wait-free queueing and ultra-low latency logging

#44

Post by xenadu02 »

emerson_clarke wrote: post #21

Another approach is just to use two stacks, one for writing and one for flushing. User threads write log lines directly to buffers from an allocator usually via a TLS mediated stream. The use of an allocator avoids locking on system calls during memory allocation and minimizes copying between user code and eventual flush to disc/network. Buffers are written to the write stack using atomic CAS, if no buffers are avail…

When I read the OP I was thinking exactly along these lines. There are a lot of nifty tricks you can use with atomic compare-exchange.

The Mac/iOS equivalent is the OSAtomicCompareAndSwap family of functions.

For C# users, I wrote about Interlocked.CompareExchange here: http://www.russbishop.net/interlocked-compareexchange. It's one of the few high-level language operations that maps directly to a processor instruction.

If you have side-effect-free mutation functions you can use compexch to merge mutations among multiple threads without locking or blocking, which I've used with immutable snapshots to provide transactional consistency to in-memory objects (without having to pre-check all conditions before mutation or having to create inverses for all operations that can 'roll back' the object mutations). Combined with immutable collections using AVL trees you can get copy-on-write immutable snapshots which is the only real way to deal with massive (50GB+) in-memory datasets that need highly concurrent reads, what-if temporary writes, and permanent writes.

Re: Wait-free queueing and ultra-low latency logging

#45

Post by nkurz »

dllthomas wrote: post #23

Nice - this is pretty much exactly my solution to the same problem. One thing I noticed on my architecture (not sure how well it generalizes) is that explicitly flushing the cacheline from the sending core dropped cache misses quite a bit.

Do you mean flushing it with _mm_clflush()/CLFLUSH? Which architecture, and what's your use case? Any theories on why this was helping?

Re: Wait-free queueing and ultra-low latency logging

#46

Post by nkurz »

FooBarWidget wrote: post #2

It's a bit sad that all these low-latency approaches require burning CPU in a loop, which uses tons of power.

It would seem like MONITOR/MWAIT (https://blogs.oracle.com/dave/resource/mwait-blog-final.txt) would be the best of both worlds: extremely low-power and low-latency. But I see very little about it. Are there reasons that it's not more widely used?

Re: Wait-free queueing and ultra-low latency logging

#47

Post by humanrebar »

jzwinck wrote: post #12

It's unfortunate that literal strings in C++ cannot be programmatically distinguished from char* buffers. It would be useful if there were a separate type for literal strings which could implicitly decay to char* when needed. And functions should be able to return that type, because you may have "literal_string toString(MyEnum)" which always returns a literal string (or perhaps null). Also, yes, Boost has some lock-f…

There are user-defined string literals (1) in C++11. They can do pretty much whatever you want.

Also, using templates it is trivial to distinguish between arrays of characters and character pointers.

Finally, there is a proposal for a string_view (2), which could be used to represent string literals, no copies needed.

(1) http://en.cppreference.com/w/cpp/language/user_literal (2) http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2013/n360...

Re: Wait-free queueing and ultra-low latency logging

#48

Post by dllthomas »

nkurz wrote: post #45
dllthomas wrote: post #23

Nice - this is pretty much exactly my solution to the same problem. One thing I noticed on my architecture (not sure how well it generalizes) is that explicitly flushing the cacheline from the sending core dropped cache misses quite a bit.

Do you mean flushing it with _mm_clflush()/CLFLUSH? Which architecture, and what's your use case? Any theories on why this was helping?

Right. Architecture is Sandy Bridge, use case is sending messages from one core to another.

The theory is straightforward: After I populate a message slot (sized at 1 cache line) in the ring buffer I know I'm not going to need to do anything with that memory on that core anytime soon. Pre-emptively evicting it from cache in favor of something that has a greater chance of being used soon has a chance of avoiding a cache miss. There remains the question of whether the CPU can figure out enough of this on its own. Empirically, the answer was "no" in my case.

Re: Wait-free queueing and ultra-low latency logging

#49

Post by mortoray »

emerson_clarke wrote: post #41
mortoray wrote: post #37

Earlier quoted context omitted.

The problem with this approach is that it requires coordination on when the swap of the two stacks is done. Using CAS doesn't really help. The consumer doesn't know if the producer is currently writing into the stack or not. It still needs another mechanism to determine when it is safe to read from that stack.

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 writ…

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?

Re: Wait-free queueing and ultra-low latency logging

#50

Post by zwieback »

javert wrote: post #43
zwieback wrote: post #40

Most of my high speed experience is in embedded systems with direct control over HW. Question: for these higher-level systems, is it possible to prevent preemption for a very short time? I'm guessing that a userland app can't do that easily but if it could then that would effectively give you larger atomic operations, which can aid in implementing lock-free solutions.

If I understand your suggestion, that only works when all the threads that share a critical section can only run on the same core. For instance, if you have a producer on core 0 and a consumer on core 1, even if the producer disables preemptions, the consumer can still enter the critical section (unless you protect it with locks). Off the top of my head I actually don't know if you can turn off preemptions from users…

Yes, excellent point. Multi-core changes how critical sections would be implemented and whether they'd be useful at all.
Post reply on HN