From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from mga11.intel.com (mga11.intel.com [192.55.52.93]) by mx.groups.io with SMTP id smtpd.web11.27977.1607906442605394391 for ; Sun, 13 Dec 2020 16:40:43 -0800 Authentication-Results: mx.groups.io; dkim=pass header.i=@intel.onmicrosoft.com header.s=selector2-intel-onmicrosoft-com header.b=Rpl4euHg; spf=pass (domain: intel.com, ip: 192.55.52.93, mailfrom: eric.dong@intel.com) IronPort-SDR: pxJvkKm/WYIcUaNRpko9ecbDe7iFWPQ6YZabEMdGdMgPyAS0eebRqEFTXuRXB8/cVWhz+W/T4T UXHqki4kPMOQ== X-IronPort-AV: E=McAfee;i="6000,8403,9834"; a="171129688" X-IronPort-AV: E=Sophos;i="5.78,417,1599548400"; d="scan'208";a="171129688" Received: from fmsmga006.fm.intel.com ([10.253.24.20]) by fmsmga102.fm.intel.com with ESMTP/TLS/ECDHE-RSA-AES256-GCM-SHA384; 13 Dec 2020 16:40:42 -0800 IronPort-SDR: BdUmGVPb7IC5LzOmnj07bt2x3B6O3yYILKZMyIEsPnu1Ec66iCdFdEYe8D6vZdFPT8Ex29jge/ ywgw2hAFmh7A== X-ExtLoop1: 1 X-IronPort-AV: E=Sophos;i="5.78,417,1599548400"; d="scan'208";a="551783504" Received: from fmsmsx606.amr.corp.intel.com ([10.18.126.86]) by fmsmga006.fm.intel.com with ESMTP; 13 Dec 2020 16:40:41 -0800 Received: from fmsmsx606.amr.corp.intel.com (10.18.126.86) by fmsmsx606.amr.corp.intel.com (10.18.126.86) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256) id 15.1.1713.5; Sun, 13 Dec 2020 16:40:41 -0800 Received: from fmsedg601.ED.cps.intel.com (10.1.192.135) by fmsmsx606.amr.corp.intel.com (10.18.126.86) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256) id 15.1.1713.5 via Frontend Transport; Sun, 13 Dec 2020 16:40:41 -0800 Received: from NAM12-BN8-obe.outbound.protection.outlook.com (104.47.55.172) by edgegateway.intel.com (192.55.55.70) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.1.1713.5; Sun, 13 Dec 2020 16:40:41 -0800 ARC-Seal: i=1; a=rsa-sha256; s=arcselector9901; d=microsoft.com; cv=none; b=m7KvZ2VDqoMRp1O4ec7Wq4hDViM0B211x1YNPSqZJuOe+nAzNDs2vKjjf0TQoCHKytGY0hIKXR6VFQx1Nkuq40tOTB6tCEgcv4vIsylXe663I841MUescHOWUSGjyLlP4ejoqed7to66x37F1LCAgB1v7mMYlm6570k0TS9YCe0qUqyInlORc5eDwdcBzbnOlWLmIqz83rMtiAl8K83OpSH438zoR29YxN99gtqax+DPlzwTEUmjLFlBwoLkkHXwgQYct6OMytPGa8n5dXLzUq2YRbp+fa2dlnK1uZiXY/eDePBg9uqmz+HwjRmfYhZm/2zHJuC9V1M/+ryoVlDCXA== 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=sVlJZze18Gyw50iEmSeUebcd5tNKruDZfeO2sP4/sTk=; b=cFcsUR/KqZ5ut7g2Iixo0QPSHAWwhoZh89J0Gc2bLLbZZHn1un2t7AHiJX0vl0AnkAuP9NXf6Q7FnY6Nl+QlPTgDCZoe14P6XRQq5HIjDW6IxrMVeQJZWETrtmsyWQNH1gCksv8fPouTcg4c7i6ZzgfvXWVuEJEWwv6gYE8zS+V4Cy/pt0OuIZUJMqacbpdz5URDPRrZm57fi+PedDCAXxX3/C/Q60bswVFUnQJama5fq7PQpJiiDKCnuq36YCypQIJV9vEbv1N2jtixYG72Thevg0MeTdD72sNHkSOr6AgsgRRkzWiyKfCASI8Kp4p0aMMsxZzDOfX+YT7eBQGsHA== 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=sVlJZze18Gyw50iEmSeUebcd5tNKruDZfeO2sP4/sTk=; b=Rpl4euHgJMJd5lQIK2nXRChdR4rLAE+/5DhHezydCUdf1geYUdv9JJMnrYZnVSsUHLyA2B2in+n3CTGuA0wXoXH/o7iFFLn73HE3fXgE5hpDRwptAxUzQPUM+vT+E7Px7tdV/Onam+Qp67hWRINKyE9Ru8AsOxxwLL17h4FVvuw= Received: from CY4PR11MB1272.namprd11.prod.outlook.com (2603:10b6:903:29::9) by CY4PR11MB1271.namprd11.prod.outlook.com (2603:10b6:903:2f::9) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.3654.15; Mon, 14 Dec 2020 00:40:38 +0000 Received: from CY4PR11MB1272.namprd11.prod.outlook.com ([fe80::59b2:5d29:472d:1d36]) by CY4PR11MB1272.namprd11.prod.outlook.com ([fe80::59b2:5d29:472d:1d36%5]) with mapi id 15.20.3654.024; Mon, 14 Dec 2020 00:40:38 +0000 From: "Dong, Eric" To: "Ni, Ray" , "devel@edk2.groups.io" CC: "Zeng, Star" , "Lou, Yun" , Laszlo Ersek Subject: Re: [PATCH V2] UefiCpuPkg/CpuFeature: reduce time complexty to calc CpuInfo.First Thread-Topic: [PATCH V2] UefiCpuPkg/CpuFeature: reduce time complexty to calc CpuInfo.First Thread-Index: AQHWz6tFfmaY6uBrvkez8Wipl4sXdan1xANA Date: Mon, 14 Dec 2020 00:40:38 +0000 Message-ID: References: <20201211104739.172-1-ray.ni@intel.com> In-Reply-To: <20201211104739.172-1-ray.ni@intel.com> Accept-Language: en-US X-MS-Has-Attach: X-MS-TNEF-Correlator: authentication-results: intel.com; dkim=none (message not signed) header.d=none;intel.com; dmarc=none action=none header.from=intel.com; x-originating-ip: [192.55.46.39] x-ms-publictraffictype: Email x-ms-office365-filtering-correlation-id: 01fbcc45-f370-4f0d-dd11-08d89fc8e0d5 x-ms-traffictypediagnostic: CY4PR11MB1271: x-ms-exchange-transport-forked: True x-microsoft-antispam-prvs: x-ms-oob-tlc-oobclassifiers: OLM:8882; x-ms-exchange-senderadcheck: 1 x-microsoft-antispam: BCL:0; x-microsoft-antispam-message-info: Vff26S9Mwm+kc/g/sxzzCzqsTBckYdC/WKlpashqrEjKW3p9YOV26g3lXpKpCA9hKrpY/z9mWJwuOdc7/N8OokfISCABUrkKKHmGgGdk9gmznYu7n5vSUU/bI5YtISHxrGbfdHNpwJ5NJJZkGKKorFH0+J88PsyaWcDULgn9yEE0ZXvyekJn/1/98pyYKBwMA9TTISvP0zpChrMM59SZavVYclYwNP2hxUxLiHLsb8D0KIwnRvLzhldx58la2i5CZgDK8QiS4OmdArpkqrID3JzHWKqn9qBN+S2mX0e997CqMUcdIajDyAL/MoQdOAlIubB5hMbJ0+itJyfgFpFIMg== x-forefront-antispam-report: CIP:255.255.255.255;CTRY:;LANG:en;SCL:1;SRV:;IPV:NLI;SFV:NSPM;H:CY4PR11MB1272.namprd11.prod.outlook.com;PTR:;CAT:NONE;SFS:(4636009)(346002)(366004)(136003)(376002)(52536014)(66946007)(53546011)(7696005)(55016002)(66556008)(76116006)(110136005)(66446008)(64756008)(26005)(54906003)(4326008)(186003)(86362001)(9686003)(71200400001)(2906002)(83380400001)(8676002)(66476007)(6506007)(508600001)(33656002)(5660300002)(8936002);DIR:OUT;SFP:1102; x-ms-exchange-antispam-messagedata: =?us-ascii?Q?70rZnKtJeMhKKuFGWe1fs1ldLNNFKtsMC1NZoHmJ8u4i15+Vl8FlBMOgUScx?= =?us-ascii?Q?YMTpsR87pveFd4rxIyOQ5a6lByVdLIOLM+AUvtlH/p+RXbLrMY4BTYYp2l/c?= =?us-ascii?Q?Ca+TnhIrEq+lsWfKioja9Sht47J6wlJyDOMIy52g60yM+3CBRDQ/QeqvC65n?= =?us-ascii?Q?jS7q0N/2ylz9nYBDtRCO2gzsXlUbxGmNUOrYlWmeDXMvs0Lnpm5ciysTBxqU?= =?us-ascii?Q?Ip8D3I7IOIWFb43+rYNgfV7mANGt9D738DGkrXZighpuTRQO1ly6FPnmVe4T?= =?us-ascii?Q?X61HC95sxP/xCt54TfMGjb5Ju35l9xBa4lCYhe9JnQn6vqW+mASPYnXbgNnO?= =?us-ascii?Q?J5ZdHTsl2reWI7bxQRTxsGx0XwWFzaxX7hN2FcLS/A6abxvDq42ca0GBf1PZ?= =?us-ascii?Q?+Z/A1pgaLql4reyFjq+6KU79XVdJw7KGXgrbulU+lcx8MBm5B3I+s/BISgbx?= =?us-ascii?Q?mw46AtSK7DG+bQ3VC4GNq2KaSEykWJdicJD/bjnYT8j7hb4CDIh7pvUgyAVe?= =?us-ascii?Q?ldJBeZN+1o69TuuKJjJyC7QHJOonScev6dfWjMpIoOuvj4uzZapHNWema1OD?= =?us-ascii?Q?1z6AS1bCaAmtDDRdRZ4nONl7A3GE1DYP5q2meEdJBnE/5pdhcMsgyj4P7nO6?= =?us-ascii?Q?EDeVzUMpTD3DTBrwmpXRBlVs3fC5i5UMdInJ2YTll55FrFsqvwmibFrcTYpQ?= =?us-ascii?Q?vXOrRxTg5lFKe+Y5T0uEHQM5Y0J4+6KYoIRSt59bwdkyFQkBlq4+MU0kjpxL?= =?us-ascii?Q?+4G8N7eXVzQvoyHHU7X42mCrFx7KC/q4R5RMEtFWXMPJsGn7NMDUuaIrf39g?= =?us-ascii?Q?Y1/2I2zGCvssQjSMFftFB/9pxb4KHxwm7Pj41rGQVIlJ6snPHjT9FL1ztU2t?= =?us-ascii?Q?bqxOCY/xqKYyfk3L8Wj0lACZKtHoFmLf5TIzg/MQSFe82gfAuRwlD/a4gV0t?= =?us-ascii?Q?7GGCBunPmXlPiwdPDpoizXQ3QHhRDLXFgRIGuK8Ci/8=3D?= MIME-Version: 1.0 X-MS-Exchange-CrossTenant-AuthAs: Internal X-MS-Exchange-CrossTenant-AuthSource: CY4PR11MB1272.namprd11.prod.outlook.com X-MS-Exchange-CrossTenant-Network-Message-Id: 01fbcc45-f370-4f0d-dd11-08d89fc8e0d5 X-MS-Exchange-CrossTenant-originalarrivaltime: 14 Dec 2020 00:40:38.6193 (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: EM7haR3dd+BFCQDCTCvuZ/tGDlUDvPXz2wUtM3WKfFggIdkHvp2dz4KmTD/DrGVjZylmxNmKfpifOmYD3dQVkQ== X-MS-Exchange-Transport-CrossTenantHeadersStamped: CY4PR11MB1271 Return-Path: eric.dong@intel.com X-OriginatorOrg: intel.com Content-Language: en-US Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: quoted-printable Reviewed-by: Eric Dong -----Original Message----- From: Ni, Ray =20 Sent: Friday, December 11, 2020 6:48 PM To: devel@edk2.groups.io Cc: Dong, Eric ; Zeng, Star ; Lou= , Yun ; Laszlo Ersek Subject: [PATCH V2] UefiCpuPkg/CpuFeature: reduce time complexty to calc Cp= uInfo.First CpuInfo.First stores whether the current thread belongs to the first packag= e in the platform, first core in a package, first thread in a core. But the time complexity of original algorithm to calculate the CpuInfo.Firs= t is O (n) * O (p) * O (c). n: number of processors p: number of packages c: number of cores per package The patch trades time with space by storing the first package, first core p= er package, first thread per core in an array. The time complexity becomes O (n). Signed-off-by: Ray Ni Cc: Eric Dong Cc: Star Zeng Cc: Yun Lou Cc: Laszlo Ersek --- .../CpuFeaturesInitialize.c | 96 +++++++++---------- 1 file changed, 47 insertions(+), 49 deletions(-) diff --git a/UefiCpuPkg/Library/RegisterCpuFeaturesLib/CpuFeaturesInitializ= e.c b/UefiCpuPkg/Library/RegisterCpuFeaturesLib/CpuFeaturesInitialize.c index d4a576385f..a1e972b1a2 100644 --- a/UefiCpuPkg/Library/RegisterCpuFeaturesLib/CpuFeaturesInitialize.c +++ b/UefiCpuPkg/Library/RegisterCpuFeaturesLib/CpuFeaturesInitialize.c @@ -105,7 +105,10 @@ CpuInitDataInitialize ( EFI_CPU_PHYSICAL_LOCATION *Location; UINT32 = PackageIndex; UINT32 CoreInd= ex;- UINT32 First;+ UINTN = Pages;+ UINT32 FirstPackage;+ = UINT32 *FirstCore;+ UINT32 = *FirstThread; ACPI_CPU_DATA *AcpiCpu= Data; CPU_STATUS_INFORMATION *CpuStatus; UINT32 = *ThreadCountPerPackage;@@ -236,74 +239,69 @@ CpuInitDa= taInitialize ( // // Initialize CpuFeaturesData->InitOrder[].CpuInfo.First+ // Use = AllocatePages () instead of AllocatePool () because pool cannot be freed in= PEI phase but page can. //+ Pages =3D EFI_SIZE_TO_PAGES (CpuStatus-= >PackageCount * sizeof (UINT32) + CpuStatus->PackageCount * CpuStatus->MaxC= oreCount * sizeof (UINT32));+ FirstCore =3D AllocatePages (Pages);+ ASSER= T (FirstCore !=3D NULL);+ FirstThread =3D FirstCore + CpuStatus->PackageC= ount; //- // Set First.Package for each thread belonging to the first p= ackage.+ // Set FirstPackage, FirstCore[], FirstThread[] to maximum packag= e ID, core ID, thread ID. //- First =3D MAX_UINT32;+ FirstPackage =3D M= AX_UINT32;+ SetMem32 (FirstCore, CpuStatus->PackageCount * sizeof (UINT3= 2), MAX_UINT32);+ SetMem32 (FirstThread, CpuStatus->PackageCount * CpuStat= us->MaxCoreCount * sizeof (UINT32), MAX_UINT32);+ for (ProcessorNumber = =3D 0; ProcessorNumber < NumberOfCpus; ProcessorNumber++) { Location = =3D &CpuFeaturesData->InitOrder[ProcessorNumber].CpuInfo.ProcessorInfo.Loca= tion;- First =3D MIN (Location->Package, First);++ //+ // Save the= minimum package ID in the platform.+ //+ FirstPackage = =3D MIN (Location->Package, FirstPackage);+ + //+ // Save the mini= mum core ID per package.+ //+ FirstCore[Location->Package] =3D MIN (L= ocation->Core, FirstCore[Location->Package]);+ + //+ // Save the min= imum thread ID per core.+ //+ FirstThread[Location->Package * CpuStat= us->MaxCoreCount + Location->Core] =3D MIN (+ Location->Thread,+ = FirstThread[Location->Package * CpuStatus->MaxCoreCount + Location->Core]+ = ); }++ //+ // Update the First field.+ // for (ProcessorNumber = =3D 0; ProcessorNumber < NumberOfCpus; ProcessorNumber++) { Location = =3D &CpuFeaturesData->InitOrder[ProcessorNumber].CpuInfo.ProcessorInfo.Loca= tion;- if (Location->Package =3D=3D First) {++ if (Location->Package = =3D=3D FirstPackage) { CpuFeaturesData->InitOrder[ProcessorNumber].Cp= uInfo.First.Package =3D 1; }- } - //- // Set First.Die/Tile/Module f= or each thread assuming:- // single Die under each package, single Tile u= nder each Die, single Module under each Tile- //- for (ProcessorNumber = =3D 0; ProcessorNumber < NumberOfCpus; ProcessorNumber++) {+ //+ // S= et First.Die/Tile/Module for each thread assuming:+ // single Die under= each package, single Tile under each Die, single Module under each Tile+ = // CpuFeaturesData->InitOrder[ProcessorNumber].CpuInfo.First.Die =3D = 1; CpuFeaturesData->InitOrder[ProcessorNumber].CpuInfo.First.Tile =3D 1= ; CpuFeaturesData->InitOrder[ProcessorNumber].CpuInfo.First.Module =3D = 1;- } - for (PackageIndex =3D 0; PackageIndex < CpuStatus->PackageCount; = PackageIndex++) {- //- // Set First.Core for each thread in the first= core of each package.- //- First =3D MAX_UINT32;- for (ProcessorN= umber =3D 0; ProcessorNumber < NumberOfCpus; ProcessorNumber++) {- Loc= ation =3D &CpuFeaturesData->InitOrder[ProcessorNumber].CpuInfo.ProcessorInf= o.Location;- if (Location->Package =3D=3D PackageIndex) {- Firs= t =3D MIN (Location->Core, First);- }+ if (Location->Core =3D=3D Fi= rstCore[Location->Package]) {+ CpuFeaturesData->InitOrder[ProcessorNum= ber].CpuInfo.First.Core =3D 1; }-- for (ProcessorNumber =3D 0; Proce= ssorNumber < NumberOfCpus; ProcessorNumber++) {- Location =3D &CpuFeat= uresData->InitOrder[ProcessorNumber].CpuInfo.ProcessorInfo.Location;- = if (Location->Package =3D=3D PackageIndex && Location->Core =3D=3D First) {= - CpuFeaturesData->InitOrder[ProcessorNumber].CpuInfo.First.Core =3D= 1;- }+ if (Location->Thread =3D=3D FirstThread[Location->Package *= CpuStatus->MaxCoreCount + Location->Core]) {+ CpuFeaturesData->InitOr= der[ProcessorNumber].CpuInfo.First.Thread =3D 1; } } - for (PackageI= ndex =3D 0; PackageIndex < CpuStatus->PackageCount; PackageIndex++) {- f= or (CoreIndex =3D 0; CoreIndex < CpuStatus->MaxCoreCount; CoreIndex++) {- = //- // Set First.Thread for the first thread of each core.- /= /- First =3D MAX_UINT32;- for (ProcessorNumber =3D 0; ProcessorNu= mber < NumberOfCpus; ProcessorNumber++) {- Location =3D &CpuFeatures= Data->InitOrder[ProcessorNumber].CpuInfo.ProcessorInfo.Location;- if= (Location->Package =3D=3D PackageIndex && Location->Core =3D=3D CoreIndex)= {- First =3D MIN (Location->Thread, First);- }- }-- = for (ProcessorNumber =3D 0; ProcessorNumber < NumberOfCpus; ProcessorNu= mber++) {- Location =3D &CpuFeaturesData->InitOrder[ProcessorNumber]= .CpuInfo.ProcessorInfo.Location;- if (Location->Package =3D=3D Packa= geIndex && Location->Core =3D=3D CoreIndex && Location->Thread =3D=3D First= ) {- CpuFeaturesData->InitOrder[ProcessorNumber].CpuInfo.First.Thr= ead =3D 1;- }- }- }- }+ FreePages (FirstCore, Pages); } /= **--=20 2.27.0.windows.1