BB Sudoku V1.0

JasonLion · Posted: Fri Oct 23, 2009 3:09 am Post subject:

Just to be clear, I was commenting on the version without semi-colons between the assignments:

briturner · Posted: Fri Oct 23, 2009 3:13 am Post subject:

Greetings,

I have tried a couple ideas people have posted here. This is what I saw:

1) Using a pointer to replace all G[PIdx]. This appears that it should save the evaluation of G[PIdx] in each instance. My testing showed a small speed up for (887 to 881 msec for the pearly 6000).

2) changing the MarkChanged macro. Again, the idea is for the compiler to not calculate the index. This actually caused my solver so slow considerably. I had to make each assignment a separate statement to make it work (rather than everything set to the final 1, I have 4 '= 1' statements). After that change, the timing was just slightly longer (just a fraction of a percent). Using [upc[0]]... was also in the noise.

Conclusion: These suggested changes can be helpful (10% speed up or more were seen by others), but the speedups are very dependent on the compiler and how well it optimizes. For me, they provided at best less than a 1% improvement.

One final note. On the discussion of the portability of the ++ statements in a series of assignments. For me, I found that the suggested macro did not work correctly (stats showed that is doubled much of steps, like number of naked singles). Reworking the macro to be separate assignments restored the portability.

Brit

PIsaacson · Posted: Fri Oct 23, 2009 7:23 am Post subject:

Using gcc 4.4.1 optimize level 3 and objdump to decompile

#define MarkChanged(x) { ChangedGroup[C2Grp[x][0]] = ChangedGroup[C2Grp[x][1]] = ChangedGroup[C2Grp[x][2]] = Changed = 1; }

daj95376 · Posted: Fri Oct 23, 2009 8:28 am Post subject:

I put the following code through my Borland C++ 5.5.1 compiler:

sudoking · Posted: Fri Oct 23, 2009 8:48 am Post subject:

briturner · Posted: Fri Oct 23, 2009 11:07 pm Post subject:

I have recently upgraded to Win 7 RC, and MS Visual Studio 2008. For releases, I use the profiled optimization for final releases, since it does make the build a couple % faster.

sudoking · Posted: Wed Oct 28, 2009 4:32 pm Post subject:

Here's an interesting development. I checked the assembler that was compiled when I used the following:

briturner · Posted: Thu Oct 29, 2009 12:48 am Post subject:

I would suspect the optimizations are not as good on the older compiler. So, the one change hit the right pattern for your compiler. I found that I could get a couple percent difference by including code that did not run with an older compiler. It was a hunt for the random unneeded change that would provide the best optimization. So, I am trying to avoid these type of changes, which try to tweak the optimizations, as compared to more legitimate changes, like changing the order of the guesses, or reducing an assignment.

When I used the modified macro, the solutions were still found, but it took maybe 40% longer. checking the stats showed that there were almost double the checks for naked and hidden singles (and thus the longer run time).

brit

ChPicard

Hi

Is it necessary to end the buffer each time the routine reads a new puzzle? I do it one time in main routine and it works.

Best regards

JPS

dmhayden · Posted: Sat Oct 31, 2009 12:35 pm Post subject:

lkSudoku · Posted: Mon Nov 16, 2009 1:20 pm Post subject:

This code is indeed fast

dobrichev · Posted: Tue Jan 05, 2010 11:48 pm Post subject:

Good Job!

There are really interesting pieces of code.

Let suggest some improvements.

1) Data definition.
Using unsigned short instead of unsigned int for Grid, Grp, and SingleVal improves performance.

briturner · Posted: Wed Jan 06, 2010 4:00 am Post subject:

Greetings,

First off, congratulations, preliminary tests are showing around a 15% to 20% improvement with your program.

There is always a bit of a problem with tweaking code for efficiency, since it is very compiler and environment (os / processor / hardware) dependent. I compiled and tested the improvements you recommended (compiled directly from the file you emailed me), and for me, it actually slightly increased the amount of time needed.

On the otherhand, when I compiled your solver (fsss), it did run faster than my solver did, by some 15% to 20%. I will be looking through your code to see what some of the differences are. I do know I left some inefficiencies in my code as part of additional functionality (like handling different solving techniques and such), but that would not account for the difference.

bt

briturner · Posted: Wed Jan 06, 2010 2:40 pm Post subject:

Greetings again,

It is going to take a bit more for me to get an apples to apples timing comparison here. 2 things I noticed are:

a) you buffer the entire file IO before starting the timing, and

b) more importantly, it looks like you are attempting to run on multiple processors (I see things like "#pragma omp parallel for schedule(static, 1) reduction(+:nSolved)").

While these are legitimate speedups, it does make the timing of the actual solving algorithm more difficult.

I think I will try putting both solvers in the same timing stub, which will help give me better timings.

bt