[Cake] Possible faster hash algorithm than jenkins attached

[Dave Taht <dave.taht@gmail.com>]

[-- Attachment #1: Type: text/plain, Size: 1446 bytes --]

According to razvan (the author of this patch)

"The final distribution across buckets seems to be at least as good as
that of the jenkins hash.

I'll keep looking into making other improvements to fq_codel.

I wanted to let you know I haven't given up on this. Thank you for
your support."

Another kvetch of the current hashing process I have is the ipaddr[0]
^ ipaddr[1] ^ ipaddr[2] ^ ipaddr[3] in prehash of ipv6.

But really, measuring,  and profiling, makes more sense before
proceeding far down this path.

---------- Forwarded message ----------
From: Dave Taht <dave.taht@gmail.com>
Date: Tue, Mar 24, 2015 at 9:53 AM
Subject: dear mr monty carlo
To: Paul McKenney <paulmck@linux.vnet.ibm.com>


so how would you go about trying out a different hash function in the kernel?

Got this teeny "xxhash" patch from a contributor, who says it´s faster
than jhash, and the benchmark says itś  gooder than jhash - and is too
shy to submit it for mainline kernel devs.

https://code.google.com/p/xxhash/

I'll slam it into my tree, but I imagine there are more comprehensive
ways to abuse and evaluate it on your side of the house....

--
Dave Täht
Let's make wifi fast, less jittery and reliable again!

https://plus.google.com/u/0/107942175615993706558/posts/TVX3o84jjmb


-- 
Dave Täht
Open Networking needs **Open Source Hardware**

https://plus.google.com/u/0/+EricRaymond/posts/JqxCe2pFr67

[-- Attachment #2: 3.14-xxhash-fq_codel.patch --]
[-- Type: text/x-patch, Size: 3358 bytes --]

diff --git a/include/linux/xxhash.h b/include/linux/xxhash.h
new file mode 100644
index 0000000..9ce9799
--- /dev/null
+++ b/include/linux/xxhash.h
@@ -0,0 +1,71 @@
+#ifndef _LINUX_XXHASH_H
+#define _LINUX_XXHASH_H
+
+/*
+ * xxHash - Fast Hash algorithm
+ * Copyright (C) 2012-2014, Yann Collet.
+ * BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions are
+ * met:
+ *
+ * * Redistributions of source code must retain the above copyright
+ * notice, this list of conditions and the following disclaimer.
+ * * Redistributions in binary form must reproduce the above
+ * copyright notice, this list of conditions and the following disclaimer
+ * in the documentation and/or other materials provided with the
+ * distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+ * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+ * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+ * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
+ * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+ * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
+ * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+ * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+ * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ *
+ * You can contact the author at :
+ * - xxHash source repository : http://code.google.com/p/xxhash/
+ *   - public discussion board : https://groups.google.com/forum/#!forum/lz4c
+ *   */
+
+#include <linux/bitops.h>
+#include <linux/unaligned/packed_struct.h>
+
+#define PRIME32_1 2654435761U
+#define PRIME32_2 2246822519U
+#define PRIME32_3 3266489917U
+#define PRIME32_4 668265263U
+#define PRIME32_5 374761393U
+
+/* xxhash_3words - hash exactly 3 words */
+static inline u32 xxhash_3words(u32 a, u32 b, u32 c, u32 seed)
+{
+	u32 h32;
+
+	h32 = seed + PRIME32_5;
+
+	h32 += 12;
+
+	h32 += a * PRIME32_3;
+	h32 = rol32(h32, 17) * PRIME32_4;
+	h32 += b * PRIME32_3;
+	h32 = rol32(h32, 17) * PRIME32_4;
+	h32 += c * PRIME32_3;
+	h32 = rol32(h32, 17) * PRIME32_4;
+
+	h32 ^= h32 >> 15;
+	h32 *= PRIME32_2;
+	h32 ^= h32 >> 13;
+	h32 *= PRIME32_3;
+	h32 ^= h32 >> 16;
+
+	return h32;
+}
+
+#endif				/* _LINUX_XXHASH_H */
diff --git a/net/sched/sch_fq_codel.c b/net/sched/sch_fq_codel.c
index ba5bc92..e000733 100644
--- a/net/sched/sch_fq_codel.c
+++ b/net/sched/sch_fq_codel.c
@@ -19,6 +19,7 @@
 #include <linux/init.h>
 #include <linux/skbuff.h>
 #include <linux/jhash.h>
+#include <linux/xxhash.h>
 #include <linux/slab.h>
 #include <linux/vmalloc.h>
 #include <net/netlink.h>
@@ -74,7 +75,7 @@ static unsigned int fq_codel_hash(const struct fq_codel_sched_data *q,
 	unsigned int hash;
 
 	skb_flow_dissect(skb, &keys);
-	hash = jhash_3words((__force u32)keys.dst,
+	hash = xxhash_3words((__force u32)keys.dst,
 			    (__force u32)keys.src ^ keys.ip_proto,
 			    (__force u32)keys.ports, q->perturbation);
 	return ((u64)hash * q->flows_cnt) >> 32;