Re: Please review: lookup changes

[Andrew Doran <ad%netbsd.org@localhost>]

On Sun, Mar 08, 2020 at 09:22:28PM +0000, Taylor R Campbell wrote:

> Maybe we could use a critbit tree?  It will have cache utilization
> characteristics similar to a red/black tree (fanout is 2 either way),
> but the lookup can be pserialized and each step may be a little
> cheaper computationally.
> 
> https://mumble.net/~campbell/hg/critbit/
> 
> Alternatively, there is rmind's thmap already in tree.

I had a look and this is a really interesting data structure.  I think this
plus a seqlock, and a nice reclamation method would do great.  My only
concern is that single threaded performance should be top notch too because
single component name lookups are often more frequent even than traps and
syscalls put together.  I suppose it's a case of trying it.

Another application I can think of is _lwp_unpark() although the minor
complication there is the radixtree is now used to allocate LIDs too by
scanning for unused slots.

Andrew