[Babel-users] profiling at 10,000 routes

[Dave Taht]

On Sat, Oct 13, 2018 at 2:02 PM Dave Taht <dave.taht at gmail.com> wrote:
>
> On Sat, Oct 13, 2018 at 5:04 AM Juliusz Chroboczek <jch at irif.fr> wrote:
> >
> > >  92.52     18.17    18.17 38243948     0.00     0.00  find_resend
> >
> > Thanks, that's helpful.
> >
> > > fix with binary search? timer wheel? ?
> >
> > Binary heap?
> >
>
> rbtree. My plan is to sort the bits, hammer them into submission, then
> jump up and down on the 4 hotspots
> until they go away in my usual sloppy POC. 64k routes or bust!
>
> https://github.com/dtaht/babeld/issues/31
>
> Finding a rbtree library we both like would be problematic, as I lean
> black (inline C include folding the exta bit into the pointer, linux
> rbtree is nicer), and you'd probably lean red (like the freebsd
> implementation? libavl?)
>
> Hmm... this?
>
> https://github.com/fmela/libdict

I was not particularly happy with the 3 pointer overhead of a full
rbtree in these cases. So, reaching
back into prehistory, I went looking at various tries.
"Hardware/Software IP Lookups with Incremental Updates"
was good reading:

http://cseweb.ucsd.edu/~varghese/PAPERS/ccr2004.pdf

with some example code here: https://github.com/xnhp0320/prefix_lookup_mc
>
>
> > -- Juliusz
>
>
>
> --
>
> Dave Täht
> CTO, TekLibre, LLC
> http://www.teklibre.com
> Tel: 1-831-205-9740



-- 

Dave Täht
CTO, TekLibre, LLC
http://www.teklibre.com
Tel: 1-831-205-9740