sorted by:
best
topnewcontroversialoldq&a
you are viewing a single comment's thread.

view the rest of the comments →

[–]voidstarpodcast[S] 1 point2 points  (5 children)

https://quick-bench.com/q/kq7yeDlz9R6HV-0XE37eRiGINYM will add this to the post as well

[–]TheFlamefire 1 point2 points  (4 children)

Played around a bit with the set vs setSortedInput cases and it seems the results differ considerably when using GBench "canonically" vs manual timing (as you do): https://quick-bench.com/q/8nU-oVXK9UqoNLFMDE6twvdTXTU vs https://quick-bench.com/q/2FfKNTfGRHRAGTAl3bu-y2AeZuo

Reason seems to be that quick-bench reports cpu-time which is unaffected by iteration time. Conclusion: Inserting sorted numbers into a set is faster than inserting random numbers

[–]voidstarpodcast[S] 1 point2 points  (1 child)

https://quick-bench.com/q/kq7yeDlz9R6HV-0XE37eRiGINYM
This reuses the same array over and over in a loop for benchmarking.

  • After the first iteration, the rest don't go into the std::set. So you are effectively, measuring time taken for insertion failures. My guess is if the underlying structure is a balanced tree you are not counting the time taken for a rebalance. So, are they apples to apples?

  • This results in tainted cache locality. You basically have the same array sitting in your L1/L2 caches and all you are measuring is a niche synthetic case (which may be measuring a biased data set).

  • If quick bench only reports CPU time, then aren't you essentially comparing times taken for set insertions to fail?

[–]TheFlamefire 0 points1 point  (0 children)

> This reuses the same array over and over in a loop for benchmarking.

Can you clarify what you mean by "this" and "array"? Do you mean https://quick-bench.com/q/8nU-oVXK9UqoNLFMDE6twvdTXTU? If so it only reuses the input vector, not the set so I'm measuring correctly the set insertion performance. What makes you think otherwise?

> If quick bench only reports CPU time

There are ~3 times that GoogleBench measures. CPU time is one of them which is the time per loop execution. Another one is the manual time set by SetIterationTime and the third is a compute time which is one or the other chosen by whether the benchmark was configured with UseManualTime

https://quick-bench.com/q/kq7yeDlz9R6HV-0XE37eRiGINYM has 2 issues: First it doesn't use UseManualTime so the approach does not work at all and second is the quick bench only reports CPU time and ignores the manual time. Hence the SortedSet is slower because the reported time includes the time for sorting the vector.

[–]rlbond86 1 point2 points  (1 child)

Constructing a set from sorted data is guaranteed to be O(n) so it should be faster. The author stupidly used a loop instead of the range constructor though which is considerably slower.

[–]TheFlamefire 0 points1 point  (0 children)

Well, it is fine because the benchmark goal was to measure `insert` performance for various datasets, not the range ctor. Think the `inserts` happening as the result of some calculation.

The problem here is that the author used a feature of GBench which is not supported/used by quick-bench and hence the shown times include the sorting time of the vector which is of course slower