On Mon, May 23, 2011 at 02:05:53PM +0100, Stuart Henderson wrote:
> On 2011/05/21 00:19, Ariane van der Steldt wrote:
> > I suspect that the PF state table is mostly lookups, therefor AVL would
> > improve performance there. That said without having looked at the code
> > though.
>
> Lots of writes too, but in normal conditions the majority are to
> existing states rather than insert/delete. However (and this is
> usually the time when performance really matters) when under
> attack you might have a huge number of states to insert.
Write to existing states are not important as long as they do not
change the key (and they do not, is my understanding). But that latter
point you mention could be major consideration. The more localized
updates of R&B trees cause less cache trashing as well.
I always liked R&B trees and their approach of keeping things
reasoanbly well-balanced.
As to a macro based implementation versus a function bad one, that is
a different matter, imo. Both trees can be implemented either way.
-Otto
