[quagga-dev 12152] Re: [PATCH 3/4] lib: use trie structure for prefix list matching

Paul Jakma paul at jakma.org
Fri Apr 17 18:24:55 BST 2015

On Mon, 13 Apr 2015, David Lamparter wrote:

> Prefix lists were implemented with a simple linear list that is scanned
> sequentially.  This is, of course, extremely inefficient as it scales by
> O(n).  This patch adds a trie-ish data structure that allows quickly
> descending based on the prefix.
> Note that the trie structure used here is designed for real-world use,
> hence it uses a relatively crude fixed-size bytewise table instead of
> some fancy balancing scheme.  It is quite cacheline efficient.
> Using real-world routeserver prefix lists, matching against a fulltable
> dump:
> entries   before     after    factor
>   9103   63.8s      .0124s   5142x
>    772    4.52s     .0101s    445.3x
>     86     .445s    .0098s     45.51x
>      7     .0379s   .0099s      3.834x
>      2     .0136s   .0095s      1.440x
>      1     .0084s   .0095s       .879x

Nice speedups.

One thing, maybe stick the trie in a different file, and put a generic 
interface over it. We already have a binary trie in lib/table, be nice 
they use the same thing. Indeed, you could even use lib/table for this? 
Why not?

Also, the bucketing thing in this trie is sort of like a fixed-bucket 
B-tree, but without balancing. Maybe one day it should become a b-tree.

And that raises the question, is this bucketed tree correct for plist 
addresses data? If so, should lib/table use this? If not, why is the 
distribution of plist prefixes different from route prefixes?

As you were asking for comments. ;)

Paul Jakma	paul at jakma.org	@pjakma	Key ID: 64A2FF6A
This is National Non-Dairy Creamer Week.

More information about the Quagga-dev mailing list