From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from dpdk.org (dpdk.org [92.243.14.124]) by inbox.dpdk.org (Postfix) with ESMTP id 16D0EA057B; Mon, 30 Mar 2020 22:20:42 +0200 (CEST) Received: from [92.243.14.124] (localhost [127.0.0.1]) by dpdk.org (Postfix) with ESMTP id A07AD2BCE; Mon, 30 Mar 2020 22:20:41 +0200 (CEST) Received: from mga03.intel.com (mga03.intel.com [134.134.136.65]) by dpdk.org (Postfix) with ESMTP id D3CBF2B8B for ; Mon, 30 Mar 2020 22:20:39 +0200 (CEST) IronPort-SDR: 3/uLyaN8a/dM9K0cEhjw75bDOuoIUtXnvqM354vLkgam8SsxaUiNYeA6q/B+Tr6/SzMZwXk57x XC1dSuMEXk0w== X-Amp-Result: SKIPPED(no attachment in message) X-Amp-File-Uploaded: False Received: from fmsmga004.fm.intel.com ([10.253.24.48]) by orsmga103.jf.intel.com with ESMTP/TLS/ECDHE-RSA-AES256-GCM-SHA384; 30 Mar 2020 13:20:38 -0700 IronPort-SDR: vhU0ihaz/LMVQ3RPSx4xZy55FXltApf31mI5MYtJfqX/2+HHEpjYJH61V6eoI7F3c6CMCe17US VH4fA/bSkyXg== X-ExtLoop1: 1 X-IronPort-AV: E=Sophos;i="5.72,325,1580803200"; d="scan'208";a="272488991" Received: from orsmsx107.amr.corp.intel.com ([10.22.240.5]) by fmsmga004.fm.intel.com with ESMTP; 30 Mar 2020 13:20:38 -0700 Received: from orsmsx159.amr.corp.intel.com (10.22.240.24) by ORSMSX107.amr.corp.intel.com (10.22.240.5) with Microsoft SMTP Server (TLS) id 14.3.439.0; Mon, 30 Mar 2020 13:20:37 -0700 Received: from ORSEDG002.ED.cps.intel.com (10.7.248.5) by ORSMSX159.amr.corp.intel.com (10.22.240.24) with Microsoft SMTP Server (TLS) id 14.3.439.0; Mon, 30 Mar 2020 13:20:37 -0700 Received: from NAM02-CY1-obe.outbound.protection.outlook.com (104.47.37.50) by edgegateway.intel.com (134.134.137.101) with Microsoft SMTP Server (TLS) id 14.3.439.0; Mon, 30 Mar 2020 13:20:37 -0700 ARC-Seal: i=1; a=rsa-sha256; s=arcselector9901; d=microsoft.com; cv=none; b=dCtInZp0XSXfZtj7twtTXrI/GE5C2X2HSCrLlnidlSQx4JUyLBTE4E7h2KWSBMae44YbcKe6H0dXodEu4vMaXzZIIN6YJGivqKgoCjsqiDOR86HJehWewHMY00ku6+cwAjFVnlHqM19bNjw+yFaEMqwn2AYowxkOVMEXQqGO2glCJGwriMQT7oW0dnV9d3rGlgYxUkbuIRREVpNuGBC+sLQ2s9AOv1H9q+WF8PRPP3BLzVFxUdrq32IzpqEVeT0OZTIb67GralbZQYr9RG4+x0Ate5VpJu0c9qiCBrl5lIzalnSb3sCUB1rHHj6tB7J8pPdCgl3voJMiv0VxXFdjYw== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=microsoft.com; s=arcselector9901; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-SenderADCheck; bh=acQGnZV01fY4HykGlZX9kJXM1FaLqpbPjS87hty2+ME=; b=lE2jeDrDA9xZSUqFtcDccBD4qh0Mt77cdYEpSpnczS2Q8tm1xUKdsw0Di7tBg///SrW6Wr6sMnNpyxcZPovUsudSfd4R1kdKoYVcsePqGbibRwj8BJOTx5uYG/VWG/xaLVMztR8jf1/L+7svOGNjtmyaIbzok3+4ry/L6ZkFJ7mpN3kAbCRMf1KCg2gNRD3cLgBlNAfJlYePtPEi9F1AaRx1us93YOOpbCe3dRzuiX1gMvuQbE3iryAhUAw/SwL9fVcGTt+Cpus4wIUSiVbT4qSxZsbEBnKsvd9iMm05YMdvOWGJImhc72EwecewnGUIJ+8PbSpUE/w8bO2g7awC8A== ARC-Authentication-Results: i=1; mx.microsoft.com 1; spf=pass smtp.mailfrom=intel.com; dmarc=pass action=none header.from=intel.com; dkim=pass header.d=intel.com; arc=none DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=intel.onmicrosoft.com; s=selector2-intel-onmicrosoft-com; h=From:Date:Subject:Message-ID:Content-Type:MIME-Version:X-MS-Exchange-SenderADCheck; bh=acQGnZV01fY4HykGlZX9kJXM1FaLqpbPjS87hty2+ME=; b=U/BqKYzrsGc1Gkijf8020qy3Y4pE+VSjTATuyDXC4n5RcFIABwOsv8W5OJs+U0CPuR8eMmBt2AyvyYPfVr5wfzSpjm8BvYNGmcPFzu0SjDgxPkAISHS/wD8Hlr7Kzz1Rwa8ZrX9FpLs/99nbkG/om0SCl6T/PlGkMmAAHdHsVLk= Received: from MN2PR11MB4158.namprd11.prod.outlook.com (2603:10b6:208:155::14) by MN2PR11MB3934.namprd11.prod.outlook.com (2603:10b6:208:152::20) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.2856.20; Mon, 30 Mar 2020 20:20:35 +0000 Received: from MN2PR11MB4158.namprd11.prod.outlook.com ([fe80::6471:daba:c5ad:2399]) by MN2PR11MB4158.namprd11.prod.outlook.com ([fe80::6471:daba:c5ad:2399%4]) with mapi id 15.20.2856.019; Mon, 30 Mar 2020 20:20:35 +0000 From: "Wang, Yipeng1" To: "Medvedkin, Vladimir" , "dev@dpdk.org" CC: "Gobriel, Sameh" , "Richardson, Bruce" Thread-Topic: [PATCH v2 1/2] hash: add hash bulk lookup with hash signatures array Thread-Index: AQHWA45QYkQ67fYZkkeSio8WzkkBUahhljaQ Date: Mon, 30 Mar 2020 20:20:35 +0000 Message-ID: References: <1583757860-375294-1-git-send-email-vladimir.medvedkin@intel.com> <1585241243-339118-1-git-send-email-vladimir.medvedkin@intel.com> In-Reply-To: <1585241243-339118-1-git-send-email-vladimir.medvedkin@intel.com> Accept-Language: en-US Content-Language: en-US X-MS-Has-Attach: X-MS-TNEF-Correlator: dlp-reaction: no-action dlp-version: 11.2.0.6 dlp-product: dlpe-windows authentication-results: spf=none (sender IP is ) smtp.mailfrom=yipeng1.wang@intel.com; x-originating-ip: [108.161.24.24] x-ms-publictraffictype: Email x-ms-office365-filtering-correlation-id: 5692b270-785e-434c-eec4-08d7d4e7ce24 x-ms-traffictypediagnostic: MN2PR11MB3934: x-ld-processed: 46c98d88-e344-4ed4-8496-4ed7712e255d,ExtAddr x-ms-exchange-transport-forked: True x-microsoft-antispam-prvs: x-ms-oob-tlc-oobclassifiers: OLM:1468; x-forefront-prvs: 0358535363 x-forefront-antispam-report: CIP:255.255.255.255; CTRY:; LANG:en; SCL:1; SRV:; IPV:NLI; SFV:NSPM; H:MN2PR11MB4158.namprd11.prod.outlook.com; PTR:; CAT:NONE; SFTY:; SFS:(10019020)(396003)(376002)(39860400002)(366004)(136003)(346002)(110136005)(5660300002)(6506007)(54906003)(53546011)(186003)(26005)(9686003)(71200400001)(55016002)(33656002)(66446008)(8936002)(7696005)(64756008)(316002)(76116006)(66476007)(478600001)(66946007)(52536014)(86362001)(4326008)(66556008)(81166006)(8676002)(107886003)(2906002)(81156014); DIR:OUT; SFP:1102; x-ms-exchange-senderadcheck: 1 x-microsoft-antispam: BCL:0; x-microsoft-antispam-message-info: Y6Ipuf+kmO3HoCP5WvLWbuZPDbHJ0OKcWLlX/Ta5fWqqWz6PXh7qssg/qF/p0BJMrtwOBjC+ETeBAIXT/acpd2byAMemAwkyln+5so+nVClCZXDS6HKOFEpO5EtdemiLM1bBvi/gMrVVdr3sVhItvaiUyJDzbKT8tcDlXQi0Ucr/3FKXhc6DhNiQ4nhcjgmxRZwx4wbSZGRebwMTQ5kbh+ymMpA0xb33yo7hhEkmlBs9t5yVl4kTrREU/gb7luDv8BtTQMMbJI9b5RGFYaNJVZVWCXWBzfO8sFQAObtD+KrdntcSrNijuu0B3J/PdGxZQyZlH+mEI+IiqRBrqYDvHHnOV3t1lzKFJJh0FrV/E6mAJYGMwLos3NEA8PGpP5num34Jlxn/XDgFLF90dgOh4Va1j5hicYBNH1hu421f6mS8r0fjoa3n8D1Uo8fY5X4J x-ms-exchange-antispam-messagedata: V7CEZXAYLxSD2AWMyHJIBNy+pIaoDTXtBZajWXmh5aEO5+NJjOhHdU+KACY/+pyzClmEY/eVe+O8f2jTSGt7gnze3LM/pTGMiTRBkLvO99WdTSlYX8ttXsXnFw1cPuoyD9sEVRbT7O29sG8Vmcvg6Q== Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: quoted-printable MIME-Version: 1.0 X-MS-Exchange-CrossTenant-Network-Message-Id: 5692b270-785e-434c-eec4-08d7d4e7ce24 X-MS-Exchange-CrossTenant-originalarrivaltime: 30 Mar 2020 20:20:35.5536 (UTC) X-MS-Exchange-CrossTenant-fromentityheader: Hosted X-MS-Exchange-CrossTenant-id: 46c98d88-e344-4ed4-8496-4ed7712e255d X-MS-Exchange-CrossTenant-mailboxtype: HOSTED X-MS-Exchange-CrossTenant-userprincipalname: NRDbalxWfCqpsMKMCZfP7NfnjFfzhTPTzYqe5vK6nbhFFOmsVuzFDwzlJvDjvXVp5ySM/ya3YMRveVtApY6a8Q== X-MS-Exchange-Transport-CrossTenantHeadersStamped: MN2PR11MB3934 X-OriginatorOrg: intel.com Subject: Re: [dpdk-dev] [PATCH v2 1/2] hash: add hash bulk lookup with hash signatures array 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: , Errors-To: dev-bounces@dpdk.org Sender: "dev" > -----Original Message----- > From: Medvedkin, Vladimir > Sent: Thursday, March 26, 2020 9:47 AM > To: dev@dpdk.org > Cc: Wang, Yipeng1 ; Gobriel, Sameh > ; Richardson, Bruce > > Subject: [PATCH v2 1/2] hash: add hash bulk lookup with hash signatures > array >=20 > Implement rte_hash_lookup_with_hash_bulk_data() - lookup function with > precomputed hash signatures. >=20 > Signed-off-by: Vladimir Medvedkin > --- > lib/librte_hash/rte_cuckoo_hash.c | 296 +++++++++++++++++++++++----- > ------- > lib/librte_hash/rte_hash.h | 27 ++++ > lib/librte_hash/rte_hash_version.map | 1 + > 3 files changed, 227 insertions(+), 97 deletions(-) >=20 > diff --git a/lib/librte_hash/rte_cuckoo_hash.c > b/lib/librte_hash/rte_cuckoo_hash.c > index 6af8ca4..24a0756 100644 > --- a/lib/librte_hash/rte_cuckoo_hash.c > +++ b/lib/librte_hash/rte_cuckoo_hash.c > @@ -1711,64 +1711,20 @@ compare_signatures(uint32_t > *prim_hash_matches, uint32_t *sec_hash_matches, > } > } >=20 > -#define PREFETCH_OFFSET 4 > static inline void > -__rte_hash_lookup_bulk_l(const struct rte_hash *h, const void **keys, > - int32_t num_keys, int32_t *positions, > - uint64_t *hit_mask, void *data[]) > +__bulk_lookup_l(const struct rte_hash *h, const void **keys, > + const struct rte_hash_bucket **primary_bkt, > + const struct rte_hash_bucket **secondary_bkt, > + uint16_t *sig, int32_t num_keys, int32_t *positions, > + uint64_t *hit_mask, void *data[]) > { > uint64_t hits =3D 0; > int32_t i; > int32_t ret; > - uint32_t prim_hash[RTE_HASH_LOOKUP_BULK_MAX]; > - uint32_t prim_index[RTE_HASH_LOOKUP_BULK_MAX]; > - uint32_t sec_index[RTE_HASH_LOOKUP_BULK_MAX]; > - uint16_t sig[RTE_HASH_LOOKUP_BULK_MAX]; > - const struct rte_hash_bucket > *primary_bkt[RTE_HASH_LOOKUP_BULK_MAX]; > - const struct rte_hash_bucket > *secondary_bkt[RTE_HASH_LOOKUP_BULK_MAX]; > uint32_t prim_hitmask[RTE_HASH_LOOKUP_BULK_MAX] =3D {0}; > uint32_t sec_hitmask[RTE_HASH_LOOKUP_BULK_MAX] =3D {0}; > struct rte_hash_bucket *cur_bkt, *next_bkt; >=20 > - /* Prefetch first keys */ > - for (i =3D 0; i < PREFETCH_OFFSET && i < num_keys; i++) > - rte_prefetch0(keys[i]); > - > - /* > - * Prefetch rest of the keys, calculate primary and > - * secondary bucket and prefetch them > - */ > - for (i =3D 0; i < (num_keys - PREFETCH_OFFSET); i++) { > - rte_prefetch0(keys[i + PREFETCH_OFFSET]); > - > - prim_hash[i] =3D rte_hash_hash(h, keys[i]); > - > - sig[i] =3D get_short_sig(prim_hash[i]); > - prim_index[i] =3D get_prim_bucket_index(h, prim_hash[i]); > - sec_index[i] =3D get_alt_bucket_index(h, prim_index[i], sig[i]); > - > - primary_bkt[i] =3D &h->buckets[prim_index[i]]; > - secondary_bkt[i] =3D &h->buckets[sec_index[i]]; > - > - rte_prefetch0(primary_bkt[i]); > - rte_prefetch0(secondary_bkt[i]); > - } > - > - /* Calculate and prefetch rest of the buckets */ > - for (; i < num_keys; i++) { > - prim_hash[i] =3D rte_hash_hash(h, keys[i]); > - > - sig[i] =3D get_short_sig(prim_hash[i]); > - prim_index[i] =3D get_prim_bucket_index(h, prim_hash[i]); > - sec_index[i] =3D get_alt_bucket_index(h, prim_index[i], sig[i]); > - > - primary_bkt[i] =3D &h->buckets[prim_index[i]]; > - secondary_bkt[i] =3D &h->buckets[sec_index[i]]; > - > - rte_prefetch0(primary_bkt[i]); > - rte_prefetch0(secondary_bkt[i]); > - } > - > __hash_rw_reader_lock(h); >=20 > /* Compare signatures and prefetch key slot of first hit */ @@ - > 1903,63 +1859,20 @@ __rte_hash_lookup_bulk_l(const struct rte_hash *h, > const void **keys, } >=20 > static inline void > -__rte_hash_lookup_bulk_lf(const struct rte_hash *h, const void **keys, > - int32_t num_keys, int32_t *positions, > - uint64_t *hit_mask, void *data[]) > +__bulk_lookup_lf(const struct rte_hash *h, const void **keys, > + const struct rte_hash_bucket **primary_bkt, > + const struct rte_hash_bucket **secondary_bkt, > + uint16_t *sig, int32_t num_keys, int32_t *positions, > + uint64_t *hit_mask, void *data[]) > { > uint64_t hits =3D 0; > int32_t i; > int32_t ret; > - uint32_t prim_hash[RTE_HASH_LOOKUP_BULK_MAX]; > - uint32_t prim_index[RTE_HASH_LOOKUP_BULK_MAX]; > - uint32_t sec_index[RTE_HASH_LOOKUP_BULK_MAX]; > - uint16_t sig[RTE_HASH_LOOKUP_BULK_MAX]; > - const struct rte_hash_bucket > *primary_bkt[RTE_HASH_LOOKUP_BULK_MAX]; > - const struct rte_hash_bucket > *secondary_bkt[RTE_HASH_LOOKUP_BULK_MAX]; > uint32_t prim_hitmask[RTE_HASH_LOOKUP_BULK_MAX] =3D {0}; > uint32_t sec_hitmask[RTE_HASH_LOOKUP_BULK_MAX] =3D {0}; > struct rte_hash_bucket *cur_bkt, *next_bkt; > uint32_t cnt_b, cnt_a; >=20 > - /* Prefetch first keys */ > - for (i =3D 0; i < PREFETCH_OFFSET && i < num_keys; i++) > - rte_prefetch0(keys[i]); > - > - /* > - * Prefetch rest of the keys, calculate primary and > - * secondary bucket and prefetch them > - */ > - for (i =3D 0; i < (num_keys - PREFETCH_OFFSET); i++) { > - rte_prefetch0(keys[i + PREFETCH_OFFSET]); > - > - prim_hash[i] =3D rte_hash_hash(h, keys[i]); > - > - sig[i] =3D get_short_sig(prim_hash[i]); > - prim_index[i] =3D get_prim_bucket_index(h, prim_hash[i]); > - sec_index[i] =3D get_alt_bucket_index(h, prim_index[i], sig[i]); > - > - primary_bkt[i] =3D &h->buckets[prim_index[i]]; > - secondary_bkt[i] =3D &h->buckets[sec_index[i]]; > - > - rte_prefetch0(primary_bkt[i]); > - rte_prefetch0(secondary_bkt[i]); > - } > - > - /* Calculate and prefetch rest of the buckets */ > - for (; i < num_keys; i++) { > - prim_hash[i] =3D rte_hash_hash(h, keys[i]); > - > - sig[i] =3D get_short_sig(prim_hash[i]); > - prim_index[i] =3D get_prim_bucket_index(h, prim_hash[i]); > - sec_index[i] =3D get_alt_bucket_index(h, prim_index[i], sig[i]); > - > - primary_bkt[i] =3D &h->buckets[prim_index[i]]; > - secondary_bkt[i] =3D &h->buckets[sec_index[i]]; > - > - rte_prefetch0(primary_bkt[i]); > - rte_prefetch0(secondary_bkt[i]); > - } > - > for (i =3D 0; i < num_keys; i++) > positions[i] =3D -ENOENT; >=20 > @@ -2124,6 +2037,92 @@ __rte_hash_lookup_bulk_lf(const struct rte_hash > *h, const void **keys, > *hit_mask =3D hits; > } >=20 > +#define PREFETCH_OFFSET 4 > +static inline void > +__bulk_lookup_prefetching_loop(const struct rte_hash *h, > + const void **keys, int32_t num_keys, > + uint16_t *sig, > + const struct rte_hash_bucket **primary_bkt, > + const struct rte_hash_bucket **secondary_bkt) { > + int32_t i; > + uint32_t prim_hash[RTE_HASH_LOOKUP_BULK_MAX]; > + uint32_t prim_index[RTE_HASH_LOOKUP_BULK_MAX]; > + uint32_t sec_index[RTE_HASH_LOOKUP_BULK_MAX]; > + > + /* Prefetch first keys */ > + for (i =3D 0; i < PREFETCH_OFFSET && i < num_keys; i++) > + rte_prefetch0(keys[i]); > + > + /* > + * Prefetch rest of the keys, calculate primary and > + * secondary bucket and prefetch them > + */ > + for (i =3D 0; i < (num_keys - PREFETCH_OFFSET); i++) { > + rte_prefetch0(keys[i + PREFETCH_OFFSET]); > + > + prim_hash[i] =3D rte_hash_hash(h, keys[i]); > + > + sig[i] =3D get_short_sig(prim_hash[i]); > + prim_index[i] =3D get_prim_bucket_index(h, prim_hash[i]); > + sec_index[i] =3D get_alt_bucket_index(h, prim_index[i], sig[i]); > + > + primary_bkt[i] =3D &h->buckets[prim_index[i]]; > + secondary_bkt[i] =3D &h->buckets[sec_index[i]]; > + > + rte_prefetch0(primary_bkt[i]); > + rte_prefetch0(secondary_bkt[i]); > + } > + > + /* Calculate and prefetch rest of the buckets */ > + for (; i < num_keys; i++) { > + prim_hash[i] =3D rte_hash_hash(h, keys[i]); > + > + sig[i] =3D get_short_sig(prim_hash[i]); > + prim_index[i] =3D get_prim_bucket_index(h, prim_hash[i]); > + sec_index[i] =3D get_alt_bucket_index(h, prim_index[i], sig[i]); > + > + primary_bkt[i] =3D &h->buckets[prim_index[i]]; > + secondary_bkt[i] =3D &h->buckets[sec_index[i]]; > + > + rte_prefetch0(primary_bkt[i]); > + rte_prefetch0(secondary_bkt[i]); > + } > +} > + > + [Wang, Yipeng] Here is an unnecessary blank line. > +static inline void > +__rte_hash_lookup_bulk_l(const struct rte_hash *h, const void **keys, > + int32_t num_keys, int32_t *positions, > + uint64_t *hit_mask, void *data[]) > +{ > + uint16_t sig[RTE_HASH_LOOKUP_BULK_MAX]; > + const struct rte_hash_bucket > *primary_bkt[RTE_HASH_LOOKUP_BULK_MAX]; [Wang, Yipeng]=20 Thanks for revising the code to be more concise. It looks so far so good to me. BTW, would you like to add also the rte_hash_lookup_with_hash_bulk function= in this patchset? Just for the completeness. Thanks Yipeng