From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from mga18.intel.com (mga18.intel.com [134.134.136.126]) by mx.groups.io with SMTP id smtpd.web11.3848.1607503723331048680 for ; Wed, 09 Dec 2020 00:48:43 -0800 Authentication-Results: mx.groups.io; dkim=pass header.i=@intel.onmicrosoft.com header.s=selector2-intel-onmicrosoft-com header.b=B5S8qIQE; spf=pass (domain: intel.com, ip: 134.134.136.126, mailfrom: star.zeng@intel.com) IronPort-SDR: jWLxwuV+awEeom/9OPXTpZkhJF3tBVon3dtwWlLd/B3253TNsuUGLY6NAsNeL+wOQcSLcyQcNZ fSxLYwDIXxVA== X-IronPort-AV: E=McAfee;i="6000,8403,9829"; a="161804398" X-IronPort-AV: E=Sophos;i="5.78,405,1599548400"; d="scan'208";a="161804398" Received: from fmsmga003.fm.intel.com ([10.253.24.29]) by orsmga106.jf.intel.com with ESMTP/TLS/ECDHE-RSA-AES256-GCM-SHA384; 09 Dec 2020 00:48:42 -0800 IronPort-SDR: n6h9bj8j88KXjJahxU65lg1mUIVi8OTg4LvtMpIiPWxdakUjlKo/s/uilyIShn3dpOK3gTNG5i y1geMJajjSmw== X-ExtLoop1: 1 X-IronPort-AV: E=Sophos;i="5.78,405,1599548400"; d="scan'208";a="376264618" Received: from fmsmsx604.amr.corp.intel.com ([10.18.126.84]) by FMSMGA003.fm.intel.com with ESMTP; 09 Dec 2020 00:48:42 -0800 Received: from fmsmsx607.amr.corp.intel.com (10.18.126.87) by fmsmsx604.amr.corp.intel.com (10.18.126.84) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256) id 15.1.1713.5; Wed, 9 Dec 2020 00:48:42 -0800 Received: from fmsedg602.ED.cps.intel.com (10.1.192.136) by fmsmsx607.amr.corp.intel.com (10.18.126.87) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_128_GCM_SHA256) id 15.1.1713.5 via Frontend Transport; Wed, 9 Dec 2020 00:48:42 -0800 Received: from NAM11-CO1-obe.outbound.protection.outlook.com (104.47.56.168) by edgegateway.intel.com (192.55.55.71) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.1.1713.5; Wed, 9 Dec 2020 00:48:41 -0800 ARC-Seal: i=1; a=rsa-sha256; s=arcselector9901; d=microsoft.com; cv=none; b=lEzYP9Je75ax/Vz7eb6wI9676tNRJjY041i7iORvOUcIn0Rkk3AOQr9BccGXEoojtu2SYB5kWMNenYPgSUc7D3q8qNJDcTwZC3vIf/cfTtFRzoJRAlwG7S0AYrE2ce77CZlNqPf3hFhVk1z+jBWmcf2dhrBrNQ2dicoEV2Y1WUS9xbvM72TfyMEQ5bxqOw4E6yVtd914LKGXI9bzLGSFx0pFCgjWnMsADtMJZc/UzW/GHfz8/I/G82lTlUq36/ZmPo70XO0cBUnYsjOFFH7oWCh7L4sr6D4KbF13XFicdTcg+JEToXWtd9nMmuEDtnM+V0njsIfSEL1zhldfMtNgDA== 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=tBLVodxp00ZUA1lTKenbqyWVtGnKSoEqbaCdXR4RD5w=; b=TtBjkq10l4IAqiouQ9aSX9AppWUjDR6ncd3zai0BET8gNa23noUsoRYCdtBpu5AknrKkodRXShPIdbKmozkc8SEYh4GnK2d5usbycsmtOr9A6p437sEiIiUyDlX3lkT97D8UnqB+brwE/1JhC4aHZ3LOdK+Qxhfj8M4T7j1RYcGk1riXiaQHAc4w+5IJlD5qQKmDO4YEXciItFNiVIDTlP+5TNvjcbt+VxmTRLqkbMI7AvwR/bX3WjNR5Sj1cF5dUU7wNPtJtQAKsgjIgB1QXWAEGV4GqCshxE+oVU9YF2W5KxhDTc4SRL0tlf+0+RsTjH3Tb2hC/F8JQYtydD3ofw== 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=tBLVodxp00ZUA1lTKenbqyWVtGnKSoEqbaCdXR4RD5w=; b=B5S8qIQENlISqrNefSDHXzmyjCdGhd7amUm57zunNeB6sYBcRWlqZLeYVz/p983uiulB79jo+uQhxRunSWVxpW8MAHSaD6ubO7FK5+u+wr5uxdYVOBRz0R+U/2QxE2jX093DF7oJ8g4mbv/EOarKnRKzKdxWvmGUeKdiGGEVgw8= Received: from DM6PR11MB4058.namprd11.prod.outlook.com (2603:10b6:5:193::13) by DM5PR11MB1643.namprd11.prod.outlook.com (2603:10b6:4:b::16) with Microsoft SMTP Server (version=TLS1_2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id 15.20.3654.12; Wed, 9 Dec 2020 08:48:41 +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.013; Wed, 9 Dec 2020 08:48:40 +0000 From: "Zeng, Star" To: "Ni, Ray" , "devel@edk2.groups.io" CC: "Dong, Eric" , "Lou, Yun" , Laszlo Ersek , "Zeng, Star" Subject: Re: [PATCH] UefiCpuPkg/CpuFeature: reduce time complexty to calc CpuInfo.First Thread-Topic: [PATCH] UefiCpuPkg/CpuFeature: reduce time complexty to calc CpuInfo.First Thread-Index: AQHWzXNNDf3Wr74jB0GF2/w9GDUrxanudJyQ Date: Wed, 9 Dec 2020 08:48:40 +0000 Message-ID: References: <20201208150142.1894-1-ray.ni@intel.com> In-Reply-To: <20201208150142.1894-1-ray.ni@intel.com> 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.102.204.36] x-ms-publictraffictype: Email x-ms-office365-filtering-correlation-id: 10a1a41f-fd7e-4c88-bd85-08d89c1f3a5b x-ms-traffictypediagnostic: DM5PR11MB1643: x-ms-exchange-transport-forked: True x-microsoft-antispam-prvs: x-ms-oob-tlc-oobclassifiers: OLM:8273; x-ms-exchange-senderadcheck: 1 x-microsoft-antispam: BCL:0; x-microsoft-antispam-message-info: 38EVIFfXAkl7fqMXBVz9OGUi45lnxPkUjEXMdk6uadIGsGxDLIzSjy+t1L7yP+rZSBEvzkhrP0xAzStT3LeO9uHIKuRLU4EOHF+u5gCQUpoybhrdaiA/1YMvIqBY6Z/P3hbNKt4c5Qaaq+lbAdhRUc0/rRk28O6i1u2p3hd+df0TAwtexn78lOpGma+QgN92UWcrfI8dbco+cFNFaeViNXiUKdW5yjusizFpMyeubSsgHw46Jgjpvn27CRVBWTiOzrxVGLehJcmvFwqwHQ0e1olz78zdJwS2P5V+K3uvc2iGT4lzI07SbDY7Ctc633KM25jXEzdA+pW1rV+Am/Au5si5q5ebO2Q434uJ+yqF4r57ZZVTsgOqqODV/xfSnMlt 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)(376002)(366004)(136003)(346002)(66946007)(66446008)(66556008)(5660300002)(66476007)(26005)(52536014)(508600001)(64756008)(4326008)(71200400001)(186003)(107886003)(2906002)(83380400001)(8676002)(86362001)(6506007)(54906003)(7696005)(33656002)(53546011)(8936002)(55016002)(9686003)(76116006)(110136005)(21314003);DIR:OUT;SFP:1102; x-ms-exchange-antispam-messagedata: =?us-ascii?Q?sbHr3JT0Rp0sP5GJtdlmvBVzBM7jSA777ub9ciCPTbpSKAHVtmnIFPvlTeqX?= =?us-ascii?Q?aeYVvJsfxE1hUi8+W0U07c2zCtJj7riIDm9jHu02TJ19hSUqS8qx4Mj1YSOi?= =?us-ascii?Q?QmVRq+LiQbZxXlUuiN0Asa3HKwdmywAA00Y5lGvffB7kDfR0JWIc0lVz1oCM?= =?us-ascii?Q?qUzQ5rTshVcOEaYckEd1Rglkef1YZVpHF1rIOEDZ7ZMzmSbZGLDcm3N2/fdK?= =?us-ascii?Q?RhRwPKgTEiUE1q10hc7JsbDWaY02AIvv3tbNUvc89glIKOyqN2S7dESUG8ai?= =?us-ascii?Q?/rf1P9BYLXSSuzvL/F3sx3KjfwQFqs8CrpBeoa5N8UJPN+k0RzyZOfHI9U2M?= =?us-ascii?Q?HLda3l7Xbs6DnqeY49D5dgWDSJzXPszn5zcBM86FKepr6GUFyiulUReZIY9h?= =?us-ascii?Q?7KV9RTPstjjdrV8wR0g0NfP8FoLOCSLH1iRiCYdaBpmeDYUymkwzHGze6p1+?= =?us-ascii?Q?bJ2tll1ZRTmA0d/Cm8+hIZQkpu/RrHns5QMFA+x73hvB0U0Ve4vDcdjUcao7?= =?us-ascii?Q?gOiltKAgme98asz9BC5fOSmOW/TKg5VJcdw8EZLf0gWY7hSeQpnP8J0u+n0+?= =?us-ascii?Q?8Ar9CrqaM+jIDSbegMqybQFaamyHCs4MVJWBF3rAC08f4M178ipM+CiQm5C5?= =?us-ascii?Q?e/77KCT2rdpMJo2eRz/j5ZMCAC+Q0a7PR93J8u80CnukTPTZuqUglSS01yFT?= =?us-ascii?Q?r1oV3ew7XejCuMOMHuSuYACeuXPdJUzE1uKdkqPvhd2wtwk+AhRp8KDcgh9J?= =?us-ascii?Q?mwwwcYTXtooKyHrGCRaQAEAh1AsZnKzXxIujG//X38hn45M7pPYSCiuHozy7?= =?us-ascii?Q?FCQrgau4NUxHai0cvyrfy2KQGhK2/FS1h3vV5e4uRdlSMs5zkBpdEmvThOqI?= =?us-ascii?Q?6zz2x0i4rgzmgbXCOiuIh1DGdTU6+04sQqB2wzXp7dGFnJf2K6YSjKFjQU9a?= =?us-ascii?Q?tjWTLnwuM7OqjDMDgVuMUBXJJ26w4Tum7mSLOKolT1g=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: 10a1a41f-fd7e-4c88-bd85-08d89c1f3a5b X-MS-Exchange-CrossTenant-originalarrivaltime: 09 Dec 2020 08:48:40.8975 (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: rv0vuWBO9+ypuslPLCwrGJHjv9WARO6s8yoLH3unEm5v6drJLABs4bGZDzPfiPCDUnSdY5DQOHlFAINRexKEgw== X-MS-Exchange-Transport-CrossTenantHeadersStamped: DM5PR11MB1643 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 Only one minor comment inline, other parts look good to me. > -----Original Message----- > From: Ni, Ray > Sent: Tuesday, December 8, 2020 11:02 PM > To: devel@edk2.groups.io > Cc: Dong, Eric ; Zeng, Star ; > Lou, Yun ; Laszlo Ersek > Subject: [PATCH] UefiCpuPkg/CpuFeature: reduce time complexty to calc > CpuInfo.First >=20 > CpuInfo.First stores whether the current thread belongs to the first > package in the platform, first core in a package, first thread in a > core. >=20 > But the time complexity of original algorithm to calculate the > CpuInfo.First is O (n) * O (p) * O (c). > n: number of processors > p: number of packages > c: number of cores per package >=20 > The patch trades time with space by storing the first package, first > core per package, first thread per core in an array. > The time complexity becomes O (n). >=20 > Signed-off-by: Ray Ni > Cc: Eric Dong > Cc: Star Zeng > Cc: Yun Lou > Cc: Laszlo Ersek > --- > .../CpuFeaturesInitialize.c | 87 ++++++++----------- > 1 file changed, 36 insertions(+), 51 deletions(-) >=20 > diff --git > a/UefiCpuPkg/Library/RegisterCpuFeaturesLib/CpuFeaturesInitialize.c > b/UefiCpuPkg/Library/RegisterCpuFeaturesLib/CpuFeaturesInitialize.c > index d4a576385f..d21a1eaf38 100644 > --- a/UefiCpuPkg/Library/RegisterCpuFeaturesLib/CpuFeaturesInitialize.c > +++ b/UefiCpuPkg/Library/RegisterCpuFeaturesLib/CpuFeaturesInitialize.c > @@ -105,7 +105,10 @@ CpuInitDataInitialize ( > EFI_CPU_PHYSICAL_LOCATION *Location; >=20 > UINT32 PackageIndex; >=20 > UINT32 CoreIndex; >=20 > - UINT32 First; >=20 > + UINTN Pages; >=20 > + UINT32 FirstPackage; >=20 > + UINT32 *FirstCore; >=20 > + UINT32 *FirstThread; >=20 > ACPI_CPU_DATA *AcpiCpuData; >=20 > CPU_STATUS_INFORMATION *CpuStatus; >=20 > UINT32 *ThreadCountPerPackage; >=20 > @@ -236,74 +239,56 @@ CpuInitDataInitialize ( >=20 >=20 > // >=20 > // Initialize CpuFeaturesData->InitOrder[].CpuInfo.First >=20 > + // Use AllocatePages () instead of AllocatePool () because pool cannot= be > freed in PEI phase but page can. >=20 > // >=20 > + Pages =3D EFI_SIZE_TO_PAGES (CpuStatus->PackageCount * sizeof > (UINT32) + CpuStatus->PackageCount * CpuStatus->MaxCoreCount * sizeof > (UINT32)); >=20 > + FirstCore =3D AllocatePages (Pages); >=20 > + ASSERT (FirstCore !=3D NULL); >=20 > + FirstThread =3D FirstCore + CpuStatus->PackageCount; >=20 > + >=20 > + FirstPackage =3D MAX_UINT32; >=20 > + for (PackageIndex =3D 0; PackageIndex < CpuStatus->PackageCount; > PackageIndex++) { >=20 > + FirstCore[PackageIndex] =3D MAX_UINT32; >=20 > + for (CoreIndex =3D 0; CoreIndex < CpuStatus->MaxCoreCount; CoreIndex= ++) > { >=20 > + FirstThread[PackageIndex * CpuStatus->MaxCoreCount + CoreIndex] = =3D > MAX_UINT32; >=20 > + } >=20 > + } Could this code block be replaced by a SetMem32(xxx, xxx, MAX_UINT32) call? Thanks, Star >=20 >=20 >=20 > - // >=20 > - // Set First.Package for each thread belonging to the first package. >=20 > - // >=20 > - First =3D MAX_UINT32; >=20 > for (ProcessorNumber =3D 0; ProcessorNumber < NumberOfCpus; > ProcessorNumber++) { >=20 > Location =3D &CpuFeaturesData- > >InitOrder[ProcessorNumber].CpuInfo.ProcessorInfo.Location; >=20 > - First =3D MIN (Location->Package, First); >=20 > + >=20 > + FirstPackage =3D MIN (Location->Package, FirstPackag= e); >=20 > + FirstCore[Location->Package] =3D MIN (Location->Core, > FirstCore[Location->Package]); >=20 > + FirstThread[Location->Package * CpuStatus->MaxCoreCount + Location- > >Core] =3D MIN ( >=20 > + Location->Thread, >=20 > + FirstThread[Location->Package * CpuStatus->MaxCoreCount + > Location->Core] >=20 > + ); >=20 > } >=20 > + >=20 > for (ProcessorNumber =3D 0; ProcessorNumber < NumberOfCpus; > ProcessorNumber++) { >=20 > Location =3D &CpuFeaturesData- > >InitOrder[ProcessorNumber].CpuInfo.ProcessorInfo.Location; >=20 > - if (Location->Package =3D=3D First) { >=20 > + >=20 > + if (Location->Package =3D=3D FirstPackage) { >=20 > CpuFeaturesData->InitOrder[ProcessorNumber].CpuInfo.First.Package = =3D > 1; >=20 > } >=20 > - } >=20 >=20 >=20 > - // >=20 > - // Set First.Die/Tile/Module for each thread assuming: >=20 > - // single Die under each package, single Tile under each Die, single = Module > under each Tile >=20 > - // >=20 > - for (ProcessorNumber =3D 0; ProcessorNumber < NumberOfCpus; > ProcessorNumber++) { >=20 > + // >=20 > + // Set First.Die/Tile/Module for each thread assuming: >=20 > + // single Die under each package, single Tile under each Die, singl= e > Module under each Tile >=20 > + // >=20 > CpuFeaturesData->InitOrder[ProcessorNumber].CpuInfo.First.Die =3D 1; >=20 > CpuFeaturesData->InitOrder[ProcessorNumber].CpuInfo.First.Tile =3D 1= ; >=20 > CpuFeaturesData->InitOrder[ProcessorNumber].CpuInfo.First.Module =3D= 1; >=20 > - } >=20 >=20 >=20 > - for (PackageIndex =3D 0; PackageIndex < CpuStatus->PackageCount; > PackageIndex++) { >=20 > - // >=20 > - // Set First.Core for each thread in the first core of each package. >=20 > - // >=20 > - First =3D MAX_UINT32; >=20 > - for (ProcessorNumber =3D 0; ProcessorNumber < NumberOfCpus; > ProcessorNumber++) { >=20 > - Location =3D &CpuFeaturesData- > >InitOrder[ProcessorNumber].CpuInfo.ProcessorInfo.Location; >=20 > - if (Location->Package =3D=3D PackageIndex) { >=20 > - First =3D MIN (Location->Core, First); >=20 > - } >=20 > + if (Location->Core =3D=3D FirstCore[Location->Package]) { >=20 > + CpuFeaturesData->InitOrder[ProcessorNumber].CpuInfo.First.Core =3D= 1; >=20 > } >=20 > - >=20 > - for (ProcessorNumber =3D 0; ProcessorNumber < NumberOfCpus; > ProcessorNumber++) { >=20 > - Location =3D &CpuFeaturesData- > >InitOrder[ProcessorNumber].CpuInfo.ProcessorInfo.Location; >=20 > - if (Location->Package =3D=3D PackageIndex && Location->Core =3D=3D= First) { >=20 > - CpuFeaturesData->InitOrder[ProcessorNumber].CpuInfo.First.Core = =3D 1; >=20 > - } >=20 > + if (Location->Thread =3D=3D FirstThread[Location->Package * CpuStatu= s- > >MaxCoreCount + Location->Core]) { >=20 > + CpuFeaturesData->InitOrder[ProcessorNumber].CpuInfo.First.Thread = =3D > 1; >=20 > } >=20 > } >=20 >=20 >=20 > - for (PackageIndex =3D 0; PackageIndex < CpuStatus->PackageCount; > PackageIndex++) { >=20 > - for (CoreIndex =3D 0; CoreIndex < CpuStatus->MaxCoreCount; CoreIndex= ++) > { >=20 > - // >=20 > - // Set First.Thread for the first thread of each core. >=20 > - // >=20 > - First =3D MAX_UINT32; >=20 > - for (ProcessorNumber =3D 0; ProcessorNumber < NumberOfCpus; > ProcessorNumber++) { >=20 > - Location =3D &CpuFeaturesData- > >InitOrder[ProcessorNumber].CpuInfo.ProcessorInfo.Location; >=20 > - if (Location->Package =3D=3D PackageIndex && Location->Core =3D= =3D > CoreIndex) { >=20 > - First =3D MIN (Location->Thread, First); >=20 > - } >=20 > - } >=20 > - >=20 > - for (ProcessorNumber =3D 0; ProcessorNumber < NumberOfCpus; > ProcessorNumber++) { >=20 > - Location =3D &CpuFeaturesData- > >InitOrder[ProcessorNumber].CpuInfo.ProcessorInfo.Location; >=20 > - if (Location->Package =3D=3D PackageIndex && Location->Core =3D= =3D > CoreIndex && Location->Thread =3D=3D First) { >=20 > - CpuFeaturesData->InitOrder[ProcessorNumber].CpuInfo.First.Thre= ad > =3D 1; >=20 > - } >=20 > - } >=20 > - } >=20 > - } >=20 > + FreePages (FirstCore, Pages); >=20 > } >=20 >=20 >=20 > /** >=20 > -- > 2.27.0.windows.1