From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mga14.intel.com (mga14.intel.com [192.55.52.115]) by dpdk.org (Postfix) with ESMTP id 066C65A50 for ; Fri, 5 Jun 2015 16:33:26 +0200 (CEST) Received: from orsmga003.jf.intel.com ([10.7.209.27]) by fmsmga103.fm.intel.com with ESMTP; 05 Jun 2015 07:33:25 -0700 X-ExtLoop1: 1 X-IronPort-AV: E=Sophos;i="5.13,559,1427785200"; d="scan'208";a="582726934" Received: from irvmail001.ir.intel.com ([163.33.26.43]) by orsmga003.jf.intel.com with ESMTP; 05 Jun 2015 07:33:25 -0700 Received: from sivswdev02.ir.intel.com (sivswdev02.ir.intel.com [10.237.217.46]) by irvmail001.ir.intel.com (8.14.3/8.13.6/MailSET/Hub) with ESMTP id t55EXOTW003752 for ; Fri, 5 Jun 2015 15:33:24 +0100 Received: from sivswdev02.ir.intel.com (localhost [127.0.0.1]) by sivswdev02.ir.intel.com with ESMTP id t55EXOOq007109 for ; Fri, 5 Jun 2015 15:33:24 +0100 Received: (from pdelarax@localhost) by sivswdev02.ir.intel.com with id t55EXOZN007105 for dev@dpdk.org; Fri, 5 Jun 2015 15:33:24 +0100 From: Pablo de Lara To: dev@dpdk.org Date: Fri, 5 Jun 2015 15:33:18 +0100 Message-Id: <1433514804-7075-1-git-send-email-pablo.de.lara.guarch@intel.com> X-Mailer: git-send-email 1.7.4.1 Subject: [dpdk-dev] [PATCH 0/6] 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: Fri, 05 Jun 2015 14:33:27 -0000 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 before having to rehash the table, so it is unlikely that a rehash is necessary, as long as there is enough free space and user uses reasonable good hash functions. Things left for v2: - Improve unit tests to show clearer performance numbers - Documentation changes Pablo de Lara (6): eal: add const in prefetch functions hash: replace existing hash library with cuckoo hash implementation hash: add new lookup_bulk_with_hash function hash: add new functions rte_hash_rehash and rte_hash_reset hash: add new functionality to store data in hash table MAINTAINERS: claim responsability for hash library MAINTAINERS | 1 + app/test/Makefile | 3 + app/test/test_hash.c | 105 +- .../common/include/arch/ppc_64/rte_prefetch.h | 6 +- .../common/include/arch/x86/rte_prefetch.h | 12 +- .../common/include/generic/rte_prefetch.h | 6 +- lib/librte_hash/rte_hash.c | 1226 +++++++++++++++++--- lib/librte_hash/rte_hash.h | 373 +++++- lib/librte_hash/rte_hash_version.map | 18 + 9 files changed, 1422 insertions(+), 328 deletions(-) -- 2.4.2