On Aug 29, 2013, at 12:45 PM, Alan Somers <asom...@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. 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); _______________________________________________ freebsd-net@freebsd.org mailing list http://lists.freebsd.org/mailman/listinfo/freebsd-net To unsubscribe, send any mail to "freebsd-net-unsubscr...@freebsd.org"