Thanks for your kind explanation, Mr. Mueller. I didn't know that these buckets would cause such a big speed increase. I always saw them as just a more efficient way of storing the hash entries. (A bucket allows you to store 2-3 hash entries at one hash table index, where you'd otherwise need to increase the size of the table to avoid a collision and keep both entries.)
I've implemented buckets now. As you said earlier about QPerft:
hgm wrote: ↑Sun Mar 29, 2020 3:04 pm
That is not a very good improvement. In Qperft the time for perft(7) drops from 18.6 to 4.18 sec when I turn on hashing (1M entries in the TT), more than a factor 4 compared to your 33%. That slows to 4.52, 4.80, 5.24, 5.99 sec when I shrink the TT to 512K, 256K , 128K or 64K entries.
With hashing off: 18.6 sec.
With hashing on (1M entries): 4.18 sec.
Time usage hashed vs non-hashed: 22.4%, speedup 77.6%
My own test is below in the code blocks.
Summary:
No hash for perft 7: 113.2 seconds
32 MB hash for perft 7 (1.2M entries, 400K buckets with 3 entries/bucket): 27.0 seconds
Time usage hashed vs non-hashed: 23.85%, speedup 76.15%.
It seems I now get comparable speedup as you do with regard to hashing, and any other speed improvements need to come from optimizing the move generator. But, that is for a later time; I just wanted the hashing working in perft to verify the zobrist keys. I'll actually take it out again for the very first version of the engine, to keep it that version as bare-bones as possible, and then build on it.
Oh, by the way... I'm now achieving this speedup by using hash tables of 32 MB, instead of 24 GB (!).
Keeping the hash at 32 MB and Increasing the number of buckets from 3 to 4, 5 and 6 keeps the time between 26.8 and 27.2 seconds; within the margin of error, IMHO. Increasing bucket size to 7 or above is very detrimental.
All thanks to you for chiming in guys
Code: Select all
No hash.
Results perft 7:
113.2 seconds for perft 7.
Finds 28.2 million leaf nodes/sec
Benchmarking perft 1-7 from starting position...
Perft 1: 20 (0 ms, inf leaves/sec)
Perft 2: 400 (0 ms, inf leaves/sec)
Perft 3: 8902 (0 ms, inf leaves/sec)
Perft 4: 197281 (7 ms, 28183000 leaves/sec)
Perft 5: 4865609 (174 ms, 27963270 leaves/sec)
Perft 6: 119060324 (4264 ms, 27922214 leaves/sec)
Perft 7: 3195901860 (113215 ms, 28228608 leaves/sec)
Total time spent: 117660 ms
Execution speed: 28217188 leaves/second
Finished.
Code: Select all
32 MB Hash
+/- 600.000 buckets
2 entries per bucket
(1.2 million entries total)
Results perft 7:
28.2 seconds (1/4th of time without hash, 75% speedup)
Finds 111.4 million leaf nodes/sec.
Benchmarking perft 1-7 from starting position...
Perft 1: 20 (0 ms, inf leaves/sec)
Perft 2: 400 (0 ms, inf leaves/sec)
Perft 3: 8902 (0 ms, inf leaves/sec)
Perft 4: 197281 (7 ms, 28183000 leaves/sec)
Perft 5: 4865609 (106 ms, 45901971 leaves/sec)
Perft 6: 119060324 (1457 ms, 81716076 leaves/sec)
Perft 7: 3195901860 (28214 ms, 113273618 leaves/sec)
Total time spent: 29784 ms
Execution speed: 111470400 leaves/second
Finished.
Code: Select all
32 MB Hash
+/- 420.000 buckets
3 entries per bucket
(1.26 million entries total)
Results perft 7:
27.0 seconds (~1/4th of time without hash, 76.1% speedup)
Finds 115.4 million leaf nodes/sec.
Benchmarking perft 1-7 from starting position...
Perft 1: 20 (0 ms, inf leaves/sec)
Perft 2: 400 (0 ms, inf leaves/sec)
Perft 3: 8902 (0 ms, inf leaves/sec)
Perft 4: 197281 (10 ms, 19728100 leaves/sec)
Perft 5: 4865609 (109 ms, 44638614 leaves/sec)
Perft 6: 119060324 (1464 ms, 81325357 leaves/sec)
Perft 7: 3195901860 (27077 ms, 118030131 leaves/sec)
Total time spent: 28660 ms
Execution speed: 115842093 leaves/second
Finished.