Bug 254959

Summary:	Optimize WTF::Bitmap::forEachSetBit to use hardware intrinsics when available
Product:	WebKit	Reporter:	David Degazio <d_degazio>
Component:	Web Template Framework	Assignee:	David Degazio <d_degazio>
Status:	RESOLVED FIXED
Severity:	Normal	CC:	webkit-bug-importer
Priority:	P2	Keywords:	InRadar
Version:	WebKit Nightly Build
Hardware:	Unspecified
OS:	Unspecified

David Degazio

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

Attachments
Add attachment proposed patch, testcase, etc.

David Degazio

Comment 1 2023-04-03 17:26:11 PDT

Pull request: https://github.com/WebKit/WebKit/pull/12349

EWS

Comment 2 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.

Note You need to log in before you can comment on or make changes to this bug.