From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mga07.intel.com (mga07.intel.com [134.134.136.100]) by dpdk.org (Postfix) with ESMTP id D516F1B158 for ; Fri, 28 Sep 2018 19:36:08 +0200 (CEST) X-Amp-Result: SKIPPED(no attachment in message) X-Amp-File-Uploaded: False Received: from fmsmga007.fm.intel.com ([10.253.24.52]) by orsmga105.jf.intel.com with ESMTP/TLS/DHE-RSA-AES256-GCM-SHA384; 28 Sep 2018 10:36:07 -0700 X-ExtLoop1: 1 X-IronPort-AV: E=Sophos;i="5.54,315,1534834800"; d="scan'208";a="73886710" Received: from fmsmsx104.amr.corp.intel.com ([10.18.124.202]) by fmsmga007.fm.intel.com with ESMTP; 28 Sep 2018 10:35:58 -0700 Received: from fmsmsx158.amr.corp.intel.com (10.18.116.75) by fmsmsx104.amr.corp.intel.com (10.18.124.202) with Microsoft SMTP Server (TLS) id 14.3.319.2; Fri, 28 Sep 2018 10:35:57 -0700 Received: from fmsmsx151.amr.corp.intel.com ([169.254.7.87]) by fmsmsx158.amr.corp.intel.com ([169.254.15.101]) with mapi id 14.03.0319.002; Fri, 28 Sep 2018 10:35:57 -0700 From: "Wang, Yipeng1" To: Honnappa Nagarahalli , "Richardson, Bruce" , "Ananyev, Konstantin" CC: "dev@dpdk.org" , "Gobriel, Sameh" Thread-Topic: [PATCH v2 5/7] hash: add extendable bucket feature Thread-Index: AQHUUgpSs/Eh6+azy0Oe76JhXbgpcqUAKviwgARM9wCAAIf0AIAAQT3g Date: Fri, 28 Sep 2018 17:35:57 +0000 Message-ID: References: <1536253745-133104-1-git-send-email-yipeng1.wang@intel.com> <1537550255-252066-1-git-send-email-yipeng1.wang@intel.com> <1537550255-252066-6-git-send-email-yipeng1.wang@intel.com> <20180927111501.GC19604@bricha3-MOBL.ger.corp.intel.com> In-Reply-To: Accept-Language: en-US Content-Language: en-US X-MS-Has-Attach: X-MS-TNEF-Correlator: dlp-product: dlpe-windows dlp-version: 11.0.400.15 dlp-reaction: no-action x-ctpclassification: CTP_NT x-titus-metadata-40: eyJDYXRlZ29yeUxhYmVscyI6IiIsIk1ldGFkYXRhIjp7Im5zIjoiaHR0cDpcL1wvd3d3LnRpdHVzLmNvbVwvbnNcL0ludGVsMyIsImlkIjoiZGI2YzAxYzUtYmRiZC00MzM1LThiOWYtZDk1YjNjNjdkNmZkIiwicHJvcHMiOlt7Im4iOiJDVFBDbGFzc2lmaWNhdGlvbiIsInZhbHMiOlt7InZhbHVlIjoiQ1RQX05UIn1dfV19LCJTdWJqZWN0TGFiZWxzIjpbXSwiVE1DVmVyc2lvbiI6IjE3LjEwLjE4MDQuNDkiLCJUcnVzdGVkTGFiZWxIYXNoIjoiV0JZVFRla0JFekE2VXZ1S2E2UWlyOFFTUjR3bmdRbzdaMjJIcmJEVHB4RmpDUWw0NEl2VUxiRTJSeFZ4SDEyWCJ9 x-originating-ip: [10.1.200.107] Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: quoted-printable MIME-Version: 1.0 Subject: Re: [dpdk-dev] [PATCH v2 5/7] 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: Fri, 28 Sep 2018 17:36:09 -0000 > -----Original Message----- > From: Honnappa Nagarahalli [mailto:Honnappa.Nagarahalli@arm.com] > Sent: Thursday, September 27, 2018 12:22 PM > To: Richardson, Bruce > Cc: Wang, Yipeng1 ; dev@dpdk.org; > michel@digirati.com.br > Subject: RE: [PATCH v2 5/7] hash: add extendable bucket feature >=20 > > > > +/* Allocate same number of extendable buckets */ > > > IMO, we are allocating too much memory to support this feature. > > > Especially, > > when we claim that keys ending up in the extendable table is a rare > > occurrence. By doubling the memory we are effectively saying that the > > main table might have 50% utilization. It will also significantly > > increase the cycles required to iterate the complete hash table (in > > rte_hash_iterate API) even when we expect that the extendable table > contains very few entries. > > > > > > I am wondering if we can provide options to control the amount of > > > extra > > memory that gets allocated and make the memory allocation dynamic (or > > on demand basis). I think this also goes well with the general > > direction DPDK is taking - allocate resources as needed rather than > > allocating all the resources during initialization. > > > > > > > Given that adding new entries should not normally be a fast-path > > function, how about allowing memory allocation in add itself. Why not > > initialize with a fairly small number of extra bucket entries, and > > then each time they are all used, double the number of entries. That > > will give efficient resource scaling, I think. > > > +1 > 'small number of extra bucket entries' =3D=3D 5% of total capacity reques= ted > (assuming cuckoo hash will provide 95% efficiency) >=20 > > /Bruce [Wang, Yipeng]=20 Thanks for the comments. We allocate same as table size for extendable buckets at creation because the purpose is to provide capacity guarantee even for the worst sce= nario (all keys collide in same buckets). Applications (e.g. Telco workloads) that require 100% capacity guarantee wi= ll be sure that insertion always succeeds below the specified table size. With any dynamic memory allocation or less buckets, this guarantee is broken (even if it is very rare). The dynamic memory allocation could fail.= =20 Users who do not need such behavior can disable this feature. Given that the cuckoo algorithm already ensures very high utilization, they usually do not need the extendable buckets.