3 ms·

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-solv

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.)

bluecalm 13y ago
Hi, I am happy to see that asm magic gains over naive code :) Feel free to host/use the code in any way you like! It will be nice addition to see how hand tuned code beats naive C implementation. (I hope your code iterates over all solutions as well, the easiest way to change mine to stop after 1st is a goto from solve to main :)) EDIT: Yeah, I meant if it counts all of them and I've just noticed 92 exit code :) I didn't expect that big a speed-up, impressive! EDIT2: to answer children post: That's great, please change -O3 to -Ofast though if you are using new GCC. It shouldn't matter much but it sometimes does; I believe -march=native won't help with generated assembly though I seems that your code from original article spent all its time in pretty printing. I am happy to see some real comparison now; I am for sure learning a lot here once I understand everything in the article.
- davidad_ 13y ago
  It counts up every solution, thus the "92" exit code. However, the non-pretty-printing version does take some shortcuts - it can't reconstruct the entire current board state in O(1) time from its actual register state. So I'm not sure exactly what you mean by "iterate over all solutions". (It certainly doesn't bail out when it finds the first solution, if that's your question.)
- davidad_ 13y ago
  Here [1] is the comparison repository, for anyone interested. [1] https://github.com/davidad/8queens/tree/%2Bc_comparison https://github.com/davidad/8queens/tree/%2Bc_comparison EDIT: I don't seem to have -Ofast, but I added a note to the readme to ask people to try it. I also added the recommended flags for Sandy Bridge, i.e. -march=core2 -msse4.1 -msse4.2.
  - anonymoushn 13y ago
    You can go at least twice as fast if you use symmetries to prune the space. I messed with the C version: $ make gcc -O3 -march=core2 -msse4.1 -msse4.2 8q_C_bluecalm.c -o 8q_C_bluecalm time ./8q_C_bluecalm ; echo $? real 0m0.376s user 0m0.373s sys 0m0.001s 92 time ./8q_x64_davidad ; echo $? real 0m0.129s user 0m0.128s sys 0m0.001s 92 Of course this doesn't matter if the point is to compare the best asm dfs to the best C dfs of the same space, but if the point is to make the best asm 8queens solver, you can get down below 6μs like this :) Edit: Using C++ templates to inline the DFS also helps time ./8q_C_bluecalm ; echo $? real 0m0.260s user 0m0.258s sys 0m0.001s 92 Unfortunately this sort of technique doesn't really apply to the asm >_> Edit again: I tried to go a bit further by replacing the board struct with your method of passing 3 bytes between levels of the dfs, but at that point the compiler was able to optimize out the whole program. Removing the templates causes the compiler to actually emit a dfs, which by now is faster than the asm (!). Removing the 2x speedup from just not looking at half of the tree slows us back down to ~1.1x the runtime of the asm: time ./8q_C_bluecalm ; echo $? real 0m0.140s user 0m0.138s sys 0m0.001s 92 Here's this last solution, the one that's ~1.1x slower than the asm on my machine: http://pastie.org/8784768 http://pastie.org/8784768 And with the free 2x speedup: http://pastie.org/8784770 http://pastie.org/8784770 One last time now: I tried getting rid of the x arg and using a global. This was much slower, so I tried getting rid of the SOLUTIONS global and using a return value. This caused the compiler to optimize out the whole program again :(
    - bluecalm 13y ago
      It seems to me that using a bitboard instead of the struct is the biggest gain. I like your version, very elegant and terse.
a_e_k 13y ago
I couldn't resist the challenge, so I wrote a non-recursive solution [0] in C++. It takes about 0.73s on an E5-4650 to loop 10000 times. Since writing it I've tried testing it against bluecalm's solution and how they compare seems to be fairly sensitive to the particular compiler and hardware combination. But it's at least a slightly different take. [0] http://pastebin.com/EciqQBg5 http://pastebin.com/EciqQBg5

bluecalm 13y ago

Hi, I am happy to see that asm magic gains over naive code :) Feel free to host/use the code in any way you like! It will be nice addition to see how hand tuned code beats naive C implementation. (I hope your code iterates over all solutions as well, the easiest way to change mine to stop after 1st is a goto from solve to main :)) EDIT: Yeah, I meant if it counts all of them and I've just noticed 92 exit code :) I didn't expect that big a speed-up, impressive! EDIT2: to answer children post: That's great, please change -O3 to -Ofast though if you are using new GCC. It shouldn't matter much but it sometimes does; I believe -march=native won't help with generated assembly though I seems that your code from original article spent all its time in pretty printing. I am happy to see some real comparison now; I am for sure learning a lot here once I understand everything in the article.

davidad_ 13y ago
It counts up every solution, thus the "92" exit code. However, the non-pretty-printing version does take some shortcuts - it can't reconstruct the entire current board state in O(1) time from its actual register state. So I'm not sure exactly what you mean by "iterate over all solutions". (It certainly doesn't bail out when it finds the first solution, if that's your question.)
davidad_ 13y ago
Here [1] is the comparison repository, for anyone interested. [1] https://github.com/davidad/8queens/tree/%2Bc_comparison https://github.com/davidad/8queens/tree/%2Bc_comparison EDIT: I don't seem to have -Ofast, but I added a note to the readme to ask people to try it. I also added the recommended flags for Sandy Bridge, i.e. -march=core2 -msse4.1 -msse4.2.
- anonymoushn 13y ago
  You can go at least twice as fast if you use symmetries to prune the space. I messed with the C version: $ make gcc -O3 -march=core2 -msse4.1 -msse4.2 8q_C_bluecalm.c -o 8q_C_bluecalm time ./8q_C_bluecalm ; echo $? real 0m0.376s user 0m0.373s sys 0m0.001s 92 time ./8q_x64_davidad ; echo $? real 0m0.129s user 0m0.128s sys 0m0.001s 92 Of course this doesn't matter if the point is to compare the best asm dfs to the best C dfs of the same space, but if the point is to make the best asm 8queens solver, you can get down below 6μs like this :) Edit: Using C++ templates to inline the DFS also helps time ./8q_C_bluecalm ; echo $? real 0m0.260s user 0m0.258s sys 0m0.001s 92 Unfortunately this sort of technique doesn't really apply to the asm >_> Edit again: I tried to go a bit further by replacing the board struct with your method of passing 3 bytes between levels of the dfs, but at that point the compiler was able to optimize out the whole program. Removing the templates causes the compiler to actually emit a dfs, which by now is faster than the asm (!). Removing the 2x speedup from just not looking at half of the tree slows us back down to ~1.1x the runtime of the asm: time ./8q_C_bluecalm ; echo $? real 0m0.140s user 0m0.138s sys 0m0.001s 92 Here's this last solution, the one that's ~1.1x slower than the asm on my machine: http://pastie.org/8784768 http://pastie.org/8784768 And with the free 2x speedup: http://pastie.org/8784770 http://pastie.org/8784770 One last time now: I tried getting rid of the x arg and using a global. This was much slower, so I tried getting rid of the SOLUTIONS global and using a return value. This caused the compiler to optimize out the whole program again :(
  - bluecalm 13y ago
    It seems to me that using a bitboard instead of the struct is the biggest gain. I like your version, very elegant and terse.

a_e_k 13y ago

I couldn't resist the challenge, so I wrote a non-recursive solution [0] in C++. It takes about 0.73s on an E5-4650 to loop 10000 times. Since writing it I've tried testing it against bluecalm's solution and how they compare seems to be fairly sensitive to the particular compiler and hardware combination. But it's at least a slightly different take. [0] http://pastebin.com/EciqQBg5 http://pastebin.com/EciqQBg5