Page MenuHomePhabricator

[CSSPGO] Fix an invalid hash table reference issue in the CS preinliner.
ClosedPublic

Authored by hoy on Jun 14 2021, 2:51 PM.

Details

Summary

We were using a StringMap object to store all profiles to be emitted. The object is basically an unordered hash table, therefore updating it in the process of trasvering it may cause issue since the underlying bucket array could change.

I'm also moving the csspgo-preinliner switch around so that no context tri will be constructed (by the constructor of CSPreInliner) when the switch is off.

Diff Detail

Event Timeline

hoy created this revision.Jun 14 2021, 2:51 PM
hoy requested review of this revision.Jun 14 2021, 2:51 PM
Herald added a project: Restricted Project. · View Herald TranscriptJun 14 2021, 2:51 PM
wlei added a comment.Jun 14 2021, 9:54 PM

Thanks for the fix!

llvm/lib/ProfileData/SampleProf.cpp
383–384

typo: Context

384

Do we need this?

384

typo: Context

wenlei added inline comments.Jun 14 2021, 10:27 PM
llvm/lib/ProfileData/SampleProf.cpp
373–374

Good catch - not sure how I come to incorrectly rely on the order of StringMap..

However the intention was to avoid extra copies of FunctionSamples as much as possible - these can large objects for copying.

I think what we could do is to collect a std::map<StringRef, StringRef> (old context to new context) for how we should update the StringMap, then iterate over the (top-down) ordered std::map to move profile to be keyed by correct context. This way we can avoid one extra copy for each FunctionSamples that needs to be moved.

hoy added inline comments.Jun 16 2021, 12:00 PM
llvm/lib/ProfileData/SampleProf.cpp
373–374

IIUC, we are trying to update the key of a promoted profile in ProfileMap. Since we cannot do that in place, we basically remove the current entry and add a new entry which just differs in the context key. If that's the case, not sure how to avoid copying a profile since the value field of an entry is not reference.

384

It's to make sure Ret is used in the release build where the following assert turns out nothing. Otherwise the ninja complaints Ret is defined by not used.

wenlei added inline comments.Jun 16 2021, 12:04 PM
llvm/lib/ProfileData/SampleProf.cpp
373–374

Here you're doing two copies, Map[A] -> temp -> Map[B]. With a std::map<StringRef, StringRef> for name mapping in top-down order, we should be able to do in-place copy Map[A] -> Map[B] by iterating over the name map?

hoy added inline comments.Jun 16 2021, 12:12 PM
llvm/lib/ProfileData/SampleProf.cpp
373–374

A and B are context strings, right? Why does the top-down order matter, say A is main->foo->bar and B is bar?

Yeah, we are using a intermediate temp. Should change ProfilesToBeAdded to StringMap<FunctionSamples&> and do the addition before the deletion.

wlei added inline comments.Jun 16 2021, 12:20 PM
llvm/lib/ProfileData/SampleProf.cpp
384

I see, how about we use find instead of try_emplace, like assert(ProfilesToBeAdded.find(ContextStr) == ProfilesToBeAdded.end() && "Context conflict during canonicalization");

wenlei added inline comments.Jun 16 2021, 12:31 PM
llvm/lib/ProfileData/SampleProf.cpp
373–374

This is my thought - two things blocks in-place copy: 1) iterating over StringMap while updating, which is solved by iterating over name mapping std::map<StringRef, StringRef>; 2) not overwriting items yet to be updated, this can be solved by ordering the updates so we make room for destination key of an update before we actually update.

hoy added inline comments.Jun 16 2021, 12:42 PM
llvm/lib/ProfileData/SampleProf.cpp
373–374

Still trying to follow. Say ProfileMap only has one entry {"main->foo->bar", Profile}. The context in Profile is "bar" and we are trying to update the key to "bar". With an extra std::map<StringRef, StringRef> , we would make something like {"main->foo->bar", "bar"}. Then how do we proceed next? Still figuring out how to avoid copying Profile.

384

That looks better but may slow down the assert compiler. Actually the (void) usage is quite common in the code base.

wlei added inline comments.Jun 16 2021, 12:47 PM
llvm/lib/ProfileData/SampleProf.cpp
384

Now I got it, thanks for the clarification.

hoy updated this revision to Diff 352529.Jun 16 2021, 1:08 PM

Addressing Wenlei and Lei's comments.

wenlei added inline comments.Jun 16 2021, 5:35 PM
llvm/lib/ProfileData/SampleProf.cpp
373–374

So the idea is to avoid copying out to a temp map then copying back. Now I see that you changed the temp map to use ref type. In that case, it's equally good as there's going to be only one copy.

400

With try_emplace, we're expecting some of the insertions will fail? In that case, such profile will be lost. Perhaps we still need to order the insertion so such failure will not happen.

hoy updated this revision to Diff 352751.Jun 17 2021, 9:13 AM

Addressing Wenlei's comment.

hoy added inline comments.Jun 17 2021, 6:09 PM
llvm/lib/ProfileData/SampleProf.cpp
400

Good point! Didn't realize that conflict could happen. Adjusted the insertion and deletion order.

hoy added a comment.Jun 17 2021, 6:13 PM

I compared the performance of the new algorithm and the old implementation with extra copying with a decent large profile. It turned out the old implementation was better in speed. This is due to the fewer string hashing operations on long context string involved in the new implementation. While the new implementation could be better with shorter context string and bigger function profiles, I'm inclined to use the old one since it's easy to read and maintain.

hoy updated this revision to Diff 352886.Jun 17 2021, 6:13 PM

Rolling back to first iteration.

hoy updated this revision to Diff 352887.Jun 17 2021, 6:14 PM

Updating D104267: [CSSPGO] Fix an invalid hash table reference issue in the CS preinliner.

wenlei accepted this revision.Jun 18 2021, 8:44 AM

I compared the performance of the new algorithm and the old implementation with extra copying with a decent large profile. It turned out the old implementation was better in speed. This is due to the fewer string hashing operations on long context string involved in the new implementation. While the new implementation could be better with shorter context string and bigger function profiles, I'm inclined to use the old one since it's easy to read and maintain.

Sounds good, thanks for giving it a try. LGTM with a minor comment.

llvm/lib/ProfileData/SampleProf.cpp
372–373

This no longer needs to be a set. I used set because of the erase operation. Now a vector would do.

373–374

May want to add a short comment explaining why an extra map (ProfilesToBeAdded) is needed, it seem not as trivial based on our discussions..

This revision is now accepted and ready to land.Jun 18 2021, 8:44 AM
hoy updated this revision to Diff 353044.Jun 18 2021, 10:34 AM

Addresing Wenlei's feedbacks.

This revision was landed with ongoing or failed builds.Jun 18 2021, 11:54 AM
This revision was automatically updated to reflect the committed changes.