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. Cheers / Feedback welcome, -David _______________________________________________ Quagga-dev mailing list [email protected] https://lists.quagga.net/mailman/listinfo/quagga-dev
