From: Stephen Hemminger <stephen@networkplumber.org>
To: Dave Taht <dave.taht@gmail.com>
Cc: bloat <bloat@lists.bufferbloat.net>, codel@lists.bufferbloat.net
Subject: Re: [Bloat] [Codel] found another good use for a queue today, possibly
Date: Mon, 26 Nov 2018 20:08:05 -0800 [thread overview]
Message-ID: <20181126200805.1393645e@xeon-e3> (raw)
In-Reply-To: <CAA93jw6HBms4JMBgH1kSNLCiR2uvGzNBtzL920Cr=RqzGZ2-BQ@mail.gmail.com>
On Mon, 26 Nov 2018 18:17:32 -0800
Dave Taht <dave.taht@gmail.com> 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?
>
>
The current favorite in DPDK land seems to be Cuckoo hashing.
It has better cache behavior than typical chaining.
next prev parent reply other threads:[~2018-11-27 4:08 UTC|newest]
Thread overview: 5+ messages / expand[flat|nested] mbox.gz Atom feed top
2018-11-27 2:17 [Bloat] " Dave Taht
2018-11-27 4:08 ` Stephen Hemminger [this message]
2018-11-27 4:17 ` [Bloat] [Codel] " Jonathan Morton
2018-11-29 4:37 ` Dave Taht
2018-11-29 17:17 ` [Bloat] " Dave Taht
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
List information: https://lists.bufferbloat.net/postorius/lists/bloat.lists.bufferbloat.net/
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=20181126200805.1393645e@xeon-e3 \
--to=stephen@networkplumber.org \
--cc=bloat@lists.bufferbloat.net \
--cc=codel@lists.bufferbloat.net \
--cc=dave.taht@gmail.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox