<p>Thank you for the additional results, I don't have access to such powerful systems so this is nice.</p>

<p>Is this the code I pushed the last time (commit <a href="https://github.com/mlpack/mlpack/commit/3af80c339a7a846bb3bdf305131c87eaa939fc01" class="commit-link"><tt>3af80c3</tt></a>) or previous ones? <br>
<a href="https://github.com/mlpack/mlpack/commit/3af80c339a7a846bb3bdf305131c87eaa939fc01" class="commit-link"><tt>3af80c3</tt></a> only has a <code>parallel for</code> loop in <code>LSHSearch::Search</code> (no parallelization in <code>ReturnIndicesFromTables</code> or <code>BaseCase</code>) and should indeed show significant speedup. I would expect even better improvement for the 32 core system, which seems to top out at around <code>x12</code> - the loop is embarassingly parallel, so a <code>x32</code> would theoretically be possible.</p>

<p>In previous commits such as <a href="https://github.com/mlpack/mlpack/commit/3d536c7ccae4b944d71137d030fa802877643d81" class="commit-link"><tt>3d536c7</tt></a> there is also code to parallelize <code>ReturnIndicesFromTables</code>. For it to run, the <code>OMP_NESTED</code> environment variable must be set to <code>TRUE</code> and the query file must have only 1 query point. This is the use case in which a user has a trained model in memory, accepts new queries one-by-one in a live fashion, and responds with approximate nearest neighbors for each query in real time. <em>I'm not sure if this is a real use case for our users.</em><br>
<strong>And that code is where the problem I described earlier lies</strong> - I have found that the parallel code is in the end slower than the sequential one.</p>

<p>I think this is to blame: The <code>for loops</code> I have parallelized are trivial (small range), so the overhead of launching and syncing and killing threads is actually more than the time they would take if we just left them alone.<br>
The real bottleneck is <code>arma::find()</code> and <code>arma::unique()</code>, for which I tried (and failed miserably) to implement parallel versions faster than the sequential ones, mainly because my sequential implementation is far inferior to that of armadillo's. Maybe one solution to that would be finding armadillo's code, copying it verbatim (taking care of licensing)  and parallelizing that, but I tried looking into their file structure and could make no sense of where the important stuff happens.</p>

<p style="font-size:small;-webkit-text-size-adjust:none;color:#666;">&mdash;<br />You are receiving this because you are subscribed to this thread.<br />Reply to this email directly, <a href="https://github.com/mlpack/mlpack/pull/700#issuecomment-230607496">view it on GitHub</a>, or <a href="https://github.com/notifications/unsubscribe/AJ4bFHmbqVRwBrOLICpbKCnJFtEk0aTTks5qSst7gaJpZM4I5KSz">mute the thread</a>.<img alt="" height="1" src="https://github.com/notifications/beacon/AJ4bFJNhFuu3rePduFmvVm-QxBLz74bVks5qSst7gaJpZM4I5KSz.gif" width="1" /></p>
<div itemscope itemtype="http://schema.org/EmailMessage">
<div itemprop="action" itemscope itemtype="http://schema.org/ViewAction">
  <link itemprop="url" href="https://github.com/mlpack/mlpack/pull/700#issuecomment-230607496"></link>
  <meta itemprop="name" content="View Pull Request"></meta>
</div>
<meta itemprop="description" content="View this Pull Request on GitHub"></meta>
</div>