Bug 254959 - Optimize WTF::Bitmap::forEachSetBit to use hardware intrinsics when available
Summary: Optimize WTF::Bitmap::forEachSetBit to use hardware intrinsics when available
Status: RESOLVED FIXED
Alias: None
Product: WebKit
Classification: Unclassified
Component: Web Template Framework (show other bugs)
Version: WebKit Nightly Build
Hardware: Unspecified Unspecified
: P2 Normal
Assignee: David Degazio
URL:
Keywords: InRadar
Depends on:
Blocks:
 
Reported: 2023-04-03 17:21 PDT by David Degazio
Modified: 2023-04-04 17:46 PDT (History)
1 user (show)

See Also:


Attachments

Note You need to log in before you can comment on or make changes to this bug.
Description David Degazio 2023-04-03 17:21:15 PDT
rdar://107584830

Currently, when iterating over the bits of a WTF::Bitmap, we manually iterate bit by bit. On x86_64 and ARM64 however, we should generally have access to bit-counting instructions in hardware. This means instead of doing one iteration for every 1 or 0 bit, we still do one iteration for every 1 bit, but skip up to a word of 0 bits at a time. This can massively reduce iteration time especially for sparse bitmaps.
Comment 1 David Degazio 2023-04-03 17:26:11 PDT
Pull request: https://github.com/WebKit/WebKit/pull/12349
Comment 2 EWS 2023-04-04 17:46:16 PDT
Committed 262602@main (316ccf979869): <https://commits.webkit.org/262602@main>

Reviewed commits have been landed. Closing PR #12349 and removing active labels.