This is an archive of the discontinued LLVM Phabricator instance.

[dsymutil] Be smarter in caching calls to realpath
ClosedPublic

Authored by JDevlieghere on Feb 20 2018, 7:21 AM.

Details

Summary

Calling realpath is expensive but necessary to perform the uniqueing in
dsymutil. Although we already cached the results for every individual
file in the line table, we had reports of it taking 40 seconds of a 3.5
minute link.

This patch adds a second level of caching. When we do have to call
realpath, we cache its result for its parents path. We didn't replace
the existing caching, because it's fast (indexed) and saves us from
reading the line table for entries we've already seen.

For WebkitCore this results in a decrease of 11% in linking time: from
85.79 to 76.11 seconds (average over 3 runs).

Diff Detail

Event Timeline

JDevlieghere created this revision.Feb 20 2018, 7:21 AM
JDevlieghere edited the summary of this revision. (Show Details)
  • Remove logging
aprantl added inline comments.Feb 20 2018, 8:51 AM
llvm/tools/dsymutil/DwarfLinker.cpp
103

Can you add some of the explanatory text from the review description here? I.e., that realpath is expensive?

106

Resolve a path by calling realpath() ...

122

would it be more efficient to instead return the SmallString<256> directly, so it gets allocated by the caller and we avoid the copy upon return? I haven't looked at what the caller is doing with it.

125

I don't know how many entries this StringMap is going to have, but this looks expensive in terms of memory usage. Perhaps consider using a StringMap<std::string> instead?

1949

Might be more efficient to wrap this in an

#ifndef NDEBUG
#endif

block.

friss added inline comments.Feb 20 2018, 9:18 AM
llvm/tools/dsymutil/DwarfLinker.cpp
122

Returning a StringRef to a local variable is just confusing (now I see that this actually gets converted into a std::string so it's not incorrect, but it's still confusing). I would pass that StringPool to the resolver instead and intern the resolved path there. Then you can return just a StringRef to the permanent storage.

1945–1947

You can drop that backward compatibility stuff at the same time.

JDevlieghere marked 7 inline comments as done.

Thanks for the feedback, @aprantl and @friss!

llvm/tools/dsymutil/DwarfLinker.cpp
1949

I gave it a shot but I'm not convinced it's better :-)

aprantl added inline comments.Feb 20 2018, 10:17 AM
llvm/tools/dsymutil/DwarfLinker.cpp
1949

Does the call to getFileNameByIndex get optimized away? If yes then that's okay, otherwise I'd prefer the NDEBUG block.

aprantl added inline comments.Feb 20 2018, 10:23 AM
llvm/tools/dsymutil/DwarfLinker.cpp
125

This is now interning a temporary result that is getting interned again at the call site?

I think it would make more sense to intern the string that is entered into the StringMap and make it a StringMap<StringRef>. Or both? Fred?

davide requested changes to this revision.Feb 20 2018, 10:29 AM

The meta comment I have here is whether we need to segregate this is in dsymutil or expose that somewhere else (e.g. in Support/).
My feeling is that this utility could be of more general use for pathname resolution.
Among others, lldb calls realpath a bit, and maybe there are components in clang doing the same. Jonas, what do you think?

This revision now requires changes to proceed.Feb 20 2018, 10:29 AM
JDevlieghere marked 2 inline comments as done.Feb 20 2018, 11:07 AM

The meta comment I have here is whether we need to segregate this is in dsymutil or expose that somewhere else (e.g. in Support/).

As long as only dsymutil is the only user of this code, I think it should live here.

My feeling is that this utility could be of more general use for pathname resolution.

I agree and that's why I kept it as generic as possible. (Until I added the StringPool argument, which totally makes sense here)

Among others, lldb calls realpath a bit, and maybe there are components in clang doing the same. Jonas, what do you think?

Is there any particular call to realpath you're thinking about? From what I saw there weren't that many call sites that would benefit from this optimization. It works very well for dsymutil, because it's not uncommon for several object files to live in the same directory. If you're resolving unrelated paths, you end up worse because of the caching overhead.

But maybe I missed something... If that's the case I'm more than happy to move this into support!

llvm/tools/dsymutil/DwarfLinker.cpp
1949

No the call is what populates the File. It's just the return type that's checked. Wrapping it in an IFDEF looks weird because you split off the variable and the equals sign from the call. It breaks the flow of the code and adds two lines compared to one for the (void).

davide accepted this revision.Feb 20 2018, 1:05 PM

The meta comment I have here is whether we need to segregate this is in dsymutil or expose that somewhere else (e.g. in Support/).

As long as only dsymutil is the only user of this code, I think it should live here.

My feeling is that this utility could be of more general use for pathname resolution.

I agree and that's why I kept it as generic as possible. (Until I added the StringPool argument, which totally makes sense here)

Among others, lldb calls realpath a bit, and maybe there are components in clang doing the same. Jonas, what do you think?

Is there any particular call to realpath you're thinking about? From what I saw there weren't that many call sites that would benefit from this optimization. It works very well for dsymutil, because it's not uncommon for several object files to live in the same directory. If you're resolving unrelated paths, you end up worse because of the caching overhead.

Yes, what you say makes sense. My worry was that people don't really know of the utility if it's private to a file, but I guess it also doesn't really make sense to promote to a generic library until we have more than a use case (and currently, I have none :)
This is fine by me, happy to see this in when Adrian/Fred are happy with it.

This revision is now accepted and ready to land.Feb 20 2018, 1:05 PM
JDevlieghere marked an inline comment as done.
JDevlieghere edited the summary of this revision. (Show Details)

Originally I removed the first level of caching (based on the file index in the line table), which turned out to make things slower. That makes sense, because it's really fast (indexed) and because we don't have to read the line table again for files we've already seen.

Results of running dsymutil on WebkitCore:

LT caching only
85.76 real        72.54 user        12.99 sys
85.69 real        72.62 user        12.84 sys
85.93 real        72.66 user        13.11 sys

ParentPath caching only
97.68 real        92.57 user         4.94 sys
96.27 real        91.38 user         4.72 sys
96.67 real        91.64 user         4.82 sys

Both LT and ParentPath caching
75.84 real        70.81 user         4.77 sys
76.27 real        71.26 user         4.83 sys
76.22 real        71.33 user         4.75 sys
friss added inline comments.Feb 21 2018, 7:25 AM
llvm/tools/dsymutil/DwarfLinker.cpp
125

This is now interning a temporary result that is getting interned again at the call site?

I think it would make more sense to intern the string that is entered into the StringMap and make it a StringMap<StringRef>. Or both? Fred?

Yes, that's what I had mind, sorry for not having been clear. internString will provide permanent storage. I would never create a std::string, call internString on ResolvedPath and store a StringRef in the StringMap.

JDevlieghere added inline comments.Feb 21 2018, 7:33 AM
llvm/tools/dsymutil/DwarfLinker.cpp
125

I missed this comment, the string being interened again at the call site was a bug and has since been removed.

Unless I'm missing something, storing the interened string in the map makes no sense. We're not caching the full path, only the *parent path* which is shared between objects living in the same directory. That's the whole point of this (what is now caleld second level) cache. I've already updated the documentation to make this more explicit.

Please let me know if you think there's still an issue with the current implementation.

To avoid further confusion I'll let Fred clarify how to best manage the storage so we don't go off into different directions :-)

friss accepted this revision.Feb 21 2018, 10:39 AM
friss added inline comments.
llvm/tools/dsymutil/DwarfLinker.cpp
125

Of course, you're correct.

This revision was automatically updated to reflect the committed changes.