Well, for one, you would return no information in case of a miss, so that on storing you would have to recalculate the etry address.Sven Schüle wrote:I am certainly able to understand C code, even if it looks like that:hgm wrote:You mean you are unable to see why the code I shown above would work?
That indeed seems like a problem...I simply don't like it that way. A simple loop does the same since the compiler will unroll it due to the number of slots being a compile time constant. Updating the slot variable with some XORs may be a nice hacker trick but why invest energy if an obvious solution is available?Code: Select all
int slot=0; HashEntry *entry = hashTable + (key & hashMask); if(entry[slot].lock == key || entry[slot^=1].lock == key || entry[slot^=2].lock == key || entry[slot^=1].lock == key) { // hit entry += slot; ... } else { // miss slot = -1; }Code: Select all
inline HashEntry * ttProbe(uint64_t key) { HashEntry * entry = hashTable + (key & hashMask); for (int slot = 0; slot < 4; slot++) { if (entry[slot].lock == key) { return &(entry[slot]); } } return 0; }
Secondly, since you seem so bent on being able to easily modify the code in every possible way (a grave violation of the maximum-flexibility-minimum-usefullness principle, btw), what if the distance between the slots isn't always the same. E.g. if I would have 4 slots in a bucket, and want to store in slot, slot^1 (replacing the lowest depth if the new entry is deeper) or slot+2 (the always-replace backup)? Whether you explicitly unroll loops of 2 or 3 iterations is largely a matter of taste, and it is definitely more flexible to explicitly unroll them, as that allows probing of other patterns than just sequential.
That being said, it still doesn't have any bearing on whether introducing a intermediate level of organization in the hash table (multi-entry buckets) is a good idea. The unstructured set of entries, (with the mask seeing to it all primary hits go to a multiple of 4) could also be probed with a loop:
Code: Select all
HashEntry *entry = hashTable + (key & mask);
for(slot=3; slot>=0; slot--) if(entry[slot].lock == key) break;
if(slot >= 0) { // hit
entry += slot;
...
}
Your position seems perilously close to:
* if it is fast and efficient code, it is a 'hackers trick'
* if it is cumbersome and inefficiet code, it is 'software developement'
).