Skip to content

Use doubling allocation strategy for CF2_ArrStack.

Daniel McArdle requested to merge dmcardle/freetype:cf2_arrstack_allocations into master

Based on a chromium fuzzer timeout (crbug.com/1206181), I discovered that CF2_ArrStack spends a lot of CPU time on resizing.

Currently, cf2_arrstack_push grows the array by a fixed increment every time it runs out of space. As a result, we pay O(n) allocations to insert n elements.

Mathemagically, the doubling strategy improves the amortized cost to O(1) allocations (on average) when inserting n elements.

Merge request reports