Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Sign up for GitHub

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Jump to bottom

Depth counts differ Single vs Multi threaded #2

Open
guylangston opened this issue Dec 13, 2020 · 3 comments
Open

Depth counts differ Single vs Multi threaded #2

guylangston opened this issue Dec 13, 2020 · 3 comments

Comments

@guylangston
Copy link
Owner

guylangston commented Dec 13, 2020 •
edited
Loading

With safe-locks the depth counts should be the same. Optimistic locking should add a small number of duplicates.

30min fp

image

5min fp! with a bb:lock:* pool

image

TODO: Compare with multi-threaded; compare on an exhausted well-known puzzle
@guylangston
Copy link
Owner Author

guylangston commented Dec 13, 2020 •
edited
Loading

Using more aggresive locking
image

@guylangston
Copy link
Owner Author 

Puzzle Exit Conditions: TimeOut: 3 min
Batch Exit Conditions : TimeOut: 8 hr, 0 min
Environment           : WILLOW 'Intel(R) Core(TM) i7-3930K CPU @ 3.20GHz' OS:WIN10.0.19042.0 dotnet:5.0.1 Threads:12 x64 RELEASE
Solver Environment    : v5 -- SolverNodeLookup using IExtendedFunctionalityDescriptor and chaining
Started               : 2020-12-13 12:34:00Z

           Name: SokoSolve.Core.Lib.LibraryPuzzle
          Ident: SQ1~P7
         Rating: 783
~~###########
~##.....#..P#
###.X.XX#...#
#.##X....XX.#
#..#..X.#...#
######.######
#OO.OOX.#$##~
#.OO....###~~
#..OO#####~~~
#########~~~~

Solver: v2.1u5 [SingleThreadedForwardReverseSolver] Single-threaded logic for solving a Reverse and a Forward solver on a SINGLE pool
Memory Used: 164.9 MB, delta: 160.1 MB ~ 81 bytes/node => max nodes:779,573,677
[DONE] TimeOut                 2,049,000 nodes at    284/s in 2 hr, 0 min.
### Statistics ###
| Name                 | Nodes     | Avg. Speed | Duration (sec) | Duplicates | Warnings | Errors | Dead      | Current Depth | 
|----------------------|-----------|------------|----------------|------------|----------|--------|-----------|---------------|
|                      | 2,049,000 |     283.82 |       7,219.33 | 976,856    |        0 |      0 | 2,824,855 |               |
| NodeLookupSimpleList |   304,493 |      42.18 |       7,219.35 |            |        0 |      0 |           |               |
| NodeLookupSimpleList |   293,740 |      40.69 |       7,219.35 |            |        0 |      0 |           |               |
| SolverQueue          |    55,543 |       7.69 |       7,219.35 |            |        0 |      0 |           |               |
| SolverQueue          |    56,780 |       7.86 |       7,219.35 |            |        0 |      0 |           |               |
### Forward Tree ###
| Depth | Total  | Growth Rate | UnEval | Complete | 
|-------|--------|-------------|--------|----------|
|     0 |      1 |        0.00 |      0 |      100 |
|     1 |      2 |        2.00 |      0 |      100 |
|     2 |      8 |        4.00 |      0 |      100 |
|     3 |     26 |        3.25 |      0 |      100 |
|     4 |     59 |        2.27 |      0 |      100 |
|     5 |    120 |        2.03 |      0 |      100 |
|     6 |    214 |        1.78 |      0 |      100 |
|     7 |    351 |        1.64 |      0 |      100 |
|     8 |    551 |        1.57 |      0 |      100 |
|     9 |    829 |        1.50 |      0 |      100 |
|    10 |  1,214 |        1.46 |      0 |      100 |
|    11 |  1,745 |        1.44 |      0 |      100 |
|    12 |  2,444 |        1.40 |      0 |      100 |
|    13 |  3,381 |        1.38 |      0 |      100 |
|    14 |  4,637 |        1.37 |      0 |      100 |
|    15 |  6,305 |        1.36 |      0 |      100 |
|    16 |  8,379 |        1.33 |      0 |      100 |
|    17 | 10,945 |        1.31 |      0 |      100 |
|    18 | 14,096 |        1.29 |      0 |      100 |
|    19 | 17,856 |        1.27 |      0 |      100 |
|    20 | 22,275 |        1.25 |      0 |      100 |
|    21 | 27,597 |        1.24 |      0 |      100 |
|    22 | 33,854 |        1.23 |      0 |      100 |
|    23 | 41,103 |        1.21 |      0 |      100 |
|    24 | 49,178 |        1.20 |    720 |       98 |
|    25 | 57,323 |        1.17 | 54,824 |        4 |
### Reverse Tree ###
| Depth | Total  | Growth Rate | UnEval | Complete | 
|-------|--------|-------------|--------|----------|
|     0 |      1 |        0.00 |      1 |        0 |
|     1 |      4 |        4.00 |      0 |      100 |
|     2 |      6 |        1.50 |      0 |      100 |
|     3 |      4 |        0.67 |      0 |      100 |
|     4 |      2 |        0.50 |      0 |      100 |
|     5 |      1 |        0.50 |      0 |      100 |
|     6 |      1 |        1.00 |      0 |      100 |
|     7 |      2 |        2.00 |      0 |      100 |
|     8 |     18 |        9.00 |      0 |      100 |
|     9 |     52 |        2.89 |      0 |      100 |
|    10 |     75 |        1.44 |      0 |      100 |
|    11 |     77 |        1.03 |      0 |      100 |
|    12 |     77 |        1.00 |      0 |      100 |
|    13 |     83 |        1.08 |      0 |      100 |
|    14 |     77 |        0.93 |      0 |      100 |
|    15 |     57 |        0.74 |      0 |      100 |
|    16 |     61 |        1.07 |      0 |      100 |
|    17 |    109 |        1.79 |      0 |      100 |
|    18 |    233 |        2.14 |      0 |      100 |
|    19 |    403 |        1.73 |      0 |      100 |
|    20 |    601 |        1.49 |      0 |      100 |
|    21 |    867 |        1.44 |      0 |      100 |
|    22 |  1,185 |        1.37 |      0 |      100 |
|    23 |  1,404 |        1.18 |      0 |      100 |
|    24 |  1,437 |        1.02 |      0 |      100 |
|    25 |  1,384 |        0.96 |      0 |      100 |
|    26 |  1,269 |        0.92 |      0 |      100 |
|    27 |  1,068 |        0.84 |      0 |      100 |
|    28 |    861 |        0.81 |      0 |      100 |
|    29 |    795 |        0.92 |      0 |      100 |
|    30 |    922 |        1.16 |      0 |      100 |
|    31 |  1,242 |        1.35 |      0 |      100 |
|    32 |  1,814 |        1.46 |      0 |      100 |
|    33 |  2,602 |        1.43 |      0 |      100 |
|    34 |  3,509 |        1.35 |      0 |      100 |
|    35 |  4,487 |        1.28 |      0 |      100 |
|    36 |  5,396 |        1.20 |      0 |      100 |
|    37 |  6,067 |        1.12 |      0 |      100 |
|    38 |  6,308 |        1.04 |      0 |      100 |
|    39 |  6,195 |        0.98 |      0 |      100 |
|    40 |  5,884 |        0.95 |      0 |      100 |
|    41 |  5,600 |        0.95 |      0 |      100 |
|    42 |  5,649 |        1.01 |      0 |      100 |
|    43 |  6,418 |        1.14 |      0 |      100 |
|    44 |  8,261 |        1.29 |      0 |      100 |
|    45 | 11,560 |        1.40 |      0 |      100 |
|    46 | 16,620 |        1.44 |      0 |      100 |
|    47 | 23,482 |        1.41 |      0 |      100 |
|    48 | 31,784 |        1.35 |      0 |      100 |
|    49 | 41,006 |        1.29 |      0 |      100 |
|    50 | 50,813 |        1.24 | 20,874 |       58 |
|    51 | 35,907 |        0.71 | 35,907 |        0 |
======[End Of Report]============================================================================
Checking against known solutions/attempts. AttemptId=522 : Storing Attempt
Completed               : 2020-12-13 14:34:20Z
Computer: WILLOW 'Intel(R) Core(TM) i7-3930K CPU @ 3.20GHz' OS:WIN10.0.19042.0 dotnet:5.0.1 Threads:12 x64 RELEASE
 Version: 'e516162 Better depth reporting; reintroduced detailted reports to Console output, rev:370' at 2020-12-13 14:34:20Z, v3.4.0
    Args: SQ1~P7 --solver fr --pool bb:bst:lt --min 120 
  Report: C:\repo\SokoSolve\src\SokoSolve.Console\results\SokoSolve--2020-12-13T12-34-00.txt
| Solver | Pool      | Puzzle | State   | Solutions | Statistics                                    | 
|--------|-----------|--------|---------|-----------|-----------------------------------------------|
| fr     | bb:bst:lt | SQ1~P7 | TimeOut |           |   2,049,000 nodes at     284/s in 2 hr, 0 min |

@guylangston
Copy link
Owner Author 

Puzzle Exit Conditions: TimeOut: 3 min
Batch Exit Conditions : TimeOut: 8 hr, 0 min
Environment           : WILLOW 'Intel(R) Core(TM) i7-3930K CPU @ 3.20GHz' OS:WIN10.0.19042.0 dotnet:5.0.1 Threads:12 x64 RELEASE
Solver Environment    : v5 -- SolverNodeLookup using IExtendedFunctionalityDescriptor and chaining
Started               : 2020-12-16 10:09:56Z

           Name: SokoSolve.Core.Lib.LibraryPuzzle
          Ident: SQ1~P7
         Rating: 783
~~###########
~##.....#..P#
###.X.XX#...#
#.##X....XX.#
#..#..X.#...#
######.######
#OO.OOX.#$##~
#.OO....###~~
#..OO#####~~~
#########~~~~

Solver: v2.1u5 [SingleThreadedForwardReverseSolver] Single-threaded logic for solving a Reverse and a Forward solver on a SINGLE pool
Memory Used: 283.0 MB, delta: 277.0 MB ~ 80 bytes/node => max nodes:793,872,179
[DONE] TimeOut                 3,613,000 nodes at    167/s in 6 hr, 0 min.
### Statistics ###
| Name                 | Nodes     | Avg. Speed | Duration (sec) | Duplicates | Warnings | Errors | Dead      | Current Depth | 
|----------------------|-----------|------------|----------------|------------|----------|--------|-----------|---------------|
|                      | 3,613,000 |     166.92 |      21,645.61 | 1,745,212  |        0 |      0 | 5,741,024 |               |
| NodeLookupSimpleList |   524,142 |      24.21 |      21,645.63 |            |        0 |      0 |           |               |
| NodeLookupSimpleList |   505,699 |      23.36 |      21,645.63 |            |        0 |      0 |           |               |
| SolverQueue          |    83,552 |       3.86 |      21,645.63 |            |        0 |      0 |           |               |
| SolverQueue          |    86,721 |       4.01 |      21,645.63 |            |        0 |      0 |           |               |
### Forward Tree ###
| Depth | Total  | Growth Rate | UnEval | Complete | 
|-------|--------|-------------|--------|----------|
|     0 |      1 |        0.00 |      0 |      100 |
|     1 |      2 |        2.00 |      0 |      100 |
|     2 |      8 |        4.00 |      0 |      100 |
|     3 |     26 |        3.25 |      0 |      100 |
|     4 |     59 |        2.27 |      0 |      100 |
|     5 |    120 |        2.03 |      0 |      100 |
|     6 |    214 |        1.78 |      0 |      100 |
|     7 |    351 |        1.64 |      0 |      100 |
|     8 |    551 |        1.57 |      0 |      100 |
|     9 |    829 |        1.50 |      0 |      100 |
|    10 |  1,214 |        1.46 |      0 |      100 |
|    11 |  1,745 |        1.44 |      0 |      100 |
|    12 |  2,444 |        1.40 |      0 |      100 |
|    13 |  3,381 |        1.38 |      0 |      100 |
|    14 |  4,637 |        1.37 |      0 |      100 |
|    15 |  6,305 |        1.36 |      0 |      100 |
|    16 |  8,379 |        1.33 |      0 |      100 |
|    17 | 10,945 |        1.31 |      0 |      100 |
|    18 | 14,096 |        1.29 |      0 |      100 |
|    19 | 17,856 |        1.27 |      0 |      100 |
|    20 | 22,275 |        1.25 |      0 |      100 |
|    21 | 27,597 |        1.24 |      0 |      100 |
|    22 | 33,854 |        1.23 |      0 |      100 |
|    23 | 41,103 |        1.21 |      0 |      100 |
|    24 | 49,178 |        1.20 |      0 |      100 |
|    25 | 58,047 |        1.18 |      0 |      100 |
|    26 | 67,486 |        1.16 |      0 |      100 |
|    27 | 77,459 |        1.15 | 12,902 |       83 |
|    28 | 73,980 |        0.96 | 70,651 |        4 |
### Reverse Tree ###
| Depth | Total  | Growth Rate | UnEval | Complete | 
|-------|--------|-------------|--------|----------|
|     0 |      1 |        0.00 |      1 |        0 |
|     1 |      4 |        4.00 |      0 |      100 |
|     2 |      6 |        1.50 |      0 |      100 |
|     3 |      4 |        0.67 |      0 |      100 |
|     4 |      2 |        0.50 |      0 |      100 |
|     5 |      1 |        0.50 |      0 |      100 |
|     6 |      1 |        1.00 |      0 |      100 |
|     7 |      2 |        2.00 |      0 |      100 |
|     8 |     18 |        9.00 |      0 |      100 |
|     9 |     52 |        2.89 |      0 |      100 |
|    10 |     75 |        1.44 |      0 |      100 |
|    11 |     77 |        1.03 |      0 |      100 |
|    12 |     77 |        1.00 |      0 |      100 |
|    13 |     83 |        1.08 |      0 |      100 |
|    14 |     77 |        0.93 |      0 |      100 |
|    15 |     57 |        0.74 |      0 |      100 |
|    16 |     61 |        1.07 |      0 |      100 |
|    17 |    109 |        1.79 |      0 |      100 |
|    18 |    233 |        2.14 |      0 |      100 |
|    19 |    403 |        1.73 |      0 |      100 |
|    20 |    601 |        1.49 |      0 |      100 |
|    21 |    867 |        1.44 |      0 |      100 |
|    22 |  1,185 |        1.37 |      0 |      100 |
|    23 |  1,404 |        1.18 |      0 |      100 |
|    24 |  1,437 |        1.02 |      0 |      100 |
|    25 |  1,384 |        0.96 |      0 |      100 |
|    26 |  1,269 |        0.92 |      0 |      100 |
|    27 |  1,068 |        0.84 |      0 |      100 |
|    28 |    861 |        0.81 |      0 |      100 |
|    29 |    795 |        0.92 |      0 |      100 |
|    30 |    922 |        1.16 |      0 |      100 |
|    31 |  1,242 |        1.35 |      0 |      100 |
|    32 |  1,814 |        1.46 |      0 |      100 |
|    33 |  2,602 |        1.43 |      0 |      100 |
|    34 |  3,509 |        1.35 |      0 |      100 |
|    35 |  4,487 |        1.28 |      0 |      100 |
|    36 |  5,396 |        1.20 |      0 |      100 |
|    37 |  6,067 |        1.12 |      0 |      100 |
|    38 |  6,308 |        1.04 |      0 |      100 |
|    39 |  6,195 |        0.98 |      0 |      100 |
|    40 |  5,884 |        0.95 |      0 |      100 |
|    41 |  5,600 |        0.95 |      0 |      100 |
|    42 |  5,649 |        1.01 |      0 |      100 |
|    43 |  6,418 |        1.14 |      0 |      100 |
|    44 |  8,261 |        1.29 |      0 |      100 |
|    45 | 11,560 |        1.40 |      0 |      100 |
|    46 | 16,620 |        1.44 |      0 |      100 |
|    47 | 23,482 |        1.41 |      0 |      100 |
|    48 | 31,784 |        1.35 |      0 |      100 |
|    49 | 41,006 |        1.29 |      0 |      100 |
|    50 | 50,813 |        1.24 |      0 |      100 |
|    51 | 60,984 |        1.20 |      0 |      100 |
|    52 | 71,671 |        1.18 |      0 |      100 |
|    53 | 83,384 |        1.16 | 54,895 |       34 |
|    54 | 31,827 |        0.38 | 31,827 |        0 |
======[End Of Report]============================================================================
Completed               : 2020-12-16 16:10:43Z
Computer: WILLOW 'Intel(R) Core(TM) i7-3930K CPU @ 3.20GHz' OS:WIN10.0.19042.0 dotnet:5.0.1 Threads:12 x64 RELEASE
 Version: 'd8b1d94 Nullable Refactor, rev:383' at 2020-12-16 16:10:43Z, v3.4.0
    Args: SQ1~P7 --solver fr --pool bb:bst:lt --min 360 
  Report: C:\repo\SokoSolve\src\SokoSolve.Console\results\SokoSolve--2020-12-16T10-09-56.txt
| Solver | Pool      | Puzzle | State   | Solutions | Statistics                                    | 
|--------|-----------|--------|---------|-----------|-----------------------------------------------|
| fr     | bb:bst:lt | SQ1~P7 | TimeOut |           |   3,613,000 nodes at     167/s in 6 hr, 0 min |

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Assignees
No one assigned
Labels
None yet
Projects
None yet
Milestone
No milestone
Development

No branches or pull requests
1 participant
@guylangston