Modulo based load balancing without a mutex?

I might be going about this all wrong, but here's my problem and proposed solution:

You have a 50+ gigabyte file with hundreds开发者_StackOverflow社区 of millions of independent records that need to be processed very quickly. My current solution is getting 74 million records / hour. I'm using a blocking queue for the I/O thread, and each worker thread tries to grab chunks of data from this queue.

The above is pretty slow due to mutex contention among I/O and worker threads.

Is there a way to do this style of producer/consumer without locks?

Rather than using a blocking queue and having the worker threads pull from it, give each thread it's own queue and have the I/O thread push batches of work into each thread's queue.

A circular queue would be very good for this, assuming you don't mind taking the extra effort to implement some way to keep track of how many more items can be pushed into each queue; you would have to be careful not to overwrite unprocessed records if the I/O thread is reading new records faster than the worker thread is processing them.

One way of ensuring that records aren't overwritten is having the worker threads send a message to update the I/O thread with how many records have been processed, every so often. This approach requires no locking; only an atomic operation to update the I/O thread every so often.

Aside from this, you may also be able to get some better performance by using non-blocking I/O to read more records while you push the last batch into the queues. It also helps to know if the bottleneck is disk access or processing.

What about a single reader thread putting workable sized chunks into a queue that consumers access. Or have the consumers put their own Ids into a queue that the file reader draws from everytime it reads another chunk. The latter would probably nOt block the reader often.

Single Producer Single Consumers (SPSC) lock-free queues exist. And from this you could have the producer thread dispatch the work to each of the workers in a round-robin fashion (one queue per worker). Beware that some queues can get full, and just ignore them in this case (for this round).

Regarding IO: can you actually split the file ? If you have a cheap way to detect the end of a record, it could be simple to split the file and put the various parts on different machines. Or just buy a faster HDD.