From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from EUR02-HE1-obe.outbound.protection.outlook.com (mail-eopbgr10088.outbound.protection.outlook.com [40.107.1.88]) by dpdk.org (Postfix) with ESMTP id 1D0241B136 for ; Sat, 29 Sep 2018 23:09:30 +0200 (CEST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=armh.onmicrosoft.com; s=selector1-arm-com; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-SenderADCheck; bh=osEUyRbJof+lrdPLOzaWuLgb0ZGGLl82dFfyw9/kFtQ=; b=o6paMVgp6xqqU4g0DWFNZ3bcOxSmjgaXfKcY6s7j6mk1d03sTr8G8idx8OpurV/9dR9nkds0ru6OkvHAM4Hye7LUVqnF1bb1hi3FoYfQ8KJdX9swfI2SJxd7huXsrMtIhXZ4c/Rm+szSFASrmuQeVUc2F4dxn7mwK+vNNK+Noig= Received: from AM6PR08MB3672.eurprd08.prod.outlook.com (20.177.115.29) by AM6PR08MB3319.eurprd08.prod.outlook.com (52.135.165.12) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.1185.24; Sat, 29 Sep 2018 21:09:28 +0000 Received: from AM6PR08MB3672.eurprd08.prod.outlook.com ([fe80::f423:e46a:a03c:e928]) by AM6PR08MB3672.eurprd08.prod.outlook.com ([fe80::f423:e46a:a03c:e928%2]) with mapi id 15.20.1185.024; Sat, 29 Sep 2018 21:09:28 +0000 From: Honnappa Nagarahalli To: "Wang, Yipeng1" , "Richardson, Bruce" , "Ananyev, Konstantin" CC: "dev@dpdk.org" , "Gobriel, Sameh" , nd Thread-Topic: [PATCH v2 5/7] hash: add extendable bucket feature Thread-Index: AQHUUgpSs/Eh6+azy0Oe76JhXbgpcqUAKviwgAPXngCAAIbVcIABde2AgAHMkrA= Date: Sat, 29 Sep 2018 21:09:28 +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: authentication-results: spf=none (sender IP is ) smtp.mailfrom=Honnappa.Nagarahalli@arm.com; x-originating-ip: [217.140.111.135] x-ms-publictraffictype: Email x-microsoft-exchange-diagnostics: 1; AM6PR08MB3319; 6:NOQroUYkjdlJaf7xOEzxf7xdGqnW2ohniOObuDCfbjKLGmrmRFuHTeTN7Ljzh0fvHv2ZPLw8lSeAPkKn4OFJiz7BIBgHR2D2y+geGvD2mQUS3KdC09QNYDsjomb7dxXA9gqWN4aGKG7IMj7dIh2ki6bH1np5RB/s4knQ91m2Q+9LJu3eY0WVSiYRgeXtfb8833D/Yjqbhns2WYar6gWmBcGBusdaITgoPulOsjoCJjx0gEOFFOMTAE7iMuxWCSHgC9JJf7lbdLGZUS/B+hDBgOXv8wKTJLfZERPO6giArVf1mMo2+xYQap2Q75YoBTpdd9abcQN0gkb/EW9jL4B+YYxwSEDQJPsprM3KcDQvA8fi5f4ccIQtEnGdimF8BtWcBqfadPCszPyMlO9vzLi6zNKU0waxum/ZY7kinyaydoJGt+6L39UO478mhiuJZNEv3RufvVg5xR6NiLeklADllw==; 5:OgfxDSWae5UnrL15YRw+A45ZPgS5M8sPZcAoA0sCycrEcl03XydeP3NfnXNvzeF7n4ztafbT5TFomubUe/8HF9pglrRIIAsjAk/mlxt0giUCwg7sU1Dd0ZTjl8ZavSevk0yY65TOreq6NTFmg2D2wEEEro8sJlJBOlQLk67VN+Y=; 7:Ha0CEKWA9GY1uBpkZQUq2nBy0Z5kW+MwY5Cs/Ov94VhAQErnFlit8VKPYZ9q9JQVsTWz9bQKmQvU3tCPyXY8Um/75Xhs08cXHO4SGFH2LzURsfZtOAb05a1j4yq9W53HBhmtOOaBoIM7o+4qzaxCeFljL7CNMH0WqZei5jcVMagUYLRv5rjovyYVGsMdc8Xx8NFbzj4lXlqRJbVcHRiKhPElZxJGxlnxEDea4uGMCt40AZXmeEPxyUZnFid5MPE0 x-ms-exchange-antispam-srfa-diagnostics: SOS; x-ms-office365-filtering-correlation-id: c1566868-ef92-4665-fce8-08d6264fd801 x-ms-office365-filtering-ht: Tenant x-microsoft-antispam: BCL:0; PCL:0; RULEID:(7020095)(4652040)(8989299)(4534165)(4627221)(201703031133081)(201702281549075)(8990200)(5600074)(711020)(4618075)(2017052603328)(7153060)(7193020); SRVR:AM6PR08MB3319; x-ms-traffictypediagnostic: AM6PR08MB3319: nodisclaimer: True x-microsoft-antispam-prvs: x-exchange-antispam-report-test: UriScan:(278428928389397); x-ms-exchange-senderadcheck: 1 x-exchange-antispam-report-cfa-test: BCL:0; PCL:0; RULEID:(8211001083)(6040522)(2401047)(8121501046)(5005006)(10201501046)(3002001)(93006095)(93001095)(3231355)(944501410)(52105095)(6055026)(149066)(150057)(6041310)(20161123562045)(20161123558120)(20161123564045)(201703131423095)(201702281528075)(20161123555045)(201703061421075)(201703061406153)(20161123560045)(201708071742011)(7699051); SRVR:AM6PR08MB3319; BCL:0; PCL:0; RULEID:; SRVR:AM6PR08MB3319; x-forefront-prvs: 0810818DA0 x-forefront-antispam-report: SFV:NSPM; SFS:(10009020)(366004)(396003)(39850400004)(376002)(346002)(136003)(51914003)(199004)(189003)(2900100001)(93886005)(26005)(102836004)(5660300001)(3846002)(6116002)(186003)(97736004)(105586002)(106356001)(71190400001)(34290500001)(54906003)(110136005)(71200400001)(8936002)(316002)(55016002)(9686003)(6436002)(6246003)(4326008)(53936002)(25786009)(81156014)(81166006)(229853002)(8676002)(5250100002)(14454004)(66066001)(256004)(14444005)(68736007)(7736002)(7696005)(99286004)(6506007)(74316002)(72206003)(76176011)(305945005)(478600001)(86362001)(33656002)(476003)(486006)(2906002)(446003)(11346002); DIR:OUT; SFP:1101; SCL:1; SRVR:AM6PR08MB3319; H:AM6PR08MB3672.eurprd08.prod.outlook.com; FPR:; SPF:None; LANG:en; PTR:InfoNoRecords; A:1; MX:1; received-spf: None (protection.outlook.com: arm.com does not designate permitted sender hosts) x-microsoft-antispam-message-info: Ml+dE46QmKj+bE5tszatQinXIN0IeWdVcn+WF6KSd6h7mHITA4u0yXbzLDcuJxMtMWhZsfpknRjXVWuOmpgpm06d4/JhaIxBirbrTNjQa7fG31IbPIV4Pd3GEINaJ/KvuhqjJdeGp/0Vq4lBq+1MCwiCYXC7Bz2z3Z3fX4KCNKXBdE/5yqRuvNjDABeG+sdRkXvlK3QfPW9adSJwUQjLu6WEEtqWKGdaTpv/RVUmbKnnDs0UohspLAjEOerIXP5HxyA/pmxhbYVeiFCQZoLVM+P74/gbtmcOyCfIOiFSnRe/Ngm8iub5YJv8H2sp9vzM9lWD56PBph/tmT1TSTHEOKfP+5af0m8YzLznbnTwQ/k= spamdiagnosticoutput: 1:99 spamdiagnosticmetadata: NSPM Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: quoted-printable MIME-Version: 1.0 X-OriginatorOrg: arm.com X-MS-Exchange-CrossTenant-Network-Message-Id: c1566868-ef92-4665-fce8-08d6264fd801 X-MS-Exchange-CrossTenant-originalarrivaltime: 29 Sep 2018 21:09:28.7003 (UTC) X-MS-Exchange-CrossTenant-fromentityheader: Hosted X-MS-Exchange-CrossTenant-id: f34e5979-57d9-4aaa-ad4d-b122a662184d X-MS-Exchange-Transport-CrossTenantHeadersStamped: AM6PR08MB3319 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: Sat, 29 Sep 2018 21:09:30 -0000 > > > > > > > +/* 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 > > requested (assuming cuckoo hash will provide 95% efficiency) > > > > > /Bruce > [Wang, Yipeng] > 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 scenario (all= keys > collide in same buckets). > Applications (e.g. Telco workloads) that require 100% capacity guarantee = will > be sure that insertion always succeeds below the specified table size. > With any dynamic memory allocation or less buckets, this guarantee is bro= ken > (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, th= ey > usually do not need the extendable buckets. Adding the dynamic memory allocation will make the code complicated. It is = also possible that, keeping this feature disabled, one can create the table= with more than required number of entries. I suggest we document the reaso= n for doubling the memory. If someone sees a concrete requirement for dynam= ic allocation in the future, the code can be changed.