Page MenuHomePhabricator

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

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

Details

Summary

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
llvm/lib/Support/FoldingSet.cpp
90

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().

llvm/lib/Support/FoldingSet.cpp
90

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.