Hi, I recently implemented thmap [1] -- a concurrent trie-hash map, combining the elements of hashing and radix trie. It is supports lock-free lookups and concurrent inserts/deletes. It is designed to be optimal as a general purpose *concurrent* associative array [2][3].
I am going to import it under src/sys/net/npf, so it could be used by NPF. However, there are various other areas in the kernel where it could improve the performance significantly, e.g. in the network stack, 5-tuple mapping to socket (in_pcb.c). While I currently do not have plans to work in those areas, if anybody would like to use it elsewhere, I can import thmap in the src/sys/kern directory. Let me know. Thanks. [1] https://github.com/rmind/thmap [2] http://www.netbsd.org/~rmind/thmap_lookup_80_64bit_keys_intel_4980hq.svg [3] http://www.netbsd.org/~rmind/thmap_insert_80_64bit_keys_intel_4980hq.svg -- Mindaugas
