Overkilling the 8-queens Problem

http://davidad.github.io/blog/2014/02/25/overkilling-the-8-queens-problem/

by AndyKelley • 12 years ago

201 53 12 years ago

davidad.github.io

IbJacked• 12 years ago

Hard to believe I wrote anything useful back in the day, having just an A, X, and Y.

wglb• 12 years ago

These new instruction sets look like a serious luxury, don't they?

davidad_8• 12 years ago

They truly, truly are.

curiousDog• 12 years ago

Would it have been easier to code it in C, compile with -O3 and then further tweak the assembly?

TheLoneWolfling2• 12 years ago

Perhaps. But code coming out of a C compiler (especially code compiled with -O3) can be really difficult to grok.

bluecalm4• 12 years ago

I wonder how my old C code stack up to this as well. 15ms seems like eternity btw. My naive old code without any thought in it (no bit magic, no intrinsics) and only with -Ofast flag on i7 3770 Windows 7 iterates all the solutions in 10.1ms as well as prints first of them on the screen.

If redirected to file it takes 0.232ms, again to iterate all the solutions and print first of them.

It would be nice if authors provide some way to compare it to their code. Preferably on say 15 queens instead of 8 so pretty printing time could be ignored :)

davidad_8• 12 years ago

The semantics of C map poorly onto this kind of code. The types of decisions that need to be made here, like combining certain state values into single registers so they can be operated on in parallel, and the particular structure of branching, would be difficult to make post-hoc to a C-style program.

If you're excited about it, though, I'd encourage you to give it a shot and write a blog post about your experience! However hard it turns out to be, I bet we'd all learn something new. (:

colmmacc• 12 years ago

People often think that the N-queens problem is just an abstract exercise, good sample work that stretches the mind. But when we were building Route 53, we actually use the N-queens problem, it's part of how we assign Shuffle Shards;

     https://github.com/awslabs/route53-infima#shuffleshard

The solution we included in Infima is a recursive search with backtracking because of some other needs;

     http://git.io/332VLA

but it's the N-queens problem, in a real practical setting.

primitivesuave• 12 years ago

When I was a kid, my late uncle gave me and my cousins this big speech about what the N queens problem is and how it was applied in designing chips - I never really understood his verbal description. The link you just shared is so well written and gives such a great perspective on applications of N queens - thanks for sharing it.

applecore• 12 years ago

Clickable:

https://github.com/awslabs/route53-infima#shuffleshard

http://git.io/332VLA

dfc3• 12 years ago

I do not think I have ever seen so many stylistic/rare/historic ligatures used on a web page. Does anyone know if something changed in Iceweasel Aurora? Is this something that can be turned on in css?

UPDATE: If I allow javascript the web page is rendered using some google fonts which probably do not provide any ligatures. However if I do not allow JS and Iceweasel uses my default serif font (Minion Pro) the page is littered with all sorts of contextual/historic/stylistic ligatures.

TheLoneWolfling2• 12 years ago

text-rendering: optimizelegibility

dfc3• 12 years ago

Thanks. I think I might have to rethink my choice of default fonts. It seems that Iceweasel uses all available ligatures. I have to use fontspec to explicitly turn on the rare/obscure ligatures in latex. Hopefully Mozilla will give a little thought to enabling all ligatures by default.

Examples: https://imgur.com/a/7Fcdm

deutronium• 12 years ago

That's a really fascinating article! I'd love to see how a C implementation would match up to that.

As an aside there seems to be lots of really interesting concepts involved involved in implementing chess engines.

From representing the chessboard in a highly compact manor through the use of bitboards (http://www.frayn.net/beowulf/theory.html#bitboards) to searching for 'best' possible moves.

bluecalm4• 12 years ago

My old code: http://codetidy.com/8255/

windows.h is for QueryPerformanceCounter used only in main(); compile with gcc -Ofast

It iterates/counts all solutions + prints first of them (as 01 board) in 0.23ms on my i7 (if you redirect output to file). You can also run it for N queens changing #define Qs to something bigger. The code as you see is silly (not needed conditional in main loop among other things) and not optimized, still it's pretty fast :) I am not sure what hardware they used but it takes 10x less time on my computer vs theirs.

davidad_8• 12 years ago

Hi bluecalm! I tweaked both your code and mine to uselessly solve the problem 10000 times, and not pretty print anything, so the difference in raw 8-queens-solving speed is readily apparent. Here are the results:

    bash-3.2$ make
    gcc -O3 8q_C_bluecalm.c -o 8q_C_bluecalm
    nasm 8q_x64_davidad.asm -DLOOPED=10000 -f macho64 -o 8q_x64_davidad.o
    ld -o 8q_x64_davidad 8q_x64_davidad.o

    time ./8q_C_bluecalm  ; echo $?

    real	0m0.802s
    user	0m0.801s
    sys 	0m0.001s
    92

    time ./8q_x64_davidad ; echo $?

    real	0m0.113s
    user	0m0.112s
    sys 	0m0.000s
    92

If you'd like, I'm happy to post this as a branch of my repository so others can replicate. (I only hesitate because it's a derivative work of your code.)

adwhit• 12 years ago

I am said Hacker Schooler who issued the challenge. I thought I'd done well with a Rust solution that ran in 42ms [0].

I was well and truly pwned, as they say (but at least I got some sleep last night).

[0] http://rosettacode.org/wiki/N-queens_problem#Rust

dbaupp• 12 years ago

Looks cool!

BTW, the convention would be for `static SIZE: i8 = 8;` (i.e. upper case), and I would strongly recommend you don't use `i8` for that, because SIZE * SIZE = 0 (but not in const-exprs, it seems). `uint` is the type of the smallest size that is guaranteed that to work for all array indexing.

Also, you can use `bool` instead of i8 for your array elements. (A Rust bool is a u8/i8 that is guaranteed to be either 0 or 1, i.e. exactly what your code has.)

Lastly, one conventionally matches on just `None` rather than `None()`. (This actually lead me to file https://github.com/mozilla/rust/issues/12560 to make it require that there be no `()`, so thank you for prompting that.)

JoeAltmaier• 12 years ago

Beautiful! I derived this solution back in 81 when Byte Magazine had a contest. It took 20 minutes to run in Basic on an HP 2000.

mjn• 12 years ago

As an asm tutorial / case study, I found this neat. In terms of a conclusion, I found it potentially neat, but found myself wondering: cool, but how much of a win is all this special-cased effort, versus some kind of off-the-shelf constraint solver written in portable code? It'd be interesting to see a benchmark so we could have an idea if we're talking about a 50% win, orders of magnitude win, etc.

To get a rough baseline for what a generic solution could take, I took nqueens in Answer-Set Programming [1], set n=8, and ran it through clingo [2] on an Amazon micro instance, which gets me 15ms.

Another interesting question might be whether the two solutions have different scaling properties as n increases. The ASP solution scales like this (averaging a few runs and rounding):

   n   time
   8     15ms
  10     19
  15     50
  20    130
  25    290
  30    600
  35   1050ms [1.05s]

[1] http://www.hakank.org/answer_set_programming/nqueens.lp. This encoding can be optimized a bit as well, but is a decent starting point.

[2] http://potassco.sourceforge.net, a menagerie of logic-programming tools, written in C++. 'gringo' takes a high-level encoding and turns it into something more SAT-like, 'clasp' solves the SAT-like (variable-free) programs, and 'clingo' staples the two steps together into one binary. I used the version in Debian stable package 'gringo', which reports itself as "clingo 3.0.4 (clasp 1.3.10)"

davidad_8• 12 years ago

See [1]; it is about a factor of 7 win vs. a reasonable C implementation.

[1] https://github.com/davidad/8queens/tree/%2Bc_comparison

ufo• 12 years ago

How do those numbers compare to the usual backtracking approach from the OP?I'm curious, specially with how the backtracking scales as N increases (this would be when all the heuristics from the sat solvers would really kick in)

mzl2• 12 years ago

N-queens, while quite a cute problem, is typically not that interesting as a constraint programming benchmark. The way to make it fast is to have a bit-set representation of the domains, which is not the best representation for many other important cases.

I tested the standard Gecode (http://www.gecode.org) implementation from version 4.2.1 without any special options on a MacBook Pro with a 2.6GHz Intel Core i7. Note that Gecode does not have bit-set representations for domains, so it is not optimized for this special case. Tests were run for 500 iterations and repeated 5 times to get deviations below 2.5%. I get the following timings for your sizes plus 50 and 100:

    n   time
    8     0.0368 ms
   10     0.0243 ms
   15     0.0221 ms
   20     0.1263 ms 
   25     0.2677 ms
   30     0.1621 ms 
   35     0.2433 ms 
   50     2.3234 ms 
  100     0.5509 ms

The timings are of course all strongly dependent on the heuristic used for finding the solution which is shown by the varying times above.

Constraint programming is typically also very dependent on the the pruning power of the constraints. Adding the option "-icl dom" which makes the pruning for the all-different constraints domain consistent, gives the following timings.

    n   time
    8     0.1138 ms
   10     0.0603 ms
   15     0.0879 ms
   20     0.2801 ms 
   25     0.6612 ms
   30     0.4657 ms 
   35     0.7553 ms  
   50     2.7687 ms 
  100     8.7687 ms

As can be seen, domain consistency did not actually help us in this case time-wise. The number of search-nodes visited range between 17 and 1066 for the normal consistency level, while the number of nodes visited for the domain consistent version range between 14 and 286. The reduction in search tree size was however offset by the increased complexity of the propagator.

mzl2• 12 years ago

As an update I saw that the original post was about finding all the solutions to the problem, compared to the single first solution searched for above. Running for finding all solutions, I got the following timings (same computer as above, same settings, default consistency).

    n   time           search tree  solutions
    8      0.8752 ms       767          92
   10     14.2759 ms     11431         724
   12    306.7616 ms    232163       14200
   14   8782.4620 ms   6391931      365596

Downloading the c-versions from https://github.com/davidad/8queens/tree/%2Bc_comparison gives a reference-time using the time built-in command of around 750 ms for 10k iterations. This means that the C solver takes around 0.075 ms per iteration which is a factor of ten faster than the Gecode version. That is not unreasonable given that the Gecode version is a high-level model in a general framework.

I did not manage to build the assembly-version unfortunately.

EDIT: Updated the timings and comments of the C-solver to represent that it actually solved the problem 10k times. Lesson, never do benchmarks quickly :-)

plumeria• 12 years ago

Fellow wikipedians: Curiously, there is no English Wikipedia entry for MCPL.

muglug• 12 years ago

Yes – I don't think it ever served much purpose beyond academic papers. The referenced paper's author, Martin Richards, never mentioned it when supervised me. Another language of his, BCPL, is here: http://en.wikipedia.org/wiki/BCPL

Edit: Turns out he created it after I graduated. See here: http://www.cl.cam.ac.uk/~mr10/MCPL.html for more info

djvu92• 12 years ago

I feel nowadays to meaningfully talk about performance of N-queens problem N should start with 18 instead of 8.. Here is a C++ solution with 40 lines of code and can solve 18-queens in less than a minute on a laptop:

https://gist.github.com/jdeng/7915749

shoo2• 12 years ago

N = 2 ^ 18 = 262144 queens in less than 6 seconds in a VM on a laptop

its in ~210 lines of C++:

https://bitbucket.org/rfc/dopt_nqueen/src/3e812164d97a8e91d4...

uses random local search approach, as described in russell and norvig (http://aima.cs.berkeley.edu/).

wrote this code during https://www.coursera.org/course/optimization

IanCal3• 12 years ago

Apologies, I'm posting this few times, but are you calculating the total number of solutions, or just finding a solution? The latter has a closed form solution: https://gist.github.com/IanCal/1858601

That'll do ~N=1e6 in a second (I'm sure there are lots of optimisations that could be done in it though), or solutions for N=4 to N=1000 in less than 10.

The more complex problem is finding out how many solutions there are in total.

IanCal3• 12 years ago

Are you calculating the total number of solutions, or just finding a solution? The latter has a closed form solution: https://gist.github.com/IanCal/1858601

That'll do ~N=1e6 in a second (I'm sure there are lots of optimisations that could be done in it though), or solutions for N=4 to N=1000 in less than 10.

The more complex problem is finding out how many solutions there are in total.

IanCal3• 12 years ago

I can't edit this now, but I just realised it's 1e7, not 1e6 in 1s.

djvu92• 12 years ago

Counting all the solutions. http://en.wikipedia.org/wiki/Eight_queens_puzzle#Counting_so...

userbinator2• 12 years ago

This is the sort of thing that really shows why someone who knows Asm well can beat even the best compiler - because high-level languages, in hiding the details of the machine under layers of abstraction, are also hiding those details that make it possible to write efficient code. Examples include using the flags and the stack in "unusual" (to HLLs) ways, no requirement to conform to any calling conventions, etc.

That said, the size optimiser in me sees a noticeable absence of rbx, rsi, rdi, and ebp; those registers should be used before going into the r8~r15, since the "extended" registers require a prefix byte to the instruction every time they're used. In fact since only r8, r10, r13, r14, and r15 are used, this code could be rewritten to use only one extended register and you wouldn't need the "mov rdi, r8" at the end.

nkurz2• 12 years ago

those registers should be used before going into the r8~r15, since the "extended" registers require a prefix byte to the instruction every time they're used.

It's hard to argue against "shorter", but since the modern processors this code targets all have a decoded instruction micro-op cache, there is no front-end bottleneck and the instruction length doesn't actually slow anything down.

Also, the four registers you mention are all callee-save on Windows (just RBX and RBP for Mac and Linux) , so avoiding them means you don't have to save and restore them. Given a choice, use a scratch register. That said, R12-R15 are callee-save too, so this may not apply here.

Personally, I dislike the messiness of the historical names when using them for non-historical purposes. I think if it was more acceptable to alias them to R1, R2, etc I'd prefer them more than I do.

userbinator2• 12 years ago

but since the modern processors this code targets all have a decoded instruction micro-op cache, there is no front-end bottleneck and the instruction length doesn't actually slow anything down.

Right, this code is running entirely in the core and that's part of what makes it so fast.

Also, the four registers you mention are all callee-save on Windows (just RBX and RBP for Mac and Linux) , so avoiding them means you don't have to save and restore them.

Callee-save and caller-save are just a calling convention; and one of the advantages of using Asm is you don't have to care about calling conventions except if you're interfacing with some other language, which isn't the case here - it's pure Asm. There's not even a single function call in it.

Besides, saving and restoring those registers (if you really need to) only takes 4 bytes each (2 in 32-bit mode) - a push and a pop. This tradeoff pays off if you're going to use them in more than 4 instructions.

Patient0• 12 years ago

This looks like a great blog. The previous entry on virtual memory is also pretty informative.

zurn• 12 years ago

It would be interesting hear from a compiler guy why it's hard to produce this sort of code on x86 compiling from C or OpenCL. Bonus points for GPU version :)

mar77i• 12 years ago

reminds me hof how I taught the c64 one of wolfram's 1d automata (as in http://www.mathpuzzle.com/MAA/42-From%20Keyfobs%20to%20Ringt... ) by heavily relying on lookup tables and bit shifting which got down the calculation times to about 30s for the whole 320x200 hires screen. Fun times.

Overkilling the 8-queens Problem

Related Stories