From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-qk0-x229.google.com (mail-qk0-x229.google.com [IPv6:2607:f8b0:400d:c09::229]) (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 038983B2A4 for ; Sun, 26 Mar 2017 12:00:35 -0400 (EDT) Received: by mail-qk0-x229.google.com with SMTP id d10so16083769qke.1 for ; Sun, 26 Mar 2017 09:00:35 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=mime-version:from:date:message-id:subject:to :content-transfer-encoding; bh=aLr54l52LZBaMk6917zgGx+f6TSLJH9mcP7VItmKwRM=; b=b/WjYrQ9vnPXiB6ppwSBdViUne3PpOVcbwsQAJpb4r6FlPAO6A+UyUSAPo952rHqbF GtuLfh62wwB8mba4lfvm7nRJK8g7rLR9DKoS5GEvAuQBOx9F1HqSPMOsP90juO1AKBm5 o9HTrFG88uFImvmyATXSxTEQtrcYGgrUna7Go0Wr4OvXYwduUx/z78TDRwwXe8Zn+sWq 7RYzqw3CfkCOiBQz/efMzw5YXU9QABVKFbPzdxqKmzPFRckGGpxvHF1UmDHgaG+SPXSk B07jNp7uMjdVXNI341HmbQdyTWC6xZZqMIOqZMiZMWYuXNjqve2U9rdCLrPej+gsONmg 4d9A== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:mime-version:from:date:message-id:subject:to :content-transfer-encoding; bh=aLr54l52LZBaMk6917zgGx+f6TSLJH9mcP7VItmKwRM=; b=ZjNz+bU4QwBi3Nx/b3mOLfOKRpGWlEmytgPvZydy4ZdEnT/jDSxGQyVkPOVz5phlJU Wz8dIXaH2uegFGJUVvM2+6LDTgYEyWWv09uMbfZpbuM50TlTCxc0YU6FhQcJCyWzdgnJ xuJBJdJ57layYdGMY6ceHx4z+fGETijtFqq3LqngYwXYbUcwmcW1RqKaLr2Ra7M0Fobk yuVojmFOaD0f+qS1oY9VCUgP9qvXvTpo/K2IHDi8LwxLnFYUdZZYgzUxfXIR80kjEhHb 6NRWAHpqhbuH+hNd1LSbW8R0w7wxaNoWhueELgiMlrZ6URzLOT3OMTZE0SM24KIH+y24 Loww== X-Gm-Message-State: AFeK/H2/qarLIf9nKrjsB6z+ToF5F/7MzLAlICjUvMjMFuDQ8qAB/xuiUPeHr83zzXeXdg39PTUIWatIx764Fw== X-Received: by 10.55.160.73 with SMTP id j70mr3878174qke.59.1490544035039; Sun, 26 Mar 2017 09:00:35 -0700 (PDT) MIME-Version: 1.0 Received: by 10.12.140.8 with HTTP; Sun, 26 Mar 2017 09:00:34 -0700 (PDT) From: Dave Taht Date: Sun, 26 Mar 2017 09:00:34 -0700 Message-ID: To: Cake List Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: quoted-printable Subject: [Cake] an experiment with an alternate hasher 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: Sun, 26 Mar 2017 16:00:36 -0000 I am trying to see if I can get an adaquate avalanche distribution using a hash of popcount(src),(popcount(dst),srcport,dstport, protocol, seed. popcount is, regrettably, an sse4.2-only instruction, and this version of the assembly routine can actually popcount up to 8 ipv6 addresses in a row, but you typically just pass it 2. I had a great deal of fun writing this tho I haven't got around to actually seeing how good a resulting hash would be! The ipv4 version does both src and dst with a single popcnt. The startup cost to further hash this is pretty insane - 30 cycles in http://burtleburtle.net/bob/hash/spooky.html. Xor? CRC? 00000000004005a0 : 4005a0: 31 c0 xor %eax,%eax 4005a2: 89 f1 mov %esi,%ecx 00000000004005a4 : 4005a4: 48 c1 e0 08 shl $0x8,%rax 4005a8: f3 4c 0f b8 07 popcnt (%rdi),%r8 4005ad: 48 83 c7 10 add $0x10,%rdi 4005b1: 4c 09 c0 or %r8,%rax 4005b4: f3 4c 0f b8 47 f8 popcnt -0x8(%rdi),%r8 4005ba: 4c 01 c0 add %r8,%rax 4005bd: e2 e5 loop 4005a4 4005bf: c3 retq --=20 Dave T=C3=A4ht Let's go make home routers and wifi faster! With better software! http://blog.cerowrt.org