This is an archive of the discontinued LLVM Phabricator instance.

[XRay] fix 99th percentile lookups by sorting the array correctly
ClosedPublic

Authored by pelikan on Jan 30 2018, 6:59 AM.

Diff Detail

Event Timeline

pelikan created this revision.Jan 30 2018, 6:59 AM
dberris requested changes to this revision.Jan 30 2018, 9:06 AM

Good catch! See other comment though.

tools/llvm-xray/xray-account.cc
244–248

I don't think this does the same thing as the original code did (or what it was intended to do).

std::nth_element doesn't actually sort the elements before the n'th element. It just guarantees that the element that would have been at the n'th position is there.

We still need the two other calls to std::nth_element that would find the correct median, 90pct, and 99pct.

This revision now requires changes to proceed.Jan 30 2018, 9:06 AM
pelikan updated this revision to Diff 131981.Jan 30 2018, 9:14 AM

nth_element doesn't actually order things on either side; put them back

pelikan edited the summary of this revision. (Show Details)Jan 30 2018, 9:15 AM
pelikan added inline comments.
tools/llvm-xray/xray-account.cc
244–248

Ah, it only partially sorts them. I mis-read that on the internet (first time I saw that function). Sorry, fixed.

pelikan marked an inline comment as done.Jan 30 2018, 9:16 AM
dberris added inline comments.Jan 30 2018, 9:20 AM
tools/llvm-xray/xray-account.cc
244–248

Okay, now the problem is that calls to nth_element may re-order the elements before the n'th element. :)

If you want to make this cleaner with less repetition (and less potential for error), you might consider breaking this out into a function that encapsulates the nth_element and lookup to return the actual value. Something like:

R.Median = findPercentile(Timings, MedianOff);
R.Pct90 = findPercentile(Timings, Pct90Off);
...

Then you can hide the nth_element call.

pelikan updated this revision to Diff 131984.Jan 30 2018, 9:30 AM
pelikan marked an inline comment as done.

reorder like it used to be

tools/llvm-xray/xray-account.cc
244–248

Hahaha, gentle reminder I should probably go home. :-)

Thanks, fixed so it looks more like it used to. No need for special functions here IMHO.

dberris accepted this revision.Jan 30 2018, 9:48 AM

LGTM

This revision is now accepted and ready to land.Jan 30 2018, 9:48 AM
This revision was automatically updated to reflect the committed changes.