Cake - FQ_codel the next generation
 help / color / mirror / Atom feed
From: Jonathan Morton <chromatix99@gmail.com>
To: Eric Luehrsen <ericluehrsen@hotmail.com>
Cc: "John Yates" <john@yates-sheets.org>,
	"cake@lists.bufferbloat.net" <cake@lists.bufferbloat.net>,
	"lede-dev@lists.infradead.org" <lede-dev@lists.infradead.org>,
	"Dave Täht" <dave@taht.net>
Subject: Re: [Cake] [LEDE-DEV] Cake SQM killing my DIR-860L - was: [17.01] Kernel: bump to 4.4.51
Date: Fri, 3 Mar 2017 07:49:57 +0200	[thread overview]
Message-ID: <D59F3712-415F-4DB7-A18E-1E55C1461723@gmail.com> (raw)
In-Reply-To: <DM5PR11MB15644BBFA60A0C7CEA041CF9CC2B0@DM5PR11MB1564.namprd11.prod.outlook.com>


> On 3 Mar, 2017, at 07:00, Eric Luehrsen <ericluehrsen@hotmail.com> wrote:
> 
> That's not what I was going for. Agree, it would not be good to depend 
> on an inferior hash. You mentioned divide as a "cost." So I was 
> proposing a thought around a "benefit" estimate. If hash collisions are 
> not as important (or are they), then what is "benefit / cost?"

The computational cost of one divide is not the only consideration I have in mind.

Cake’s set-associative hash is fundamentally predicated on the number of hash buckets *not* being prime, as it requires further decomposing the hash into a major and minor part when a collision is detected.  The minor part is then iterated to try to locate a matching or free bucket.

This is considerably easier to do and reason about when everything is a power of two.  Then, modulus is a masking operation, and divide is a shift, either of which can be done in one cycle flat.

AFAIK, however, the main CPU cost of the hash function in Cake is not the hash itself, but the packet dissection required to obtain the data it operates on.  This is something a profile would shed more light on.

 - Jonathan Morton


  reply	other threads:[~2017-03-03  5:50 UTC|newest]

Thread overview: 14+ messages / expand[flat|nested]  mbox.gz  Atom feed  top
     [not found] <e955b05f85fea5661cfe306be0a28250@inventati.org>
     [not found] ` <07479F0A-40DD-44E5-B67E-28117C7CF228@gmx.de>
     [not found]   ` <1488400107.3610.1@smtp.autistici.org>
     [not found]     ` <2B251BF1-C965-444D-A831-9981861E453E@gmx.de>
     [not found]       ` <1488484262.16753.0@smtp.autistici.org>
2017-03-02 21:10         ` Dave Täht
2017-03-02 23:16           ` John Yates
2017-03-03  0:00             ` Jonathan Morton
2017-03-02 23:55           ` John Yates
2017-03-03  0:02             ` Jonathan Morton
2017-03-03  4:31               ` Eric Luehrsen
2017-03-03  4:35                 ` Jonathan Morton
2017-03-03  5:00                   ` Eric Luehrsen
2017-03-03  5:49                     ` Jonathan Morton [this message]
2017-03-03  6:21                       ` Dave Taht
2017-03-06 13:30                         ` Benjamin Cronce
2017-03-06 14:44                           ` Jonathan Morton
2017-03-06 18:08                             ` Benjamin Cronce
2017-03-06 18:46                               ` Jonathan Morton

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/cake.lists.bufferbloat.net/

* Reply using the --to, --cc, and --in-reply-to
  switches of git-send-email(1):

  git send-email \
    --in-reply-to=D59F3712-415F-4DB7-A18E-1E55C1461723@gmail.com \
    --to=chromatix99@gmail.com \
    --cc=cake@lists.bufferbloat.net \
    --cc=dave@taht.net \
    --cc=ericluehrsen@hotmail.com \
    --cc=john@yates-sheets.org \
    --cc=lede-dev@lists.infradead.org \
    /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