[quagga-dev 12148] Re: [RFC] Improve prefix list loading & matching
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