His thesis is more clear: https://sites.google.com/site/yuriyarbitman/Home/de-amortizedcuckoohashing
He did exclude the cost of a resize, but, still... I find the core idea very attractive. We swapped an email and he said: > In general, I would say that a cryptographic hash function will do. > If you want to use a non-cryptographic hash function, then the > question is what provable random properties it has. This is also > discussed in the thesis and in the paper. On Mon, Nov 26, 2018 at 6:17 PM Dave Taht <[email protected]> wrote: > > I had been investigating various hashing schemes for speeding up the > babeld routing protocol daemon, and dealing with annoying bursty cpu > behavior (resizing memory, bursts of packets, thundering herds of > retractions), and, although it's a tough slog of a read, this adds a > queue to cuckoo hashing to good effect in flattening out insertion > time. > > https://arxiv.org/pdf/0903.0391.pdf > > But for all I know it's dependent on angels dancing on saddles mounted > on unicorns. I skip to the graphs for insertion time and go back to > the text for another round... > > "polylog(n)-wise Independent Hash Function". OK, my google-foo fails > me: The authors use sha1, would something lighter weight suit? > > > -- > > 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 _______________________________________________ Bloat mailing list [email protected] https://lists.bufferbloat.net/listinfo/bloat
