[mlpack-git] [mlpack/mlpack] LSHSearch Parallelization (#700)

[Yannis Mentekidis]

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

Is this the code I pushed the last time (commit 3af80c3) or previous ones? 
3af80c3 only has a `parallel for` loop in `LSHSearch::Search` (no parallelization in `ReturnIndicesFromTables` or `BaseCase`) and should indeed show significant speedup. I would expect even better improvement for the 32 core system, which seems to top out at around `x12` - the loop is embarassingly parallel, so a `x32` would theoretically be possible.

In previous commits such as 3d536c7 there is also code to parallelize `ReturnIndicesFromTables`. For it to run, the `OMP_NESTED` environment variable must be set to `TRUE` 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. *I'm not sure if this is a real use case for our users.*
**And that code is where the problem I described earlier lies** - I have found that the parallel code is in the end slower than the sequential one.

I think this is to blame: The `for loops` 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.
The real bottleneck is `arma::find()` and `arma::unique()`, 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.

---
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/mlpack/mlpack/pull/700#issuecomment-230607496
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://mailman.cc.gatech.edu/pipermail/mlpack-git/attachments/20160705/9e405f1e/attachment.html>