Common hash table implementation
A couple of days ago, I was thinking about a common hash table implementation, ala include/linux/list.h. Then I came across include/linux/ghash.h, and thought that someone's already done it. After that I noticed the copyright line said 1997, and a quick check in cscope showed that nobody's including it.
Does anyone know if this file is worth studying and working with? I have to wonder if nobody's using it after four years.
Does anyone see a problem with a common hash table implementation? I've implemented a few hash tables from scratch for our clustering work, and it's starting to get a little old. Something easy to use like list.h would be a lot nicer.
Signature · 9 lines
Brian Watson | "The common people of England... so
Linux Kernel Developer | jealous of their liberty, but like the
Open SSI Clustering Lab | 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/We've got a fairly nice hash table interface in BitKeeper that we'd be happy to provide under the GPL. I've always thought it would be cool to have it in the kernel, we use it everywhere.
http://bitmover.com:8888//home/bk/bugfixes/src/src/mdbm
will let you browse it. The general interface is gdbm() like and there are both file backed and memory backed versions. It was designed to be useful in small and large configs, you can get a hash into 128 bytes if I recall correctly.
Quoted 29 lines · Brian J. Watson
A couple of days ago, I was thinking about a common hash table implementation, ala
include/linux/list.h. Then I came acrossinclude/linux/ghash.h, and thought that someone's already done it. After that I noticed the copyright line said 1997, and a quick check in cscope showed that nobody's including it.Does anyone know if this file is worth studying and working with? I have to wonder if nobody's using it after four years.
Does anyone see a problem with a common hash table implementation? I've implemented a few hash tables from scratch for our clustering work, and it's starting to get a little old. Something easy to use like
list.hwould be a lot nicer.Signature · 14 lines
Brian Watson | "The common people of England... so Linux Kernel Developer | jealous of their liberty, but like the Open SSI Clustering Lab | 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/ - To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to [email protected] More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Signature · 2 lines
--- Larry McVoy lm at bitmover.com http://www.bitmover.com/lm
In message <[email protected]> you write:
Quoted 5 lines
We've got a fairly nice hash table interface in BitKeeper that we'd be happy to provide under the GPL. I've always thought it would be cool to have it in the kernel, we use it everywhere.
Hmmm.... cf. tdb on sourceforge. Although having code to be mmap or read/write backed is overkill in the kernel.
Interestingly, there's an unused, undocumented hash table interface in include/linux/ghash.h.
Cheers,
Rusty.
--
Premature optmztion is rt of all evl. --DK
Quoted 2 lines · Rusty Russell
Interestingly, there's an unused, undocumented hash table interface in
include/linux/ghash.h.
Yikes:
#define DEF_HASH(LINKAGE,NAME,HASHSIZE,TYPE,PTRS,KEYTYPE,KEY,KEYCMP,KEYEQ,HASHFN)\
--
Daniel
Quoted 6 lines · Brian J. Watson
A couple of days ago, I was thinking about a common hash table implementation, ala
include/linux/list.h. Then I came acrossinclude/linux/ghash.h, and thought that someone's already done it. After that I noticed the copyright line said 1997, and a quick check in cscope showed that nobody's including it.
Quoted 7 lines
Does anyone know if this file is worth studying and working with? I have to wonder if nobody's using it after four years.
Does anyone see a problem with a common hash table implementation? I've implemented a few hash tables from scratch for our clustering work, and it's starting to get a little old. Something easy to use like
list.hwould be a lot nicer.
You may look at
which is essentially a automatic generator of code for static hash tables like those from linux/mm/
Richard.
--
Richard Guenther <[email protected]>
WWW: http://www.tat.physik.uni-tuebingen.de/~rguenth/
The GLAME Project: http://www.glame.de/
Quoted 5 lines · Larry McVoy
We've got a fairly nice hash table interface in BitKeeper that we'd be happy to provide under the GPL. I've always thought it would be cool to have it in the kernel, we use it everywhere.
Oh goodie, lots of new hash functions to test :-) I'll pass the interesting ones on to the guys with the serious hash-testing equipment.
I think the original poster was thinking more along the lines of a generic insertion, deletion and lookup interface, which we are now doing in an almost-generic way in a few places. Once place that is distinctly un-generic is the buffer hash, for no good reason that I can see. This would be a good starting point for a demonstration.
--
Daniel
Quoted 7 lines · Daniel Phillips
Quoted 5 lines · Larry McVoy
We've got a fairly nice hash table interface in BitKeeper that we'd be happy to provide under the GPL. I've always thought it would be cool to have it in the kernel, we use it everywhere.
Thanks, Larry. Your hashing functions are much more sophisticated than the simple modulo operator I've been using for hashing by inode number.
Quoted 6 lines
I think the original poster was thinking more along the lines of a generic insertion, deletion and lookup interface, which we are now doing in an almost-generic way in a few places. Once place that is distinctly un-generic is the buffer hash, for no good reason that I can see. This would be a good starting point for a demonstration.
Daniel's correct. I'm hashing function agnostic, but would like some common code to simplify the management of a hash table.
Richard Guenther sent the following link to his own common hashing code, which makes nice use of pseudo-templates:
A few things I would consider changing are:
- ditching the pprev pointer
- encapsulating the next pointer inside a struct hash_head_##FOOBAR
- stripping out the hard-coded hashing function, and allowing the user to provide their own
All the backslashes offend my aesthetic sensibility, but the preprocessor provides no alternative. ;)
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 11 lines · Brian J. Watson
Quoted 6 lines · Daniel Phillips
Quoted 5 lines · Larry McVoy
We've got a fairly nice hash table interface in BitKeeper that we'd be happy to provide under the GPL. I've always thought it would be cool to have it in the kernel, we use it everywhere.
Thanks, Larry. Your hashing functions are much more sophisticated than the simple modulo operator I've been using for hashing by inode number.
Yes, I tested almost all of them to see how well they worked my directory index application. There are really only two criterea:
1) How random is the hash
2) How efficient is it
My testing was hardly what you would call rigorous. Basically, what I do is hash a lot of very unrandom strings and see how uniform the resulting hash bucket distribution is. The *only* function from Larry's set that did well on the randomness side is the linear congruential hash - it did nearly as well as my dx_hack_hash.
Surprisingly, at least to me, the CRC32 turned in an extremely variable performance. With a small number of buckets (say 100) it did ok, but with a larger numbers it showed a very lumpy distribution. Yes, this is way too imprecise a way of describing what happened and I should take a closer look at it. I don't have the mathematical background to be really sure about this, but I suspect CRC32 isn't optimized at all for randomness - it's optimized for detecting bit errors and has good properties with respect to neighbouring bits, properties that are no use at all to a randomizing funciton. Anyway, I wasn't all that unhappy to see CRC32 turn in a poor performance for two reasons: a) the 1K xor table would represent a 25% increase of the indexing code and b) hashing through the table eats an extra 1K of precious L1 cache.
The linear congruential hash from Larry's set and my dx_hack_hash share a common characteristic: they both munge each character against a pseudorandom sequence. In Larry's hash it's a linear congruential sequence, and in my case it's a feedback shift register. In addition, I use a multiply to spread the effect of each character over a broader range of bits.
Larry's hash doesn't do this and you can see right away that strings that vary only in the last character aren't going to be distributed very randomly. It might work a little better with the hashing step spelled this way:
- ((h) = 0x63c63cd9*(h) + 0x9c39c33d + (c))
+ ((h) = 0x63c63cd9*(h + (c)) + 0x9c39c33d)
I haven't tried this, but I will.
There are people out there who know a lot more about analyzing hash functions than I do, and I have their names somewhere in my mailbox. I'll go look them up soon and submit for proper testing the whole batch of functions that have been suggested to me over the last few months. By the way, in case you haven't already deduced this, this stuff is really time consuming.
[...]
Quoted 9 lines
Richard Guenther sent the following link to his own common hashing code, which makes nice use of pseudo-templates:
http://cvs.sourceforge.net/cgi-bin/viewcvs.cgi/~checkout~/glame/glame
/src/include/hash.h?rev=1.5&content-type=text/plainA few things I would consider changing are:
- ditching the pprev pointer
Yes, you want to use the generic list macros there.
Quoted 1 line
- encapsulating the next pointer inside a struct hash_head_##FOOBAR
I think the generic list macros give you that for free.
Quoted 2 lines
- stripping out the hard-coded hashing function, and allowing the user to provide their own
Naturally. And trying to reduce the size of the macros. It's not that easy to get stuff that has dozens of lines ending with "\" into the kernel. You might have better luck just generalizing a few short sets of common operations used in hashes, and showing examples of how you'd use them to rewrite some of the existing hash code. Obviously, the new, improved approach has to be no less efficient than the current way of doing things.
Quoted 2 lines
All the backslashes offend my aesthetic sensibility, but the preprocessor provides no alternative. ;)
It's hard to argue against using inlines there. It's true that there are a lot of generalizations you just can't do with inlines, but so what? What matters is how efficient the generated code is and to a lesser extent, how readable the source is. You could make that source quite a bit more readable with a few *small* macros and some inline functions. Suggestion: express the bucket probe as an inline, compute the hash outside and pass it in. Then you can wrap the whole thing up in a really short macro.
--
Daniel
Quoted 5 lines · Daniel Phillips
Quoted 4 lines · Brian J. Watson
Daniel Phillips wrote:
Richard Guenther sent the following link to his own common hashing code, which makes nice use of pseudo-templates:
Quoted 8 lines
Quoted 6 lines
http://cvs.sourceforge.net/cgi-bin/viewcvs.cgi/~checkout~/glame/glame
/src/include/hash.h?rev=1.5&content-type=text/plainA few things I would consider changing are:
- ditching the pprev pointer
Yes, you want to use the generic list macros there.
You get one-pointer size hash table entries and generic deletion from it.
Quoted 3 lines
Quoted 1 line
- encapsulating the next pointer inside a struct hash_head_##FOOBAR
I think the generic list macros give you that for free.
Umm, if you use such, you get lists.h style type-casting stuff which doesnt have a nice interface as
my_type *hash_find_my()
instead you'd get
hash_dead_my *hash_find_my()
which you'll have to cast with something like the list_entry() macro.
Quoted 2 lines
Quoted 2 lines
- stripping out the hard-coded hashing function, and allowing the user to provide their own
Ok, if the two expressions are not generic enough.
Quoted 7 lines
Naturally. And trying to reduce the size of the macros. It's not that easy to get stuff that has dozens of lines ending with "\" into the kernel. You might have better luck just generalizing a few short sets of common operations used in hashes, and showing examples of how you'd use them to rewrite some of the existing hash code. Obviously, the new, improved approach has to be no less efficient than the current way of doing things.
All those \s are to encapsulate the whole thing into the template-style macro - not that I like this, but I cannot see an alternative.
Quoted 11 lines
Quoted 2 lines
All the backslashes offend my aesthetic sensibility, but the preprocessor provides no alternative. ;)
It's hard to argue against using inlines there. It's true that there are a lot of generalizations you just can't do with inlines, but so what? What matters is how efficient the generated code is and to a lesser extent, how readable the source is. You could make that source quite a bit more readable with a few *small* macros and some inline functions. Suggestion: express the bucket probe as an inline, compute the hash outside and pass it in. Then you can wrap the whole thing up in a really short macro.
Ok, with an approach like the list.h one (struct hash_head) you'd get there, but of course without automatic type conversion (and safety). Of course, if you can tidy up the macro without changing to use a hash_head structure, I'd be glad to see how :)
Richard.
--
Richard Guenther <[email protected]>
WWW: http://www.tat.physik.uni-tuebingen.de/~rguenth/
The GLAME Project: http://www.glame.de/
Quoted 9 lines · Richard Guenther
Quoted 8 lines · Daniel Phillips
Quoted 7 lines · Brian J. Watson
Daniel Phillips wrote:
Richard Guenther sent the following link to his own common hashing code, which makes nice use of pseudo-templates:http://cvs.sourceforge.net/cgi-bin/viewcvs.cgi/~checkout~/glame/g
lame /src/include/hash.h?rev=1.5&content-type=text/plain
Quoted 8 lines
Quoted 5 lines
Quoted 3 lines
A few things I would consider changing are:
- ditching the pprev pointer
Yes, you want to use the generic list macros there.
You get one-pointer size hash table entries and generic deletion from it.
Having thought about it a little more, I don't see why the symmetric double link (i.e., like the page hash, not like the buffer hash) couldn't be used with single-pointer tables, using similar tests for NULL in insertion and deletion.
Quoted 7 lines
Quoted 4 lines
Quoted 2 lines
- encapsulating the next pointer inside a struct
hash_head_##FOOBARI think the generic list macros give you that for free.
Umm, if you use such, you get
lists.hstyle type-casting stuff which doesnt have a nice interface as
You could wrap the final product in inlines with internal typecasts. As you pointed out, C just doesn't have templates.
Quoted 11 lines
Quoted 7 lines
Naturally. And trying to reduce the size of the macros. It's not that easy to get stuff that has dozens of lines ending with "\" into the kernel. You might have better luck just generalizing a few short sets of common operations used in hashes, and showing examples of how you'd use them to rewrite some of the existing hash code. Obviously, the new, improved approach has to be no less efficient than the current way of doing things.
All those \s are to encapsulate the whole thing into the template-style macro - not that I like this, but I cannot see an alternative.
An obvious alternative is to leave things the way they are. I've noticed that this is a stance Linus typically adopts for improvements that aren't clearly better in every way ;-)
--
Daniel
Quoted 2 lines · Daniel Phillips
1) How random is the hash
2) How efficient is it
The hash is not the only part to consider for performance. The rest of the code is important as well. The code I pointed you to has been really carefully tuned for performance. And it can be made to be MP safe, SGI did that and managed to get 455,000 random fetches/second on an 8 way R4400 (each of these is about the same as the original Pentium at 150Mhz).
Signature · 2 lines
--- Larry McVoy lm at bitmover.com http://www.bitmover.com/lm
Quoted 8 lines · Daniel Phillips
Yes, I tested almost all of them to see how well they worked my directory index application. There are really only two criterea:
1) How random is the hash
2) How efficient is itMy testing was hardly what you would call rigorous. Basically, what I do is hash a lot of very unrandom strings and see how uniform the
Actually, to measure the randomness you need to measure the randomness of
the output in the face of non-random input. Most well constructed hash functions perform well when the strings are random, however real world data (e.g. directory contntent) is not random at all.
Efficiency should measure both space and time resources. If it should work in a multithreaded situation then another level of complexity is added.
--
Eyal Lebedinsky ([email protected]) <http://samba.anu.edu.au/eyal/>
Quoted 7 lines · Larry McVoy
Quoted 2 lines · Daniel Phillips
1) How random is the hash
2) How efficient is itThe hash is not the only part to consider for performance. The rest of the code is important as well. The code I pointed you to has been really carefully tuned for performance.
Yes, I can see that. The linear congruential hash will be faster than the CRC32 on most modern machines, where we have fast multiplies vs multi-cycle table access.
If it's true that the CRC32 is actually less random as well, I'd consider dropping the others and just going with the linear congruential hash.
Quoted 4 lines
And it can be made to be MP
safe, SGI did that and managed to get 455,000 random fetches/second on an 8 way R4400 (each of these is about the same as the original Pentium at 150Mhz).
Did I mention that your linear congruential hash rated among the best of all I've tested? It's possible it might be further improved along the lines I suggested. I'll try this pretty soon.
--
Daniel
Quoted 7 lines · Eyal Lebedinsky
Quoted 6 lines · Daniel Phillips
Yes, I tested almost all of them to see how well they worked my directory index application. There are really only two criterea:
1) How random is the hash
2) How efficient is it
Quoted 6 lines
Quoted 3 lines
My testing was hardly what you would call rigorous. Basically, what I do is hash a lot of very unrandom strings and see how uniform the
Actually, to measure the randomness you need to measure the randomness of the output in the face of non-random input.
This is exactly what I do.
Quoted 3 lines
Most well constructed
hash functions perform well when the strings are random, however real world data (e.g. directory contntent) is not random at all.
I think you meant to say there, "even many poorly constructed hash functions perform well when..."
Quoted 3 lines
Efficiency should measure both space and time resources. If it should work in a multithreaded situation then another level of complexity is added.
Sure, I could have added "how big is it". For me, that's just another kind of efficiency. Writing the code so it's reentrant is just good practice. There is no excuse whatsoever for not doing that for something simple like a hash function, even if you yourself never expect to run two copies concurrently.
--
Daniel