Commit fbff065cdeb698370fd063a9b033b86cf5780fdd
2023-05-03T22:19:07
Replace GetResourceFromHashSet with map lookup Function GetResourceFromHashSet had linear time complexity because it was sweeping through the set until a resource with a matching ID was found. This change replaces hash sets with hash maps to get constant time lookup. This solves, among other things, O(N^2) time complexity for rendering scenes containing a large number of surfaces. Function GetResourceFromHashSet was consuming over 50% of all CPU time on the main thread of Chrome's GPU process while running the MotionMark 1.2 Images test. With this change, the benchmark score increases by 70% on an M1 MacBook running a PGO official build of Chrome. Bug: chromium:1435066 Change-Id: I895ac0141a91d324c63adec2c0efb8e030d9675b Reviewed-on: https://chromium-review.googlesource.com/c/angle/angle/+/4505950 Reviewed-by: Shahbaz Youssefi <syoussefi@chromium.org> Commit-Queue: Shahbaz Youssefi <syoussefi@chromium.org> Commit-Queue: Justin Novosad <junov@chromium.org> Reviewed-by: Igor Nazarov <i.nazarov@samsung.com>