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.
regards,
--
Paul Jakma [email protected] @pjakma Key ID: 64A2FF6A
Fortune:
IBM's original motto:
Cogito ergo vendo; vendo ergo sum.
_______________________________________________
Quagga-dev mailing list
[email protected]
https://lists.quagga.net/mailman/listinfo/quagga-dev
