From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-qk0-x22a.google.com (mail-qk0-x22a.google.com [IPv6:2607:f8b0:400d:c09::22a]) (using TLSv1 with cipher RC4-SHA (128/128 bits)) (Client CN "smtp.gmail.com", Issuer "Google Internet Authority G2" (verified OK)) by huchra.bufferbloat.net (Postfix) with ESMTPS id 4D71B21F2E5 for ; Mon, 13 Apr 2015 18:29:06 -0700 (PDT) Received: by qkhg7 with SMTP id g7so211688897qkh.2 for ; Mon, 13 Apr 2015 18:29:05 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:date:message-id:subject:from:to:content-type; bh=al2ZSgD95oUHkkeRkwFpALHizmY71tplt/sAOsUmqy4=; b=BPjJsgft6dVqAz7xietp0lkABsvwUShTe1Xlt+7Vp7FFsPpJnPuBnfmJv2sfcdfvyu HpvyLxy5aYcEI2K7HO1bBDsH10qVTndvoR9eITZorvbfs7ID53izlEShJoAXfx4g7LWc xJR6mi02lMjjoE1JdqbQH93og1uFlQQ10fDIY4pb9MgCdttaKw33G+CjXWcwnWMyHor+ iGe4q/T8pafOx5YLbG2+3kF4HsUKwz3/7d4yKJj4qiiqEzlylAlKGhzGCtUBftBbb0z+ FYP2CigHSBYwuEeFasEoYN0c57taL9yy6B9oXIm5/OlWmPG9kuRjMKInD++q0YXzgJH/ YouA== MIME-Version: 1.0 X-Received: by 10.182.255.195 with SMTP id as3mr14326082obd.56.1428974945722; Mon, 13 Apr 2015 18:29:05 -0700 (PDT) Received: by 10.202.51.66 with HTTP; Mon, 13 Apr 2015 18:29:05 -0700 (PDT) Date: Mon, 13 Apr 2015 18:29:05 -0700 Message-ID: From: Dave Taht To: cake@lists.bufferbloat.net, Razvan Cristian Content-Type: multipart/mixed; boundary=001a1134a6160881ae0513a528fd Subject: [Cake] Possible faster hash algorithm than jenkins attached X-BeenThere: cake@lists.bufferbloat.net X-Mailman-Version: 2.1.13 Precedence: list List-Id: Cake - FQ_codel the next generation List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Tue, 14 Apr 2015 01:29:35 -0000 --001a1134a6160881ae0513a528fd Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: quoted-printable 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 Date: Tue, Mar 24, 2015 at 9:53 AM Subject: dear mr monty carlo To: Paul McKenney so how would you go about trying out a different hash function in the kerne= l? Got this teeny "xxhash" patch from a contributor, who says it=C2=B4s faster than jhash, and the benchmark says it=C5=9B 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=C3=A4ht Let's make wifi fast, less jittery and reliable again! https://plus.google.com/u/0/107942175615993706558/posts/TVX3o84jjmb --=20 Dave T=C3=A4ht Open Networking needs **Open Source Hardware** https://plus.google.com/u/0/+EricRaymond/posts/JqxCe2pFr67 --001a1134a6160881ae0513a528fd Content-Type: text/x-patch; charset=US-ASCII; name="3.14-xxhash-fq_codel.patch" Content-Disposition: attachment; filename="3.14-xxhash-fq_codel.patch" Content-Transfer-Encoding: base64 X-Attachment-Id: f_i7njg0wo0 ZGlmZiAtLWdpdCBhL2luY2x1ZGUvbGludXgveHhoYXNoLmggYi9pbmNsdWRlL2xpbnV4L3h4aGFz aC5oCm5ldyBmaWxlIG1vZGUgMTAwNjQ0CmluZGV4IDAwMDAwMDAuLjljZTk3OTkKLS0tIC9kZXYv bnVsbAorKysgYi9pbmNsdWRlL2xpbnV4L3h4aGFzaC5oCkBAIC0wLDAgKzEsNzEgQEAKKyNpZm5k ZWYgX0xJTlVYX1hYSEFTSF9ICisjZGVmaW5lIF9MSU5VWF9YWEhBU0hfSAorCisvKgorICogeHhI YXNoIC0gRmFzdCBIYXNoIGFsZ29yaXRobQorICogQ29weXJpZ2h0IChDKSAyMDEyLTIwMTQsIFlh bm4gQ29sbGV0LgorICogQlNEIDItQ2xhdXNlIExpY2Vuc2UgKGh0dHA6Ly93d3cub3BlbnNvdXJj ZS5vcmcvbGljZW5zZXMvYnNkLWxpY2Vuc2UucGhwKQorICoKKyAqIFJlZGlzdHJpYnV0aW9uIGFu ZCB1c2UgaW4gc291cmNlIGFuZCBiaW5hcnkgZm9ybXMsIHdpdGggb3Igd2l0aG91dAorICogbW9k aWZpY2F0aW9uLCBhcmUgcGVybWl0dGVkIHByb3ZpZGVkIHRoYXQgdGhlIGZvbGxvd2luZyBjb25k aXRpb25zIGFyZQorICogbWV0OgorICoKKyAqICogUmVkaXN0cmlidXRpb25zIG9mIHNvdXJjZSBj b2RlIG11c3QgcmV0YWluIHRoZSBhYm92ZSBjb3B5cmlnaHQKKyAqIG5vdGljZSwgdGhpcyBsaXN0 IG9mIGNvbmRpdGlvbnMgYW5kIHRoZSBmb2xsb3dpbmcgZGlzY2xhaW1lci4KKyAqICogUmVkaXN0 cmlidXRpb25zIGluIGJpbmFyeSBmb3JtIG11c3QgcmVwcm9kdWNlIHRoZSBhYm92ZQorICogY29w eXJpZ2h0IG5vdGljZSwgdGhpcyBsaXN0IG9mIGNvbmRpdGlvbnMgYW5kIHRoZSBmb2xsb3dpbmcg ZGlzY2xhaW1lcgorICogaW4gdGhlIGRvY3VtZW50YXRpb24gYW5kL29yIG90aGVyIG1hdGVyaWFs cyBwcm92aWRlZCB3aXRoIHRoZQorICogZGlzdHJpYnV0aW9uLgorICoKKyAqIFRISVMgU09GVFdB UkUgSVMgUFJPVklERUQgQlkgVEhFIENPUFlSSUdIVCBIT0xERVJTIEFORCBDT05UUklCVVRPUlMK KyAqICJBUyBJUyIgQU5EIEFOWSBFWFBSRVNTIE9SIElNUExJRUQgV0FSUkFOVElFUywgSU5DTFVE SU5HLCBCVVQgTk9UCisgKiBMSU1JVEVEIFRPLCBUSEUgSU1QTElFRCBXQVJSQU5USUVTIE9GIE1F UkNIQU5UQUJJTElUWSBBTkQgRklUTkVTUyBGT1IKKyAqIEEgUEFSVElDVUxBUiBQVVJQT1NFIEFS RSBESVNDTEFJTUVELiBJTiBOTyBFVkVOVCBTSEFMTCBUSEUgQ09QWVJJR0hUCisgKiBPV05FUiBP UiBDT05UUklCVVRPUlMgQkUgTElBQkxFIEZPUiBBTlkgRElSRUNULCBJTkRJUkVDVCwgSU5DSURF TlRBTCwKKyAqIFNQRUNJQUwsIEVYRU1QTEFSWSwgT1IgQ09OU0VRVUVOVElBTCBEQU1BR0VTIChJ TkNMVURJTkcsIEJVVCBOT1QKKyAqIExJTUlURUQgVE8sIFBST0NVUkVNRU5UIE9GIFNVQlNUSVRV VEUgR09PRFMgT1IgU0VSVklDRVM7IExPU1MgT0YgVVNFLAorICogREFUQSwgT1IgUFJPRklUUzsg T1IgQlVTSU5FU1MgSU5URVJSVVBUSU9OKSBIT1dFVkVSIENBVVNFRCBBTkQgT04gQU5ZCisgKiBU SEVPUlkgT0YgTElBQklMSVRZLCBXSEVUSEVSIElOIENPTlRSQUNULCBTVFJJQ1QgTElBQklMSVRZ LCBPUiBUT1JUCisgKiAoSU5DTFVESU5HIE5FR0xJR0VOQ0UgT1IgT1RIRVJXSVNFKSBBUklTSU5H IElOIEFOWSBXQVkgT1VUIE9GIFRIRSBVU0UKKyAqIE9GIFRISVMgU09GVFdBUkUsIEVWRU4gSUYg QURWSVNFRCBPRiBUSEUgUE9TU0lCSUxJVFkgT0YgU1VDSCBEQU1BR0UuCisgKgorICogWW91IGNh biBjb250YWN0IHRoZSBhdXRob3IgYXQgOgorICogLSB4eEhhc2ggc291cmNlIHJlcG9zaXRvcnkg OiBodHRwOi8vY29kZS5nb29nbGUuY29tL3AveHhoYXNoLworICogICAtIHB1YmxpYyBkaXNjdXNz aW9uIGJvYXJkIDogaHR0cHM6Ly9ncm91cHMuZ29vZ2xlLmNvbS9mb3J1bS8jIWZvcnVtL2x6NGMK KyAqICAgKi8KKworI2luY2x1ZGUgPGxpbnV4L2JpdG9wcy5oPgorI2luY2x1ZGUgPGxpbnV4L3Vu YWxpZ25lZC9wYWNrZWRfc3RydWN0Lmg+CisKKyNkZWZpbmUgUFJJTUUzMl8xIDI2NTQ0MzU3NjFV CisjZGVmaW5lIFBSSU1FMzJfMiAyMjQ2ODIyNTE5VQorI2RlZmluZSBQUklNRTMyXzMgMzI2NjQ4 OTkxN1UKKyNkZWZpbmUgUFJJTUUzMl80IDY2ODI2NTI2M1UKKyNkZWZpbmUgUFJJTUUzMl81IDM3 NDc2MTM5M1UKKworLyogeHhoYXNoXzN3b3JkcyAtIGhhc2ggZXhhY3RseSAzIHdvcmRzICovCitz dGF0aWMgaW5saW5lIHUzMiB4eGhhc2hfM3dvcmRzKHUzMiBhLCB1MzIgYiwgdTMyIGMsIHUzMiBz ZWVkKQoreworCXUzMiBoMzI7CisKKwloMzIgPSBzZWVkICsgUFJJTUUzMl81OworCisJaDMyICs9 IDEyOworCisJaDMyICs9IGEgKiBQUklNRTMyXzM7CisJaDMyID0gcm9sMzIoaDMyLCAxNykgKiBQ UklNRTMyXzQ7CisJaDMyICs9IGIgKiBQUklNRTMyXzM7CisJaDMyID0gcm9sMzIoaDMyLCAxNykg KiBQUklNRTMyXzQ7CisJaDMyICs9IGMgKiBQUklNRTMyXzM7CisJaDMyID0gcm9sMzIoaDMyLCAx NykgKiBQUklNRTMyXzQ7CisKKwloMzIgXj0gaDMyID4+IDE1OworCWgzMiAqPSBQUklNRTMyXzI7 CisJaDMyIF49IGgzMiA+PiAxMzsKKwloMzIgKj0gUFJJTUUzMl8zOworCWgzMiBePSBoMzIgPj4g MTY7CisKKwlyZXR1cm4gaDMyOworfQorCisjZW5kaWYJCQkJLyogX0xJTlVYX1hYSEFTSF9IICov CmRpZmYgLS1naXQgYS9uZXQvc2NoZWQvc2NoX2ZxX2NvZGVsLmMgYi9uZXQvc2NoZWQvc2NoX2Zx X2NvZGVsLmMKaW5kZXggYmE1YmM5Mi4uZTAwMDczMyAxMDA2NDQKLS0tIGEvbmV0L3NjaGVkL3Nj aF9mcV9jb2RlbC5jCisrKyBiL25ldC9zY2hlZC9zY2hfZnFfY29kZWwuYwpAQCAtMTksNiArMTks NyBAQAogI2luY2x1ZGUgPGxpbnV4L2luaXQuaD4KICNpbmNsdWRlIDxsaW51eC9za2J1ZmYuaD4K ICNpbmNsdWRlIDxsaW51eC9qaGFzaC5oPgorI2luY2x1ZGUgPGxpbnV4L3h4aGFzaC5oPgogI2lu Y2x1ZGUgPGxpbnV4L3NsYWIuaD4KICNpbmNsdWRlIDxsaW51eC92bWFsbG9jLmg+CiAjaW5jbHVk ZSA8bmV0L25ldGxpbmsuaD4KQEAgLTc0LDcgKzc1LDcgQEAgc3RhdGljIHVuc2lnbmVkIGludCBm cV9jb2RlbF9oYXNoKGNvbnN0IHN0cnVjdCBmcV9jb2RlbF9zY2hlZF9kYXRhICpxLAogCXVuc2ln bmVkIGludCBoYXNoOwogCiAJc2tiX2Zsb3dfZGlzc2VjdChza2IsICZrZXlzKTsKLQloYXNoID0g amhhc2hfM3dvcmRzKChfX2ZvcmNlIHUzMilrZXlzLmRzdCwKKwloYXNoID0geHhoYXNoXzN3b3Jk cygoX19mb3JjZSB1MzIpa2V5cy5kc3QsCiAJCQkgICAgKF9fZm9yY2UgdTMyKWtleXMuc3JjIF4g a2V5cy5pcF9wcm90bywKIAkJCSAgICAoX19mb3JjZSB1MzIpa2V5cy5wb3J0cywgcS0+cGVydHVy YmF0aW9uKTsKIAlyZXR1cm4gKCh1NjQpaGFzaCAqIHEtPmZsb3dzX2NudCkgPj4gMzI7Cg== --001a1134a6160881ae0513a528fd--