Page MenuHomePhabricator

[Support] FoldingSetNodeID::AddString(): reserve memory

Authored by lebedev.ri on Jun 7 2020, 8:14 AM.



It is traditionally potentially very inefficient to not preallocate the memory,
but rely on reallocation every time you push something into vector.

For example, looking at unity build of RawSpeed
(-O3 -g0 -emit-llvm -Xclang -disable-llvm-optzns),
the memory story is as follows:

total runtime: 11.34s.
calls to allocation functions: 2694053 (237612/s)
temporary memory allocations: 645188 (56904/s)
peak heap memory consumption: 231.36MB
peak RSS (including heaptrack overhead): 397.39MB

Looking at details, FoldingSetNodeID::AddString() is noteworthy, frequently called and is allocation-heavy.

But it is quite obvious how many times we will push into Bits - we will push String.size() itself,
and then we will push once per every 4 bytes of String (padding last block).

And if we preallocate, we get:

total runtime: 11.20s.
calls to allocation functions: 2594704 (231669/s)
temporary memory allocations: 560004 (50000/s)
peak heap memory consumption: 231.36MB
peak RSS (including heaptrack overhead): 398.06MB

Which is a measurable win:

total runtime: -0.14s.                             #  -1.23 %
calls to allocation functions: -99349 (719920/s)   #  -3.69 %
temporary memory allocations: -85184 (617275/s)    # -13.2 % (!)
peak heap memory consumption: 0B
peak RSS (including heaptrack overhead): 0B
total memory leaked: 0B

Diff Detail

Event Timeline

lebedev.ri created this revision.Jun 7 2020, 8:14 AM
lebedev.ri edited the summary of this revision. (Show Details)Jun 7 2020, 8:21 AM
bkramer added inline comments.Jun 7 2020, 8:38 AM

We have divideCeil in MathExtras.

lebedev.ri updated this revision to Diff 269064.Jun 7 2020, 9:20 AM
lebedev.ri marked 2 inline comments as done.

Use divideCeil().


Ah, that is how it's called here. Thanks.

This revision is now accepted and ready to land.Jun 7 2020, 9:42 AM
This revision was automatically updated to reflect the committed changes.