Wait-free queueing and ultra-low latency logging • Hacker News Board

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

#11

Post by mortoray » Thu, May 29, 2014, 12:08 PM UTC

fmstephe wrote: post #10

mortoray wrote: post #9

Earlier quoted context omitted.

Note it's important to be "wait-free" and not just "lock-free". The first item here does appear to be "wait-free".

I am curious about your definition of wait-free and lock-free. There are a number of conflicting definitions for these two terms floating around the internet. If we take a very simple problem, incrementing a shared counter and doing some other work and returning its new value. In pseudo-code (with no exception handling). --- A lock based solution would look like this public void inc() { this.l.lock() this.value++ thi…

I'm going on what wikipedia describes as [lock-free](https://en.wikipedia.org/wiki/Lock-free). In that theoretical sense there is no difference between a mutex lock and a spin-lock. But, they may both be "lock-free". By the definition presented there virtually all programs are lock-free... that would be better termed "deadlock-free".

Most people I've meet though assume lock-free just implies not using mutexes, but that spin-locks are fine. There appears to be a conflict between this definition (the one you've given) and the theoretical one.

I generally stick to the term "wait-free" since it's meaning is less ambiguous.

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

#12

Post by jzwinck » Thu, May 29, 2014, 12:16 PM UTC

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-free stuff now. It didn't back when the author was writing the code described.

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

#13

Post by fmstephe » Thu, May 29, 2014, 12:24 PM UTC

mortoray wrote: post #11

fmstephe wrote: post #10

Earlier quoted context omitted.

I am curious about your definition of wait-free and lock-free. There are a number of conflicting definitions for these two terms floating around the internet. If we take a very simple problem, incrementing a shared counter and doing some other work and returning its new value. In pseudo-code (with no exception handling). --- A lock based solution would look like this public void inc() { this.l.lock() this.value++ thi…

I'm going on what wikipedia describes as [lock-free]( https://en.wikipedia.org/wiki/Lock-free ). In that theoretical sense there is no difference between a mutex lock and a spin-lock. But, they may both be "lock-free". By the definition presented there virtually all programs are lock-free... that would be better termed "deadlock-free". Most people I've meet though assume lock-free just implies not using mutexes, but…

The definition for lock free written there is the same as the one I wrote above.

The crucial sentence is found in the second paragraph. Where non-blocking is the umbrella term covering both lock, wait and obstruction free algorithms.

"In modern usage, therefore, an algorithm is non-blocking if the suspension of one or more threads will not stop the potential progress of the remaining threads"

Neither spin locks nor OS locks satisfy this part of the definition. A thread holding a lock who is suspended will prevent any progress being made by any other thread.

I would avoid using wait-free in general because it is a very specialised kind of non-blocking algorithm.

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

#14

Post by easytiger » Thu, May 29, 2014, 12:29 PM UTC

mortoray wrote: post #7

easytiger wrote: post #6

I wonder about the implementation of the ringbuffer itself. Would boost::spsc_queue be suitable for a similar task?

That definitely looks like it's providing the same functionality my ring buffer did. It's impossible to say whether it is as efficient as mine was without profiling it. It's possible. Even if it's almost as efficient, or even half as efficient, I'd still consider using it. Writing this stuff consumes a lot of time. I notice the newest versions of this class added a "consume" function. I assume it's for the same reaso…

interesting, i've actually been oblivious to the mechanics when i'm using it (too much business logic to do).

I'm also using it and burning a whole core doing a busy wait. I was going to try and fix this but i'm not sure how much i care. if we aren't paying for cpu time then it doesn't matter

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

#15

Post by mortoray » Thu, May 29, 2014, 12:51 PM UTC

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…

Yes, a string-literal type would be very helpful. In my Leaf language I have literal types. I think they offer some good optimiation abilities.

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

#16

Post by a-priori » Thu, May 29, 2014, 12:57 PM UTC

fmstephe wrote: post #3

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.

In this particular case you should be able to use no-op instructions to spin without consuming much power. Since the consumer only spins when the queue is empty we know there will be space on the ring buffer and producers won't be impacted. When the consumer wakes from a no-op loop and finds work on the queue it can switch back to a hot loop for a certain amount of time before returning to a no-op cold loop. My under…

I think your colleague is talking about the PAUSE instruction (which is also known as REP NOP, since they encode to the same bytes). It's a special instruction that hints to the processor that it's in a spin-loop waiting on a synchronisation variable to change. It's used in tight wait loops like this:

    wait_loop: 
        pause
        cmp eax, sync_var
        jne wait_loop

The PAUSE instruction introduces a small delay to synchronise the spin loop to the memory bus frequency. This is a power savings, since the value of sync_var, as seen from the perspective of this code, can't change faster than that. Also, because the CPU can execute much faster than the memory bus, it prevents many memory requests from piling up while in the loop (because of out-of-order execution; those requests will have to be unrolled when the loop exits), making the loop faster to exit. Because of Hyperthreading, the pause also gives another thread a brief opportunity to execute on the same core.

https://software.intel.com/sites/default/files/m/d/4/1/d/8/1...

Intel does, however, recommend other approaches to dealing with tight loops like this. See here:

https://software.intel.com/en-us/articles/long-duration-spin...

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

#17

Post by fmstephe » Thu, May 29, 2014, 1:03 PM UTC

a-priori wrote: post #16

fmstephe wrote: post #3

Earlier quoted context omitted.

In this particular case you should be able to use no-op instructions to spin without consuming much power. Since the consumer only spins when the queue is empty we know there will be space on the ring buffer and producers won't be impacted. When the consumer wakes from a no-op loop and finds work on the queue it can switch back to a hot loop for a certain amount of time before returning to a no-op cold loop. My under…

I think your colleague is talking about the PAUSE instruction (which is also known as REP NOP, since they encode to the same bytes). It's a special instruction that hints to the processor that it's in a spin-loop waiting on a synchronisation variable to change. It's used in tight wait loops like this: wait_loop: pause cmp eax, sync_var jne wait_loop The PAUSE instruction introduces a small delay to synchronise the sp…

I take my hat off to you a-priori

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

#18

Post by easytiger » Thu, May 29, 2014, 1:09 PM UTC

ajtulloch wrote: post #8

For some excellent examples of concurrent queues in C++, Facebook's `folly` C++ library contains a really clean lock-free SPSC queue [1], and a really fast MPMC queue [2]. [1]: https://github.com/facebook/folly/blob/master/folly/Producer... [2]: https://github.com/facebook/folly/blob/master/folly/MPMCQueu...

i always get very sad that folly's map doesn't support deletion/removal. :(

I';ve yet to have a usecase where that is ok

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

#19

Post by a-priori » Thu, May 29, 2014, 1:11 PM UTC

fmstephe wrote: post #17

a-priori wrote: post #16

Earlier quoted context omitted.

I think your colleague is talking about the PAUSE instruction (which is also known as REP NOP, since they encode to the same bytes). It's a special instruction that hints to the processor that it's in a spin-loop waiting on a synchronisation variable to change. It's used in tight wait loops like this: wait_loop: pause cmp eax, sync_var jne wait_loop The PAUSE instruction introduces a small delay to synchronise the sp…

I take my hat off to you a-priori

Glad to help :)

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

#20

Post by zwieback » Thu, May 29, 2014, 1:19 PM UTC

Nice writeup, enjoyed reading this.

Instead of pointers to string literals, did you consider tokens instead, e.g. a big enum with a matching string table for the consumer? That's what we did in the past in device drivers although for space reasons instead of speed.