Speeding up Sudoku Explainer

Interactive on-site game threads go here

Speeding up Sudoku Explainer

Postby 1to9only » Mon Aug 05, 2019 9:24 am

Here are a few 'hacks' to speed up Sudoku Explainer (SE).

In the Patterns Game, a lot of time is spent re-rating puzzles for submission, so saving a few milliseconds here and there eventually accumulate to seconds, minutes (maybe hours!)...

The source to SE (1.2.1) was posted by rjamil here.
The serate code (1.2.1.3) can be downloaded from here.

1.
Remove the GUI bits (if using SE to rate puzzles only).

2.
Comment out all the 'assert' statements in the code, code changes required.

3.
Remove the puzzle 'checks' stuff (the puzzle is already a valid submission!), code changes required.

4.
Flatten the directory structure (i.e. ALL files in /sudoku), lots of code changes required.

5.
Remove other GUI bits (htmls, gifs), even GUI specific source and code (mostly html stuff).

6. Finally,
Remove all comments. Build. Obfuscate the jar file!

7. Testing
Use puzzles from a Patterns Game. Run thru once with vanilla SE. Verify that custom SE produces the same ratings.

[Edit 10 Aug] If the GUI is required, then the directory structure cannot be flattened.
.
Last edited by 1to9only on Sat Aug 10, 2019 4:26 pm, edited 1 time in total.
1to9only
 
Posts: 1285
Joined: 04 April 2018

Re: Speeding up Sudoku Explainer

Postby 1to9only » Mon Aug 05, 2019 9:25 am

These are changes made in SukakuExplainer here, but can be applied to SudokuExplainer to speed up serate of puzzles that contain chains.

1. In Chaining.java and ChainingHint.java
Comment out all 'assert' statements.

2. In Chaining.java
Move the cardinality assignment line:
Code: Select all
                int cardinality = cell.getPotentialValues().cardinality();
                if (cell.getValue() == 0) { // the cell is empty

to AFTER the if statement:
Code: Select all
                if (cell.getValue() == 0) { // the cell is empty
                int cardinality = cell.getPotentialValues().cardinality();

There are 2 of these, in methods getLoopHintList(...) and getMultipleChainsHintList(...).

3. In Chaining.java
Find and comment out these 4 lines:
Code: Select all
                        if (length >= 1) // Seems this can be removed!

Code: Select all
                        if (length >= 1) // Seems this can be removed

Code: Select all
                    if (!isParent(p, pOff)) { // Why this filter? (seems useless)

Code: Select all
                    }

This is the closing brace to the previous if statement.

4. In Chaining.java, in method getOffToOn(...)
Replace these lines:
Code: Select all
            // Second rule: if there is only two positions for this potential, the other one gets on
            List<Class<? extends Grid.Region>> partTypes = new ArrayList<Class<? extends Grid.Region>>(3);
            partTypes.add(Grid.Block.class);
            partTypes.add(Grid.Row.class);
            partTypes.add(Grid.Column.class);
            for (Class<? extends Grid.Region> partType : partTypes) {

with this line:
Code: Select all
            for (Class<? extends Grid.Region> partType : grid.getRegionTypes()) {

.
Last edited by 1to9only on Mon Aug 05, 2019 10:32 am, edited 1 time in total.
1to9only
 
Posts: 1285
Joined: 04 April 2018

Re: Speeding up Sudoku Explainer

Postby 1to9only » Mon Aug 05, 2019 9:25 am

These 'hacks' are to remove code that are not needed for the serate process, and/or to extract more speed from SE serate.

1.
If the GUI has been removed, then the following can also be removed: Asker.java, Settings.java, SolvingTechnique.java, Tester.java, WarningHint.java, WarningHintProducer.java

Code changes are required to: Cell.java, Grid.java, Solver.java. In Solver.java, 'most' of the code can be commented out.

In Solver.java, in method getDifficulty(), the 'try' statement(s) can be commented out. The 'want' statements can be commented out if the feature ie not used.

2.
In CommonTuples.java, this is in method searchCommonTupleLight(...):
Code: Select all
            result.or(candidate);
            if (candidate.cardinality() == 0)
                return null;

modify this to match similar code in method searchCommonTuple(...):
Code: Select all
            if (candidate.cardinality() <= 1)
                return null;
            result.or(candidate);

3.
In Chaining.java, there are a number of calls to initialize a new Potential class, e.g.
Code: Select all
                    result.add(new Potential(cell, p.value, false, p,
                            getRegionCause(region),
                            "the value can occur only once in the " + region.toString()));

The String concatenation is wasted milliseconds, modify the string (which I've tried), or make the String empty or even null (which I've not tried!).

[Edit 10 Aug] 1-3.
.
Last edited by 1to9only on Sat Aug 10, 2019 4:36 pm, edited 1 time in total.
1to9only
 
Posts: 1285
Joined: 04 April 2018

Re: Speeding up Sudoku Explainer

Postby 1to9only » Mon Aug 05, 2019 9:25 am

[reserved]
1to9only
 
Posts: 1285
Joined: 04 April 2018

Re: Speeding up Sudoku Explainer

Postby dobrichev » Mon Aug 05, 2019 2:46 pm

In diuf/sudoku/solver/rules/chaining/Chaining.java, protected List<ChainingHint> getHintList(Grid grid)
Code: Select all
        Collections.sort(result, new Comparator<ChainingHint>() {
            public int compare(ChainingHint h1, ChainingHint h2) {
                double d1 = h1.getDifficulty();
                double d2 = h2.getDifficulty();
                if (d1 < d2)
                    return -1;
                else if (d1 > d2)
                    return 1;
                int l1 = h1.getComplexity();
                int l2 = h2.getComplexity();
                if (l1 == l2)
                    return h1.getSortKey() - h2.getSortKey();
                return l1 - l2;
            }
        });

takes many minutes to sort a list of size ~18000.
Precomputing getDifficulty() and getComplexity() on a single pass should improve this.

This returns me back to the question why we don't share a single code repository for all these changes. Surely there are reasons, but can't we avoid some of them doing our life easier?

Update: With Nested Multiple Chains enabled, the same piece of code crashed the process after ~5% of the hint collection was performed on a really hard pencilmark-only puzzle.
Hidden Text: Show
Code: Select all
java -Xdebug -Xrunjdwp:transport=dt_socket,address=8000,server=y,suspend=y -Xrs -Xmx500m -cp pmseBatch.jar diuf.sudoku.test.hints --input=tarekBackdoor6.4 > tarekBackdoor6.4.seSteps
Exception in thread "main" java.lang.OutOfMemoryError: GC overhead limit exceeded
   at java.util.Arrays.copyOf(Arrays.java:3181)
   at java.util.ArrayList.grow(ArrayList.java:265)
   at java.util.ArrayList.ensureExplicitCapacity(ArrayList.java:239)
   at java.util.ArrayList.ensureCapacityInternal(ArrayList.java:231)
   at java.util.ArrayList.addAll(ArrayList.java:583)
   at diuf.sudoku.solver.rules.chaining.ChainingHint.getChain(ChainingHint.java:43)
   at diuf.sudoku.solver.rules.chaining.ChainingHint.getNestedComplexity(ChainingHint.java:181)
   at diuf.sudoku.solver.rules.chaining.ChainingHint.getComplexity(ChainingHint.java:451)
   at diuf.sudoku.solver.rules.chaining.ChainingHint.getLengthDifficulty(ChainingHint.java:331)
   at diuf.sudoku.solver.rules.chaining.BinaryChainingHint.getDifficulty(BinaryChainingHint.java:118)
   at diuf.sudoku.solver.rules.chaining.Chaining$1.compare(Chaining.java:108)
   at diuf.sudoku.solver.rules.chaining.Chaining$1.compare(Chaining.java:1)
   at java.util.TimSort.gallopLeft(TimSort.java:560)
   at java.util.TimSort.mergeAt(TimSort.java:507)
   at java.util.TimSort.mergeCollapse(TimSort.java:441)
   at java.util.TimSort.sort(TimSort.java:245)
   at java.util.Arrays.sort(Arrays.java:1512)
   at java.util.ArrayList.sort(ArrayList.java:1462)
   at java.util.Collections.sort(Collections.java:175)
   at diuf.sudoku.solver.rules.chaining.Chaining.getHintList(Chaining.java:105)
   at diuf.sudoku.solver.rules.chaining.Chaining.getHints(Chaining.java:1042)
   at diuf.sudoku.solver.rules.chaining.Chaining.getAdvancedPotentials(Chaining.java:808)
   at diuf.sudoku.solver.rules.chaining.Chaining.doChaining(Chaining.java:762)
   at diuf.sudoku.solver.rules.chaining.Chaining.doRegionChainings(Chaining.java:441)
   at diuf.sudoku.solver.rules.chaining.Chaining.getMultipleChainsHintList(Chaining.java:186)
   at diuf.sudoku.solver.rules.chaining.Chaining.getHintList(Chaining.java:88)
   at diuf.sudoku.solver.rules.chaining.Chaining.getHints(Chaining.java:1042)
   at diuf.sudoku.solver.rules.chaining.Chaining.getAdvancedPotentials(Chaining.java:808)
   at diuf.sudoku.solver.rules.chaining.Chaining.doChaining(Chaining.java:762)
   at diuf.sudoku.solver.rules.chaining.Chaining.doRegionChainings(Chaining.java:441)
   at diuf.sudoku.solver.rules.chaining.Chaining.getMultipleChainsHintList(Chaining.java:186)
   at diuf.sudoku.solver.rules.chaining.Chaining.getHintList(Chaining.java:88)
dobrichev
2016 Supporter
 
Posts: 1762
Joined: 24 May 2010

Re: Speeding up Sudoku Explainer

Postby 1to9only » Sat Aug 10, 2019 4:49 pm

dobrichev wrote:In diuf/sudoku/solver/rules/chaining/Chaining.java, protected List<ChainingHint> getHintList(Grid grid)
Code: Select all
        Collections.sort(result, new Comparator<ChainingHint>() {
            public int compare(ChainingHint h1, ChainingHint h2) {
                double d1 = h1.getDifficulty();
                double d2 = h2.getDifficulty();
                if (d1 < d2)
                    return -1;
                else if (d1 > d2)
                    return 1;
                int l1 = h1.getComplexity();
                int l2 = h2.getComplexity();
                if (l1 == l2)
                    return h1.getSortKey() - h2.getSortKey();
                return l1 - l2;
            }
        });


I've tried a variation of this to rate submissions from a previous pattern game - the time savings did not amount to much. Maybe the savings would have been greater in sukaku chains.

When using the option -Xprof to profile the application, over two-thirds of the total time is spent in just two methods - Chaining.getOffToOn and Chaining.getOnToOff :
Code: Select all
     Compiled + native   Method
 42.4% 32475  +   699    diuf.sudoku.solver.rules.chaining.Chaining.getOffToOn
 22.8% 16828  +  1003    diuf.sudoku.solver.rules.chaining.Chaining.getOnToOff

I don't think the 2 methods can be optimised, but maybe the methods they call can be looked at ...
.
1to9only
 
Posts: 1285
Joined: 04 April 2018

Re: Speeding up Sudoku Explainer

Postby dobrichev » Sat Aug 10, 2019 6:44 pm

Of course everything can be optimized, even in java.

We must consider:
- the data model - much to do there;
- the number of calls (possible caching for avoiding duplicate calls);
- what you said.

If you read the update of my recent post, one of the causes for the slow sort is the memory pressure. Also the number of comparisons increases faster than O(N), therefore caching the compared keys is a must for larger lists.
dobrichev
2016 Supporter
 
Posts: 1762
Joined: 24 May 2010


Return to Interactive games