Negative dentries, 20 years later

Posted Apr 12, 2022 20:54 UTC (Tue) by cesarb (subscriber, #6266)
In reply to: Negative dentries, 20 years later by NYKevin
Parent article: Negative dentries, 20 years later

> We're not trying to figure out whether the bucket is occupied, we're trying to find its nearest occupied neighbors so that we can find an empty range of buckets.

Actually, now that I thought about it better, not even that might be necessary. A hash bucket itself is already a "range" of directory entries, since it being empty means that none of the entries hashing to that bucket are present. Since the number of hash buckets is limited, that could be enough to limit the number of negative "ranges".

to post comments

Negative dentries, 20 years later

Posted Apr 12, 2022 21:09 UTC (Tue) by NYKevin (subscriber, #129325) [Link]

Yes, you can do that, but it buys you less than you think:

* Under open addressing (linear/quadratic probing, cuckoo hashing, etc.), the number of buckets must be greater than the number of dentries, and for performance reasons, it should be significantly greater.
* Under closed addressing (separate chaining), the number of dentries cannot be much more than a small (constant) multiple of the number of buckets, or performance suffers.

In both cases: Assuming the hash function is a quasi-random oracle, the probability of a hash collision should be quite low, and should become lower as the hash table grows (so that the average number of collisions that each dentry suffers remains bounded above). A cached negative dentry range consisting of a single hash bucket will only help you for other dentries that would have collided with that bucket, which should not be very many in practice, or else the hash function is bad.