I'm looking for a fast 64 bit hashing function for hash table lookups. I really only need it for arrays of (unsigned-byte 8). Does anyone know of such a thing? I have been using one of Bob Jenkins' hashes (see http://burtleburtle.net/bob/hash/index.html) that I re-coded in Lisp, but I'm not really getting the performance I want. This is mostly due to my lack of skill of creating optimized Lisp code. Any pointers appreciated. Cheers, Chris Dean
Hi Chris, If you don't find a better solution, please post the code so that we can all throw declare bombs at it until it screams (both for mercy and is really fast). On Jun 5, 2008, at 1:49 PM, Chris Dean wrote: > > > I'm looking for a fast 64 bit hashing function for hash table lookups. > I really only need it for arrays of (unsigned-byte 8). > > Does anyone know of such a thing? > > I have been using one of Bob Jenkins' hashes (see > http://burtleburtle.net/bob/hash/index.html) that I re-coded in Lisp, > but I'm not really getting the performance I want. This is mostly due > to my lack of skill of creating optimized Lisp code. > > Any pointers appreciated. > > Cheers, > Chris Dean > -- Gary Warren King, metabang.com Cell: (413) 559 8738 Fax: (206) 338-4052 gwkkwg on Skype * garethsan on AIM
Gary King <gwking@metabang.com> writes: > If you don't find a better solution, please post the code so that we > can all throw declare bombs at it until it screams (both for mercy > and is really fast). Sure thing. At the moment it is needlessly complex and baroque, but I'll post it if I don't hear of a good solution. Cheers, Chris Dean
Unable to parse email body. Email id is 8183
Martin Simmons <martin@lispworks.com> writes: > You could try an equalp hash-table, but I make no promises about the > efficiency :-) > > What is "fast" will probably depend on the lengths of the arrays and how much > the elements vary. E.g. for random elements, just looking at the first 4 > might be sufficient. I actually need just the hashing function, not a hash-table. Basically the equivalent of sxhash for (array (unsigned-byte 8) (*)) We have a disk based database that uses that 64 bit hash. Similar to the Berkeley DB hash databses. The builtin LispWorks hash-table works great, and I do use equalp hash-tables :). Cheers, Chris Dean
Have you looked at Fowler-Noll-Vo (FNV) hash? http://www.isthe.com/chongo/tech/comp/fnv/index.html >From the "History section": "FNV hashes are designed to be fast while maintaining a low collision rate. The FNV speed allows one to quickly hash lots of data while maintaining a reasonable collision rate. The high dispersion of the FNV hashes makes them well suited for hashing nearly identical strings such as URLs, hostnames, filenames, text, IP addresses, etc. " I don't have a Lisp implementation sitting around, but it's a pretty short, straightforward algo. On Thu, Jun 5, 2008 at 1:32 PM, Chris Dean <ctdean@sokitomi.com> wrote: > > > Martin Simmons <martin@lispworks.com> writes: >> You could try an equalp hash-table, but I make no promises about the >> efficiency :-) >> >> What is "fast" will probably depend on the lengths of the arrays and how much >> the elements vary. E.g. for random elements, just looking at the first 4 >> might be sufficient. > > I actually need just the hashing function, not a hash-table. > Basically the equivalent of sxhash for (array (unsigned-byte 8) (*)) > > We have a disk based database that uses that 64 bit hash. Similar to > the Berkeley DB hash databses. > > The builtin LispWorks hash-table works great, and I do use equalp > hash-tables :). > > Cheers, > Chris Dean > >
"Christopher Brown" <cjbrown102@gmail.com> writes: > Have you looked at Fowler-Noll-Vo (FNV) hash? > http://www.isthe.com/chongo/tech/comp/fnv/index.html That's great, thanks. I'll take a look. Cheers, Chris Dean