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. ;)
regards,
--
Paul Jakma [email protected] @pjakma Key ID: 64A2FF6A
Fortune:
This is National Non-Dairy Creamer Week.
_______________________________________________
Quagga-dev mailing list
[email protected]
https://lists.quagga.net/mailman/listinfo/quagga-dev
