12 ms·

A simple C++11 thread pool implementation

61 points by hellofunk 7y ago

NCG_Mike 7y ago
Not sure but there may be two bugs in the code. The use of notify on the condition outside of the mutex lock. I know this would cause problems with boost, not sure about std::.
- brandmeyer 7y ago
  > Not sure but there may be two bugs in the code. The use of notify on the condition outside of the mutex lock. That's not a bug. The notifier can either signal the condition variable with or without the corresponding lock held and both cases are race-free. In some implementations, it may be more performant to signal the condvar with the lock still held, while in others it is more performant to signal the condvar after releasing the lock. In this discussion "implementations" isn't referring to boost, libstdc++, or LLVM's glue library, "implementations" is referring to the underlying system libraries. Alas, most of the implementations aren't willing to tell you which one is better.
  - 0xffff2 7y ago
    I understand the case where it's more performant to notify outside of the lock, so that the notified thread doesn't wake up and immediately block again waiting for the notifying thread to release the lock. What would the case where it's more performant to notify while holding the lock look like? Is the underlying implementation somehow able to transfer ownership of the mutex?
    - brandmeyer 7y ago
      I must admit that I could be mistaken. There was a stack overflow question about this very topic wherein an NPTL implementer spoke up and claimed the following (any errors in this are the fault of my own recollection): > There is at least one implementation that takes advantage of the requirement that a condition variable be associated with a unique lock to make fewer futex(2) calls, such that the signaling and woken thread make exactly one system call each. NPTL does this. However, I cannot find that Q&A pairing any more. It is certainly the case on the RTOS I'm using right now that it is more optimal to signal outside the lock and rely on the fact that uncontended locking and unlocking operations don't make passes through the scheduler.
      - gpderetta 7y ago
        You are thinking of FUTEX_*_REQUEUE (see the man page for details). It will move (some of) the waiters from the condvar futex to the mutex futex. IIRC, the optimization is called wait morphing. IIRC it is so hard to get it right in practice (the number of races and corner cases is staggering) that recent libc versions might have stopped doing it. I might be misremembering though.
    - petters 7y ago
      I read somewhere that pthreads can transfer ownership.
- thestoicattack 7y ago
  Per [1] the lock does not need to be held when calling notify. In the 17 standard this is §33.5 but I can't quite parse out the real requirements there. [1] https://en.cppreference.com/w/cpp/thread/condition_variable https://en.cppreference.com/w/cpp/thread/condition_variable
  - graetzer 7y ago
    Its usually a good idea to hold the lock because the other thread(s) might not have called wait() yet. As a rule of thumb: its usually a bug to not hold the lock before notify(), unless you synchronize it with another condition
    - usefulcat 7y ago
      In this case I think it should be ok because !this->tasks.empty() is part of the predicate, and will be true after a new item is enqueued (and before notify is called). So if the producer is interrupted between releasing the mutex and calling notify, the consumer would not call wait. But yeah, in general I agree with the advice.. I'm pretty sure I've made that mistake before.
      - ComputerGuru 7y ago
        It depends on if the predicate can (also) be changed without the lock being held, as otherwise the release/acquire ordering semantics are not guaranteed. So long as items are only every enqueued with the lock held, it should be ok.
        gpderetta 7y ago
        according to cppreference: "Even if the shared variable is atomic, it must be modified under the mutex in order to correctly publish the modification to the waiting thread." That's not normative but I can't be bothered to check the c++ standard for exact wordings. Also SuSv4 doesn't have an explicit prohibition on modifying the predicate outside a critical section. But if you do, you are truly on your own.
trzeci 7y ago
The 'simple' adjective is vastly abused - in majority of cases code behind 'simple' project isn't simple - like in this case a person without mid-advanced knowledge about threading / binding / synchronisation / generic programming will have a problem to grasp what's going on in the implementation. Side note is that I love how rust simplified that (https://docs.rs/threadpool/1.7.1/threadpool/ https://docs.rs/threadpool/1.7.1/threadpool/).
- mschuetz 7y ago
  It's simple as in simple to use. Something that C++ needs more of.
  - jupp0r 7y ago
    No it's not. It looks like it on the surface, but real world usage will run into the blocking `get()` methods blocking threads on the thread pool leading to deadlocks or low throughput. What C++ needs is a well thought out design of how to transfer values in a purely asynchronous manner (like Rust futures, JavaScript promises, etc).
    - MaxBarraclough 7y ago
      Is that kind of thing a concern in other thread-pool implementations too?
      - jupp0r 7y ago
        The thread pool normally just allows you to execute code (think void() lambdas). Returning values to the caller isn’t something they normally do, but is normally managed by higher level concurrency libraries like facebooks folly or libq (among others).
        MaxBarraclough 7y ago
        Ah yes of course, auto result = pool.enqueue.... is blocking. Oh dear.
jupp0r 7y ago
You better hope the potentially blocking waiters don’t run inside a thread pool or trouble awaits (pun intended).
jhasse 7y ago
Unfortunately no longer maintained. Multiple forks exist though: https://github.com/progschj/ThreadPool/issues/40#issuecomment-468250869 https://github.com/progschj/ThreadPool/issues/40#issuecommen...
- hellofunk 7y ago
  It's not maintained but it sure does work well. I've been throwing all kinds of workloads at it, always works like a charm. The forks don't seem to actually fix problems, they just add various features to the library, features I don't personally need. And many of the forks are also not updated in a long time. I guess short and simple is sometimes good enough to last?
0xff00ffee 7y ago
It's been so long since I've programmed in C++ that I can't even read this code. Last time I wrote an anonymous function I had to use boost::lambda, now there's an override for [] on line 39? And wtf is the arrow operator doing out there in space on line 19? Starting the day with heavy dose of FOMO...
- thestoicattack 7y ago
  L19 is a trailing return type. L39 et seq. is a lambda expression.
  - 0xff00ffee 7y ago
    Thanks. Native lambdas. Huh. It's like waking up to see people flying their cars to work. :)
    - steveklabnik 7y ago
      Here are the docs, if you're curious: https://en.cppreference.com/w/cpp/language/lambda https://en.cppreference.com/w/cpp/language/lambda
- gumby 7y ago
  > Starting the day with heavy dose of FOMO... I don't know if you should "F" necessarily but you are "MO" :-) C++ has become a completely new language, with a large carbuncle of back compatibility attached (though they've been slowly deprecating some of that). I like programming in modern C++ and am lucky enough to be able to compile everything std=c++17 (which we recently changed to =c++20 though support for that standard is just starting to appear). It's quite an expressive and powerful language. Though a lot of the legacy stuff is ugly, it does give you access to older code, external libraries and the like. So you can write clear code using modern C++ and still be able to link in older code. Pretty nice.
brandmeyer 7y ago
Threadpools are rabbit-hole problems. They seem structurally simple at first, but they also have some unexpected failure modes. There are two that I'm aware of, and there are almost certainly more. 1) Nonuniform work sizes. Optimally scheduling the work when the sizes are nonuniform is Hard. An almost-optimal algorithm is to dispatch larger items before smaller items. This implementation dispatches work in FIFO order. While this is Not Wrong (TM), its far from optimal when the work sizes are nonuniform. 2) Small work sizes. As the size of each work item gets smaller and smaller, the proportion of the runtime cost which is spent to dispatch the work becomes larger and larger. I'm working on a system which has dozens of work items to execute, but each one is only 50-100 microseconds long. It turns out that this is an awfully inconvenient work size, and contention on a common FIFO was limiting available parallelism. I found I got nearly 50% speedup by giving each worker thread its own workqueue and round-robin dispatching among them. 3) (edited to add) They don't model fork/join parallelism well on a common pool. If work items also wait for work to complete, then the OP's implementation may deadlock them. To avoid deadlock, the join operator must be capable of executing a work item. The C++11 future API isn't rich enough to do this in user code. See also WG21 paper N3557 for more on this topic. From the perspective of a standards body, threadpools are similar to associative data structures. There is a community of users who would like to have a one-size-fits-all implementation. But it turns out that actual workloads have wildly differing requirements. In practice, a standard library must provide several different models of a threadpool to satisfy them, or users will be forever complaining and/or rolling their own.
- malkia 7y ago
  But also, coordination with the OS and thread pools from other processes - e.g. GrandCentral / dispatch. If you have multiple apps using that same thread pool they need to be aware of that, and the OS seems like what should be managing these...
- apankrat 7y ago
  Re #2 - If you are on Windows, take a look at IOCP as a queuing mechanism. Use one IOC port to queue work for the threads and use another IOC port to submit completed work back to whoever's listening. Worker threads then merely wait for the next completion packet, execute the work and post the packet into the second ("done") port. Dead simple and, due to how IOCP works, with very little overhead. Strictly speaking, this is not what IOC ports are meant for, but the performance you get out of this is nothing short of amazing and the code ends up being short and simple. [0] https://docs.microsoft.com/en-us/windows/win32/fileio/i-o-completion-ports https://docs.microsoft.com/en-us/windows/win32/fileio/i-o-co...
knorker 7y ago
This is a "hello world" of C++11 threading. I'm not sure what this is doing on HN.
- stabbles 7y ago
  I wonder how many people would know about using return_type = typename std::result_of<F(Args...)>::type though.
  - 0xffff2 7y ago
    It's a neat trick I hadn't seen before, but it doesn't seem particularly advanced. There are all kinds of things in the STL that I don't remember or care about until I actually need them.
  - knorker 7y ago
    Maybe in this context they shouldn't, either. using return_type = decltype(f(args...)); seems easier to read and "more C++11". Also the "> >" is a pre-C++11 pattern.
    - JakobProgsch 7y ago
      Earlier versions did use decltype but that causes issues with pointers to member functions. See: https://github.com/progschj/ThreadPool/commit/ac2a77d5cc04361d341f63b1d19706a4d1b4943e https://github.com/progschj/ThreadPool/commit/ac2a77d5cc0436... result_of has now been deprecated in newer C++ versions but since this advertises itself as C++11 thread pool I intend to leave it as is.
- Vel0cityX 7y ago
  It also has 2.9k stars on GitHub for some reason.
  - nomel 7y ago
    Fundamentally concepts are enjoyed by most everyone, including those who are learning about them the first time, especially when they're explained clearly.
Koshkin 7y ago
On a somewhat tangential note, for C++ threading, Intel TBB is the best thing after sliced bread. Can't recommend it enough. It's just plain amazing. Very advanced. Complete with a flow-graph implementation. Should be part of the toolkit of every serious programmer (on par with C++ standard library).
neuroscihacker 7y ago
This library was very useful for my simple use case for image processing. Thank you to the author! I made a few changes to it to make it more flexible in terms of when it starts, stops, and restarts: https://github.com/seung-lab/euclidean-distance-transform-3d/blob/master/cpp/threadpool.h https://github.com/seung-lab/euclidean-distance-transform-3d...
abacate 7y ago
The queue is a single contention point which will have a considerable overhead unless the work takes a long time to execute (ie, enqueue is infrequent). This kind of approach is usually not what you want: either you want to spawn threads as new work arrives (when each work unit is independent of each other), or you want to have a static number of threads each doing some predefined work (ideally one per core). Scheduling pieces of work like this is going to be terrible for cache locality and will probably result in a number of threads waiting for each other and result in underutilization of the available cores.
- JakobProgsch 7y ago
  > This kind of approach is usually not what you want One thing I learned from all the issues and emails I have received about this repository over the years is that what people consider the "usual" use case of threads varies wildly. Some only care for the concurrency but not the performance, some have huge amounts of tiny work items, some have small amounts of huge work items, some have complex dependencies, some have none at all etc.

61 points by hellofunk 7y ago

Not sure but there may be two bugs in the code. The use of notify on the condition outside of the mutex lock. I know this would cause problems with boost, not sure about std::.

brandmeyer 7y ago
> Not sure but there may be two bugs in the code. The use of notify on the condition outside of the mutex lock. That's not a bug. The notifier can either signal the condition variable with or without the corresponding lock held and both cases are race-free. In some implementations, it may be more performant to signal the condvar with the lock still held, while in others it is more performant to signal the condvar after releasing the lock. In this discussion "implementations" isn't referring to boost, libstdc++, or LLVM's glue library, "implementations" is referring to the underlying system libraries. Alas, most of the implementations aren't willing to tell you which one is better.
- 0xffff2 7y ago
  I understand the case where it's more performant to notify outside of the lock, so that the notified thread doesn't wake up and immediately block again waiting for the notifying thread to release the lock. What would the case where it's more performant to notify while holding the lock look like? Is the underlying implementation somehow able to transfer ownership of the mutex?
  - brandmeyer 7y ago
    I must admit that I could be mistaken. There was a stack overflow question about this very topic wherein an NPTL implementer spoke up and claimed the following (any errors in this are the fault of my own recollection): > There is at least one implementation that takes advantage of the requirement that a condition variable be associated with a unique lock to make fewer futex(2) calls, such that the signaling and woken thread make exactly one system call each. NPTL does this. However, I cannot find that Q&A pairing any more. It is certainly the case on the RTOS I'm using right now that it is more optimal to signal outside the lock and rely on the fact that uncontended locking and unlocking operations don't make passes through the scheduler.
    - gpderetta 7y ago
      You are thinking of FUTEX_*_REQUEUE (see the man page for details). It will move (some of) the waiters from the condvar futex to the mutex futex. IIRC, the optimization is called wait morphing. IIRC it is so hard to get it right in practice (the number of races and corner cases is staggering) that recent libc versions might have stopped doing it. I might be misremembering though.
  - petters 7y ago
    I read somewhere that pthreads can transfer ownership.
thestoicattack 7y ago
Per [1] the lock does not need to be held when calling notify. In the 17 standard this is §33.5 but I can't quite parse out the real requirements there. [1] https://en.cppreference.com/w/cpp/thread/condition_variable https://en.cppreference.com/w/cpp/thread/condition_variable
- graetzer 7y ago
  Its usually a good idea to hold the lock because the other thread(s) might not have called wait() yet. As a rule of thumb: its usually a bug to not hold the lock before notify(), unless you synchronize it with another condition
  - usefulcat 7y ago
    In this case I think it should be ok because !this->tasks.empty() is part of the predicate, and will be true after a new item is enqueued (and before notify is called). So if the producer is interrupted between releasing the mutex and calling notify, the consumer would not call wait. But yeah, in general I agree with the advice.. I'm pretty sure I've made that mistake before.
    - ComputerGuru 7y ago
      It depends on if the predicate can (also) be changed without the lock being held, as otherwise the release/acquire ordering semantics are not guaranteed. So long as items are only every enqueued with the lock held, it should be ok.
      - gpderetta 7y ago
        according to cppreference: "Even if the shared variable is atomic, it must be modified under the mutex in order to correctly publish the modification to the waiting thread." That's not normative but I can't be bothered to check the c++ standard for exact wordings. Also SuSv4 doesn't have an explicit prohibition on modifying the predicate outside a critical section. But if you do, you are truly on your own.

trzeci 7y ago

The 'simple' adjective is vastly abused - in majority of cases code behind 'simple' project isn't simple - like in this case a person without mid-advanced knowledge about threading / binding / synchronisation / generic programming will have a problem to grasp what's going on in the implementation. Side note is that I love how rust simplified that (https://docs.rs/threadpool/1.7.1/threadpool/ https://docs.rs/threadpool/1.7.1/threadpool/).

mschuetz 7y ago
It's simple as in simple to use. Something that C++ needs more of.
- jupp0r 7y ago
  No it's not. It looks like it on the surface, but real world usage will run into the blocking `get()` methods blocking threads on the thread pool leading to deadlocks or low throughput. What C++ needs is a well thought out design of how to transfer values in a purely asynchronous manner (like Rust futures, JavaScript promises, etc).
  - MaxBarraclough 7y ago
    Is that kind of thing a concern in other thread-pool implementations too?
    - jupp0r 7y ago
      The thread pool normally just allows you to execute code (think void() lambdas). Returning values to the caller isn’t something they normally do, but is normally managed by higher level concurrency libraries like facebooks folly or libq (among others).
      - MaxBarraclough 7y ago
        Ah yes of course, auto result = pool.enqueue.... is blocking. Oh dear.

jupp0r 7y ago

You better hope the potentially blocking waiters don’t run inside a thread pool or trouble awaits (pun intended).

jhasse 7y ago

Unfortunately no longer maintained. Multiple forks exist though: https://github.com/progschj/ThreadPool/issues/40#issuecomment-468250869 https://github.com/progschj/ThreadPool/issues/40#issuecommen...

hellofunk 7y ago
It's not maintained but it sure does work well. I've been throwing all kinds of workloads at it, always works like a charm. The forks don't seem to actually fix problems, they just add various features to the library, features I don't personally need. And many of the forks are also not updated in a long time. I guess short and simple is sometimes good enough to last?

0xff00ffee 7y ago

It's been so long since I've programmed in C++ that I can't even read this code. Last time I wrote an anonymous function I had to use boost::lambda, now there's an override for [] on line 39? And wtf is the arrow operator doing out there in space on line 19? Starting the day with heavy dose of FOMO...

thestoicattack 7y ago
L19 is a trailing return type. L39 et seq. is a lambda expression.
- 0xff00ffee 7y ago
  Thanks. Native lambdas. Huh. It's like waking up to see people flying their cars to work. :)
  - steveklabnik 7y ago
    Here are the docs, if you're curious: https://en.cppreference.com/w/cpp/language/lambda https://en.cppreference.com/w/cpp/language/lambda
gumby 7y ago
> Starting the day with heavy dose of FOMO... I don't know if you should "F" necessarily but you are "MO" :-) C++ has become a completely new language, with a large carbuncle of back compatibility attached (though they've been slowly deprecating some of that). I like programming in modern C++ and am lucky enough to be able to compile everything std=c++17 (which we recently changed to =c++20 though support for that standard is just starting to appear). It's quite an expressive and powerful language. Though a lot of the legacy stuff is ugly, it does give you access to older code, external libraries and the like. So you can write clear code using modern C++ and still be able to link in older code. Pretty nice.

brandmeyer 7y ago

Threadpools are rabbit-hole problems. They seem structurally simple at first, but they also have some unexpected failure modes. There are two that I'm aware of, and there are almost certainly more. 1) Nonuniform work sizes. Optimally scheduling the work when the sizes are nonuniform is Hard. An almost-optimal algorithm is to dispatch larger items before smaller items. This implementation dispatches work in FIFO order. While this is Not Wrong (TM), its far from optimal when the work sizes are nonuniform. 2) Small work sizes. As the size of each work item gets smaller and smaller, the proportion of the runtime cost which is spent to dispatch the work becomes larger and larger. I'm working on a system which has dozens of work items to execute, but each one is only 50-100 microseconds long. It turns out that this is an awfully inconvenient work size, and contention on a common FIFO was limiting available parallelism. I found I got nearly 50% speedup by giving each worker thread its own workqueue and round-robin dispatching among them. 3) (edited to add) They don't model fork/join parallelism well on a common pool. If work items also wait for work to complete, then the OP's implementation may deadlock them. To avoid deadlock, the join operator must be capable of executing a work item. The C++11 future API isn't rich enough to do this in user code. See also WG21 paper N3557 for more on this topic. From the perspective of a standards body, threadpools are similar to associative data structures. There is a community of users who would like to have a one-size-fits-all implementation. But it turns out that actual workloads have wildly differing requirements. In practice, a standard library must provide several different models of a threadpool to satisfy them, or users will be forever complaining and/or rolling their own.

malkia 7y ago
But also, coordination with the OS and thread pools from other processes - e.g. GrandCentral / dispatch. If you have multiple apps using that same thread pool they need to be aware of that, and the OS seems like what should be managing these...
apankrat 7y ago
Re #2 - If you are on Windows, take a look at IOCP as a queuing mechanism. Use one IOC port to queue work for the threads and use another IOC port to submit completed work back to whoever's listening. Worker threads then merely wait for the next completion packet, execute the work and post the packet into the second ("done") port. Dead simple and, due to how IOCP works, with very little overhead. Strictly speaking, this is not what IOC ports are meant for, but the performance you get out of this is nothing short of amazing and the code ends up being short and simple. [0] https://docs.microsoft.com/en-us/windows/win32/fileio/i-o-completion-ports https://docs.microsoft.com/en-us/windows/win32/fileio/i-o-co...

knorker 7y ago

This is a "hello world" of C++11 threading. I'm not sure what this is doing on HN.

stabbles 7y ago
I wonder how many people would know about using return_type = typename std::result_of<F(Args...)>::type though.
- 0xffff2 7y ago
  It's a neat trick I hadn't seen before, but it doesn't seem particularly advanced. There are all kinds of things in the STL that I don't remember or care about until I actually need them.
- knorker 7y ago
  Maybe in this context they shouldn't, either. using return_type = decltype(f(args...)); seems easier to read and "more C++11". Also the "> >" is a pre-C++11 pattern.
  - JakobProgsch 7y ago
    Earlier versions did use decltype but that causes issues with pointers to member functions. See: https://github.com/progschj/ThreadPool/commit/ac2a77d5cc04361d341f63b1d19706a4d1b4943e https://github.com/progschj/ThreadPool/commit/ac2a77d5cc0436... result_of has now been deprecated in newer C++ versions but since this advertises itself as C++11 thread pool I intend to leave it as is.
Vel0cityX 7y ago
It also has 2.9k stars on GitHub for some reason.
- nomel 7y ago
  Fundamentally concepts are enjoyed by most everyone, including those who are learning about them the first time, especially when they're explained clearly.

Koshkin 7y ago

On a somewhat tangential note, for C++ threading, Intel TBB is the best thing after sliced bread. Can't recommend it enough. It's just plain amazing. Very advanced. Complete with a flow-graph implementation. Should be part of the toolkit of every serious programmer (on par with C++ standard library).

neuroscihacker 7y ago

This library was very useful for my simple use case for image processing. Thank you to the author! I made a few changes to it to make it more flexible in terms of when it starts, stops, and restarts: https://github.com/seung-lab/euclidean-distance-transform-3d/blob/master/cpp/threadpool.h https://github.com/seung-lab/euclidean-distance-transform-3d...

abacate 7y ago

The queue is a single contention point which will have a considerable overhead unless the work takes a long time to execute (ie, enqueue is infrequent). This kind of approach is usually not what you want: either you want to spawn threads as new work arrives (when each work unit is independent of each other), or you want to have a static number of threads each doing some predefined work (ideally one per core). Scheduling pieces of work like this is going to be terrible for cache locality and will probably result in a number of threads waiting for each other and result in underutilization of the available cores.

JakobProgsch 7y ago
> This kind of approach is usually not what you want One thing I learned from all the issues and emails I have received about this repository over the years is that what people consider the "usual" use case of threads varies wildly. Some only care for the concurrency but not the performance, some have huge amounts of tiny work items, some have small amounts of huge work items, some have complex dependencies, some have none at all etc.