The New Sudoku Players' Forum

[champagne]

It is possible to compile Java code into native machine code using the GNU gcj compiler. Instead of a virtual java machine interpreter, it literally uses several libraries (libgcj/libgcjgc...) to provide standard Java service functions. I used this technique several years ago on some Java code to "cheaply" halve the process time. I don't have gcj on my current mingw installation and I don't see where there is one easily available other than on cygwin and/or linux, so I'll try building a mingw gcj using the latest gcc 4.5.1 source code. If I'm successful, it might help with the decisions of whether or not to convert/rewrite various SE algorithms into C/C++.

As for "blind porting" Java to C or C++, using C++ and STL in lieu of the Java classes is probably much easier than converting to standard C. Again, this is from some heavy lifting of Java code to C++ when we were looking for more than a doubling of speed. Essentially, we finally redesigned internal structures and algorithms using C++/STL/Boost to simplify the code and vastly reduce the processing time.

If we take the time to define a relatively complete set of techniques (including things such as sk-loops, exocets, ribbons, nrc whips/braids ...) and design a framework that easily allows for additional techniques and scoring algorithm changes, then the project should prove to be very interesting. SInce I use mingw/gnu C++/STL/Boost, that would be my choice for platform development, especially since using the C++ compiler doesn't prohibit writing functions in standard ansi C code.

Cheers,
Paul

I would agree on most of paul's remarks.
In a blind optimisation, we can expect an improvement in a ratio of 1/2 or i/3 at most.
I don't see any penalty to the use of C++ compared to C.

The problem with SE rating is to my view the use of forcing chains in the set or rules. For "hardest puzzles", the runtime ratio between SE and my solver is about 1/1000, but I excluded from my set of rules nearly all technics assuming a search using a start candidate or group of candidates.

Changing the set fo rules is an heavy decision.
Moving to C or C++ will have a poor efficiency ratio if a compiled version can be produced easily as writes paul.

But the problem of compiled versions is not so easy to solve. I am programming in C++. I worked before with an old version of Borland's compiler. I am now using the free Microsoft visual C++. I had to re write some parts of the code to switch from one to the other. The huge advantage of Java is just to avoid these traps.

I think the best result would come from an agreed optimisation of the program keeping Java as langage, but adjusting the set of rules. What is not exactly the initial proposal. I made that on my own solver.

My second best proposal would be the use of C++, if and only if the compiling issue is solved;

champagne

[JasonLion]

If you are doing a one to one direct port of the existing Java code then it would be best to use C++, since several Java language features have no equivalent in C, but do in C++. However, if re-implimenting from scratch it doesn't make much difference if you use C or C++.

It is very easy to write C code that will compile on any compiler once you have had a little experience at it. Writing portable C++ is slightly more complex, but still not a major problem.

I've seen speedups of two going from interpreted Java to compiled Java and speedups of ten making direct ports from interpreted Java to C++. Of course both of these numbers vary, depending on where the bottlenecks are. If re-implimenting things from scratch for speed it is possible to get much larger speedups, depending on just how bad the original code is. Given my cursory examination of the existing code, I suspect that some very dramatic speed improvements are likely.

SE ratings have developed a significance to the Sudoku community, despite their problems. Changing the weighting/order of how techniques are applied risks losing that significance. There are one or two issues that are so egregious that everyone will probably agree that they should be fixed, but moving beyond that very small set is problematic.

[hobiwan]

I ported gsf's sudocoup (standard C with heavy use of macros to avoid function calls) to Java and ran it with various puzzle collections to get a feeling for the speed penalty for using Java. Here are the results:

Code: Select all

            C-Version   Java-Version  J/C
17s          1.90s        3.00s       1.58
top1465      0.20s        0.37s       1.85
top50000     2.81s        4.54s       1.61
q2-taxonomy  5.90s       10.15s       1.72

As you can see in CPU heavy applications that run long enough to let the JIT compiler kick in the difference in speed is much less dramatic than the numbers often posted elsewhere (about +70% for the Java version).

A while back a similar experiment with sorting algorithms gave slightly worse results for Java (about +120% on average).

If you really want to significantly speed up SudokuExplainer you will have to change the internal data representation and the algorithms.

[gsf]

neat experiment hobiwan

If you really want to significantly speed up SudokuExplainer you will have to change the internal data representation and the algorithms.

that's why I suggested C
it will force re-examination of all data structures
conversion to C++ might make that too easy
and might let stuff that might be good for shared coding but bad for performance slip through

[PIsaacson]

It took longer than expected to find/build a version of gcj-mingw for Windows 7 x64. Here's a quick synopsis of the results for attempts to speed up Sudoku Explainer (serate and standard version) without any modifications and just using the Java source or Java classes:

I compared all the benchmarks against the Sun jre6 x86 (32 bit) java vm.

o I used gcj built using the current gcc 4.5.1 source on mingw x64 and compiled *.exe files using the SE java source (couldn't find the serate mods).
o I used Excelsior Jet 7.2 and compiled the SE and serate class files.
o I used the Sun jre6 x64 (64 bit) java vm.

Attempting to use optimization with gcj 4.5.1 for SE produced non-functional executables while unoptimized code executed, but was no faster for any of the tests. Using some Java/C standard benchmarks (http://en.wikipedia.org/wiki/Comparison_of_Java_and_C++ ref 10 & 13), gcj 4.5.1 with -O3 typically outperformed Java x86 by more than a factor of 2.

Excelsion Jet 7.2 produced SE/serate executables that typically ran about 30% faster than Java x86. The Java/C standard benchmarks as posted in ref 13 were improved by about 10% over the Jet 6 beta results.

Sun jre6 x64 required absolutely no compilation/modifications and easily outperformed Java x86 by a factor of 2 for SE/serate and for almost all of the Java/C standard benchmarks.

Final conclusion - if you have a 64 bit OS, using Sun jre6 x64 java is the easiest way to speed up those long running SE/serate jobs. Compiling the java source code using gcj (assuming the optimization problem gets fixed) doesn't seem worth the effort. Excelsior Jet, for those stuck on x86 32 bit OSs, can alleviate some of the long wait times by 25-40%.

Recommendation - bite the bullet and start from scratch.

Cheers,
Paul

[ronk]

Final conclusion - if you have a 64 bit OS, using Sun jre6 x64 java is the easiest way to speed up those long running SE/serate jobs. Compiling the java source code using gcj (assuming the optimization problem gets fixed) doesn't seem worth the effort. Excelsior Jet, for those stuck on x86 32 bit OSs, can alleviate some of the long wait times by 25-40%.

Recommendation - bite the bullet and start from scratch.

Paul, many thanks for your time and effort in running these benchmarks and making this evaluation.

It seems to me that the next task is to study the data structures used by Sudoku Explainer. Two independent evaluations should be sufficient, sooo ... do we have two volunteers

[PIsaacson]

Ron,

I've started to review some of the more complex code in an attempt to simplify and reduce the algorithms invoved into pseudo-code. When I'm done, I can send the layouts of the critical structures along with the pseudo-code. But... that more or less assumes that we want to retain the identical or near identical scoring/solving techniques used in SE. If that is the intent/decision, then the end goal is just to produce a much faster running SE??? Do we have consensus???

I'm fairly proficient at C++, so I volunteer to be one of the worker-bees, but someone needs to be the team-leader and decision maker. I nominate you, Ron, for that role. Anyone second that??? This doesn't have to be popularity contest, but I think those interested in re-engineering SE should voice their opinions and get involved.

Cheers,
Paul

[Red Ed]

I am now too busy running the Labour party to help.

But I can still heckle from the opposition benches. Why don't you get on with tackling dynamic forcing chains (or whatever the nightmarishly slow bit of SE is) first? Isolate the relevant code - e.g. by just disabling all the other techniques - and test it on a load of puzzles until you've got some good examples of difficult ones (and their corresponding chains). Post that to the forum. Then study the chains code until you understand it well enough to post an implementation-independent summary. Finally, set to work on writing the fastest code you can that produces the same output.

If this results in an algorithm+implementation that's much faster than SE's then the project is worth seeing through, building code that operates in a manner compatible with the now-optimised chains stuff. But if no-one can face attacking the hardest/slowest technique from the outset then I have no reason for optimism that there'll be any success later on.

[PIsaacson]

... Then study the chains code until you understand it well enough to post an implementation-independent summary. Finally, set to work on writing the fastest code you can that produces the same output.

Ed,

I'm on it, but it'll take some time. The code has little or no comments, so it's slow going to state the algorithm in pseudo-code. I feel less confident about disabling anything to force just the more difficult techniques, but I am placing in trace code at various locations in order to ascertain the execution path/flow. I'm still uncertain of the end goal...

Cheers,
Paul

[JasonLion]

The primary goal, as I understand it, is to produce a program to use for calculating ratings of puzzles for use in the patterns game that is far faster than SE is currently. It is not completely obvious that this is possible, though it seems very likely.

Various entertaining side projects are also involved. For example, it would be nice to have an SE compatible rating program in C (or perhaps C++), rather than Java, for easier integration into puzzle game work flow. This also provides an opportunity to correct some bugs in SE. A new implementation also provides the opportunity to reconsider the ratings and make a few touch ups to how specific techniques rate. More broadly, this also presents an opportunity to lower the barriers to entry for people trying to participate in the pattern game.

[PIsaacson]

Jason,

I don't disagree with you about changing the scoring, fixing the bugs, adding additional techniques, BUT... That would give you a fast scoring program, but one that does not necessarily replicate prior SE ratings. Maybe that isn't too awful as long as the scores would be "in the ballpark"??? A sufficient fast scoring program would allow for any prior collections to be re-scored and large discrepancies could be manually reviewed on a case-by-case basis, but again, I have to ask: Is that the end goal???

Unless a new scoring program exactly replicates the old SE scores (including the bugs and other glitches), there may be great resistance to accepting it regardless of how fast it can score collections. Currently, I have a scoring program based on nrczt whips that can process hundreds of puzzles per second, but the scores have no resemblance to SE scores. Denis Berthier has posted extensively on using chain length as a measure of degree of difficulty and has done extensive analysis on the correlation to SE scores. But, I don't see a great clamor for adopting that as a standard for scoring.

The thread is indeed titled "Team project: C or C++ version of Sudoku Explainer" so the intent seems obvious, but I question whether or not that is really what we (whoever we are) want. Personally, I think SE ratings break down after 9.4-9.5 simply because it has not been updated with the latest tricks of the trade. Some patterns, such as SK loops, are now readily identifiable and help crack really tough puzzle classes. Rank-0 patterns such as Sue-de-Coqs and doubly-linked ALSs or Death Blossoms also help destroy some really over-rated puzzles as well. My point is that we have a chance to start from scratch, so shouldn't we take the time and do it right and produce something that can easily add additional techniques as they become available/coded?

Cheers,
Paul

[ronk]

The thread is indeed titled "Team project: C or C++ version of Sudoku Explainer" so the intent seems obvious, but I question whether or not that is really what we (whoever we are) want.

I guess I should change that title. As I understand it, the goal is to produce a command-line rating program that duplicates the ratings of Sudoku Explainer. This would include the "pearl" and "diamond" ratings used by the Patterns Game. The initial product should IMO reproduce Explainer's ratings exactly, warts and all. This gives us a solid, if somewhat twisted, benchmark to which to compare.

No GUI

No hints

Why don't you get on with tackling dynamic forcing chains (or whatever the nightmarishly slow bit of SE is) first? Isolate the relevant code - e.g. by just disabling all the other techniques - and test it on a load of puzzles until you've got some good examples of difficult ones (and their corresponding chains). Post that to the forum. Then study the chains code until you understand it well enough to post an implementation-independent summary. Finally, set to work on writing the fastest code you can that produces the same output.

If this results in an algorithm+implementation that's much faster than SE's then the project is worth seeing through, building code that operates in a manner compatible with the now-optimised chains stuff. But if no-one can face attacking the hardest/slowest technique from the outset then I have no reason for optimism that there'll be any success later on.

Good idea, but if we don't bootstrap our way to the more complex techniques, by first implementing the simpler techniques, then the puzzle-solver-rater will have to use pencilmarks as its input. And from where do these pencilmarks come? Can existing Explainer Java code be modified to output pencilmarks for the technique of interest? Any thoughts here?

And if we leapfrog to some of the complex techniques, I still think we first need to define basic data structures that promise to provide high performance.

[Red Ed]

Can existing Explainer Java code be modified to output pencilmarks for the technique of interest?

Yes, and that's a better idea than mine (of just disabling all other techniques). Modify the chains code we want to improve so that on entry it spits out a pm'd grid and on exit it reports the chains it found plus timing info then exits then whole program. Thus every invocation of the modified SE on a sufficiently hard puzzle gives you one more chains example to add to the library.

And if we leapfrog to some of the complex techniques, I still think we first need to define basic data structures that promise to provide high performance.

Different data structures deliver good/bad performance in different situations; and the chains code will probably require its own internal data structures independent of everything else. I remain in favour of hitting chains, hard, without thinking about the other stuff. Very glad to see Paul's started to do just that apparently.

[BryanL]

My 2c is,

Initially get a c version using the scoring methodology (as close as possible) of SE happening first. At least that covers the issue of all the prior puzzle ratings (I don't care if the bugs are included or not - it seems a bit silly to include them but if equivalent scoring is the goal...)

Then discuss and settle on a more up to date rating scheme.

One reason I suggest this is because I can see it is going to be quite a bit of work all up and if the goal is too ambitious at the start it could well get fragmented and or bogged down in implementation.

Another is that, during a transition period, both the old and new ratings could be used, until everyone is familiar with the new, and the old rating could just wither and die. I am sure gremlin could add a script to its repertoire to re-score all the posted games, if just in a summary.

A third point is that I am fairly sure that the data structures and algorithms used in SE will be reimplemented for reasons of efficiency and also - well others will use their own (agreed upon) style. Assuming (I would wager on it) that the data structures and algorithms change, then it would be really difficult to get the rating system to match the old.

I would jump straight in but don't know java and am put off (as I am sure others are) by the plethora of files making up SE.

Bryan

[champagne]

It seems to me that the discussion is looping with no significant progress.

1) IMO that nothing has to be changed in the existing scale of rating, at least as a first goal . It would create to many problems.

2) I would not over estimate the issue of SE speed in the entry barriers for the pattern game. We are all equal in that part of the game.

3) The best i can offer, and I'll work on it to see how hard it would be, is to produce a simplified version of my solver (C++) matching the SE rating specifications. It should be relatively easy for the first part of the rating (below 7) and I don't expect huge problems before the "dynamic forcing chains". At the end, I should have a better knowledge on "how works SE".

4) This first test would be a "non GUI" program with an empty command line. I can organize the task to have thecode available on my web site.

champagne