How to improve performance of pushing data to a mutex locked queue

user_620863 0
Viewed 481

I have a queue of "jobs" (function pointers and data) pushed onto it from a main thread, which then notifies worker threads to pop the data off and run it.

The functions are pretty basic and look like this:

class JobQueue {
public: 
    // usually called by main thread but other threads can use this too
    void push(Job job) {
        {
            std::lock_guard<std::mutex> lock(mutex);   // this takes 40% of the thread's time (when NOT sync'ing)
            ready = true;
            queue.emplace_back(job);
        }
        cv.notify_one();   // this also takes another 40% of the thread's time
    }

    // only called by worker threads
    Job pop() {
        std::unique_lock<std::mutex> lock(mutex);
        cv.wait(lock, [&]{return ready;});
        Job job = list.front();
        list.pop_front();
        return job;
    }

private:
    std::list<Job>            queue;
    std::mutex                mutex;
    std::condition_variable   cv;
    bool                      ready;
};

But I have a major problem, push() is really slow. The worker threads outpace the main thread, which in my test adding jobs is all the main thread does. (The worker threads perform 20 4x4 matrix rotations that feed into eachother and get printed at the end so they're not optimized away) This seems to get worse with the number of worker threads available too. If each "Job" is bigger, say 100 matrix operations, this negative goes away and more threads == better, but the Jobs I would give it in practice are much smaller than that.

The hottest calls are the mutex lock and notify_one(), which take up 40% of the time each, everything else is negligible it seems. Also, the mutex lock is rarely waiting, it is nearly always available.

I'm not sure what I should do here, is there an obvious or not-so obvious optimization I can make that will help, or perhaps I have made a mistake? Any insight would be greatly appreciated.

(here are some metrics I took if it might help, they don't count the time it takes to create threads, the pattern is the same even for billions of jobs)

Time to calc 2000000 matrice rotations
(20 rotations x 100000 jobs)
threads   0:       149 ms  << no-bool baseline
threads   1:       151 ms  << single threaded w/pool
threads   2:        89 ms
threads   3:       120 ms
threads   4:       216 ms
threads   8:       269 ms
threads  12:       311 ms  << hardware hint
threads  16:       329 ms
threads  24:       332 ms
threads  96:       336 ms

enter image description here

enter image description here (all worker threads have the same pattern, green is execution, red is waiting on synchronization)

optimization multithreading c++
2 Answers

TL;DR: Do more work in each task. (Perhaps take more than one current task off the queue each time, but there are many other possibilities.)

Your tasks are (computationally) too small. A 4x4 matrix multiplication is just a few multiplies and adds. ~60-70 operations. 20 of them done together isn't much more expensive, ~1500 (pipelined) arithmetic operations. The cost of the thread switch including waking a thread waiting on the cv and then the actual context switch, is likely higher than this - possibly much higher.

Also, the cost of the synchronization (the manipulation of the mutex and the cv) is very expensive, especially in the case of contention, especially on a multi-core system where the hardware native synchronization operations are much more expensive than arithmetic (because of cache coherency enforcement between the multiple cores).

This is why you observe that the problem lessens when each task is doing 100 of these matrix operations, increased from 20: The workers were going back to the well for more stuff to do too often, causing contention, when they only had 20 MMs to do ... giving them 100 to do slows them down enough that contention is reduced.

(In a comment you indicate that there is only one supplier, pretty much eliminating that as a source of contention to the queue. But even there, the more tasks than can be enqueued together while under the cv lock the better - up to the limit where it is blocking workers from taking tasks.)

user_7515790

I suggest using an event handler.

The events are of two types:

  • New job arrives
  • Worker completes job

The main thread maintains a job queue, accessed only by the main thread ( so no mutex locking )

When a job arrives it is placed on job queue. When a worker completes a job a job is popped and passed to the worker

You will also need a free worker queue, at startup and when no jobs are available.

You will also need an event handler. These are tricky, so best to use a well tested library rather than rolling your own. I use boost::asio

user_165820
Related