On 03/13/2015 08:09 PM, Luke Gorrie wrote: > I'm looking for a suitable FFI hashtable to use with LuaJIT. The use case I > have in mind is hashtables with fixed-size keys and values (C structs of > 1-64 bytes fixed at creation time). Up to around one million elements per > table. I'd like a short and simple implementation. > > I am currently investigating khash and looking at adapting its API to the > FFI: > https://github.com/attractivechaos/klib/pull/45 > > Any hot tips? > > In a perfect world I would actually love something that supports key->value > lookups, in-order traversals, and longest-prefix matching. I say this just > in case anybody knows of such a unicorn. I'm okay with focusing on > key->value lookups for the moment. Looks good, but I don't like your memcmp equal check. With fixed size keys you need to exploit the fact that the keys are aligned and fixed size. so you need to unroll memcmp with this information into wordsize cmp ops. My attempts to unroll memcmp on perfect hashes was 50% - 2000% faster. yes, 200x faster. See http://blogs.perl.org/users/rurban/2014/08/perfect-hashes-and-faster-than-memcmp.html -- Reini
Attachment:
signature.asc
Description: OpenPGP digital signature