search

Wikunia / ConstraintSolver.jl

ConstraintSolver in Julia: Blog posts ->
https://opensourc.es/blog/constraint-solver-1
MIT License
136 stars 13 forks source link

First version of own scc #192

Closed Wikunia closed 3 years ago

Wikunia commented 3 years ago

Implementation of #191

add some additional testing

Docstrings:

Use something similar to MatchingInit for SCC such that one doesn't create new arrays all the time.

codecov[bot] commented 3 years ago

Codecov Report

Merging #192 (4640c55) into master (824fc93) will decrease coverage by 0.00%. The diff coverage is 100.00%.

Impacted file tree graph

@@            Coverage Diff             @@
##           master     #192      +/-   ##
==========================================
- Coverage   96.67%   96.67%   -0.01%     
==========================================
  Files          35       36       +1     
  Lines        3006     3066      +60     
==========================================
+ Hits         2906     2964      +58     
- Misses        100      102       +2
Impacted Files Coverage Δ
src/constraints/all_different.jl 100.00% <100.00%> (ø)
src/constraints/all_different/scc.jl 100.00% <100.00%> (ø)
src/type_inits.jl 94.44% <100.00%> (+0.15%) :arrow_up:
src/types.jl 100.00% <100.00%> (ø)
src/Variable.jl 95.83% <0.00%> (-2.09%) :arrow_down:

Continue to review full report at Codecov.

Legend - Click here to learn more Δ = absolute <relative> (impact), ø = not affected, ? = missing data Powered by Codecov. Last update 824fc93...4640c55. Read the comment docs.

Wikunia commented 3 years ago

Benchmark Report for ConstraintSolver

Job Properties

Results

A ratio greater than 1.0 denotes a possible regression (marked with :x:), while a ratio less than 1.0 denotes a possible improvement (marked with :white_check_mark:). Only significant results - results that indicate possible regressions or improvements - are shown below (thus, an empty table means that all benchmark results remained invariant between builds).

ID time ratio memory ratio
["eternity", "5x5_all"] 1.01 (5%) 0.99 (1%) :white_check_mark:
["eternity", "6x5"] 1.02 (5%) 0.98 (1%) :white_check_mark:
["graph_coloring", "US_50colors"] 1.00 (5%) 0.99 (1%) :white_check_mark:
["graph_coloring", "US_50colors+equal"] 1.00 (5%) 0.99 (1%) :white_check_mark:
["graph_coloring", "le450_5d"] 0.87 (5%) :white_check_mark: 0.48 (1%) :white_check_mark:
["graph_coloring", "queen7_7"] 0.92 (5%) :white_check_mark: 0.62 (1%) :white_check_mark:
["killer_sudoku", "niall_5500"] 1.05 (5%) :x: 0.91 (1%) :white_check_mark:
["killer_sudoku", "niall_5500_special"] 1.18 (5%) :x: 1.08 (1%) :x:
["killer_sudoku", "niall_5501"] 0.95 (5%) 0.84 (1%) :white_check_mark:
["killer_sudoku", "niall_5501_special"] 3.29 (5%) :x: 2.28 (1%) :x:
["sudoku", "top95_1"] 1.02 (5%) 0.97 (1%) :white_check_mark:
["sudoku", "top95_11"] 1.03 (5%) 0.96 (1%) :white_check_mark:
["sudoku", "top95_16"] 1.03 (5%) 0.96 (1%) :white_check_mark:
["sudoku", "top95_21"] 1.02 (5%) 0.97 (1%) :white_check_mark:
["sudoku", "top95_26"] 1.02 (5%) 0.97 (1%) :white_check_mark:
["sudoku", "top95_31"] 1.03 (5%) 0.99 (1%) :white_check_mark:
["sudoku", "top95_36"] 1.02 (5%) 0.97 (1%) :white_check_mark:
["sudoku", "top95_41"] 1.02 (5%) 0.98 (1%) :white_check_mark:
["sudoku", "top95_46"] 1.02 (5%) 0.96 (1%) :white_check_mark:
["sudoku", "top95_51"] 1.03 (5%) 0.99 (1%) :white_check_mark:
["sudoku", "top95_6"] 1.02 (5%) 0.97 (1%) :white_check_mark:
["sudoku", "top95_61"] 1.02 (5%) 0.97 (1%) :white_check_mark:
["sudoku", "top95_71"] 1.03 (5%) 0.98 (1%) :white_check_mark:
["sudoku", "top95_76"] 1.03 (5%) 0.96 (1%) :white_check_mark:
["sudoku", "top95_81"] 1.02 (5%) 0.97 (1%) :white_check_mark:
["sudoku", "top95_86"] 1.03 (5%) 0.99 (1%) :white_check_mark:
["sudoku", "top95_91"] 1.03 (5%) 0.99 (1%) :white_check_mark:

Benchmark Group List

Here's a list of all the benchmark groups executed by this job:

Julia versioninfo

Target

Julia Version 1.5.0
Commit 96786e22cc (2020-08-01 23:44 UTC)
Platform Info:
  OS: Linux (x86_64-pc-linux-gnu)
      "Arch Linux"
  uname: Linux 5.9.10-arch1-1 #1 SMP PREEMPT Sun, 22 Nov 2020 14:16:59 +0000 x86_64 unknown
  CPU: Intel(R) Xeon(R) CPU E5-1650 0 @ 3.20GHz: 
                 speed         user         nice          sys         idle          irq
       #1-12  2122 MHz      73811 s         41 s       3451 s    1177854 s        245 s

  Memory: 46.98863983154297 GB (45179.58984375 MB free)
  Uptime: 1046.0 sec
  Load Avg:  1.0078125  0.99072265625  0.65625
  WORD_SIZE: 64
  LIBM: libopenlibm
  LLVM: libLLVM-9.0.1 (ORCJIT, sandybridge)

Baseline

Julia Version 1.5.0
Commit 96786e22cc (2020-08-01 23:44 UTC)
Platform Info:
  OS: Linux (x86_64-pc-linux-gnu)
      "Arch Linux"
  uname: Linux 5.9.10-arch1-1 #1 SMP PREEMPT Sun, 22 Nov 2020 14:16:59 +0000 x86_64 unknown
  CPU: Intel(R) Xeon(R) CPU E5-1650 0 @ 3.20GHz: 
                 speed         user         nice          sys         idle          irq
       #1-12  1758 MHz     141816 s         41 s       5784 s    1937722 s        394 s

  Memory: 46.98863983154297 GB (46032.75390625 MB free)
  Uptime: 1738.0 sec
  Load Avg:  1.00341796875  1.01806640625  0.87890625
  WORD_SIZE: 64
  LIBM: libopenlibm
  LLVM: libLLVM-9.0.1 (ORCJIT, sandybridge)
Wikunia commented 3 years ago

Benchmark Report for ConstraintSolver

Job Properties

Results

A ratio greater than 1.0 denotes a possible regression (marked with :x:), while a ratio less than 1.0 denotes a possible improvement (marked with :white_check_mark:). Only significant results - results that indicate possible regressions or improvements - are shown below (thus, an empty table means that all benchmark results remained invariant between builds).

ID time ratio memory ratio
["eternity", "5x5_all"] 1.00 (5%) 0.96 (1%) :white_check_mark:
["eternity", "6x5"] 1.00 (5%) 0.95 (1%) :white_check_mark:
["graph_coloring", "US_50colors"] 1.01 (5%) 0.98 (1%) :white_check_mark:
["graph_coloring", "US_50colors+equal"] 1.01 (5%) 0.98 (1%) :white_check_mark:
["graph_coloring", "le450_5d"] 0.84 (5%) :white_check_mark: 0.32 (1%) :white_check_mark:
["graph_coloring", "queen7_7"] 0.90 (5%) :white_check_mark: 0.51 (1%) :white_check_mark:
["killer_sudoku", "niall_5500"] 1.05 (5%) :x: 0.76 (1%) :white_check_mark:
["killer_sudoku", "niall_5500_special"] 1.11 (5%) :x: 0.96 (1%) :white_check_mark:
["killer_sudoku", "niall_5501"] 0.94 (5%) :white_check_mark: 0.71 (1%) :white_check_mark:
["killer_sudoku", "niall_5501_special"] 3.35 (5%) :x: 2.06 (1%) :x:
["sudoku", "top95_1"] 1.02 (5%) 0.93 (1%) :white_check_mark:
["sudoku", "top95_11"] 1.02 (5%) 0.85 (1%) :white_check_mark:
["sudoku", "top95_16"] 1.02 (5%) 0.85 (1%) :white_check_mark:
["sudoku", "top95_21"] 1.02 (5%) 0.92 (1%) :white_check_mark:
["sudoku", "top95_26"] 1.02 (5%) 0.91 (1%) :white_check_mark:
["sudoku", "top95_31"] 1.02 (5%) 0.89 (1%) :white_check_mark:
["sudoku", "top95_36"] 1.02 (5%) 0.93 (1%) :white_check_mark:
["sudoku", "top95_41"] 1.02 (5%) 0.90 (1%) :white_check_mark:
["sudoku", "top95_46"] 1.02 (5%) 0.89 (1%) :white_check_mark:
["sudoku", "top95_51"] 1.02 (5%) 0.90 (1%) :white_check_mark:
["sudoku", "top95_56"] 1.03 (5%) 0.89 (1%) :white_check_mark:
["sudoku", "top95_6"] 1.02 (5%) 0.94 (1%) :white_check_mark:
["sudoku", "top95_61"] 1.02 (5%) 0.89 (1%) :white_check_mark:
["sudoku", "top95_66"] 1.03 (5%) 0.88 (1%) :white_check_mark:
["sudoku", "top95_71"] 1.02 (5%) 0.91 (1%) :white_check_mark:
["sudoku", "top95_76"] 1.02 (5%) 0.89 (1%) :white_check_mark:
["sudoku", "top95_81"] 1.02 (5%) 0.91 (1%) :white_check_mark:
["sudoku", "top95_86"] 1.02 (5%) 0.92 (1%) :white_check_mark:
["sudoku", "top95_91"] 1.02 (5%) 0.90 (1%) :white_check_mark:

Benchmark Group List

Here's a list of all the benchmark groups executed by this job:

Julia versioninfo

Target

Julia Version 1.5.0
Commit 96786e22cc (2020-08-01 23:44 UTC)
Platform Info:
  OS: Linux (x86_64-pc-linux-gnu)
      "Arch Linux"
  uname: Linux 5.9.11-arch2-1 #1 SMP PREEMPT Sat, 28 Nov 2020 02:07:22 +0000 x86_64 unknown
  CPU: Intel(R) Xeon(R) CPU E5-1650 0 @ 3.20GHz: 
                 speed         user         nice          sys         idle          irq
       #1-12  3363 MHz      71365 s       4475 s       7910 s    1172205 s        331 s

  Memory: 46.9886360168457 GB (45257.49609375 MB free)
  Uptime: 1048.0 sec
  Load Avg:  1.05126953125  1.1669921875  0.7236328125
  WORD_SIZE: 64
  LIBM: libopenlibm
  LLVM: libLLVM-9.0.1 (ORCJIT, sandybridge)

Baseline

Julia Version 1.5.0
Commit 96786e22cc (2020-08-01 23:44 UTC)
Platform Info:
  OS: Linux (x86_64-pc-linux-gnu)
      "Arch Linux"
  uname: Linux 5.9.11-arch2-1 #1 SMP PREEMPT Sat, 28 Nov 2020 02:07:22 +0000 x86_64 unknown
  CPU: Intel(R) Xeon(R) CPU E5-1650 0 @ 3.20GHz: 
                 speed         user         nice          sys         idle          irq
       #1-12  1620 MHz     139220 s       4475 s      10283 s    1934517 s        505 s

  Memory: 46.9886360168457 GB (46014.1328125 MB free)
  Uptime: 1742.0 sec
  Load Avg:  1.0947265625  1.072265625  0.9326171875
  WORD_SIZE: 64
  LIBM: libopenlibm
  LLVM: libLLVM-9.0.1 (ORCJIT, sandybridge)
Wikunia commented 3 years ago

I need to figure out why killer sudokus slow down. Additionally run the full graph coloring benchmark suite on it.

Wikunia commented 3 years ago

The bt_infeasible can be different because of the order of how di_ei is defined. Should benchmark own version of scc with the old version but there using the new ordering to have a fairer comparison.

Wikunia commented 3 years ago

Benchmark Report for ConstraintSolver

Job Properties

Results

A ratio greater than 1.0 denotes a possible regression (marked with :x:), while a ratio less than 1.0 denotes a possible improvement (marked with :white_check_mark:). Only significant results - results that indicate possible regressions or improvements - are shown below (thus, an empty table means that all benchmark results remained invariant between builds).

ID time ratio memory ratio
["eternity", "5x5_all"] 0.96 (5%) 0.96 (1%) :white_check_mark:
["eternity", "6x5"] 0.98 (5%) 0.95 (1%) :white_check_mark:
["graph_coloring", "US_50colors"] 1.01 (5%) 0.99 (1%) :white_check_mark:
["graph_coloring", "le450_5d"] 0.94 (5%) :white_check_mark: 0.38 (1%) :white_check_mark:
["graph_coloring", "queen7_7"] 0.97 (5%) 0.62 (1%) :white_check_mark:
["killer_sudoku", "niall_5500"] 0.93 (5%) :white_check_mark: 0.71 (1%) :white_check_mark:
["killer_sudoku", "niall_5500_special"] 0.81 (5%) :white_check_mark: 0.79 (1%) :white_check_mark:
["killer_sudoku", "niall_5501"] 0.93 (5%) :white_check_mark: 0.72 (1%) :white_check_mark:
["killer_sudoku", "niall_5501_special"] 0.92 (5%) :white_check_mark: 0.78 (1%) :white_check_mark:
["sudoku", "top95_1"] 0.98 (5%) 0.89 (1%) :white_check_mark:
["sudoku", "top95_11"] 0.97 (5%) 0.82 (1%) :white_check_mark:
["sudoku", "top95_16"] 0.96 (5%) 0.82 (1%) :white_check_mark:
["sudoku", "top95_21"] 0.97 (5%) 0.88 (1%) :white_check_mark:
["sudoku", "top95_26"] 0.97 (5%) 0.87 (1%) :white_check_mark:
["sudoku", "top95_31"] 0.98 (5%) 0.86 (1%) :white_check_mark:
["sudoku", "top95_36"] 0.97 (5%) 0.88 (1%) :white_check_mark:
["sudoku", "top95_41"] 0.97 (5%) 0.87 (1%) :white_check_mark:
["sudoku", "top95_46"] 0.97 (5%) 0.86 (1%) :white_check_mark:
["sudoku", "top95_51"] 0.98 (5%) 0.87 (1%) :white_check_mark:
["sudoku", "top95_56"] 0.98 (5%) 0.86 (1%) :white_check_mark:
["sudoku", "top95_6"] 0.97 (5%) 0.89 (1%) :white_check_mark:
["sudoku", "top95_61"] 0.97 (5%) 0.86 (1%) :white_check_mark:
["sudoku", "top95_66"] 0.98 (5%) 0.86 (1%) :white_check_mark:
["sudoku", "top95_71"] 0.97 (5%) 0.87 (1%) :white_check_mark:
["sudoku", "top95_76"] 0.97 (5%) 0.85 (1%) :white_check_mark:
["sudoku", "top95_81"] 0.97 (5%) 0.87 (1%) :white_check_mark:
["sudoku", "top95_86"] 0.98 (5%) 0.88 (1%) :white_check_mark:
["sudoku", "top95_91"] 0.98 (5%) 0.87 (1%) :white_check_mark:

Benchmark Group List

Here's a list of all the benchmark groups executed by this job:

Julia versioninfo

Target

Julia Version 1.5.0
Commit 96786e22cc (2020-08-01 23:44 UTC)
Platform Info:
  OS: Linux (x86_64-pc-linux-gnu)
      "Arch Linux"
  uname: Linux 5.9.11-arch2-1 #1 SMP PREEMPT Sat, 28 Nov 2020 02:07:22 +0000 x86_64 unknown
  CPU: Intel(R) Xeon(R) CPU E5-1650 0 @ 3.20GHz: 
                 speed         user         nice          sys         idle          irq
       #1-12  1924 MHz     229261 s        332 s      35385 s   28928008 s       4043 s

  Memory: 46.9886360168457 GB (42568.6328125 MB free)
  Uptime: 24344.0 sec
  Load Avg:  1.099609375  1.1044921875  1.0029296875
  WORD_SIZE: 64
  LIBM: libopenlibm
  LLVM: libLLVM-9.0.1 (ORCJIT, sandybridge)

Baseline

Julia Version 1.5.0
Commit 96786e22cc (2020-08-01 23:44 UTC)
Platform Info:
  OS: Linux (x86_64-pc-linux-gnu)
      "Arch Linux"
  uname: Linux 5.9.11-arch2-1 #1 SMP PREEMPT Sat, 28 Nov 2020 02:07:22 +0000 x86_64 unknown
  CPU: Intel(R) Xeon(R) CPU E5-1650 0 @ 3.20GHz: 
                 speed         user         nice          sys         idle          irq
       #1-12  1501 MHz     298308 s        332 s      37703 s   29700851 s       4231 s

  Memory: 46.9886360168457 GB (42886.5 MB free)
  Uptime: 25048.0 sec
  Load Avg:  1.05859375  1.0546875  1.0107421875
  WORD_SIZE: 64
  LIBM: libopenlibm
  LLVM: libLLVM-9.0.1 (ORCJIT, sandybridge)