3 ms·

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 w

by mjn 13y 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 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 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_ 13y 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 https://github.com/davidad/8queens/tree/%2Bc_comparison
ufo 13y 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)
mzl 13y 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 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.
- mzl 13y 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 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 :-)

by mjn 13y ago

davidad_ 13y 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 https://github.com/davidad/8queens/tree/%2Bc_comparison

ufo 13y 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)

mzl 13y 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 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.

mzl 13y 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 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 :-)