From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail.mhcomputing.net (master.mhcomputing.net [74.208.46.186]) by dpdk.org (Postfix) with ESMTP id 1BEA3AF87 for ; Tue, 9 Sep 2014 22:38:07 +0200 (CEST) Received: by mail.mhcomputing.net (Postfix, from userid 1000) id A924C80C76D; Tue, 9 Sep 2014 13:42:52 -0700 (PDT) Date: Tue, 9 Sep 2014 13:42:52 -0700 From: Matthew Hall To: "De Lara Guarch, Pablo" Message-ID: <20140909204252.GA11510@mhcomputing.net> References: <20140909103153.GA7969@mhcomputing.net> <59AF69C657FD0841A61C55336867B5B0343EFBBD@IRSMSX103.ger.corp.intel.com> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: User-Agent: Mutt/1.5.23 (2014-03-12) Cc: "dev@dpdk.org" Subject: Re: [dpdk-dev] Defaults for rte_hash X-BeenThere: dev@dpdk.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: patches and discussions about DPDK List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Tue, 09 Sep 2014 20:38:07 -0000 On Tue, Sep 09, 2014 at 11:42:40AM +0000, De Lara Guarch, Pablo wrote: > That 4 is not shifted, so it is actually 4 entries/bucket. Actually, the > maximum number of entries you can use is 16, as bucket will be as big as a > cache line. However, regardless the number of entries, memory size will > remain the same, but using 4 entries/bucket, with 16-byte key, all keys > stored for a bucket will fit in a cache line, so performance looks to be > better in this case (although a non-optimal hash function could lead not to > be able to store all keys, as chances to fill a bucket are higher). Anyway, > for this example, 4 entries/bucket looks a good number to me. So, a general purpose hash usually has some kind of conflict resolution when a bucket is full rather than just tossing out entries. It could be open addressing, chaining, secondary hashing, etc. If I'm putting security indicators into a bucket and the buckets just toss stuff out without warning that's a security problem. Same thing could be true for firewall tables. Also, if we're assuming a 16-byte key, what happens when I want to do matching against www.badness.com or www.this-is-a-really-long-malware-domain.net ? Did anybody have a performant general purpose hash table for DPDK that doesn't have problems with bigger keys or depth issues in a bucket? Matthew.