1744052 - Large amount of time spent in texture_pack::guillotine::GuillotineAllocator::allocate

Status: VERIFIED FIXED

(Core :: Graphics: WebRender, defect)

Description

[Jeff Muizelaar [:jrmuizel]]

From https://codepen.io/noahblon/pen/wEfCz

https://share.firefox.dev/3xMOfCC

Runs much better in Chrome

Comment 1

[Nicolas Silva [:nical]]

The guillotine allocator stores the free rectangles three bins (by size) to speed up the search, but it looks like the bin sizes are tiny (1, 16, 32px, probably leftover from a distant past when this allocator was used for glyphs), so I suspect that all render tasks end up in the same bin. It would be useful to gather some rough stats about render task sizes and fix the bins accordingly.

If that's not enough we could consider a different data structure when the number of items is high.

Comment 2

[Nicolas Silva [:nical]]

Attachment: Bug 1744052 - Speed up the guillotine allocator. r=jrmuizel

• Store the free rect sizes with fewer bits in a spearate array to scan it faster (the bulk of the optimization is here)
• Round up the allocation sizes to reduce fragmentation a bit
• Remove the dead best-area-fit code, we can resurrect it later if need be.

With this patch the, the guillotine allocator almsot disappears from the profile.

Comment 3

[Pulsebot]

Pushed by [e-mail]:
https://hg.mozilla.org/integration/autoland/rev/7a2debb638b4
Speed up the guillotine allocator. r=jrmuizel

Comment 4

[Cristian Tuns]

https://hg.mozilla.org/mozilla-central/rev/7a2debb638b4

Comment 5

[Catalin Sasca, Desktop Test Engineering [:csasca]]

Reproduced the issue on Firefox 96.0a1 (2021-12-02) under macOS 11.6.2 by using the link provided in Comment 0.

The performance is improved on Firefox 97.0b9 and Nightly 98.0a1 (2022-01-30). Tests were performed on macOS 11.6.2, Windows 11 and Ubuntu 20.04.