From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-lf0-x243.google.com (mail-lf0-x243.google.com [IPv6:2a00:1450:4010:c07::243]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (No client certificate requested) by lists.bufferbloat.net (Postfix) with ESMTPS id C29173B2A3 for ; Fri, 3 Mar 2017 00:50:01 -0500 (EST) Received: by mail-lf0-x243.google.com with SMTP id g70so6231517lfh.3 for ; Thu, 02 Mar 2017 21:50:01 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=mime-version:subject:from:in-reply-to:date:cc :content-transfer-encoding:message-id:references:to; bh=VrVH2CWbQrzOo6NwTw4EhT9ya1BApvJ7XLf2nwx0c8o=; b=OWWZlNCqpFVbIKKDMIUpa3/eT9b1V6PQpIzAeveM0Fe3l9LtnPZO9KwZnmd3BSYKM1 Ts2Sw5SfusZl3nE0ZAZo9UNr3ryYzS+IrTER12J82Ovq6rlTgzMK8edXHU8pYs1lm5op fsTI7M8FGVa5YuyjsqJfEPQJ6N5c9cnAqZOQuZPlRjZPPitwVb0Mu8xh8G/mxLCaQ06o IU7GEA8+01DNI5J6+FFY0h64Dxn3qsXaXlsjBoctbTDIeh97hzLV0VcLPO42Anh2BK4F uuxvIsYI7VAVr7ZTBN6RloqnG77D7SNmcBI7Sm7huGOsMSH9lBjzhO4p3G4dCRDdg3Ny TuAg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:subject:from:in-reply-to:date:cc :content-transfer-encoding:message-id:references:to; bh=VrVH2CWbQrzOo6NwTw4EhT9ya1BApvJ7XLf2nwx0c8o=; b=NGqEJuzoUn80+AeCVOMQGH/sR9DHkE7cazCPcHUz8g6EXkwyUnks+Y+4QjTuNVHJHR a8J1Xsc+/K61IHm+pMkJit/EvWH/u1yRLMImSE532cNKIaY8PUiwz3nFKi+9uPw6kZiO 9pKNMZIzS9m4XZq1QJpFJJip2DP67LmFnJuR8/YzngkuXfzWdsFA0oRnCdPR7OAh8Tpq Zro1wYSqQyE85+5yiwLrgy1ibGnPeyTAjhLFQ7Dd5KzEROMc/n6W7EduzEKb6tTGWy8Y 3QdswPOzMBYVLKF0C/4sr+Ql9RCeTtZ/NZsiBWAiIPDWoTuXeqrMxcdec+NRjQNSBn+V crVA== X-Gm-Message-State: AMke39nmetPQ3VJsDX4IvUf3YI2F4Je1Qvz9Vd3U/OLwUxfc/0M+c7Hxstww+V6uqbkJiw== X-Received: by 10.25.29.211 with SMTP id d202mr255040lfd.152.1488520200654; Thu, 02 Mar 2017 21:50:00 -0800 (PST) Received: from [192.168.100.16] (37-219-206-78.nat.bb.dnainternet.fi. [37.219.206.78]) by smtp.gmail.com with ESMTPSA id h24sm2088889ljb.46.2017.03.02.21.49.59 (version=TLS1 cipher=ECDHE-RSA-AES128-SHA bits=128/128); Thu, 02 Mar 2017 21:50:00 -0800 (PST) Content-Type: text/plain; charset=windows-1252 Mime-Version: 1.0 (Mac OS X Mail 9.3 \(3124\)) From: Jonathan Morton In-Reply-To: Date: Fri, 3 Mar 2017 07:49:57 +0200 Cc: John Yates , "cake@lists.bufferbloat.net" , "lede-dev@lists.infradead.org" , =?windows-1252?Q?Dave_T=E4ht?= Content-Transfer-Encoding: quoted-printable Message-Id: References: <07479F0A-40DD-44E5-B67E-28117C7CF228@gmx.de> <1488400107.3610.1@smtp.autistici.org> <2B251BF1-C965-444D-A831-9981861E453E@gmx.de> <1488484262.16753.0@smtp.autistici.org> <98E899EF-5E66-42CC-88AA-79FA80A4F228@gmail.com> <2D2AE632-75BB-4DDE-B370-0996EFECF14B@gmail.com> To: Eric Luehrsen X-Mailer: Apple Mail (2.3124) Subject: Re: [Cake] [LEDE-DEV] Cake SQM killing my DIR-860L - was: [17.01] Kernel: bump to 4.4.51 X-BeenThere: cake@lists.bufferbloat.net X-Mailman-Version: 2.1.20 Precedence: list List-Id: Cake - FQ_codel the next generation List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Fri, 03 Mar 2017 05:50:02 -0000 > On 3 Mar, 2017, at 07:00, Eric Luehrsen = wrote: >=20 > That's not what I was going for. Agree, it would not be good to depend=20= > on an inferior hash. You mentioned divide as a "cost." So I was=20 > proposing a thought around a "benefit" estimate. If hash collisions = are=20 > 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=92s 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