[quagga-dev 12148] Re: [RFC] Improve prefix list loading & matching

Paul Jakma paul at jakma.org
Fri Apr 17 17:57:09 BST 2015

On Mon, 13 Apr 2015, David Lamparter wrote:

> Hi everyone,
> this patch set moves prefix list matching from sequential-walking a 
> linear list to walking down a trie.  This pushes common use cases to 
> O(1); the worst case behaviour (lots of /32s) is still O(n).

> The patch set consists of 2 preparation patches:
> - lib: hide internal prefix list structures
> - lib: straighten out ORF prefix list support
> The actual trie implementation:
> - lib: use trie structure for prefix list matching
>  (not signed-off for merging, needs more documentation, but code is done)
> And finally config load improvements:
> - lib: optimise prefix list setup
> I also have a test tool (for both correctness and performance), have to
> clean that up though.
> Performance for a routeserver setup looks like this:
> - startup config load:  54.44s -> 7.77s  (x7.01)
> - operative:             3.36s -> 2.14s  (x1.57)
>  (latter has rather large stddev, improvement is somewhere between factor
>   x1.5 and x2.0)
> Times are user CPU for the whole of bgpd, replaying a real-world startup.

That's awesome. Nice.

Paul Jakma	paul at jakma.org	@pjakma	Key ID: 64A2FF6A
IBM's original motto:
 	Cogito ergo vendo; vendo ergo sum.

More information about the Quagga-dev mailing list