[mtlmtlmtlmtl]

I recommend anyone who's interested in this topic, or in data structures and optimisation, to pick apart Stockfish' transposition table implementation[0,1]. It's essentially a highly customised hash table. It has to handle multiple threads reading and replacing entries, with no locking. It can't grow dynamically, and so it has to "age out" entries.

Think of it like hash table implementation with the difficulty set to brutal. You can't grow dynamically(too many entries). You can't store the key, since it'll almost double the size of each entry. You can't use locks. Lookup times need to be practically constant time.

[0]: https://github.com/official-stockfish/Stockfish/blob/master/...

[1]: https://github.com/official-stockfish/Stockfish/blob/master/...

[agalunar]

True, although I'd say transposition tables are much, much easier in a crucial aspect – you deal with hash collisions by simply overwriting the current entry or nop'ing. There's no linear probing, no cuckoo hashing, &c; when you want to update an entry, you check whether you'd rather store the new thing or keep the old, and that's it.

[mtlmtlmtlmtl]

That's true in theory, but in the actual Stockfish implementation, a sort of mixed strategy is employed where entries are kept in clusters of 3. So there's a type of limited linear probing there too. Additionally, there's a lot of cleverness employed in how a position's hash is mapped to an individual cluster, and how collisions are avoided without storing a copy of the position or the full key(see the first_entry method in the header and the key16 field in the entry struct).

But indeed, it's not a large amount of code. But there's a lot of thought put into every aspect of how the data is laid out, and how the table is probed. It's a nice case study in domain specific optimisation.

[agalunar]

That's not linear probing, though; that's having a 3-way associative cache.

Maybe that's how I should have phrased my comment: a transposition table is a cache, not a hash map,* because entries can be lost (overwritten). Furthermore, insertions may not succeed.

I know you know this; I mentioned it because I didn't want anyone to read Stockfish's source expecting an implementation of a hash map and then get confused.

Stockfish's source is well-written and incidentally didactic, so I'd definitely second the recommendation to read it.

*Or hash table, or dictionary; these are all synonyms, I just prefer "map" myself.

[haunter]

Here is the same in sjeng used by Apple in the macOS Chess.app https://opensource.apple.com/source/Chess/Chess-410.4.1/sjen...

[mtlmtlmtlmtl]

At a cursory glance, this a good example of a much simpler approach than the Stockfish one. It is far less optimized though. But that's reasonable given the age of that code.

[Jabbles]

> It has to handle multiple threads reading and replacing entries, with no locking.

Is this undefined behavior or does the memory model of C++ guarantee anything given the reads/writes are presumably whole words?

I realise that the implementation doesn't actually have to be deterministic, but does the language guarantee anything in these cases?

[mtlmtlmtlmtl]

This implementation isn't actually race free per-se. It can happen that reads and writes overlap resulting in bad entries, but they are generally rare, since Stockfish utilises various heuristics to ensure that different threads are searching non-overlapping parts of the search tree most of the time. Erroneous information at a single node doesn't usually have a huge effect since ultimately the best move is chosen through a vote between the different threads. So it sort of cheats by avoiding most races and collisions, and then having ways of spotting bad entries, ignoring and overwriting them.

This is all a bit hand-wavey, but there you have it. You could do this with atomics by shaving down the size of an entry to 64 bits(Stockfish uses 10 bytes), I suppose.

[rurban]

Then they should really try https://github.com/greg7mdp/parallel-hashmap, the current state of the art.

[sapiogram]

Stockfish is the state of the art for its particular use case. General-purpose hash table are completely irrelevant, they'll never be able to compete on performance. Specific things Stockfish can assume:

* The table doesn't need to dynamically grow.

* Entries are allowed to be lost, but inserts can also simply fail

* Key collisions are considered acceptable, and because of this, Stockfish doesn't store the key in the table, only its hash. Even artificially high collision rates have been shown to not significantly impact playing strength.

* Bogus data due to race conditions is considered acceptable, same as above.

[rurban]

doubt that, will test. read the descr of my link. extremely optimized for simd, and parallel access in bigger clusters than stockfish.