From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mga04.intel.com (mga04.intel.com [192.55.52.120]) by dpdk.org (Postfix) with ESMTP id 5C3E71B3C0 for ; Tue, 23 Oct 2018 10:55:39 +0200 (CEST) X-Amp-Result: UNKNOWN X-Amp-Original-Verdict: FILE UNKNOWN X-Amp-File-Uploaded: False Received: from orsmga003.jf.intel.com ([10.7.209.27]) by fmsmga104.fm.intel.com with ESMTP/TLS/DHE-RSA-AES256-GCM-SHA384; 23 Oct 2018 01:55:38 -0700 X-ExtLoop1: 1 X-IronPort-AV: E=Sophos;i="5.54,415,1534834800"; d="scan'208";a="94261284" Received: from bricha3-mobl.ger.corp.intel.com ([10.237.221.107]) by orsmga003.jf.intel.com with SMTP; 23 Oct 2018 01:55:36 -0700 Received: by (sSMTP sendmail emulation); Tue, 23 Oct 2018 09:55:35 +0100 Date: Tue, 23 Oct 2018 09:55:35 +0100 From: Bruce Richardson To: Yipeng Wang Cc: dev@dpdk.org, honnappa.nagarahalli@arm.com Message-ID: <20181023085534.GB22220@bricha3-MOBL.ger.corp.intel.com> References: <1540233588-202969-1-git-send-email-yipeng1.wang@intel.com> <1540233588-202969-3-git-send-email-yipeng1.wang@intel.com> MIME-Version: 1.0 Content-Type: text/plain; charset=us-ascii Content-Disposition: inline In-Reply-To: <1540233588-202969-3-git-send-email-yipeng1.wang@intel.com> Organization: Intel Research and Development Ireland Ltd. User-Agent: Mutt/1.10.1 (2018-07-13) Subject: Re: [dpdk-dev] [PATCH v8 2/4] hash: add extendable bucket feature X-BeenThere: dev@dpdk.org X-Mailman-Version: 2.1.15 Precedence: list List-Id: DPDK patches and discussions List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Tue, 23 Oct 2018 08:55:39 -0000 On Mon, Oct 22, 2018 at 11:39:46AM -0700, Yipeng Wang wrote: > In use cases that hash table capacity needs to be guaranteed, > the extendable bucket feature can be used to contain extra > keys in linked lists when conflict happens. This is similar > concept to the extendable bucket hash table in packet > framework. > > This commit adds the extendable bucket feature. User can turn > it on or off through the extra flag field during table > creation time. > > Extendable bucket table composes of buckets that can be > linked list to current main table. When extendable bucket > is enabled, the hash table load can always achieve 100%. > In other words, the table can always accommodate the same > number of keys as the specified table size. This provides > 100% table capacity guarantee. > > Although keys ending up in the ext buckets may have longer > look up time, they should be rare due to the cuckoo > algorithm. > > Signed-off-by: Yipeng Wang > Acked-by: Dharmik Thakkar > --- Acked-by: Bruce Richardson