This is an archive of the discontinued LLVM Phabricator instance.

Add benchmarks for sorting and heap functions.
ClosedPublic

Authored by sbenza on Nov 1 2018, 8:33 AM.

Details

Summary

Benchmarks for std::sort, std::stable_sort, std::make_heap,
std::sort_heap, std::pop_heap and std::push_heap.

The benchmarks are run with integers and strings, and with different
sorted input.

Event Timeline

sbenza created this revision.Nov 1 2018, 8:33 AM

Is there any value in breaking these out into one benchmark per file? I can see this file ever-growing as we add new benchmarks.

sbenza added a comment.Nov 1 2018, 9:08 AM

Is there any value in breaking these out into one benchmark per file? I can see this file ever-growing as we add new benchmarks.

No idea. I was just following the pattern of one benchmark .cpp per header. I think <algorithm> would be the only one with the potential bloat.

Is there any value in breaking these out into one benchmark per file? I can see this file ever-growing as we add new benchmarks.

I don't thin so. If you want to run a single benchmark in a file, you can use --benchmark_filter=<regex> to select it.

Otherwise, this LGTM.

benchmarks/algorithms.bench.cpp
327

For stable sort we want to explore more input sizes between 1 and 200. Currently stable sort is adaptive on the input size, switching to insertion sort for inputs smaller than 128. This seems to cause us to perform 2x worse for inputs of 100 elements. Early experiments show we perform better when the switch is around 16 to 32 elements, but we should have some coverage to prove it.

sbenza updated this revision to Diff 174666.Nov 19 2018, 12:09 PM

Changed the sizes to be denser in the lower end.

sbenza marked an inline comment as done.Nov 19 2018, 12:10 PM
EricWF accepted this revision.Nov 19 2018, 2:35 PM
This revision is now accepted and ready to land.Nov 19 2018, 2:35 PM
This revision was automatically updated to reflect the committed changes.