[quagga-dev 12152] Re: [PATCH 3/4] lib: use trie structure for prefix list matching
paul at jakma.org
Fri Apr 17 18:24:55 BST 2015
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
> 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
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?
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. ;)
Paul Jakma paul at jakma.org @pjakma Key ID: 64A2FF6A
This is National Non-Dairy Creamer Week.
More information about the Quagga-dev