Re: Concurrent trie-hash map

[Kengo NAKAHARA <k-nakahara%iij.ad.jp@localhost>]

Hi,

On 2018/10/17 5:00, Mindaugas Rasiukevicius wrote:
> 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.

If it is imported to src/sys/kern, I want use it to re-implement
sys/netinet/ip_flow.c::ipflowtable. However, I don't have enough time to
do it right now...


> [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

Wow, excellent scaling! :)


Thanks,

-- 
//////////////////////////////////////////////////////////////////////
Internet Initiative Japan Inc.

Device Engineering Section,
IoT Platform Development Department,
Network Division,
Technology Unit

Kengo NAKAHARA <k-nakahara%iij.ad.jp@localhost>