> > This is mostly theoretical. Most hash tables are badly sized and have
> > often bad hashing algorithms that tend to cause long linear list.
>
> So fix the sizing and use a proper hash algorithm. Indeed, it's more
> difficult if sizing is hard.
>
> I'm not against trees, but I like to see proper reasoning to choose
> one above the other. Trees execute log(n) compare functions for any
> operation on it. If your dataset is large, that is something which can
> really hurt, compared to average single hash computation plus a single
> compare for properly sized hash tables.
>
> > It is also almost impossible to resize the tables easily.
>
> Yes, that is a major drawback.
This is a major reason for this. it is a first baby
step in moving in a direction where we can reseize the name cache
and hopefully eventually the vnode pool, and to better be able
to deal with sane vnode recycling.
>
> > > Is it just to be able to grow the cache without extra work?
> > >
> >
> > AFAIK the whole work was done to make the cache more sane. The current
> > version is just insane enough that Bob was crying, shouting and playing
> > with red wine bottles during c2k9.
>
> That's not enough reason to change the data structure. Again, there
> can be good reasons, but choosing trees for sets where in-order
> iteration is not needed should be validated. Not just by a gut
> feeling, but by measurememnts or analysis of implementations.
>
And this is not "gut feeling" - we were measuring kernel and make
build namecache hits, and /usr/bin/time to build at c2k9 with this diff and
with the old layer. At this point - no difference in performance.
(which is important. we don't want to slow things down)
-Bob
