From owner-freebsd-net@FreeBSD.ORG Thu Aug 29 20:21:07 2013 Return-Path: Delivered-To: net@freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2001:1900:2254:206a::19:1]) (using TLSv1 with cipher ADH-AES256-SHA (256/256 bits)) (No client certificate requested) by hub.freebsd.org (Postfix) with ESMTP id 95BE64C6; Thu, 29 Aug 2013 20:21:07 +0000 (UTC) (envelope-from asomers@gmail.com) Received: from mail-qa0-x233.google.com (mail-qa0-x233.google.com [IPv6:2607:f8b0:400d:c00::233]) (using TLSv1 with cipher ECDHE-RSA-RC4-SHA (128/128 bits)) (No client certificate requested) by mx1.freebsd.org (Postfix) with ESMTPS id 0BE372692; Thu, 29 Aug 2013 20:21:06 +0000 (UTC) Received: by mail-qa0-f51.google.com with SMTP id bv4so702370qab.3 for ; Thu, 29 Aug 2013 13:21:06 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:sender:in-reply-to:references:date:message-id:subject :from:to:cc:content-type; bh=5vxxH+s3gd/HOVTD7ikX0bfmGwV4VP/RsWHW2nelBqo=; b=Ua8CzKrkq1z18X/uhwiFm3S99kiuGvJFR165oDmrXTdpTL/us6QrL4Yr6/hTzV7RsT IMH9dBMwTLcEvodj5xNhV6Rp6x9rWV55sZ374X4e6L7GoZlM7ruFbRg/cJY9l/v5uyv2 hGTweZ8ZRh19qnHLauxqgyDHkPLfEJWkiNhQ+h+qt014cffuvkL4e5bKsVPVpc0vl7qg 1aaoIuo6MG0t+Vxno8UOjgZSBybrBxUFnDSGTvtSVPybEbVbhJpYQV2Ce71g0Jv9ekrd 3bvDuMq4QwaWcgmG6k7mHAzFM6aOOrrZEworY91Wa/dn/WgcglF/Xws7C5OlIi8R+tl0 DjZQ== MIME-Version: 1.0 X-Received: by 10.224.23.134 with SMTP id r6mr7207108qab.34.1377807666112; Thu, 29 Aug 2013 13:21:06 -0700 (PDT) Sender: asomers@gmail.com Received: by 10.49.39.101 with HTTP; Thu, 29 Aug 2013 13:21:05 -0700 (PDT) In-Reply-To: <0771FC4F-BCDD-4985-A33F-09951806AD99@barracuda.com> References: <521BBD21.4070304@freebsd.org> <521EE8DA.3060107@freebsd.org> <0771FC4F-BCDD-4985-A33F-09951806AD99@barracuda.com> Date: Thu, 29 Aug 2013 14:21:05 -0600 X-Google-Sender-Auth: tD5HdcWsW6On3TITBCf8wMaZt7c Message-ID: Subject: Re: Flow ID, LACP, and igb From: Alan Somers To: "T.C. Gubatayao" Content-Type: text/plain; charset=ISO-8859-1 X-Content-Filtered-By: Mailman/MimeDel 2.1.14 Cc: Jack F Vogel , "Justin T. Gibbs" , Andre Oppermann , Alan Somers , "net@freebsd.org" X-BeenThere: freebsd-net@freebsd.org X-Mailman-Version: 2.1.14 Precedence: list List-Id: Networking and TCP/IP with FreeBSD List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Thu, 29 Aug 2013 20:21:07 -0000 On Thu, Aug 29, 2013 at 1:33 PM, T.C. Gubatayao wrote: > On Aug 29, 2013, at 12:45 PM, Alan Somers wrote: > > > I pulled all four hash functions out into userland and microbenchmarked > them. > > The upshot is that hash32 and fnv_hash are the fastest, jenkins_hash is > > slower, and siphash24 is the slowest. Also, Clang resulted in much > faster > > code than gcc. > > I didn't realize that you were testing incremental hashing with 4 and 6 > byte > keys. > > There might be advantages to conditionally filling out a contiguous key > and then performing the hash on that. You could guarantee key alignment, > for > one, and this would benefit the hashes which perform word-sized reads. > > Based on my quick tests, lookup3 and SipHash improve significantly. > They're faster, but even with this change, jenkins_hash is still 6 times slower than FNV hash. Also, your technique of copying the hashable fields into a separate buffer would need modification to work with different types of packet and different LAGG_F_HASH[234] flags. Because different packets have different hashable fields, struct key would need to be expanded to include the vlan tag, IPV6 addresses, and IPv6 flowid. lagg_hashmbuf would then have to zero the unused fields. In any case, that's not going to make Jenkins and SipHash24 more likely to beat FNV. > > T.C. > > diff -u a/lagg_hash.c b/lagg_hash.c > --- a/lagg_hash.c 2013-08-29 14:21:17.255307349 -0400 > +++ b/lagg_hash.c 2013-08-29 15:16:31.135653259 -0400 > @@ -7,22 +7,30 @@ > #include > #include > #include > - > -uint32_t jenkins_hash32(const uint32_t *, size_t, uint32_t); > +#include > > #define ITERATIONS 100000000 > > typedef uint32_t do_hash_t(void); > > -// Pad the MACs with 0s because jenkins_hash operates on 32-bit inputs > -const uint8_t ether_shost[] = {181, 16, 73, 9, 219, 22, 0, 0}; > -const uint8_t ether_dhost[] = {69, 170, 210, 111, 24, 120, 0, 0}; > +const uint8_t ether_shost[] = {181, 16, 73, 9, 219, 22}; > +const uint8_t ether_dhost[] = {69, 170, 210, 111, 24, 120}; > +const uint8_t ether_hosts[] = { 181, 16, 73, 9, 219, 22, > + 69, 170, 210, 111, 24, 120 }; > const struct in_addr ip_src = {.s_addr = 1329258245}; > const struct in_addr ip_dst = {.s_addr = 1319097119}; > +const struct in_addr ips[2] = { { .s_addr = 1329258245 }, > + { .s_addr = 1319097119 } }; > const uint32_t ports = 3132895450; > const uint8_t sipkey[16] = {7, 239, 255, 43, 68, 53, 56, 225, > 98, 81, 177, 80, 92, 235, 242, 39}; > > +struct key { > + uint8_t ether_hosts[12]; > + struct in_addr ips[2]; > + uint16_t ports[2]; > +} __attribute__((packed)); > + > /* > * Simulate how lagg_hashmbuf uses FNV hash for a TCP/IP packet > * No VLAN tagging > @@ -58,6 +66,15 @@ > return (p); > } > > +static __inline init_key(struct key *key) > +{ > + > + /* Simulate copying the info out of the mbuf. */ > + memcpy(key->ether_hosts, ether_hosts, sizeof(ether_hosts)); > + memcpy(key->ips, ips, sizeof(ips)); > + memcpy(key->ports, &ports, sizeof(ports)); > +} > + > /* > * Simulate how lagg_hashmbuf would use siphash24 for a TCP/IP packet > * No VLAN tagging > @@ -65,16 +82,11 @@ > uint32_t do_siphash24(void) > { > SIPHASH_CTX ctx; > + struct key key; > > - SipHash24_Init(&ctx); > - SipHash_SetKey(&ctx, sipkey); > + init_key(&key); > > - SipHash_Update(&ctx, ether_shost, 6); > - SipHash_Update(&ctx, ether_dhost, 6); > - SipHash_Update(&ctx, &ip_src, sizeof(struct in_addr)); > - SipHash_Update(&ctx, &ip_dst, sizeof(struct in_addr)); > - SipHash_Update(&ctx, &ports, sizeof(ports)); > - return (SipHash_End(&ctx) & 0xFFFFFFFF); > + return (SipHash24(&ctx, sipkey, &key, sizeof(key)) & 0xFFFFFFFF); > } > > /* > @@ -83,19 +95,11 @@ > */ > uint32_t do_jenkins(void) > { > - /* Jenkins hash does not recommend any specific initializer */ > - uint32_t p = FNV1_32_INIT; > + struct key key; > > - /* > - * jenkins_hash uses 32-bit inputs, so we need to present the MACs > as > - * arrays of 2 32-bit values > - */ > - p = jenkins_hash32((uint32_t*)ether_shost, 2, p); > - p = jenkins_hash32((uint32_t*)ether_dhost, 2, p); > - p = jenkins_hash32((uint32_t*)&ip_src, sizeof(struct in_addr) / 4, > p); > - p = jenkins_hash32((uint32_t*)&ip_dst, sizeof(struct in_addr) / 4, > p); > - p = jenkins_hash32(&ports, sizeof(ports) / 4, p); > - return (p); > + init_key(&key); > + > + return (jenkins_hash(&key, sizeof(key), FNV1_32_INIT)); > } > > > diff -u a/siphash.h b/siphash.h > --- a/siphash.h 2013-08-29 14:21:21.851306417 -0400 > +++ b/siphash.h 2013-08-29 14:26:44.470240137 -0400 > @@ -73,8 +73,8 @@ > void SipHash_Final(void *, SIPHASH_CTX *); > uint64_t SipHash_End(SIPHASH_CTX *); > > -#define SipHash24(x, y, z, i) SipHashX((x), 2, 4, (y), (z), (i)); > -#define SipHash48(x, y, z, i) SipHashX((x), 4, 8, (y), (z), (i)); > +#define SipHash24(x, y, z, i) SipHashX((x), 2, 4, (y), (z), (i)) > +#define SipHash48(x, y, z, i) SipHashX((x), 4, 8, (y), (z), (i)) > uint64_t SipHashX(SIPHASH_CTX *, int, int, const uint8_t [16], const void > *, > size_t); > >