Interesting hash-replacement scheme
Posted: Sat Apr 08, 2017 1:07 pm
When we don't want to bother with aligning hash buckets with cache lines (which could be space wasting if an integer number of entries does not exactly fit the cache line, and make the code a bit cumbersome), the following replacement scheme seems a nice alterative:
A position could be stored in only three places, starting at the 'primary' index N calculated from the hash key. This limits the number of entries you have to test for a signature match. When none of the three matches, one of them will have to replaced, in the following order of priority:
1) If the primary entry is obsolete, as determined by its aging field, (e.g. not referenced in this and the previous search), it will be replaced. This will cause obsolete entries to be flushed from the table.
2) The entry with the lowest depth of N and N+1 is designated 'replacement candidate'. This will make the highest depths survive for the entire search (or analysis session), except for a very tiny fraction where two map next to each other.
4) If the depth to store is exactly one less than that of the replacement candidate ('undercut'), replace the latter. This gives a good protection for intermediate-depth entries, as the higher their depth, the rarer the frequency with which the search produces a depth high enough to undercut them. But they would not live forever, even in the same search.
5) If the depth of N+2 is lower or equal to that of the replacement candidate, store the new position in entry N+2.
6) Store the new position in the replacement cadidate.
Note that an overloaded table suffers a barrage of very-low-depth entries (QS, or if you don't store QS, d=1). So the lowest depth of the triple will almost always be very low. To lose its status as 'always-replace' entry, it must be lucky to get hit by a depth that is larger than the lowest of the other two. Then that one will almost immediately be overwritten by a QS/d=1 entry, and become the always-replace slot for a long time. This would lead to a perpetual increase of the second-lowest depth, making the chances that the entry holding it can be used by the search of the currently traversed sub-tree smaller and smaller. The under-cut puts a stop to that, and would occasionally lower the depth of the second-lowest entry when it is adjacent to the deepest entry. And if it is not adjacent, sooner or later the adjacent one, where all replacements go, would get hit by an equal or deeper entry, leading to overwriting of the formerly protected one by a QS/d=1 entry, and then see its own depth slowly degrade through undercutting. (The bold-face 'or equal' above tries to make this sooner rather than later.)
So 33% of the table will be used to collect the deepest nodes of the search, to hold them 'forever'. (I.e. until they no longer belong to the set of deepest nodes because the search produced enough deeper ones, or are declared obsolete by increasing the search number. The latter is something you would only do in games, but not in analysis.)
A position could be stored in only three places, starting at the 'primary' index N calculated from the hash key. This limits the number of entries you have to test for a signature match. When none of the three matches, one of them will have to replaced, in the following order of priority:
1) If the primary entry is obsolete, as determined by its aging field, (e.g. not referenced in this and the previous search), it will be replaced. This will cause obsolete entries to be flushed from the table.
2) The entry with the lowest depth of N and N+1 is designated 'replacement candidate'. This will make the highest depths survive for the entire search (or analysis session), except for a very tiny fraction where two map next to each other.
4) If the depth to store is exactly one less than that of the replacement candidate ('undercut'), replace the latter. This gives a good protection for intermediate-depth entries, as the higher their depth, the rarer the frequency with which the search produces a depth high enough to undercut them. But they would not live forever, even in the same search.
5) If the depth of N+2 is lower or equal to that of the replacement candidate, store the new position in entry N+2.
6) Store the new position in the replacement cadidate.
Note that an overloaded table suffers a barrage of very-low-depth entries (QS, or if you don't store QS, d=1). So the lowest depth of the triple will almost always be very low. To lose its status as 'always-replace' entry, it must be lucky to get hit by a depth that is larger than the lowest of the other two. Then that one will almost immediately be overwritten by a QS/d=1 entry, and become the always-replace slot for a long time. This would lead to a perpetual increase of the second-lowest depth, making the chances that the entry holding it can be used by the search of the currently traversed sub-tree smaller and smaller. The under-cut puts a stop to that, and would occasionally lower the depth of the second-lowest entry when it is adjacent to the deepest entry. And if it is not adjacent, sooner or later the adjacent one, where all replacements go, would get hit by an equal or deeper entry, leading to overwriting of the formerly protected one by a QS/d=1 entry, and then see its own depth slowly degrade through undercutting. (The bold-face 'or equal' above tries to make this sooner rather than later.)
So 33% of the table will be used to collect the deepest nodes of the search, to hold them 'forever'. (I.e. until they no longer belong to the set of deepest nodes because the search produced enough deeper ones, or are declared obsolete by increasing the search number. The latter is something you would only do in games, but not in analysis.)
Code: Select all
// hash store
if(slot < 0) { // indicates we had a miss; 'entry' was left pointing to primary slot
if(searchNr - entry->age < 2) { // primary entry touched in current or previous search
slot = (entry[0].depth > entry[1].depth); // replacement candidate (0 or 1)
if(resultDepth != entry[slot].depth - 1) { // no undercut
if(entry[2].depth <= entry[slot].depth) slot = 2;
}
entry += slot; // points to entry to be replaced
}
}
entry->lock = hashKey;
...