Common hash table implementation
A message that is not in the archive (sent off-list or not yet received): [email protected]
Quoted 6 lines · Andi Kleen
It's a "fuzzy hash", which is a bit different from the normal hash and probably not always appropiate.
It was at one point used in the dcache but then later ripped out again when the data structures changed.
Ahh. I'm not familiar with fuzzy hashes, but I suspected they might not be what I was interested in.
Quoted 7 lines
I would like to see a generic hash abstraction in the spirit of
list.hEspecially if it would NOT use normallist_headsas open hash table heads but instead single pointers for the head [currently some importanthash tables like the inode hash are twice as big as needed because each bucket is two pointers instead of one]
I agree. Hash tables such as inode_hashtable and dentry_hashtable are half as efficient under stress as they would otherwise be, because they use an array of list_heads.
OTOH, I have no objections to using list_heads in other applications where a singly-linked list is all that's needed. Common code is a Good Thing. I'm just commenting specifically on hash table implementations, which tend to be used for really _big_ data structures.
Signature · 10 lines
Brian Watson | "The common people of England... so
Linux Kernel Developer | jealous of their liberty, but like the
Open SSI Clustering Project | common people of most other countries
Compaq Computer Corp | never rightly considering wherein it
Los Angeles, CA | consists..."
| -Adam Smith, Wealth of Nations,
1776
mailto:[email protected]
http://opensource.compaq.com/Quoted 7 lines · Brian J. Watson
Quoted 2 lines · Andi Kleen
hash tables like the inode hash are twice as big as needed because each bucket is two pointers instead of one]
I agree. Hash tables such as
inode_hashtableanddentry_hashtableare half as efficient under stress as they would otherwise be, because they use an array oflist_heads.
Whoops, yes. The buffer_head pprev strategy gives both the double linked list and a table vector of single links, at the expense of a few extra tests.
For a one-size-fits-all hash strategy the question is, double-linked of singled-linked? The advantage of a double linked list for a hash is quick, generic deletion. Using the pprev strategy the disadvantage of double links in the table vector can be eliminated. The main advantage of the single link is space savings both in the table and in the structures. The disadvantage is having to do an extra bucket search on deletion, though this is partially offset by fewer pointer operations to perform insertion or deletion.
It's hard to say which is fastest. It might turn out that the single linked strategy is actually faster, it really depends on typical depth of the buckets. A double-linked list deletion needs to follow two pointers and set two links, the single-linked list only one of each. There's a similar difference for insertion. So the extra overhead of insertion and deletion can be set off against say, three or four iterations of the bucket search loop. If buckets average six to eight elements deep, it's a tie.
A more subtle cost of the double-link approach is the slight extra cache pressure due to the enlarged objects. This cost is incurred continously as the objects are used, it might very well add up to more than the cost of the final list traversal for the delete in the single-linked case.
How about implementing both strategies, using your generic interface to make them look the same? And then seeing which is fastest in practice.
--
Daniel