title: Efficient multiprocessing of massive, brute force maximization in Python 3
body: <p>This is an extension of my recent question <a href="https://stackoverflow.com/questions/10607747/avoiding-race-conditions-in-python-3s-multiprocessing-queues">Avoiding race conditions in Python 3&#39;s multiprocessing Queues</a>. Hopefully this version of the question is more specific.</p>
  
  <p><strong>TL;DR: In a multiprocessing model where worker processes are fed from a queue using <code>multiprocessing.Queue</code>, why are my worker processes so idle?</strong> Each process has its own input queue so they're not fighting each other for a shared queue's lock, but the queues spend a lot of time actually just empty. The main process is running an I/O-bound thread -- is that slowing the CPU-bound filling of the input queues?</p>
  
  <p>I'm trying to find the maximal element of the Cartesian product of N sets each with M_i elements (for 0 &lt;= i &lt; N) under a certain constraint. Recall that the elements of the Cartesian product are length-N tuples whose elements are are elements of the N sets. I'll call these tuples 'combinations' to emphasize the fact that I'm looping over every combination of the original sets. A combination meets the constraint when my function <code>is_feasible</code> returns <code>True</code>. In my problem, I'm trying to find the combination whose elements have the greatest weight: <code>sum(element.weight for element in combination)</code>.</p>
  
  <p>My problem size is large, but so is my company's server. <strong>I'm trying to rewrite the following serial algorithm as a parallel algorithm.</strong></p>
  
  <pre class="lang-python prettyprint-override"><code>from operator import itemgetter
  from itertools import product # Cartesian product function from the std lib
  def optimize(sets):
      """Return the largest (total-weight, combination) tuple from all
      possible combinations of the elements in the several sets, subject
      to the constraint that is_feasible(combo) returns True."""
      return max(
                  map(
                      lambda combination: (
                          sum(element.weight for element in combination),
                          combination
                      ),
                      filter(
                          is_feasible, # Returns True if combo meets constraint
                          product(*sets)
                      )
                  ),
                  key=itemgetter(0) # Only maximize based on sum of weight
              )
  </code></pre>
  
  <p>My current multiprocessing approach is to create worker processes and feed them combinations with an input queue. When the workers receive a <a href="https://stackoverflow.com/questions/10607747/avoiding-race-conditions-in-python-3s-multiprocessing-queues">poison pill</a> they place the best combination they've seen on an output queue and exit. I fill the input queue from the main thread of the main process. One advantage of this technique is that I can spawn a secondary thread from the main process to run a monitoring tool (just a REPL I can use to see how many combinations have been processed so far and how full the queues are).</p>
  
  <pre><code>                    +-----------+
              in_q0   |   worker0 |----\
              /-------+-----------+     \
  +-----------+   in_q1   +-----------+  \ out_q  +-----------+
  |   main    |-----------|   worker1 |-----------|   main    |
  +-----------+           +-----------+  /        +-----------+
              \-------+-----------+     /
              in_q2   |   worker2 |----/
                      +-----------+
  </code></pre>
  
  <p>I originally had all the workers reading from one input queue but found that none of them were hitting the CPU. Figuring that they were spending all their time waiting for queue.get() to unblock, I gave them their own queues. That increased pressure on the CPU, so I figured the workers were active more often. However, the queues spend most of their time empty! (I know this from the monitoring REPL I mentioned). This suggests to me that the main loop filling up the queues is slow. Here is that loop:</p>
  
  <pre class="lang-python prettyprint-override"><code>from itertools import cycle
  main():
      # (Create workers, each with its own input queue)
      # Cycle through each worker's queue and add a combination to that queue
      for combo, worker in zip(product(*sets), cycle(workers)):
          worker.in_q.put(combo)
      # (Collect results and return)
  </code></pre>
  
  <p>I'm guessing the bottleneck is <code>worker.in_q.put()</code>. How do I make that faster? My first instinct was to make the workers slower, but that just doesn't make sense... Is the problem that the monitor thread is stopping the loop too often? How would I be able to tell?</p>
  
  <p>Alternatively, is there another way to implement this that doesn't involve so much waiting on locks?</p>