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

1–10 of 56 posts

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

#3

Post by fmstephe »

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 understanding is that even having very small no-op pauses can significantly reduce the amount of energy used, and crucially heat generated, while only having a very modest impact on latency. A good fit for bursty low latency systems.

To be clear, I am only relating something that another developer described to me. I've not actually implemented this myself. :)

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

#4

Post by mortoray »

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…

My loop continually checked the buffers and the locks, it never did a noop. Those fenced instructions are probably not the most power efficient. Power consumption was not a concern, latency was our primary goal.

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

#5

Post by mortoray »

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 is very unfortunate. On that project we looked at all sorts of ways to avoid burning cores but they all had significant latency issues. If it involved going to the kernel then there was a major context switch overhead. But the big killer is the non-constant time. Each time you go to the kernel there's a danger of loosing your timeslice or being shunted to some other core. This leads to very high variance in performance. (I must always repeat though, this variance is not likely relevant in most applications.)

So we spun in loops. And we had the CPUs set to maximum performance (no idle-time scaling). The total real load was probably less than 1%, so yes, it's very unfortunate.

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

#7

Post by mortoray »

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 reason my class did it. Instead of pushing/popping you can directly modify memory in the ring buffer. This avoids one copy operation.

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

#8

Post by ajtulloch »

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

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

#9

Post by mortoray »

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

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

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

#10

Post by fmstephe »

mortoray wrote: post #9
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...

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++
        this.l.unlock()
    }
This has the crucial property that if a thread gets descheduled by the OS while it holds the lock no other thread can make progress until that thread has been restored and releases the lock. Importantly this is true whether we use user space spin locks or OS integrated locks.

--- A lock-free solution would look like

    public void inc() {
        while(!compareAndSet(&this.value, this.value+1))
    }
This has the charming property that if a thread gets descheduled by the OS anywhere inside this method other threads will not be impacted. However, there is a pathological case where a single thread may repeatedly fail the call to compareAndSet(...). While this does mean that some other thread(s) must be making progress an unlucky thread may be delayed indefinitely.

--- A wait-free solution for this on x64 would look like

   public void inc() {
        // do some inline assembly
        XADD this.value 1
        // that's enough assembly
   }
where the XADD instruction is guaranteed to always work atomically and safely regardless of how many other threads are also xadding to the same address. In practice wait-free algorithms are exceptionally complex and often slower than their lock-free counterparts. Wait-free techniques are most popular with academics (because they are so hard :) and with hard real-time systems because you can't risk failing indefinitely on a contended compareAndSet(...).

This is a good explanation of what I understand to be lock-free and wait-free

http://rethinkdb.com/blog/lock-free-vs-wait-free-concurrency...

Here is a really good discussion about it

https://groups.google.com/forum/#!topic/mechanical-sympathy/...

Truly no flame intended. I just often find it hard to discuss these things over the net because of the range of possible definitions.

Post reply on HN