Date: Thu, 29 Aug 2013 14:21:05 -0600 From: Alan Somers <asomers@freebsd.org> To: "T.C. Gubatayao" <tgubatayao@barracuda.com> Cc: Jack F Vogel <jfv@freebsd.org>, "Justin T. Gibbs" <gibbs@freebsd.org>, Andre Oppermann <andre@freebsd.org>, Alan Somers <asomers@freebsd.org>, "net@freebsd.org" <net@freebsd.org> Subject: Re: Flow ID, LACP, and igb Message-ID: <CAOtMX2i5BXqm4_gP67MEmN8szCabp8_QRKfZM0tqFtbEKS31SA@mail.gmail.com> In-Reply-To: <0771FC4F-BCDD-4985-A33F-09951806AD99@barracuda.com> References: <D01A0CB2-B1E3-4F4B-97FA-4C821C0E3FD2@FreeBSD.org> <521BBD21.4070304@freebsd.org> <CAOtMX2jvKGY==t9i-a_8RtMAPH2p1VDj950nMHHouryoz3nbsA@mail.gmail.com> <521EE8DA.3060107@freebsd.org> <BCC2C62D4FE171479E2F1C2593FE508B0BE24383@BN-SCL-MBX03.Cudanet.local> <CAOtMX2h5SGh5eYV50y%2BQB_s367V9iattGU862wwXcONDV%2BTG8g@mail.gmail.com> <0771FC4F-BCDD-4985-A33F-09951806AD99@barracuda.com>
next in thread | previous in thread | raw e-mail | index | archive | help
On Thu, Aug 29, 2013 at 1:33 PM, T.C. Gubatayao <tgubatayao@barracuda.com>wrote:
> On Aug 29, 2013, at 12:45 PM, Alan Somers <asomers@freebsd.org> 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 <sys/hash.h>
> #include <sys/fnv_hash.h>
> #include <sys/time.h>
> -
> -uint32_t jenkins_hash32(const uint32_t *, size_t, uint32_t);
> +#include <string.h>
>
> #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);
>
>
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?CAOtMX2i5BXqm4_gP67MEmN8szCabp8_QRKfZM0tqFtbEKS31SA>