StatisticsMedian: Fix bug

[jmr]

Previously, this could return the wrong result when there was an even number of elements.

There were two nth_element calls. The second call could change elements in [center2, end]), which was where center pointed. Therefore, *center sometimes had the wrong value after the second nth_element call.

Rewrite to use max_element instead of the second call to nth_element. This avoids modifying the vector.

[LebedevRI]

Please add tests.

[jmr]

Please add tests.

The tests already exist. They failed sometimes. That's how I found it.

[LebedevRI]

Please add tests.

The tests already exist. They failed sometimes. That's how I found it.

Could you show the failure? Define sometimes? Was that failure non-deterministic? I've never seen it... This should be tested in https://github.com/google/benchmark/blob/dfc8a92abc88a9d630a9f8e01c678fedde4c3090/test/statistics_gtest.cc#L15-L19.

[jmr]

Could you show the failure?

[ RUN      ] StatisticsTest.Median
third_party/benchmark/test/statistics_gtest.cc:17: Failure
Expected equality of these values:
  benchmark::StatisticsMedian({1, 2, 3, 4})
    Which is: 3
  2.5

Define sometimes? Was that failure non-deterministic?

1/2 of the time, non-deterministically.

I've never seen it...

If you use libc++ with appropriate debug flags, you will see it. It will randomize [begin, nth) and (nth, end):

https://github.com/llvm/llvm-project/blob/5ec13535235d07eafd64058551bc495f87c283b1/libcxx/include/__algorithm/nth_element.h#L237

A longer sequence will decrease the probability of success factorially.

This should be tested in

https://github.com/google/benchmark/blob/dfc8a92abc88a9d630a9f8e01c678fedde4c3090/test/statistics_gtest.cc#L15-L19

.

It is.

[LebedevRI]

Ok, so the actual bug here is iterator invalidation, effectively. We should dereference center before calling std::nth_element() again, and then everything would still work. This was really not at all obvious from the patch description, maybe improve it a bit?

But this is still an improvement, so okay.

[jmr]

Ok, so the actual bug here is iterator invalidation, effectively.

No, the iterator is still valid. The problem is an assumption that nth_element(begin, nth, end) doesn't affect (nth, end).

[LebedevRI]

Ok, so the actual bug here is iterator invalidation, effectively.

No, the iterator is still valid. The problem is an assumption that nth_element(begin, nth, end) doesn't affect (nth, end).

I did say "effectively" - if you consider that the center is an iterator pointing to the median-ish element of the copy.

[dmah42]

thanks!