From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-lf0-x22f.google.com (mail-lf0-x22f.google.com [IPv6:2a00:1450:4010:c07::22f]) (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 E340F3B29E for ; Thu, 2 Mar 2017 18:55:31 -0500 (EST) Received: by mail-lf0-x22f.google.com with SMTP id a6so40817087lfa.0 for ; Thu, 02 Mar 2017 15:55:31 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=mime-version:sender:in-reply-to:references:from:date:message-id :subject:to:cc:content-transfer-encoding; bh=8BX5NOazVRELwwOVw68gKZxEfaGFe6VhowM/+Slo7pE=; b=ZDHEYimI7jRWjdUsk1uFw/x+gzHjKzoBvKhiWj3MFz9XExNMhknXWMRty+o8lICtL6 +EML2dTd0zP+fBKn8ypjz7vSzMJIZBkoSoO3DqtnMOySOnIc6BEte8mU7Z9GPaJCGQeo vz9vE8ra9eUm+OXpvWf/p/Td9t4wsnKl/qZXAs1ZnNm9HnbjzFgSy2rBncZD8IJ1RBar hMDjCX4JgZhRL2M8634A0kakP02oZ7mcGRzT7R5y6gq1/YOaOhx+GVB5sJk8Lrlq51yQ N0wxS5NPHXcqVUJAMlhz6+OeVD7mBYPCTs4++4u9jUpNLLgpNgDsYff6RyiXfeE2upwy H8IA== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:sender:in-reply-to:references:from :date:message-id:subject:to:cc:content-transfer-encoding; bh=8BX5NOazVRELwwOVw68gKZxEfaGFe6VhowM/+Slo7pE=; b=XzAB/2gvsDAHL3pxwlF9OvAAs2lA/aVVbHRRodqyP1wFDy/PeJ0O8ywYeZ6LdxcEL8 Cg7ou4AoIAzeykYMisEmXuXbULfX37AMTpedYZqXxYNhuHUXlwLuNh3XITj1P8Iotarv d7Z29Q1Q/NEXAXH5FZrpRN4aESygUvPEPnuNMg5M4/ydbivu/mAZAqIuaBMVtQBhL1mg VyY6WklWILfKi4bSJfdUmLdP7MkLh3gMF+ICRfSbEujRDiC4hcuPcLUsw0CeMdsa6Wik W8xPBEc8IWJmFZ+Eks70SQO7JRz9IbBypG7/BVAPgHGAyIBXYcTFf7fJLIu540OVu/ZX CG/w== X-Gm-Message-State: AMke39mMsCfwWhvAaNt+l2Qs6bGpnKM6UQ3B8Jtcl6rwAp5f3pLJyQJ3W7Cj7QPpabmyNO8IsOVRUYEkWNrbaw== X-Received: by 10.25.160.132 with SMTP id j126mr4800946lfe.24.1488498930502; Thu, 02 Mar 2017 15:55:30 -0800 (PST) MIME-Version: 1.0 Sender: john.yates.sheets@gmail.com Received: by 10.25.205.193 with HTTP; Thu, 2 Mar 2017 15:55:29 -0800 (PST) In-Reply-To: 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> From: John Yates Date: Thu, 2 Mar 2017 18:55:29 -0500 X-Google-Sender-Auth: nJIrQNIYStlp0pEigNLv5n3qvkQ Message-ID: To: =?UTF-8?Q?Dave_T=C3=A4ht?= Cc: lede-dev@lists.infradead.org, cake@lists.bufferbloat.net Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: quoted-printable 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: Thu, 02 Mar 2017 23:55:32 -0000 On Thu, Mar 2, 2017 at 4:10 PM, Dave T=C3=A4ht wrote: > As for speeding up hashing, I've been looking over various algorithms to > do that for years now, I'm open to suggestions. The fastest new ones > tend to depend on co-processor support. The fastest I've seen relies on > the CRC32 instruction which is only in some intel platforms. This is an area where I have a fair amount of experience. It is a misconception that CRC is a good hash function. It is good at detecting errors but has poor avalanche performance. What are the requirements for this hashing function? - How much data is being hashed? (I would guess a limited number of bytes rather than an entire packet payload.) - What is the typical number of hash table buckets? Must it be a power of 2? Or are you willing to make it a prime number? Assuming you can afford a 1KB lookup table I would suggest the SBox hash in figure four of this article: http://papa.bretmulvey.com/post/124028832958/hash-functions The virtue of a prime number of buckets is that when you mod your 32-bit hash value to get a bucket index you harvest _all_ of the entropy in the hash, not just the entropy in the bits you preserve. /john