title: Parallelize tasks but preserving input order in output
body: <p>I have a sub system that looks like this:</p>
  
  <pre><code>        [read]          [decode]       [deliver] 
  Byte      --&gt;  Undecoded  --&gt;   Decoded   --&gt;  Output queue
  stream          message         message     
  </code></pre>
  
  <p>The input is a socket/byte stream. The first step is to read a message. The next step is to decode the message (and store the result inside the message object). The last step is to deliver the message.</p>
  
  <p>I would like to parallelize the decoding step, but I must keep the output order the same as the input order. So if message A and B are received and the decoding of message B is faster I have to wait until A is done to deliver it.</p>
  
  <p>I have made a naive initial implementation in Java but my profiling indicates that I lose too much in the handover steps (both from the “stream reader” to the “decoder” and from “decoder” to the output). When running a test program on a 24 core computer (including hyper threading) I get:</p>
  
  <ul>
  <li>1100 K msg/s when running a single-thread-implementation. </li>
  <li>110 K msg/s when running a naive 12-thread-implementation (with a lot of
  queues).</li>
  </ul>
  
  <p>My naive implementation is available at <a href="http://pastebin.com/be1JqZy3" rel="nofollow">http://pastebin.com/be1JqZy3</a> It is over 200 lines of code so it will probably only interest those who really want to know how it is possible to make a parallel version 10 times slower than a serial (hint: start look at the class ThreadPoolDecoder).</p>
  
  <p>Does anybody has a pattern/framework to use when performing this kind of problem, where the work is continues (stream based) can be parallelized but has to be sorted upon output?</p>