Understanding the Disruptor, a Beginner's Guide to Hardcore Concurrency -Trisha Gee & Mike Barker
Why Stack Overflow recommends it
Stack Overflow users link it when answering questions about low-latency Java queues, lazySet semantics, and the pitfalls of parallelizing work across threads.
Recommended by 2 people across 2 different months, 2011 to 2013.
What it is
A 2011 conference talk by Trisha Gee and Mike Barker of LMAX introducing the Disruptor, an open-source high-performance inter-thread messaging framework. It uses the Disruptor to explain memory barriers, cache coherency and why naive parallelism can slow code down.
What people said
Recommends Edwin Buck · 2012-04 · Stack Overflow · on “What is the absolute fastest way to implement a concurrent queue with ONLY one consumer and one producer?”
For the lowest latency in Java that I am aware of, you could use the Disruptor pattern developed by LMAX. Basically, they are reducing all latency, which means a lot of rather unique solutions to well established problems. For example, they preallocate as much as possible and reuse the objects (to prevent garbage collection from adding additional latency). Their solution is based upon memory barriers, which prevent out-of-order execution of code form crossing certain checkpoints. By doing this, they can ensure proper synchronization between one producer thread and a number of consumer threads. Here is a whitepaper describing the problem and LMAX's solution [LINK] , and a recent youtube video
Recommends Andreas Fester · 2012-10 · Stack Overflow · on “CPU usage vs Number of threads”
As the other answers already state, "it depends". In an ideal world, for n cores, you would get a throughput of factor n, given that you do the same job in a separate thread on each core (which already contains a false assumption, since you need to somehow synchronize the threads when they read from the same queue). Understanding the Disruptor, a Beginner's Guide to Hardcore Concurrency [this video] gives some nice examples what you need to consider when parallezing tasks, and also shows some cases where the attempt to parallelize leads to a longer execution time.
Cites PersonalNexus · 2011-12 · Stack Overflow · on “How is lazySet in Java's Atomic* classes implemented?”
In this video [this video] about Disruptor [LINK] , a concurrency framework, the lazySet method of Java's Atomic* classes (e.g. AtomicLong) is mentioned. According to the documentation [LINK] , this method "eventually sets to the given value". Does anybody know what the underlying mechanism is to implement this (specifically on x86 on Windows, if that is relevant). It can't be InterlockedExchange() [LINK] , because that would set the value and make sure cache lines are flushed before returning, if I'm not mistaken.
Cites Andreas Fester · 2013-03 · Stack Overflow · on “C++ What is the fastest way to scan for certain elements within a unsigned char array and a unsigned char vector?”
As others wrote, the complexity of the best algorithm is O(n) , especially since your array is not sorted. To make the search faster, you could subdivide the array and scan each portion separately in separate threads . This would scale linearly with the number of CPU cores you have available on your machine. If, for example, you have four cores available, then spawn four threads and let each thread scan one fourth of the array. Probably this discussion might help: Using threads to reduce array search time [LINK] In any case (and this is true for any performance related issues), you should profile your code. Create a test case for the approach you have, measure the time it takes and take this