COM-464 Deep Sleep by SeverTopan · Pull Request #2 · SynaptiveMedical/thread-pool-cpp

SeverTopan · 2018-02-07T21:04:42Z

This PR serves to add deep sleeping on worker slow paths in the thread pool. It solves inkooboo#20.

Essentially, this thread pool previously busy waited when no tasks were present, and this ate up CPU when the process was idle. Threads now enter an 'idle' state in which they block on a condition variable when asleep. This results in the threads consuming 0 CPU when idle, with a performance cost that renders it up to 3% slower than before. Tests are detailed below.

Note that this PR also solves inkooboo#18, and it is built on top of a fix for inkooboo#19.

This PR is backed by a set of torture tests that use our Synaptive Task Library. I'll be making a PR soon that commits those.

Test Details

The following new tests were performed upon the Synaptive Task Library using this thead pool as the underlying scheduler:

Death Tests: checking whether the thread pool cleans up correctly when the process terminates.
Mandelbrot Performance Benchmark: Flushes the thread pool full of tasks and measures how long it takes to complete the batch of tasks.
Throughput Benchmark: Holds the number of tasks in the threadpool constant, and measures how many tasks are processed during a given period of time.
Torture Test: Submits bursts of tasks to the thread pool, with random delays inserted in each task. The bursts of tasks transition the worker threads through each of their Active, Busy Wait, and Idle states.
Last but not least: Idling Test. This was the test used to generate the data in Idling Performance inkooboo/thread-pool-cpp#20. It launches the thread pool but leaves it idle.

There were several previous tests in Common that utilized the thread pool which I'm not mentioning here (e.g. TaskBehaviourTest, TaskInliningTest, SynaptiveImagePerformanceTest, Async Primitives, etc...). They all function correctly.

Test Results

The following are the numerical results from the test cases mentioned above.

Mandelbrot Performance Benchmark

Sub-test: IndividualTasks - submits a new task to the thread pool for each pixel calculation in a 2500 X 2500 mandelbrot set image. Values are test duration in milliseconds. Overall,

Platform	Old Scheduler	Old thread-pool-cpp	Deep Sleep thread-pool-cpp
MSVC	56196	40039	40369
GCC	97976	36527	31317

Sub-test: TaskChains - submits the mandelbrot calculation tasks in a chained fashion to the thread pool in order to leverage task inlining. 64 task chains containing all calculations are submitted to the thread pool. Values are test duration in milliseconds.

Platform	Old Scheduler	Old thread-pool-cpp	Deep Sleep thread-pool-cpp
MSVC	23933	13735	14484
GCC	45377	15540	12795

Note that in this case, the edits actually seem faster than the original thread pool implementation. This may have to do with the design of the busy waiting sequence.

Task Throughput Test

I ran the throughput test for 10 seconds while keeping the number of tasks in the thread pool fixed at each of 1, 5, 10, 50, 100, 150, 200, 300, 400, 500, 600, 700, 800, 900, 1000, 2000, 3000, 4000 and 5000. The number of tasks in the thread pool are fixed by spawning N tasks, and having each task post another task to the pool before completion. I then measured how long it took to process one individual task in each case. The following are the averages of all these values. Values are in average processing time per task in nanoseconds.

Platform	Old Scheduler	Old thread-pool-cpp	Deep Sleep thread-pool-cpp
MSVC	1020	593	610
GCC	1569	693	716

IdlingTest

The CPU usage of the thread pool tends to 0 regardless of the number of threads spun up; they're all asleep 😴.

Busy wait behavious can now be configured in the task options. Constructors now use rvalues.

SeverTopan · 2018-02-07T21:51:16Z

-            }
        }
-        else if(dif < 0)
+        else if(dif < 0 && (!is_strong || m_enqueue_pos.load(std::memory_order_relaxed) - m_buffer_mask - 1 == m_dequeue_pos.load(std::memory_order_relaxed)))


This line solves inkooboo#18 for enqueueing.

You still have two independent loads and one of the atomic variables may change independently from the second one between the two loads. It's not very clear what you mean here by the "strong" notation?

Fixed in #3.

SeverTopan · 2018-02-07T21:51:28Z

-            }
        }
-        else if(dif < 0)
+        else if(dif < 0 && (!is_strong || m_dequeue_pos.load(std::memory_order_relaxed) == m_enqueue_pos.load(std::memory_order_relaxed)))


This line solves inkooboo#18 for dequeueing.

The same here this may still fail even if the queue is not empty. Imagine that as a result of reordering the m_enqueu_pos is being loaded first then your thread is being suspended, then when it wakes up m_enqueu_pos is already different. So you will be comparing your m_dequeue_pos with old m_enqueue_pos.

Fixed in #3.

SeverTopan · 2018-02-07T21:53:06Z

     */
    template <typename U>
-    bool push(U&& data);
+    bool pushStrong(U&& data);


I dichotomized the push/pop interface such that it is similar to atomic::compare_exchange_weak/atomic::compare_exchange_strong - the weak versions are faster, but may fail spuriously.

SeverTopan · 2018-02-07T21:56:19Z

+* The bag supports multiple consumers, and a single producer per slot.
+*/
+template <template<typename> class Queue>
+class SlottedBag


This is a really niche structure I made up for keeping track of idle threads in the context of the lockfree interaction between workers and calls to post(). See the brief above.

The class templates its queue to match the design pattern in worker.hpp and thread_pool.hpp.

SeverTopan · 2018-02-07T21:58:18Z

@@ -131,7 +135,30 @@ template <typename Task, template<typename> class Queue>
 template <typename Handler>
 inline bool ThreadPoolImpl<Task, Queue>::tryPost(Handler&& handler)


This is where the posting happens.

SeverTopan · 2018-02-07T22:01:03Z

+    /**
+    * @brief The BusyWaitOptions class provides worker busy wait behaviour options.
+    */
+    class BusyWaitOptions


You can configure the busy wait pattern assigned to workers. By default, workers will run 3 busy wait loops, with exponentially increasing backoff starting from 1ms (i.e. 1ms, 2ms, 4ms). This pattern was experimentally determined to be efficient on my machine, and is subject to change.

SeverTopan · 2018-02-07T22:04:10Z

+
 template <typename Task, template<typename> class Queue>
-inline void Worker<Task, Queue>::threadFunc(size_t id, WorkerVector* workers)
+inline void Worker<Task, Queue>::threadFunc(size_t id, WorkerVector* workers, SlottedBag<Queue>* idle_workers, std::atomic<size_t>* num_busy_waiters)


This is where the task consumption happens.

doxxx

That looks great, Sever! I've looked through the changes and nothing jumps out at me with my less than stellar C++ knowledge.

hadamyan · 2018-02-15T19:02:26Z

+inline bool MPMCBoundedQueue<T>::push(U&& data, bool is_strong)
 {
    Cell* cell;
    size_t pos = m_enqueue_pos.load(std::memory_order_relaxed);


Strongly suggest having acquire memory ordering here. Because of reordering and predictive optimization some further code may execute before the load finishes, which is not what you desire here.

Fixed in #3.

hadamyan · 2018-02-15T19:05:42Z

-            if(m_enqueue_pos.compare_exchange_weak(
-                   pos, pos + 1, std::memory_order_relaxed))
-            {
+            if(m_enqueue_pos.compare_exchange_weak(pos, pos + 1, std::memory_order_relaxed))


Use acquire_release semantics here for the same reason. Because of reordering there might be some writes to a wrong cell, even if intuitively it seems it can't be.

load a then do b based on value of a may become do b based on some predicted value of a then check if a is different undo b

If you use acquire_release semantics it is guaranteed not to happen

Fixed in #3.

hadamyan · 2018-02-15T19:12:40Z

-            }
        }
-        else if(dif < 0)
+        else if(dif < 0 && (!is_strong || m_dequeue_pos.load(std::memory_order_relaxed) == m_enqueue_pos.load(std::memory_order_relaxed)))


As we spoke this effectively introduces spin locking. Your for loop will end up indefinitely looping if one of the producer threads gets suspended during the process of pushing. And this may have an adverse effect by consuming cpu resources and reducing the chances of the producer thread to wake up.

This type of behavior is not what you want to be hardwired in the design of your low level LF data structure.

Fixed in #3.

hadamyan · 2018-02-15T19:13:05Z


-    cell->sequence.store(
-        pos + m_buffer_mask + 1, std::memory_order_release);
+    cell->sequence.store(pos + m_buffer_mask + 1, std::memory_order_release);


using release semantics is correct here

hadamyan · 2018-02-15T19:55:40Z

+inline bool MPMCBoundedQueue<T>::pop(T& data, bool is_strong)
 {
    Cell* cell;
    size_t pos = m_dequeue_pos.load(std::memory_order_relaxed);


same here acquire

Fixed in #3.

hadamyan · 2018-02-15T19:55:51Z

-            if(m_dequeue_pos.compare_exchange_weak(
-                   pos, pos + 1, std::memory_order_relaxed))
-            {
+            if(m_dequeue_pos.compare_exchange_weak(pos, pos + 1, std::memory_order_relaxed))


acquire_release

Fixed in #3.

hadamyan · 2018-02-20T20:19:28Z

@@ -169,7 +208,33 @@ inline MPMCBoundedQueue<T>& MPMCBoundedQueue<T>::operator=(MPMCBoundedQueue&& rh



You don't need to use std::move with scalar types. m_buffer_mask is a scalar type you can simply copy it.

Fixed in #3. Removed this altogether.

hadamyan · 2018-02-20T20:25:17Z

@@ -169,7 +208,33 @@ inline MPMCBoundedQueue<T>& MPMCBoundedQueue<T>::operator=(MPMCBoundedQueue&& rh



Also in general it's a good practice to set rhs to some sensible state after moving from it. This may help catching bugs when you buy mistake try to use the object which was already moved:
A a;
A a2 = std::move(a);
do something with a

If you handle the move properly and throw a proper exception when trying to use a moved object you can catch such bugs in place of use

Fixed in #3. Removed this altogether.

hadamyan · 2018-02-20T20:30:45Z

@@ -76,19 +76,40 @@ class MPMCBoundedQueue
    MPMCBoundedQueue& operator=(MPMCBoundedQueue&& rhs) noexcept;


This class obviously should not have a copy constructor and copy assignment operator. It's a good practice to explicitly delete them.

Couldn't this still be useful if ulterior synchronization is used to ensure rhs has entered a defined state?

Fixed in #3.

hadamyan · 2018-02-20T21:46:59Z

+}
+
+template <template<typename> class Queue>
+inline bool SlottedBag<Queue>::tryEmptyAny(size_t& id)


There are two alternatives interfaces you can use for this function to avoid passing id by reference:

use std::optional if the compiler is C++17 compatible

return a std::tuple<bool, size_t>

We're still using C++14, but I'll switch the signature over to the tuple form.

Fixed in #3.

SeverTopan · 2018-02-21T22:21:41Z

+        * @brief setIterationFunction Set the function to be called upon each sleep iteration.
+        * @param function The iteration function to be called.
+        */
+        void setIterationFunction(IterationFunction&& function);


I'm not super convinced about the rvalue references everywhere here, will revisit.

SeverTopan · 2018-02-23T20:46:39Z

Please see #3 for updates.

SeverTopan · 2018-03-02T17:43:54Z

Closing - please defer to #3.

Sever Topan added 13 commits January 19, 2018 13:22

Partial implementation of deep sleeping threads.

c505f23

Integration of the Bounded Random Access Bag, readability improvements.

49fc93e

Race tweaks.

28890fa

Namespacing.

90dcd37

Exception cleanup and MPMCBoundedQueue bugfix.

56dac93

MPMCBoundedQueue selectable strength.

9fb102a

Move busy wait iterations to thread pool options.

e81af46

Ordering edits and code clarification.

f8b7ac9

Resolve ABA condition in worker wakeup.

7017c70

Rename to SlottedBag.

dc351e6

Thread Pool Options Cleanup and Functional Extension.

1e48afd

Busy wait behavious can now be configured in the task options. Constructors now use rvalues.

Template SlottedBag's Internal Queue

d50c57e

Style cleanup.

6666a22

SeverTopan self-assigned this Feb 7, 2018

SeverTopan commented Feb 7, 2018

View reviewed changes

SeverTopan changed the base branch from master to synaptive/master February 7, 2018 22:02

SeverTopan commented Feb 7, 2018

View reviewed changes

SeverTopan requested review from PoyangLiu, doxxx, mmthomas, stephure and stewartbright February 7, 2018 22:16

doxxx approved these changes Feb 8, 2018

View reviewed changes

mmthomas approved these changes Feb 8, 2018

View reviewed changes

hadamyan reviewed Feb 15, 2018

View reviewed changes

hadamyan reviewed Feb 20, 2018

View reviewed changes

SeverTopan commented Feb 21, 2018

View reviewed changes

SeverTopan mentioned this pull request Feb 23, 2018

COM-464 Deep Sleep with Rouser #3

Merged

SeverTopan closed this Mar 2, 2018

SeverTopan deleted the synaptive/dev/sever/COM-464_DeepSleep branch March 20, 2018 14:55

		@@ -131,7 +135,30 @@ template <typename Task, template<typename> class Queue>
		template <typename Handler>
		inline bool ThreadPoolImpl<Task, Queue>::tryPost(Handler&& handler)

		@@ -169,7 +208,33 @@ inline MPMCBoundedQueue<T>& MPMCBoundedQueue<T>::operator=(MPMCBoundedQueue&& rh

		@@ -76,19 +76,40 @@ class MPMCBoundedQueue
		MPMCBoundedQueue& operator=(MPMCBoundedQueue&& rhs) noexcept;

Uh oh!

Conversation

SeverTopan commented Feb 7, 2018 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Test Details

Test Results

Mandelbrot Performance Benchmark

Task Throughput Test

IdlingTest

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

SeverTopan Feb 7, 2018 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

SeverTopan Feb 7, 2018 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

SeverTopan Feb 7, 2018 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

doxxx left a comment

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

SeverTopan commented Feb 7, 2018 •

edited

Loading

SeverTopan Feb 7, 2018 •

edited

Loading

SeverTopan Feb 7, 2018 •

edited

Loading

SeverTopan Feb 7, 2018 •

edited

Loading