]> git.puffer.fish Git - mirror/frr.git/commit
lib: use trie structure for prefix list matching
authorDavid Lamparter <equinox@opensourcerouting.org>
Mon, 13 Apr 2015 08:21:36 +0000 (10:21 +0200)
committerDonald Sharp <sharpd@cumulusnetworks.com>
Tue, 3 Nov 2015 13:54:14 +0000 (05:54 -0800)
commit7e111b6b0de44a9d351cdfeda4c674224a65ec3b
tree849687e00fff77c217f49ec3b0bd9f641c3207eb
parentc7da3d50b38b430494465c1ba0d68244bfd16d56
lib: use trie structure for prefix list matching

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

This buys CPU with memory.  Memory usage on an IXP setup with 100k
prefix list entries is an additional 4 MB on top of the 9.5 MB that it
was before.
lib/memtypes.c
lib/plist.c