How to improve performance of a blocking queue written in C?

user_3513453 0
Viewed 261

I have written a blocking queue in C very similar to the one provided by Java's BlockingQueue class. The queue basically provides the following API:

void blocking_queue_add(Blocking_Queue* bq, void* element);
void* blocking_queue_get(Blocking_Queue* bq);

and has the following properties:

  • It has a fixed size.
  • If blocking_queue_add is called when the queue is full, the caller is blocked until the queue has space.
  • If blocking_queue_get is called when the queue is empty, the caller is blocked until there is data to fetch.
  • If multiple callers are blocked waiting for blocking_queue_add or blocking_queue_get, they need to be served in order (FIFO).

I'm having a hard time implementing a queue that satisfies the last point while keeping acceptable performance. I'm using pthreads to do the synchronization and, in order to satisfy the FIFO requirement, I am relying on pthread_cond_wait and pthread_cond_broadcast functions. The whole idea is that all blocked callers will be waiting on a condition. Once one of them can be served, a broadcast signal is emitted and they all wake up. At this point, they can easily check who is the selected one, based on an internal FIFO state. The others voluntarily block themselves by calling pthread_cond_wait again and wait their turn.

This implementation seems to work fine and the queue itself seems to be working. However, I have a huge performance drop when there are a lot more consumers than producers, or vice versa. The problem is that when I have this unbalance, there will always be a lot of blocked callers, so the overhead of waking up all of them by calling pthread_cond_broadcast everytime becomes unacceptable.

I'm looking for hints about how to solve this. I compared my queue with Java's implementation and it is faster when dealing with small workloads, but when I test a scenario with a large and totally unbalanced workload, my implementation is a disaster, and Java's implementation seems to be only linearly slower. In fact, if I remove all of the queue-related code from my implementation and just change both blocking_queue_add and blocking_queue_get functions to just have the cond/broadcast logic, it is already a disaster.

Any input is appreciated, thanks.

Brandon's idea improved the performance a lot. Performance now seems to be more than 2x better than the Java implementation.

For anyone interested in the future, I made the source-code open source: https://github.com/felipeek/c-fifo-blocking-queue

multithreading c
1 Answers

'm having a hard time implementing a queue that satisfies the last point while keeping acceptable performance. I'm using pthreads to do the synchronization and, in order to satisfy the FIFO requirement, I am relying on pthread_cond_wait and pthread_cond_broadcast functions.

In this case, when a thread adds to the queue it does a pthread_cond_broadcast() and wakes up all threads that were blocked waiting to fetch data from the empty queue; and (if there's lots of threads that were blocked waiting) this causes lots of CPU time to get wasted by thread switches and scheduler overhead; because each waiting thread unblocks, tries to acquire a mutex (and probably blocks and unblocks again while trying to get the mutex) then checks to see if it's next, and then blocks again if it isn't next.

To fix that; each thread needs its own separate condition variable. When a thread starts waiting for data from an empty queue it puts its condition variable on a "queue of waiting readers"; and when a thread adds data to the queue it takes the first condition variable from the "queue of waiting readers" and (if there is a waiter) does one pthread_cond_signal() (and not a broadcast) so that only one waiting thread is unblocked.

Note that the "queue of waiting reader's condition variables" can be a linked list of "struct waiter { struct waiter * next; pthread_cond_t condVar; }" structures; and these structures can be created and initialized when a thread is created and then continually recycled (until the thread terminates).

For "multiple writers" it's essentially the same problem with the same solution (and can re-use the same "struct waiter" created when the thread was created). When a thread needs to wait to add data to the queue it adds its condition variable to a "linked list of waiting writers" and when a thread finishes removing data from the queue it does one pthread_cond_signal() to unblock the next waiting writer.

Note that this should significantly improve performance when its under high contention (lots of waiting readers or lots of waiting writers); but the extra overhead of managing "queues of waiters" may also reduce performance under low contention (worst case is when there's regularly only one waiting thread, which is the best case for your current approach using pthread_cond_broadcast).

user_5597370
Related