From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from mga04.intel.com (mga04.intel.com [192.55.52.120]) by mx.groups.io with SMTP id smtpd.web12.29622.1607915899239218027 for ; Sun, 13 Dec 2020 19:18:19 -0800 Authentication-Results: mx.groups.io; dkim=pass header.i=@intel.onmicrosoft.com header.s=selector2-intel-onmicrosoft-com header.b=YTEZBRSE; spf=pass (domain: intel.com, ip: 192.55.52.120, mailfrom: star.zeng@intel.com) IronPort-SDR: b4353OMCwUX1vzZ2ASo7GBWgDNOvVgMEQ6XQR5YrgNTsdp64NZepyCbQgYluX4VNXWALxMq5Iv UawMxuzf4XDw== X-IronPort-AV: E=McAfee;i="6000,8403,9834"; a="172083695" X-IronPort-AV: E=Sophos;i="5.78,417,1599548400"; d="scan'208";a="172083695" Received: from fmsmga008.fm.intel.com ([10.253.24.58]) by fmsmga104.fm.intel.com with ESMTP/TLS/ECDHE-RSA-AES256-GCM-SHA384; 13 Dec 2020 19:18:13 -0800 IronPort-SDR: g4Bmjhnn5M22N0sqamNeOsIa5dQGJfPtvbWf+IPUUKD+Pjo9JnsG087wE4UzVf7OL6t+GCKq72 PGeHDFIH9Z4w== X-ExtLoop1: 1 X-IronPort-AV: E=Sophos;i="5.78,417,1599548400"; d="scan'208";a="331665937" Received: from orsmsx604.amr.corp.intel.com ([10.22.229.17]) by fmsmga008.fm.intel.com with ESMTP; 13 Dec 2020 19:18:13 -0800 Received: from orsmsx608.amr.corp.intel.com (10.22.229.21) by ORSMSX604.amr.corp.intel.com (10.22.229.17) 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 19:18:12 -0800 Received: from orsmsx610.amr.corp.intel.com (10.22.229.23) by ORSMSX608.amr.corp.intel.com (10.22.229.21) 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 19:18:12 -0800 Received: from orsedg603.ED.cps.intel.com (10.7.248.4) by orsmsx610.amr.corp.intel.com (10.22.229.23) 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 19:18:12 -0800 Received: from NAM02-BL2-obe.outbound.protection.outlook.com (104.47.38.56) by edgegateway.intel.com (134.134.137.100) 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 19:18:10 -0800 ARC-Seal: i=1; a=rsa-sha256; s=arcselector9901; d=microsoft.com; cv=none; b=KZ64YXZsv8BTh1MzUY3rANdksf2uyxb+LygjZgpyiQ4y/2ZkKMu2e7cT6f+hfHgMZk07jx+wFb+BZ3Fns77OZDj/xny8E2NOPhnqaLyni3Z0yu62VYEFYp9qDf/qZqYuUTJb1Hh6nel3yWTV+mayu2jzy2JxuTtNa4YNOrmBkXwor6XDPtMzu87V4misiwTaTIPVklzY9u2zYgEaLbzbiS3f2vqqS/Iv9CX+ZPPHYfSeV5CvD7JIZHG8TVO6AeKYLNJcL8WYn5kCoFrxPZPJ57EK9UJgna1sAnGAK/kFhFfwOacdkFodQykqLS7h0tL8nk7KIEOc9pO8KLfpJJsilQ== 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=SVVwpsSNqBbLnN2/D/RH8p7wstHDVRiutrRrPCqRhVo=; b=WWMy2LZjGA7cQRL9jW/JBtcbnGnqLWTV09NlLPwvffFzFPr2tAzURYsNtfVruIMCvbee8GZiwr7L4BpPAnb5w0aPxMdZfYF2IDKLUCMjjr7JM/UZgf1OVVaYQ/XypwjeKhnphbu1fN3HHj5ByFGxc8mX4iRBbqbqc4Gv7qpKvtT0kUHTpPjywWEv/VO9ScFMOLtQnv/q8TlunHISW8l+BWf1fv7NaZyQYhOaU1VcedjalKjOrkbdpcfdSRRAcNxtlLL+PbTI8QKZbW3MZcGmus8p2y5UMQey6xEhuwHvSacHgaSeAdk7zoy5QpM1NlouUvf7FfIKFDwgZrvYBgnr3g== 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=SVVwpsSNqBbLnN2/D/RH8p7wstHDVRiutrRrPCqRhVo=; b=YTEZBRSEhdUVKYRY4VWyZbkeZwhz46s4yP5RbYR+PaWQDsmtB94sF3hyuKjgp5hlMS+aLAUyUIhzKYa7ht3wBtR//q6nCXbhSfTWXxYSL9/Bdq5Jekx8Ppuq0YJM8/nW4BFfzzYiZ5oCKpX4oHnA5F7FPymotWPnq4mRHA0sLKI= Received: from DM6PR11MB4058.namprd11.prod.outlook.com (2603:10b6:5:193::13) by DM6PR11MB4529.namprd11.prod.outlook.com (2603:10b6:5:2ae::21) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.3654.13; Mon, 14 Dec 2020 03:18:08 +0000 Received: from DM6PR11MB4058.namprd11.prod.outlook.com ([fe80::409a:9424:2f64:d205]) by DM6PR11MB4058.namprd11.prod.outlook.com ([fe80::409a:9424:2f64:d205%3]) with mapi id 15.20.3654.025; Mon, 14 Dec 2020 03:18:07 +0000 From: "Zeng, Star" To: "Dong, Eric" , "Ni, Ray" , "devel@edk2.groups.io" CC: "Lou, Yun" , Laszlo Ersek , "Zeng, Star" 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: AQHWz6tF0OXAvF7St0288ZvGZVfukKn1xCUAgAAr66A= Date: Mon, 14 Dec 2020 03:18:07 +0000 Message-ID: References: <20201211104739.172-1-ray.ni@intel.com> In-Reply-To: Accept-Language: zh-CN, 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.198.147.202] x-ms-publictraffictype: Email x-ms-office365-filtering-correlation-id: da800ce9-bef4-4ced-b12f-08d89fdee107 x-ms-traffictypediagnostic: DM6PR11MB4529: x-ms-exchange-transport-forked: True x-microsoft-antispam-prvs: x-ms-oob-tlc-oobclassifiers: OLM:6108; x-ms-exchange-senderadcheck: 1 x-microsoft-antispam: BCL:0; x-microsoft-antispam-message-info: oNukxTneBcV6YGF+TsaL+fNL3KNAs9XW7mmK6GyuWgN0UDaSemNu/fOjP5K55rSHvOXzjTAKuIJX4NRDJnBVdb9/YNnLGBswh9wXh9+4Rq45QuHe/0PeRpTDwe5L9m4gJqPpNsTqtC0Kuv5CTpA7Cb1B59rLq9ZMAWCsgXNVB+PQRVCy7uxl8ijXGAzIeTIEGpqEMbJQ5TKyrl8MQcVSSlJEyLTEguJmK2iDDbOMzAxSWxncUUhvcllfKFh2eub7dmwNwFKnCKjRnGdgT9dpFBgSZYn460nn9rzkMy/lI7b0jXidTLsruPnUCGYc0OH/NNacKuiBlQtzTuf5d26g7Q== x-forefront-antispam-report: CIP:255.255.255.255;CTRY:;LANG:en;SCL:1;SRV:;IPV:NLI;SFV:NSPM;H:DM6PR11MB4058.namprd11.prod.outlook.com;PTR:;CAT:NONE;SFS:(4636009)(136003)(346002)(366004)(376002)(9686003)(66476007)(110136005)(5660300002)(64756008)(33656002)(186003)(86362001)(66946007)(54906003)(2906002)(4326008)(26005)(66556008)(76116006)(66446008)(52536014)(83380400001)(53546011)(8676002)(6506007)(7696005)(71200400001)(8936002)(508600001)(107886003)(55016002);DIR:OUT;SFP:1102; x-ms-exchange-antispam-messagedata: =?us-ascii?Q?WxBfH/GKCezN3VHvfa5nll8QBx21Tb1ugpX4Y4Zsybw7Ju2VTouSxb2qg4Ta?= =?us-ascii?Q?dgwCXSPWdGWsNsQfLgv9qDAJFO8T+qztKPcxFEu6oDlXvogtqYIdeZUd6QFh?= =?us-ascii?Q?8Ysz6P9yBxUrkyn8ZqO5T3TfXBDSgRs+hAfq00JAjQYhJ40Ne9gqCvdr5LaQ?= =?us-ascii?Q?z0LnDCawuhxlp5QFeqpu6IEeO9PQsR2Ko6F5Foa7kD+AhlgiGj6yXKTkYZW2?= =?us-ascii?Q?GNVagGsinv8EPGvslUFxbkJQfFR1w6oTsldmLDl6bLbW6Fyg5h3S1WtonHtj?= =?us-ascii?Q?JfJD7i4zYqjLfH13OfbdknQRk9RHAEQLaAn8B46l3BpA+rMmgmisen2BOC/5?= =?us-ascii?Q?yCZzgwTBl1vya2oBx15YGtxfpniFNtzaJ9VF7q3fCXro3yjiFurYkEUEaTJk?= =?us-ascii?Q?MzEX8yQJa1epI7Mpx9/qzdxAx4dqoZLhPGLcAhopK28dAi4bgW+89A+KO7+0?= =?us-ascii?Q?9tECmdv3Rr6DxEIL//+tN9ssSbYzTC/0IIMEy6ByCOl6YUosigQZ8URzHMxf?= =?us-ascii?Q?WgBGkesCxCeCE+nqKPzsILs/2Hr5FJ/5nMoguJgGe/Q7uSdw7K4MaRVMy1MI?= =?us-ascii?Q?cqLLCMqXny+sl9LtlwXTojF7/e+C4+JX1BHn5OBx2TckdDdFPjYDaBhbuTsV?= =?us-ascii?Q?1pu6Rrl18MS2T2x84H2AANs/qkPzLItuCCqazoBoKj9rvibFiXGTRtjdUlPn?= =?us-ascii?Q?/CJxpU3lVUkzoDDD6X4TDJRyOCYRrpvpH2aSfEdb72tcPyOyWoxiJSpcPFP/?= =?us-ascii?Q?xIoeXRp660DiYgSjb7gh4GBMBglurT7Gj/dUaWV8X/MD/q3UbJTO5uEhc2bP?= =?us-ascii?Q?NMLCgoXz0q3C3ACDV/yXcQWjCFOvCye9jlqToS5NKU8AA3t/hPPWYmamzz89?= =?us-ascii?Q?hPaoZqKKSwUxKr39ftF5eTGBJxdHb2lJDv09ab68o2/fZ2uOZ1nd81OW1HyH?= =?us-ascii?Q?GR+pjAlkZEC1E/aHBIF2L6/fd26IJRU6nubxdfbNeLA=3D?= MIME-Version: 1.0 X-MS-Exchange-CrossTenant-AuthAs: Internal X-MS-Exchange-CrossTenant-AuthSource: DM6PR11MB4058.namprd11.prod.outlook.com X-MS-Exchange-CrossTenant-Network-Message-Id: da800ce9-bef4-4ced-b12f-08d89fdee107 X-MS-Exchange-CrossTenant-originalarrivaltime: 14 Dec 2020 03:18:07.9119 (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: g98Dri8UJXFFtcjNEVe3HwEbItv03cziSITrBHG+TbCOurjpzakX59zyV9QjhvDNZEhfLoP+2wLm/+0X5NS2iw== X-MS-Exchange-Transport-CrossTenantHeadersStamped: DM6PR11MB4529 Return-Path: star.zeng@intel.com X-OriginatorOrg: intel.com Content-Language: en-US Content-Type: text/plain; charset="us-ascii" Content-Transfer-Encoding: quoted-printable Reviewed-by: Star Zeng -----Original Message----- From: Dong, Eric =20 Sent: Monday, December 14, 2020 8:41 AM To: Ni, Ray ; devel@edk2.groups.io Cc: Zeng, Star ; Lou, Yun ; Laszlo = Ersek Subject: RE: [PATCH V2] UefiCpuPkg/CpuFeature: reduce time complexty to cal= c CpuInfo.First 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