Date: Thu, 29 Aug 2013 12:33:58 -0700 From: "T.C. Gubatayao" <tgubatayao@barracuda.com> To: Alan Somers <asomers@freebsd.org> Cc: Jack F Vogel <jfv@freebsd.org>, "Justin T. Gibbs" <gibbs@freebsd.org>, Andre Oppermann <andre@freebsd.org>, "net@freebsd.org" <net@freebsd.org> Subject: Re: Flow ID, LACP, and igb Message-ID: <0771FC4F-BCDD-4985-A33F-09951806AD99@barracuda.com> In-Reply-To: <CAOtMX2h5SGh5eYV50y%2BQB_s367V9iattGU862wwXcONDV%2BTG8g@mail.gmail.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>
next in thread | previous in thread | raw e-mail | index | archive | help
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 t=
hem.
> 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 faste=
r
> code than gcc.
I didn't realize that you were testing incremental hashing with 4 and 6 byt=
e
keys.
There might be advantages to conditionally filling out a contiguous key
and then performing the hash on that. You could guarantee key alignment, f=
or =20
one, and this would benefit the hashes which perform word-sized reads.=20
Based on my quick tests, lookup3 and SipHash improve significantly.
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>
=20
#define ITERATIONS 100000000
=20
typedef uint32_t do_hash_t(void);
=20
-// Pad the MACs with 0s because jenkins_hash operates on 32-bit inputs
-const uint8_t ether_shost[] =3D {181, 16, 73, 9, 219, 22, 0, 0};
-const uint8_t ether_dhost[] =3D {69, 170, 210, 111, 24, 120, 0, 0};
+const uint8_t ether_shost[] =3D {181, 16, 73, 9, 219, 22};
+const uint8_t ether_dhost[] =3D {69, 170, 210, 111, 24, 120};
+const uint8_t ether_hosts[] =3D { 181, 16, 73, 9, 219, 22,
+ 69, 170, 210, 111, 24, 120 };
const struct in_addr ip_src =3D {.s_addr =3D 1329258245};
const struct in_addr ip_dst =3D {.s_addr =3D 1319097119};
+const struct in_addr ips[2] =3D { { .s_addr =3D 1329258245 },
+ { .s_addr =3D 1319097119 } };
const uint32_t ports =3D 3132895450;
const uint8_t sipkey[16] =3D {7, 239, 255, 43, 68, 53, 56, 225,
98, 81, 177, 80, 92, 235, 242, 39};
=20
+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);
}
=20
+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;
=20
- SipHash24_Init(&ctx);
- SipHash_SetKey(&ctx, sipkey);
+ init_key(&key);
=20
- 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);
}
=20
/*
@@ -83,19 +95,11 @@
*/
uint32_t do_jenkins(void)
{
- /* Jenkins hash does not recommend any specific initializer */
- uint32_t p =3D FNV1_32_INIT;
+ struct key key;
=20
- /*=20
- * jenkins_hash uses 32-bit inputs, so we need to present the MACs =
as
- * arrays of 2 32-bit values
- */
- p =3D jenkins_hash32((uint32_t*)ether_shost, 2, p);
- p =3D jenkins_hash32((uint32_t*)ether_dhost, 2, p);
- p =3D jenkins_hash32((uint32_t*)&ip_src, sizeof(struct in_addr) / 4=
, p);
- p =3D jenkins_hash32((uint32_t*)&ip_dst, sizeof(struct in_addr) / 4=
, p);
- p =3D jenkins_hash32(&ports, sizeof(ports) / 4, p);
- return (p);
+ init_key(&key);
+
+ return (jenkins_hash(&key, sizeof(key), FNV1_32_INIT));
}
=20
=20
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 *);
=20
-#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);
=20
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?0771FC4F-BCDD-4985-A33F-09951806AD99>