From owner-freebsd-net@FreeBSD.ORG Fri Aug 30 23:24:52 2013 Return-Path: Delivered-To: net@freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [8.8.178.115]) (using TLSv1 with cipher ADH-AES256-SHA (256/256 bits)) (No client certificate requested) by hub.freebsd.org (Postfix) with ESMTP id 073825DD; Fri, 30 Aug 2013 23:24:52 +0000 (UTC) (envelope-from asomers@gmail.com) Received: from mail-wi0-x234.google.com (mail-wi0-x234.google.com [IPv6:2a00:1450:400c:c05::234]) (using TLSv1 with cipher ECDHE-RSA-RC4-SHA (128/128 bits)) (No client certificate requested) by mx1.freebsd.org (Postfix) with ESMTPS id E4CF82696; Fri, 30 Aug 2013 23:24:50 +0000 (UTC) Received: by mail-wi0-f180.google.com with SMTP id l12so51060wiv.13 for ; Fri, 30 Aug 2013 16:24:49 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:sender:in-reply-to:references:date:message-id:subject :from:to:cc:content-type; bh=fLDSSp0OfJacufg1SrGhgxfw3yeSmqu3OycbUyvI1ZA=; b=KRjo/9Xxgnx65lbyXYa9mKigS4d3fvR57I0DxqCvHYXuDBwnLoHWg9nceXNgiHfQ4J JM/JU8rs91hA99RANqVMjKjZ3Kx9BbXs4wMjhD5dS720Joy2t5CkKbFikJTXASP2wHcF jlLgAG7pgJHrRNOiKbMXaX2WHPL3jDK19scc9c9kwx+6V2MuRsonjK6Ib1GN8hQ72Llk wIGjzz8g1TBOLfCfzTzFh4uA0HIB6eVf+XBjRjFngyzaOkfDbj62qnQq/SZqW79CwNjq Y6Xv18+B57KceYAY1QEeqlqxhU5m+Fb/98D7vRZCyQRyP0f+trrfZ8+UwEL6ezW891xk 0UxA== MIME-Version: 1.0 X-Received: by 10.180.219.75 with SMTP id pm11mr4283869wic.47.1377905089252; Fri, 30 Aug 2013 16:24:49 -0700 (PDT) Sender: asomers@gmail.com Received: by 10.194.171.35 with HTTP; Fri, 30 Aug 2013 16:24:49 -0700 (PDT) In-Reply-To: References: <521BBD21.4070304@freebsd.org> <521EE8DA.3060107@freebsd.org> <0771FC4F-BCDD-4985-A33F-09951806AD99@barracuda.com> Date: Fri, 30 Aug 2013 17:24:49 -0600 X-Google-Sender-Auth: n5LLHwtvkvGGDB9K70IMsIVL_yo Message-ID: Subject: Re: Flow ID, LACP, and igb From: Alan Somers To: "T.C. Gubatayao" Content-Type: text/plain; charset=ISO-8859-1 Cc: Jack F Vogel , "Justin T. Gibbs" , Andre Oppermann , Alan Somers , "net@freebsd.org" X-BeenThere: freebsd-net@freebsd.org X-Mailman-Version: 2.1.14 Precedence: list List-Id: Networking and TCP/IP with FreeBSD List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Fri, 30 Aug 2013 23:24:52 -0000 On Thu, Aug 29, 2013 at 3:40 PM, T.C. Gubatayao wrote: > On Aug 29, 2013, at 4:21 PM, Alan Somers wrote: > >> They're faster, but even with this change, jenkins_hash is still 6 times >> slower than FNV hash. > > Actually, I think your test isn't accurately simulating memory access, which > might be skewing the results. > > For example, from net/if_lagg.c: > > p = hash32_buf(&eh->ether_shost, ETHER_ADDR_LEN, p); > p = hash32_buf(&eh->ether_dhost, ETHER_ADDR_LEN, p); > > These two calls can't both be aligned, since ETHER_ADDR_LEN is 6 octets. The > same is true for the other hashed fields in the IP and TCP/UDP headers. > Assuming the mbuf data pointer is aligned, the IP addresses and ports are both > on 2-byte alignments (without VLAN or IP options). In your test, they're all > aligned and in the same cache line. > > When I modify the test to simulate an mbuf, lookup3 beats FNV and hash32, and > SipHash is only 2-3 times slower. Indeed, in your latest version FNV and hash32 are significantly slower. It isn't due to alignment issues though; those hashes don't care about alignment because they access data 8 bits at a time. The problem was that Clang was too smart for me. In my version, Clang was computing FNV hash and hash32 entirely at compile time. All the functions did at runtime was return the correct answer. Your mbuf simulation defeats that optimization. I think that your latest version is fairly accurate, and it shows that Jenkins is the fastest when compiled with Clang and when all three layers are hashed. However, FNV is faster when compiled with GCC, or when only one or two layers are hashed. In any case, the difference between FNV and Jenkins is about 4ns/packet, which is about as significant as whether to paint the roof cyan or aquamarine. As far as I'm concerned, FNV still has two major advantages: it's available in stable/9, and it's a drop-in replacement for hash32. Using Jenkins would require refactoring lagg_hashmbuf to copy the hashable fields into a stack buffer. I'm loath to do that, because then I would have to test lagg_hashmbuf with IPv6 and VLAN packets. My network isn't currently setup for those. Using FNV is a simple enough change that I would feel comfortable committing it without testing VLANs and IPv6. We have a three day weekend in my country, but hopefully I'll be able to wrap up my testing on Tuesday. > >> 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. > > Agreed, but this is relatively simple with a buffer on the stack, and does not > require zeroes or padding. See my modified test, attached. > > T.C.