kangaroo-wild with precomputed (and chosen) DP

[kTimesG]

To generate a DB 77 it take about 12 days and also a lot of RAM and SSD space needed.

Or you can just store DPs continuously as they are found, with zero RAM overhead, and simply improve the DB each and every time a new DLP is solved. If you need a lot of RAM and 12 days, you have a bad understanding / bad implementation of the algorithm... if the purpose is to build a static DB of "best DPs", this is only "best" for the solver parameters (computing power) that you have in mind, and would not help at all solving higher ranges, or solving via something magnitudes of times faster (such as a GPU large-scale cluster).

[oddstake]

Everyone optimizes based on the resources they actually have. Not everyone is running a GPU cluster or has unlimited hardware. Different setups require different trade-offs, and what looks inefficient in one configuration can make perfect sense in another.

The problem isn’t how you build the database, the scale is simply too large for current hardware.
Who do you think will win? A perfectly optimized program with limited hardware, or unlimited hardware running poorly optimized software?

Anyway, I have no intention of solving puzzle 135 with a single CPU, just experimenting with stuff.

[arulbero]

I will try to generate a DB 77 but it will take a lot of time. I will let you know when finishes and made some tests.

Explain me why you need so much RAM and time to generate 2^29 DP points.  12 days??

[oddstake]

-n 2147483648 = 2^31 DPs (not 2^29).

Look at the progress:
DPs: ... / 6,442,450,944

6,442,450,944 = 3 × 2^31 — scored mode generates 3× more candidate DPs, then selects the best 2^31 at the end.

Value   
-n (final target DPs)                         2^31 = 2.1B
Generated DPs (scored 3×)   3 × 2^31 = 6.4B
Your DB 75 (-n)                         2^29 = 536M

DB 77 which I'm trying to generate now is 4× larger than default DB 75 (2^31 vs 2^29).


DB 77  should find puzzle 85   4 times  faster   than your DB 75 if my math is correct.

Code:

./tame_phase -n 2147483648 -r 76 77 -g 17 -w 384 -b 256 --scored --checkpoint 30
============================================================
  TAME PHASE - Scored DP Database Generator
============================================================
  Range:          2^76 - 2^77
  Global bits:    17 (DP mask: 0x1ffff)
  Target DPs:     2147483648 (2147.5M)
  Scored mode:    YES
  Workers:        384 x 128 = 49152 kangaroos
  Jump table:     512 entries (bits=9, seed=42)
  Escape table:   128 entries (mult=2000)
  History:        4
  Local buf1:     2048
  Vita (life):    8388608
  Dist bytes:     10 (trunc=0)
  Hash index:     28 bits (268435456 buckets)
  Prefix:         77_scored_17
  Midpoint:       0x18000000000000000000
============================================================
[INIT] Building jump table...
[JUMP_TABLE] target_dp=2147483648 gap=1.76e+13 opt=48592007999 (2^35.5)
[INIT] Allocating hash table: 17179869184 slots (512.00 GB)
[HUGEPAGE] 512.00 GB on 1GB hugepages (512 pages)
[RUN] Starting 384 workers...
[CHECKPOINT] Auto-save every 30 minutes to 77_scored_17_checkpoint.bin
[PROGRESS] DPs: 58876 / 6442450944 (0.0%) | 1531.59M steps/s | 11715 DP/s | fill: 0.0% | ETA: 549924s | elapsed: 5s
[PROGRESS] DPs: 117383 / 6442450944 (0.0%) | 1532.74M steps/s | 11701 DP/s | fill: 0.0% | ETA: 550571s | elapsed: 10s
[PROGRESS] DPs: 175487 / 6442450944 (0.0%) | 1532.87M steps/s | 11621 DP/s | fill: 0.0% | ETA: 554385s | elapsed: 15s
[PROGRESS] DPs: 233868 / 6442450944 (0.0%) | 1532.72M steps/s | 11676 DP/s | fill: 0.0% | ETA: 551749s | elapsed: 20s
[PROGRESS] DPs: 291662 / 6442450944 (0.0%) | 1532.49M steps/s | 11559 DP/s | fill: 0.0% | ETA: 557350s | elapsed: 25s

[kTimesG]

The problem isn’t how you build the database, the scale is simply too large for current hardware.
Who do you think will win? A perfectly optimized program with limited hardware, or unlimited hardware running poorly optimized software?

The winner is the one with more computing power put to most efficient use possible, which is irrelevant of hardware, and only relevant to costs per watt, times throughput. So it doesn't matter if you have a perfectly optimized program, if it's running on a toaster. You can also have a perfectly optimized program that runs on 5000 GPUs and solves a single DLP, simply because this is the optimal quantity of computing power required, otherwise the costs are too high due to the expected time and resources.. Having more computing power is not inversely proportional to a person's IQ, which is what your comment sounds like.

So yeah: having a perfect toaster that solves 135 will cost MORE than having a 5000 GPUs cluster working on the same problem. And as a bonus, one may not live long enough until the perfect toaster spits out the solution.

[oddstake]

Having more computing power is not inversely proportional to a person's IQ, which is what your comment sounds like.

lmao , I was talking about resources, not my intelligence.
You must be proud of yourself, or maybe very frustrated. Good luck dude and happy hunting  !

[arulbero]

-n 2147483648 = 2^31 DPs (not 2^29).

Look at the progress:
DPs: ... / 6,442,450,944

6,442,450,944 = 3 × 2^31 — scored mode generates 3× more candidate DPs, then selects the best 2^31 at the end.

Value   
-n (final target DPs)                         2^31 = 2.1B
Generated DPs (scored 3×)   3 × 2^31 = 6.4B
Your DB 75 (-n)                         2^29 = 536M

DB 77 which I'm trying to generate now is 4× larger than default DB 75 (2^31 vs 2^29).


DB 77  should find puzzle 85   4 times  faster   than your DB 75 if my math is correct.

Code:

./tame_phase -n 2147483648 -r 76 77 -g 17 -w 384 -b 256 --scored --checkpoint 30
============================================================
  TAME PHASE - Scored DP Database Generator
============================================================
  Range:          2^76 - 2^77
  Global bits:    17 (DP mask: 0x1ffff)
  Target DPs:     2147483648 (2147.5M)
  Scored mode:    YES
  Workers:        384 x 128 = 49152 kangaroos
  Jump table:     512 entries (bits=9, seed=42)
  Escape table:   128 entries (mult=2000)
  History:        4
  Local buf1:     2048
  Vita (life):    8388608
  Dist bytes:     10 (trunc=0)
  Hash index:     28 bits (268435456 buckets)
  Prefix:         77_scored_17
  Midpoint:       0x18000000000000000000
============================================================
[INIT] Building jump table...
[JUMP_TABLE] target_dp=2147483648 gap=1.76e+13 opt=48592007999 (2^35.5)
[INIT] Allocating hash table: 17179869184 slots (512.00 GB)
[HUGEPAGE] 512.00 GB on 1GB hugepages (512 pages)
[RUN] Starting 384 workers...
[CHECKPOINT] Auto-save every 30 minutes to 77_scored_17_checkpoint.bin
[PROGRESS] DPs: 58876 / 6442450944 (0.0%) | 1531.59M steps/s | 11715 DP/s | fill: 0.0% | ETA: 549924s | elapsed: 5s
[PROGRESS] DPs: 117383 / 6442450944 (0.0%) | 1532.74M steps/s | 11701 DP/s | fill: 0.0% | ETA: 550571s | elapsed: 10s
[PROGRESS] DPs: 175487 / 6442450944 (0.0%) | 1532.87M steps/s | 11621 DP/s | fill: 0.0% | ETA: 554385s | elapsed: 15s
[PROGRESS] DPs: 233868 / 6442450944 (0.0%) | 1532.72M steps/s | 11676 DP/s | fill: 0.0% | ETA: 551749s | elapsed: 20s
[PROGRESS] DPs: 291662 / 6442450944 (0.0%) | 1532.49M steps/s | 11559 DP/s | fill: 0.0% | ETA: 557350s | elapsed: 25s

I generated 6*2^29 DP points, I don't know the time, multiple times, maybe 100 hours ...

EDIT: in my opinion, instead of generating a 77 db, if your goal is optimizing 85 range, try 85 range directly; you can't achieve on 85 range the same performance that I achieved in 75 (normal), but generating 2^30 points in 85 range is better than generating 2^30 points in 2^77.