6 ms·

A fast, parallel backtracking algorithm for n-queens implemented in Rust

53 points by mbrubeck 13y ago

zhemao 13y ago
Wow, that is amazingly compact. Without comments the main function is only 12 lines.
sgk284 13y ago
The algorithm implemented here appears to be based off of this paper: http://www.cl.cam.ac.uk/~mr10/backtrk.pdf http://www.cl.cam.ac.uk/~mr10/backtrk.pdf The paper goes into far more detail than the comments in the code.
pcwalton 13y ago
I recommend looking at the WorkQueue [1] for better parallelism performance on problems like these. It's not upstreamed to the Rust core distribution yet, but it's fairly solid at this point, as it's the main parallelism workhorse for Servo. One of the nice things about having low-level memory management and well as feature-rich generics in Rust is that we can come up with parallel primitives that are tuned to the problem at hand. For example, like parallel web page layout, I suspect that any parallel primitive that needs to allocate anything is going to be too slow to achieve any gains on this problem—it rules out threads, coroutines, etc. You need a super-lightweight primitive instead. [1]: https://github.com/mozilla/servo/blob/master/src/components/util/workqueue.rs https://github.com/mozilla/servo/blob/master/src/components/...
- mamcx 13y ago
  Sorry to ask a like a noob, but what is a "super-lightweight primitive"? a INT, for example?
  - pcwalton 13y ago
    A primitive that can schedule work items with very little overhead. Creating a new work item in the work queue is probably no more than a dozen instructions, compared to hundreds or thousands for creating an OS thread or Rust task.
- oscargrouch 13y ago
  > I suspect that any parallel primitive that needs to allocate anything is going to be too slow to achieve any gains on this problem Even by using TLS instead of the global heap?
  - pcwalton 13y ago
    Any decent multithreaded allocator (like the one in glibc) is going to basically make those equivalent, and if the parallel version is 10x slower than the sequential one then I suspect most of the overhead is in allocating stacks. You could try tcmalloc/jemalloc but I suspect you won't see huge gains—the overhead of allocation in general (cache pressure, etc.) seems to be swamping any gains.

53 points by mbrubeck 13y ago

Wow, that is amazingly compact. Without comments the main function is only 12 lines.

The algorithm implemented here appears to be based off of this paper: http://www.cl.cam.ac.uk/~mr10/backtrk.pdf http://www.cl.cam.ac.uk/~mr10/backtrk.pdf The paper goes into far more detail than the comments in the code.

pcwalton 13y ago

I recommend looking at the WorkQueue [1] for better parallelism performance on problems like these. It's not upstreamed to the Rust core distribution yet, but it's fairly solid at this point, as it's the main parallelism workhorse for Servo. One of the nice things about having low-level memory management and well as feature-rich generics in Rust is that we can come up with parallel primitives that are tuned to the problem at hand. For example, like parallel web page layout, I suspect that any parallel primitive that needs to allocate anything is going to be too slow to achieve any gains on this problem—it rules out threads, coroutines, etc. You need a super-lightweight primitive instead. [1]: https://github.com/mozilla/servo/blob/master/src/components/util/workqueue.rs https://github.com/mozilla/servo/blob/master/src/components/...

mamcx 13y ago
Sorry to ask a like a noob, but what is a "super-lightweight primitive"? a INT, for example?
- pcwalton 13y ago
  A primitive that can schedule work items with very little overhead. Creating a new work item in the work queue is probably no more than a dozen instructions, compared to hundreds or thousands for creating an OS thread or Rust task.
oscargrouch 13y ago
> I suspect that any parallel primitive that needs to allocate anything is going to be too slow to achieve any gains on this problem Even by using TLS instead of the global heap?
- pcwalton 13y ago
  Any decent multithreaded allocator (like the one in glibc) is going to basically make those equivalent, and if the parallel version is 10x slower than the sequential one then I suspect most of the overhead is in allocating stacks. You could try tcmalloc/jemalloc but I suspect you won't see huge gains—the overhead of allocation in general (cache pressure, etc.) seems to be swamping any gains.