This is an archive of the discontinued LLVM Phabricator instance.

[llvm-readobj] Optimize printing stack sizes to linear time.
ClosedPublic

Authored by rahmanl on May 24 2021, 9:32 PM.

Details

Summary

Currently, each function name lookup is a linear iteration over all symbols defined in the object file which makes the total running time quadratic.

This patch optimizes the function name lookup by populating an address to index map upon the first function name lookup which is used to lookup each function name in O(1).

impact: For the clang binary built with -fstack-size-section, this improves the running time of llvm-readobj --stack-size from 7 minutes to 0.25 seconds.

Diff Detail

Event Timeline

rahmanl created this revision.May 24 2021, 9:32 PM
rahmanl retitled this revision from [llvm-readobj] Optimize function name lookup with `--stack-sizes` from quadratic to linear. to [llvm-readobj] Make printing stack sizes linear instead of quadratic..May 24 2021, 9:52 PM
rahmanl edited the summary of this revision. (Show Details)
rahmanl retitled this revision from [llvm-readobj] Make printing stack sizes linear instead of quadratic. to [llvm-readobj] Optimize printing stack sizes to linear time..
rahmanl published this revision for review.May 24 2021, 9:55 PM
Herald added a project: Restricted Project. · View Herald TranscriptMay 24 2021, 9:55 PM
jhenderson added inline comments.May 25 2021, 1:16 AM
llvm/tools/llvm-readobj/ELFDumper.cpp
5750–5751

Nit: add a blank line before the start of the loop and remove the one inside the loop.

5753–5754

Based on the function name, can't this clause be moved inside the earlier loop, where it was before? That would avoid adding unnecessary symbols to the table.

6724–6731

Seems like this change is unrelated?

rahmanl updated this revision to Diff 347782.May 25 2021, 2:25 PM

Address comments.

rahmanl updated this revision to Diff 347784.May 25 2021, 2:29 PM
rahmanl marked 3 inline comments as done.

Rename map to AddressToIndexMap.

rahmanl edited the summary of this revision. (Show Details)May 25 2021, 2:31 PM
jhenderson accepted this revision.May 26 2021, 12:34 AM

LGTM, with nit.

llvm/tools/llvm-readobj/ELFDumper.cpp
5723

You can delete this line now.

This revision is now accepted and ready to land.May 26 2021, 12:34 AM
rahmanl updated this revision to Diff 348066.May 26 2021, 1:10 PM
rahmanl marked an inline comment as done.
  • Remove (void) line.

Thanks for the review @jhenderson

This revision was landed with ongoing or failed builds.May 26 2021, 1:14 PM
This revision was automatically updated to reflect the committed changes.