From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-wi0-f181.google.com (mail-wi0-f181.google.com [209.85.212.181]) by dpdk.org (Postfix) with ESMTP id 65DED9E7 for ; Thu, 9 Jul 2015 01:25:00 +0200 (CEST) Received: by widjy10 with SMTP id jy10so230131935wid.1 for ; Wed, 08 Jul 2015 16:25:00 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:from:to:cc:subject:date:message-id:organization :user-agent:in-reply-to:references:mime-version :content-transfer-encoding:content-type; bh=69krW5rvnAupdQqAxDoUlupIyOXJLrwisn6b7oqzGN8=; b=djOLd8BWQ7LPa4G0ZnqKfhNcGc4YiXT1SsgGeRQ7XJ9hOm51EwqXZ6dgIFgfsF1xVt hD5ShDjLnnqKqpriqWdsx3miNc7jzo9IKMDrdLNIxVZriq8lKRo8XUbR5u1XxyzVr1Rz 3KVuZxLa4UENDMh1WnuLIOcbl47xDZII1JHwcDyynIQsQnwe6utj+zZh+bxMzHaGwUin A22zwu0ehhXQO3AO1sS2Q/1WaI8QBNjWpptH8H5K6cLUd3u34OvJnhBYVGFZfH0u4z57 MWzWe8GGqNyIKmUGCyfi0AAYSoGoxkZ5ycJiEhqzofhs+9IRpw+MUsVcffBD87nKTq3U qTwQ== X-Gm-Message-State: ALoCoQnapr5JgwMUHhdNdsel9gSKoibsHWtFMAG5EWzaqV21A51j48uKZMmCKJ7BuvCKfSgoZ71D X-Received: by 10.194.23.36 with SMTP id j4mr24428652wjf.105.1436397900252; Wed, 08 Jul 2015 16:25:00 -0700 (PDT) Received: from xps13.localnet (136-92-190-109.dsl.ovh.fr. [109.190.92.136]) by smtp.gmail.com with ESMTPSA id z9sm5218199wiv.9.2015.07.08.16.24.58 (version=TLSv1.2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Wed, 08 Jul 2015 16:24:59 -0700 (PDT) From: Thomas Monjalon To: bruce.richardson@intel.com Date: Thu, 09 Jul 2015 01:23:54 +0200 Message-ID: <49531942.DIgM7i8NQ4@xps13> Organization: 6WIND User-Agent: KMail/4.14.8 (Linux/4.0.4-2-ARCH; KDE/4.14.8; x86_64; ; ) In-Reply-To: <1435530330-10132-1-git-send-email-pablo.de.lara.guarch@intel.com> References: <1435269919-7007-1-git-send-email-pablo.de.lara.guarch@intel.com> <1435530330-10132-1-git-send-email-pablo.de.lara.guarch@intel.com> MIME-Version: 1.0 Content-Transfer-Encoding: 7Bit Content-Type: text/plain; charset="us-ascii" Cc: dev@dpdk.org Subject: Re: [dpdk-dev] [PATCH v3 00/11] Cuckoo 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: Wed, 08 Jul 2015 23:25:00 -0000 Bruce, what is the status of this series? 2015-06-28 23:25, Pablo de Lara: > This patchset is to replace the existing hash library with > a more efficient and functional approach, using the Cuckoo hash > method to deal with collisions. This method is based on using > two different hash functions to have two possible locations > in the hash table where an entry can be. > So, if a bucket is full, a new entry can push one of the items > in that bucket to its alternative location, making space for itself. > > Advantages > ~~~~~~ > - Offers the option to store more entries when the target bucket is full > (unlike the previous implementation) > - Memory efficient: for storing those entries, it is not necessary to > request new memory, as the entries will be stored in the same table > - Constant worst lookup time: in worst case scenario, it always takes > the same time to look up an entry, as there are only two possible locations > where an entry can be. > - Storing data: user can store data in the hash table, unlike the > previous implementation, but he can still use the old API > > This implementation tipically offers over 90% utilization. > Notice that API has been extended, but old API remains. The main > change in ABI is that rte_hash structure is now private and the > deprecation of two macros. > > Changes in v3: > > - Now user can store variable size data, instead of 32 or 64-bit size data, > using the new parameter "data_len" in rte_hash_parameters > - Add lookup_bulk_with_hash function in performance unit tests > - Add new functions that handle data in performance unit tests > - Remove duplicates in performance unit tests > - Fix rte_hash_reset, which was not reseting the last entry [...] > Pablo de Lara (11): > eal: add const in prefetch functions > hash: move rte_hash structure to C file and make it internal > test/hash: enhance hash unit tests > test/hash: rename new hash perf unit test back to original name > hash: replace existing hash library with cuckoo hash implementation > hash: add new lookup_bulk_with_hash function > hash: add new function rte_hash_reset > hash: add new functionality to store data in hash table > MAINTAINERS: claim responsability for hash library > doc: announce ABI change of librte_hash > doc: update hash documentation