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

[pelikan]

Summary

It was a copy-paste typo, sorting only to the 90th percentile twice.

[dberris]

Good catch! See other comment though.

tools/llvm-xray/xray-account.cc

243–245

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.

[pelikan]

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

[pelikan]

tools/llvm-xray/xray-account.cc

243–245

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

[dberris]

tools/llvm-xray/xray-account.cc

243–245

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]

reorder like it used to be

tools/llvm-xray/xray-account.cc

243–245

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]

LGTM

[pelikan]

sync

tools/llvm-xray/xray-account.cc

 ResultRow getStats(std::vector<uint64_t> &Timings) {
   assert(!Timings.empty());
   ResultRow R;
   R.Sum = std::accumulate(Timings.begin(), Timings.end(), 0.0);
   auto MinMax = std::minmax_element(Timings.begin(), Timings.end());
   R.Min = *MinMax.first;
   R.Max = *MinMax.second;
   auto MedianOff = Timings.size() / 2;
-  std::nth_element(Timings.begin(), Timings.begin() + MedianOff, Timings.end());
-  R.Median = Timings[MedianOff];
   auto Pct90Off = std::floor(Timings.size() * 0.9);
-  std::nth_element(Timings.begin(), Timings.begin() + Pct90Off, Timings.end());
-  R.Pct90 = Timings[Pct90Off];
   auto Pct99Off = std::floor(Timings.size() * 0.99);
-  std::nth_element(Timings.begin(), Timings.begin() + Pct90Off, Timings.end());
+  std::nth_element(Timings.begin(), Timings.begin() + Pct99Off, Timings.end());
+  R.Median = Timings[MedianOff];
+  R.Pct90 = Timings[Pct90Off];
   R.Pct99 = Timings[Pct99Off];
   R.Count = Timings.size();
   return R;
 }
 
 } // namespace
 
 template <class F>