On Sat, Oct 13, 2018 at 2:02 PM Dave Taht <[email protected]> wrote: > > On Sat, Oct 13, 2018 at 5:04 AM Juliusz Chroboczek <[email protected]> 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 _______________________________________________ Babel-users mailing list [email protected] https://alioth-lists.debian.net/cgi-bin/mailman/listinfo/babel-users
