]> git.proxmox.com Git - mirror_edk2.git/commit
UefiCpuPkg/CpuFeature: reduce time complexty to calc CpuInfo.First
authorRay Ni <ray.ni@intel.com>
Fri, 11 Dec 2020 10:46:26 +0000 (18:46 +0800)
committermergify[bot] <37929162+mergify[bot]@users.noreply.github.com>
Mon, 14 Dec 2020 08:54:22 +0000 (08:54 +0000)
commit793c59da135be023b02ff93a57a3bb6b34044906
treea88488fa13d7b554b063d8da971d4c090932bf98
parent004f9776f47c4b8504bc9ce8dd584ad2d2017e23
UefiCpuPkg/CpuFeature: reduce time complexty to calc CpuInfo.First

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.

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

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).

Signed-off-by: Ray Ni <ray.ni@intel.com>
Reviewed-by: Eric Dong <eric.dong@intel.com>
Reviewed-by: Star Zeng <star.zeng@intel.com>
Cc: Yun Lou <yun.lou@intel.com>
Cc: Laszlo Ersek <lersek@redhat.com>
UefiCpuPkg/Library/RegisterCpuFeaturesLib/CpuFeaturesInitialize.c