HTTPS SSH

N-Queens

A Clojure program that benchmarks two approaches to solving the N-Queens program.

One of the approaches is that shown at Rosetta Code. It's concise, clear and rather pretty. It runs in about 1 second on my system.

The second approach is that taken by Mike Meyer at Mired in Code. Mike's blog entry describes the development of his algorithm and some approaches to making it parallel. (My original intent.)

Imagine my surprise at discovering that Mike's approach was 40 (serial) to 100 (parallel) times faster than than the other.

I'm not skilled enough with Clojure or familiar enough with Clojure profiling tools to have discovered the reason for the difference. But is certainly is interesting.

Usage

This is a Clojure project built using the Leiningen tool. To build and run the project:

cd \projects\n-queens
lein deps
lein run

Note that this will take several minutes since the Criterium tool used to do the benchmarking runs many iterations of the code to be measured in order to "warm up" the optimization in the JVM.

Here is an example of the output from a run:

Found 8 processors

Benchmarking Rosetta Code solution.
Evaluation count : 56072580 in 60 samples of 934543 calls.
          Execution time mean : 1.069846 ?s
 Execution time std-deviation : 7.843633 ns
Execution time lower quantile : 1.052998 ?s ( 2.5%)
Execution time upper quantile : 1.087745 ?s (97.5%)
                Overhead used : 9.241298 ns

Found 3 outliers in 60 samples (5.0000 %)
        low-severe   3 (5.0000 %)
Variance from outliers : 1.6389 % Variance is slightly inflated by outliers

Benchmarking recursive Mired in Code solution.
Evaluation count : 2220 in 60 samples of 37 calls.
          Execution time mean : 27.259432 ms
 Execution time std-deviation : 349.237095 ?s
Execution time lower quantile : 26.698906 ms ( 2.5%)
Execution time upper quantile : 27.907016 ms (97.5%)
                Overhead used : 9.241298 ns

Benchmarking all parallel Mired in Code solution.
Evaluation count : 3060 in 60 samples of 51 calls.
          Execution time mean : 21.187293 ms
 Execution time std-deviation : 1.198260 ms
Execution time lower quantile : 19.350979 ms ( 2.5%)
Execution time upper quantile : 23.593258 ms (97.5%)
                Overhead used : 9.241298 ns

Found 2 outliers in 60 samples (3.3333 %)
        low-severe   2 (3.3333 %)
Variance from outliers : 41.8045 % Variance is moderately inflated by outliers

Benchmarking single level parallelism Mired in Code solution.
Evaluation count : 4320 in 60 samples of 72 calls.
          Execution time mean : 12.587815 ms
 Execution time std-deviation : 1.880815 ms
Execution time lower quantile : 9.351513 ms ( 2.5%)
Execution time upper quantile : 14.205806 ms (97.5%)
                Overhead used : 9.241298 ns

Benchmaring dynamic parallelism Mired in Code solution.
Evaluation count : 5460 in 60 samples of 91 calls.
          Execution time mean : 10.667048 ms
 Execution time std-deviation : 537.434273 ?s
Execution time lower quantile : 9.951229 ms ( 2.5%)
Execution time upper quantile : 11.527415 ms (97.5%)
                Overhead used : 9.241298 ns

Backstory

As an exercise, I was planning on writing an N-Queens solver in Clojure with the intent of eventually using the concurrency features of the language to parallelize the algorithm.

As part of my research on the problem, I intended to review the method I originally learned many years (decades) ago in Niklaus Wirth's Algorithms + Data Structures = Programs, a text that taught computer programming through successive refinement. But, I either gave that book away or it is still packed away in moving boxes.

However, I did find a copy of an earlier paper in ACM where he describes the same process for solving the problem. (The article is actually an OCR of the original and, as such, is full of the errors that process tends to produce. If you read it, be careful about the errors. It is included in the doc sub-directory of the project.)

Reading the article, I was struck by what a nasty collection of global state and mutation it contains. Ah well, times change.

I was also gratified that the article mentioned that the program took about 1 second to complete on a rather power mainframe of the day. That's about the time that the slower Clojure implementation takes on my system today.

License

Copyright © 2013 FIXME

Distributed under the Eclipse Public License, the same as Clojure.