Page MenuHomePhabricator

[AutoFDO] Make call targets order deterministic for sample profil
ClosedPublic

Authored by wenlei on Aug 13 2019, 5:50 PM.

Details

Summary

StringMap is used for storing call target to frequency map for AutoFDO. However the iterating order of StringMap is non-deterministic, which leads to non-determinism in AutoFDO profile output. Now StringMap is changed to std::map for deterministic ordering and output.

Roundtrip test for text profile and binary profile is added.

Diff Detail

Repository
rL LLVM

Event Timeline

wenlei created this revision.Aug 13 2019, 5:50 PM
Herald added a project: Restricted Project. · View Herald TranscriptAug 13 2019, 5:50 PM
wenlei updated this revision to Diff 214997.Aug 13 2019, 5:52 PM

update description

Harbormaster completed remote builds in B36717: Diff 214997.
wmi added a comment.Aug 15 2019, 10:39 AM

Thanks for working on it.

llvm/include/llvm/ProfileData/SampleProf.h
146 ↗(On Diff #215416)

StringMap is more effient than std::map, but I assume the call targets list won't be very long so using std::map may not be an issue for compile time.

A problem of map is that if we want to sort CallTargetMap, I like to see the targets are sorted in count order (high to low) instead of alphabet order, so the dump will be more meaningful and we don't need sort the targets again using SortCallTargets in SampleProfile.cpp. But map cannot be internally sorted in its value_type.

How about leave CallTargetMap as a StringMap and make SortCallTargets a member function of SampleRecord and sort CallTargetMap before dumping and file writing?

wenlei marked an inline comment as done.Aug 15 2019, 4:20 PM
wenlei added inline comments.
llvm/include/llvm/ProfileData/SampleProf.h
146 ↗(On Diff #215416)

Thanks for review. Yeah, I think the number of targets is so small that efficiency benefit of StringMap is not important.

I would actually prefer the targets to be in alphabetical order - that makes the textual profile more 'stable' thus easy to compare (line by line) for count difference.

Besides, having to sort before dump moves the sorting responsibility to SampleProfileWriter for all difference formats, that's kind of duplicated, and doesn't prevent adding future writer without sorting before dumping.

SortCallTargets currently converts StringMap<uint64_t> to SmallVector<InstrProfValueData> first, then sort in place, if we extract a common Sort helper, we would need an extra copy to hold sorted result before converting to InstrProfValueData. The overhead won't be visible, but just feel it's not that clean either.

I don't have strong opinion, but do prefer to leave it as. Let me know if that is ok. Thanks.

wmi added inline comments.Aug 16 2019, 4:31 PM
llvm/include/llvm/ProfileData/SampleProf.h
146 ↗(On Diff #215416)

I would actually prefer the targets to be in alphabetical order - that makes the textual profile more 'stable' thus easy to compare (line by line) for count difference.

Even you order the targets in alphabetical order, there may be some targets showing up in one profile and disappearing in another profile -- causing a lot of churn for profile comparison. Usually the top call targets are what you concern the most. If the top call targets are scattered in a long list and their changes are amid some other targets's changes, it is easy to miss some of them.

wenlei updated this revision to Diff 215787.Aug 18 2019, 11:39 AM

Add getSortedCallTargets and SortCallTargets, per review feedback.

wmi accepted this revision.Tue, Aug 20, 11:28 AM

LGTM. Thanks!

llvm/lib/Transforms/IPO/SampleProfile.cpp
1299 ↗(On Diff #216167)

Nit: emplace may be better.

This revision is now accepted and ready to land.Tue, Aug 20, 11:28 AM
wenlei updated this revision to Diff 216235.Tue, Aug 20, 1:43 PM

address review feedback

wenlei marked 2 inline comments as done.Tue, Aug 20, 1:44 PM
wenlei added inline comments.
llvm/lib/Transforms/IPO/SampleProfile.cpp
1299 ↗(On Diff #216167)

Thanks for review. Now changed to emplace_back.

This revision was automatically updated to reflect the committed changes.
wenlei marked an inline comment as done.