This is an archive of the discontinued LLVM Phabricator instance.

[libc++][ranges] Implement `ranges::sort`.
ClosedPublic

Authored by var-const on Jun 10 2022, 9:33 PM.

Details

Diff Detail

Event Timeline

var-const created this revision.Jun 10 2022, 9:33 PM
Herald added a project: Restricted Project. · View Herald TranscriptJun 10 2022, 9:33 PM
Herald added subscribers: mgrang, mgorny. · View Herald Transcript
var-const requested review of this revision.Jun 10 2022, 9:33 PM
Herald added a project: Restricted Project. · View Herald Transcript
Herald added a reviewer: Restricted Project. · View Herald Transcript
var-const updated this revision to Diff 436101.Jun 10 2022, 9:36 PM

Slightly refactor the microoptimization

philnik requested changes to this revision.Jun 11 2022, 4:12 AM
philnik added a subscriber: philnik.

I really like the approach of using a custom comparator to apply the projections! That makes the implementation so much simpler than the way I would have done it. It already looks quite good, although I'm fearing that the custom comparator interferes with the branchless sorting for arithmetic types. If that is the case it should show up in the benchmarks.

libcxx/docs/Status/RangesAlgorithms.csv
76

A nice checkbox for a TODO

libcxx/include/__algorithm/ranges_sort.h
42–46

This is valid because sortable guarantees that the same object with different cv-ref qualifications compares identical. To be precise, sortable -> strict_weak_order -> relation -> predicate is the chain to follow for this information from https://en.cppreference.com/w/cpp/iterator/sortable.

48

This is unnecessary. ranges::next already checks for assignable_from<_Ip&, _Sp> and in that case just returns the sentinel.

63

This copies the comparator and projection. This should be catched by ranges_robust_against_copying_{comparators, projections}.pass.cpp.

libcxx/include/__algorithm/sort.h
576

using?

libcxx/test/support/almost_satisfies_types.h
330–335

Couldn't you simply use std::strong_ordering operator<=>(const Self&) const noexcept;?

383

I don't think there are any algorithms where you can pass a move-only comparator. Could you rename this to something like ComparatorNotCopyable? That would describe better what you are checking IMO.

philnik added inline comments.Jun 11 2022, 4:12 AM
libcxx/include/__algorithm/ranges_sort.h
38

Just a thought, and this should probably be done in a follow-up patch: Do we want to specialize this if is_same_v<_Comp, ranges::less> && is_same_v<_Proj, identity>? That is probably the normal use case and it would avoid code duplication. sort is quite large.

libcxx/test/std/algorithms/alg.sorting/alg.sort/sort/ranges.sort.pass.cpp
2

Could you also add a benchmark for ranges::sort and make sure the numbers are within margin of error compared to std::sort? It would be really bad if the ranges version performed worse than the classic STL version.

19

I don't think we're adding this to the synopsis in tests, but I don't really care either way.

42–47

I think you are missing SFINAE checks for sortable. I think it could be as simple as static_assert(!HasSortIt<const int*>) ditto for the range version.

76

This specifically checks with a borrowing range. I think I'd rather give it a lvalue-range and put the borrowing part into it's own test.

143

Is there a reason you aren't just using {} for the comparator?

149

Optional: Could you also check the returned iterator in all cases?

162

I think this should work. Same for you A struct above.

181

You are missing a convertible to bool test.

This revision now requires changes to proceed.Jun 11 2022, 4:12 AM
var-const updated this revision to Diff 436696.Jun 14 2022, 1:28 AM
var-const marked 13 inline comments as done.

Address comments.

I'm fearing that the custom comparator interferes with the branchless sorting for arithmetic types. If that is the case it should show up in the benchmarks.

@philnik Can you name a specific benchmark where this would show up? Perhaps we should just compare the assembly?

libcxx/include/__algorithm/ranges_sort.h
38

Thanks, it's an interesting idea -- will do in a follow-up.

42–46

This is very interesting, can you elaborate a bit? I couldn't easily see the part about cv-qualifications after reading through the chain on cppreference.

48

This version avoids having an additional variable altogether (including the unoptimized build). But I do think it's probably overkill, removed.

libcxx/test/std/algorithms/alg.sorting/alg.sort/sort/ranges.sort.pass.cpp
2

Added a benchmark, but it looks like there's too much random variation on my machine for a meaningful comparison. Perhaps you'd be interested to run the two benchmarks on your machine?

There are ~300 benchmarks (288, to be precise). About 3/4 of those are faster with the ranges version (even 10 times faster in a few instances), but about 1/4 are slower. Most of the slower ones are within 15-20% of the classic version, but some are 2.5-3 times slower (e.g. BM_Sort_string_SingleElement_16384). I don't see any obvious pattern and also no reason for the ranges version to outperform the non-ranges version -- either I'm doing something wrong, or these benchmarks contain too much random variation to do a meaningful comparison.

Pasting the raw numbers below. I'm omitting the name of the ranges benchmark (it's always equivalent to the non-ranges one) and wall time. The columns are: benchmark name / classic CPU time, ns / ranges CPU time, ns / ranges CPU time divided by classic CPU time, %

BM_Sort_uint32_Random_1	6.76	3.41	50.44%
BM_Sort_uint32_Random_4	15.3	4.09	26.73%
BM_Sort_uint32_Random_16	30.5	8.04	26.36%
BM_Sort_uint32_Random_64	51	14.9	29.22%
BM_Sort_uint32_Random_256	67.8	21.3	31.42%
BM_Sort_uint32_Random_1024	84.3	27.7	32.86%
BM_Sort_uint32_Random_16384	116	40.4	34.83%
BM_Sort_uint32_Random_262144	149	52.9	35.50%
BM_Sort_uint32_Ascending_1	6.7	3.44	51.34%
BM_Sort_uint32_Ascending_4	9.07	1.19	13.12%
BM_Sort_uint32_Ascending_16	4.13	0.713	17.26%
BM_Sort_uint32_Ascending_64	6	1.46	24.33%
BM_Sort_uint32_Ascending_256	4.99	1.58	31.66%
BM_Sort_uint32_Ascending_1024	4.76	1.51	31.72%
BM_Sort_uint32_Ascending_16384	4.66	1.44	30.90%
BM_Sort_uint32_Ascending_262144	4.68	1.45	30.98%
BM_Sort_uint32_Descending_1	6.85	3.41	49.78%
BM_Sort_uint32_Descending_4	9.09	1.41	15.51%
BM_Sort_uint32_Descending_16	37	3.04	8.22%
BM_Sort_uint32_Descending_64	11.4	2.32	20.35%
BM_Sort_uint32_Descending_256	10.4	2.44	23.46%
BM_Sort_uint32_Descending_1024	12.3	2.67	21.71%
BM_Sort_uint32_Descending_16384	12.5	2.47	19.76%
BM_Sort_uint32_Descending_262144	11.7	2.46	21.03%
BM_Sort_uint32_SingleElement_1	6.68	3.39	50.75%
BM_Sort_uint32_SingleElement_4	9.15	1.18	12.90%
BM_Sort_uint32_SingleElement_16	3.62	0.71	19.61%
BM_Sort_uint32_SingleElement_64	5.13	0.792	15.44%
BM_Sort_uint32_SingleElement_256	4.73	0.668	14.12%
BM_Sort_uint32_SingleElement_1024	4.66	0.626	13.43%
BM_Sort_uint32_SingleElement_16384	4.55	0.55	12.09%
BM_Sort_uint32_SingleElement_262144	4.56	0.548	12.02%
BM_Sort_uint32_PipeOrgan_1	6.65	3.44	51.73%
BM_Sort_uint32_PipeOrgan_4	9.09	1.24	13.64%
BM_Sort_uint32_PipeOrgan_16	11.9	1.61	13.53%
BM_Sort_uint32_PipeOrgan_64	36.4	3.66	10.05%
BM_Sort_uint32_PipeOrgan_256	15.4	2.69	17.47%
BM_Sort_uint32_PipeOrgan_1024	19.6	3.31	16.89%
BM_Sort_uint32_PipeOrgan_16384	24.5	3.83	15.63%
BM_Sort_uint32_PipeOrgan_262144	30.1	4.48	14.88%
BM_Sort_uint32_QuickSortAdversary_1	6.73	3.38	50.22%
BM_Sort_uint32_QuickSortAdversary_4	9.19	1.17	12.73%
BM_Sort_uint32_QuickSortAdversary_16	4.12	0.708	17.18%
BM_Sort_uint32_QuickSortAdversary_64	62.1	8.71	14.03%
BM_Sort_uint32_QuickSortAdversary_256	116	11.1	9.57%
BM_Sort_uint32_QuickSortAdversary_1024	176	29.3	16.65%
BM_Sort_uint32_QuickSortAdversary_16384	249	51.7	20.76%
BM_Sort_uint32_QuickSortAdversary_262144	306	58	18.95%
BM_Sort_uint64_Random_1	6.84	3.66	53.51%
BM_Sort_uint64_Random_4	15.7	4.36	27.77%
BM_Sort_uint64_Random_16	31.4	8.36	26.62%
BM_Sort_uint64_Random_64	51.2	15.1	29.49%
BM_Sort_uint64_Random_256	70.1	21.5	30.67%
BM_Sort_uint64_Random_1024	85.3	27.7	32.47%
BM_Sort_uint64_Random_16384	118	40.2	34.07%
BM_Sort_uint64_Random_262144	150	52.4	34.93%
BM_Sort_uint64_Ascending_1	6.92	3.4	49.13%
BM_Sort_uint64_Ascending_4	9.23	1.09	11.81%
BM_Sort_uint64_Ascending_16	3.65	0.721	19.75%
BM_Sort_uint64_Ascending_64	6.4	1.13	17.66%
BM_Sort_uint64_Ascending_256	5.17	1.27	24.56%
BM_Sort_uint64_Ascending_1024	4.99	1.2	24.05%
BM_Sort_uint64_Ascending_16384	4.7	1.14	24.26%
BM_Sort_uint64_Ascending_262144	4.62	1.13	24.46%
BM_Sort_uint64_Descending_1	6.67	3.61	54.12%
BM_Sort_uint64_Descending_4	9.25	1.45	15.68%
BM_Sort_uint64_Descending_16	36.9	2.86	7.75%
BM_Sort_uint64_Descending_64	12	2.12	17.67%
BM_Sort_uint64_Descending_256	11	2.03	18.45%
BM_Sort_uint64_Descending_1024	12.9	2.23	17.29%
BM_Sort_uint64_Descending_16384	12	2.06	17.17%
BM_Sort_uint64_Descending_262144	12	2.18	18.17%
BM_Sort_uint64_SingleElement_1	6.59	3.38	51.29%
BM_Sort_uint64_SingleElement_4	9.21	1.09	11.83%
BM_Sort_uint64_SingleElement_16	3.64	0.715	19.64%
BM_Sort_uint64_SingleElement_64	5.27	0.887	16.83%
BM_Sort_uint64_SingleElement_256	4.77	1.07	22.43%
BM_Sort_uint64_SingleElement_1024	4.73	0.923	19.51%
BM_Sort_uint64_SingleElement_16384	4.55	0.921	20.24%
BM_Sort_uint64_SingleElement_262144	4.59	0.938	20.44%
BM_Sort_uint64_PipeOrgan_1	6.65	3.6	54.14%
BM_Sort_uint64_PipeOrgan_4	9.06	1.14	12.58%
BM_Sort_uint64_PipeOrgan_16	12	1.41	11.75%
BM_Sort_uint64_PipeOrgan_64	36.8	3.47	9.43%
BM_Sort_uint64_PipeOrgan_256	15.4	2.56	16.62%
BM_Sort_uint64_PipeOrgan_1024	19.5	3.21	16.46%
BM_Sort_uint64_PipeOrgan_16384	24.4	3.78	15.49%
BM_Sort_uint64_PipeOrgan_262144	29.8	4.58	15.37%
BM_Sort_uint64_QuickSortAdversary_1	6.76	3.5	51.78%
BM_Sort_uint64_QuickSortAdversary_4	9.03	1.09	12.07%
BM_Sort_uint64_QuickSortAdversary_16	3.73	0.717	19.22%
BM_Sort_uint64_QuickSortAdversary_64	66.8	8.99	13.46%
BM_Sort_uint64_QuickSortAdversary_256	132	12	9.09%
BM_Sort_uint64_QuickSortAdversary_1024	189	30.5	16.14%
BM_Sort_uint64_QuickSortAdversary_16384	270	54.3	20.11%
BM_Sort_uint64_QuickSortAdversary_262144	326	68.2	20.92%
BM_Sort_pair<uint32, uint32>_Random_1	3.25	3.47	106.77%
BM_Sort_pair<uint32, uint32>_Random_4	5.67	5.91	104.23%
BM_Sort_pair<uint32, uint32>_Random_16	20.7	20.7	100.00%
BM_Sort_pair<uint32, uint32>_Random_64	31.2	30.5	97.76%
BM_Sort_pair<uint32, uint32>_Random_256	39.2	39.2	100.00%
BM_Sort_pair<uint32, uint32>_Random_1024	46.5	46.3	99.57%
BM_Sort_pair<uint32, uint32>_Random_16384	62.3	61.9	99.36%
BM_Sort_pair<uint32, uint32>_Random_262144	79.7	78.8	98.87%
BM_Sort_pair<uint32, uint32>_Ascending_1	3.19	4.15	130.09%
BM_Sort_pair<uint32, uint32>_Ascending_4	1.85	2.13	115.14%
BM_Sort_pair<uint32, uint32>_Ascending_16	2.42	2.46	101.65%
BM_Sort_pair<uint32, uint32>_Ascending_64	1.91	1.93	101.05%
BM_Sort_pair<uint32, uint32>_Ascending_256	1.99	2.02	101.51%
BM_Sort_pair<uint32, uint32>_Ascending_1024	1.91	1.96	102.62%
BM_Sort_pair<uint32, uint32>_Ascending_16384	1.82	1.87	102.75%
BM_Sort_pair<uint32, uint32>_Ascending_262144	1.82	1.85	101.65%
BM_Sort_pair<uint32, uint32>_Descending_1	3.2	3.71	115.94%
BM_Sort_pair<uint32, uint32>_Descending_4	2.56	2.56	100.00%
BM_Sort_pair<uint32, uint32>_Descending_16	5.45	5.26	96.51%
BM_Sort_pair<uint32, uint32>_Descending_64	4.35	3.94	90.57%
BM_Sort_pair<uint32, uint32>_Descending_256	3.79	3.52	92.88%
BM_Sort_pair<uint32, uint32>_Descending_1024	5.02	4.7	93.63%
BM_Sort_pair<uint32, uint32>_Descending_16384	4.78	4.5	94.14%
BM_Sort_pair<uint32, uint32>_Descending_262144	4.75	4.46	93.89%
BM_Sort_pair<uint32, uint32>_SingleElement_1	3.21	4.1	127.73%
BM_Sort_pair<uint32, uint32>_SingleElement_4	1.91	1.92	100.52%
BM_Sort_pair<uint32, uint32>_SingleElement_16	2.25	2.85	126.67%
BM_Sort_pair<uint32, uint32>_SingleElement_64	2.3	2.67	116.09%
BM_Sort_pair<uint32, uint32>_SingleElement_256	2.43	2.87	118.11%
BM_Sort_pair<uint32, uint32>_SingleElement_1024	2.3	2.71	117.83%
BM_Sort_pair<uint32, uint32>_SingleElement_16384	2.26	2.67	118.14%
BM_Sort_pair<uint32, uint32>_SingleElement_262144	2.27	2.66	117.18%
BM_Sort_pair<uint32, uint32>_PipeOrgan_1	3.18	3.63	114.15%
BM_Sort_pair<uint32, uint32>_PipeOrgan_4	2.18	2.21	101.38%
BM_Sort_pair<uint32, uint32>_PipeOrgan_16	5.27	5.14	97.53%
BM_Sort_pair<uint32, uint32>_PipeOrgan_64	5.65	5.64	99.82%
BM_Sort_pair<uint32, uint32>_PipeOrgan_256	7.51	7.46	99.33%
BM_Sort_pair<uint32, uint32>_PipeOrgan_1024	9.48	9.5	100.21%
BM_Sort_pair<uint32, uint32>_PipeOrgan_16384	10.6	10.6	100.00%
BM_Sort_pair<uint32, uint32>_PipeOrgan_262144	12.6	12.6	100.00%
BM_Sort_pair<uint32, uint32>_QuickSortAdversary_1	3.17	4.11	129.65%
BM_Sort_pair<uint32, uint32>_QuickSortAdversary_4	2.3	2.47	107.39%
BM_Sort_pair<uint32, uint32>_QuickSortAdversary_16	5.29	5.13	96.98%
BM_Sort_pair<uint32, uint32>_QuickSortAdversary_64	8.51	8.16	95.89%
BM_Sort_pair<uint32, uint32>_QuickSortAdversary_256	11.6	11.3	97.41%
BM_Sort_pair<uint32, uint32>_QuickSortAdversary_1024	14.1	13.3	94.33%
BM_Sort_pair<uint32, uint32>_QuickSortAdversary_16384	33.1	32.6	98.49%
BM_Sort_pair<uint32, uint32>_QuickSortAdversary_262144	38.3	37.9	98.96%
BM_Sort_tuple<uint32, uint64, uint32>_Random_1	3.48	4.36	125.29%
BM_Sort_tuple<uint32, uint64, uint32>_Random_4	6.27	6.57	104.78%
BM_Sort_tuple<uint32, uint64, uint32>_Random_16	25.6	24.6	96.09%
BM_Sort_tuple<uint32, uint64, uint32>_Random_64	38.2	35	91.62%
BM_Sort_tuple<uint32, uint64, uint32>_Random_256	45	41.1	91.33%
BM_Sort_tuple<uint32, uint64, uint32>_Random_1024	53.1	47.6	89.64%
BM_Sort_tuple<uint32, uint64, uint32>_Random_16384	67.8	60.3	88.94%
BM_Sort_tuple<uint32, uint64, uint32>_Random_262144	86.1	76.7	89.08%
BM_Sort_tuple<uint32, uint64, uint32>_Ascending_1	3.46	3.69	106.65%
BM_Sort_tuple<uint32, uint64, uint32>_Ascending_4	2.29	2.28	99.56%
BM_Sort_tuple<uint32, uint64, uint32>_Ascending_16	3.39	3.03	89.38%
BM_Sort_tuple<uint32, uint64, uint32>_Ascending_64	3.14	3.33	106.05%
BM_Sort_tuple<uint32, uint64, uint32>_Ascending_256	3.13	3.42	109.27%
BM_Sort_tuple<uint32, uint64, uint32>_Ascending_1024	3.08	3.34	108.44%
BM_Sort_tuple<uint32, uint64, uint32>_Ascending_16384	2.92	3.09	105.82%
BM_Sort_tuple<uint32, uint64, uint32>_Ascending_262144	3.11	3.24	104.18%
BM_Sort_tuple<uint32, uint64, uint32>_Descending_1	3.97	3.88	97.73%
BM_Sort_tuple<uint32, uint64, uint32>_Descending_4	3.93	3.28	83.46%
BM_Sort_tuple<uint32, uint64, uint32>_Descending_16	6.2	5.23	84.35%
BM_Sort_tuple<uint32, uint64, uint32>_Descending_64	5.26	4.64	88.21%
BM_Sort_tuple<uint32, uint64, uint32>_Descending_256	4.76	4.31	90.55%
BM_Sort_tuple<uint32, uint64, uint32>_Descending_1024	6.23	5.35	85.87%
BM_Sort_tuple<uint32, uint64, uint32>_Descending_16384	5.91	5.15	87.14%
BM_Sort_tuple<uint32, uint64, uint32>_Descending_262144	6.67	6.19	92.80%
BM_Sort_tuple<uint32, uint64, uint32>_SingleElement_1	3.5	3.69	105.43%
BM_Sort_tuple<uint32, uint64, uint32>_SingleElement_4	2.61	2.33	89.27%
BM_Sort_tuple<uint32, uint64, uint32>_SingleElement_16	3.43	3.31	96.50%
BM_Sort_tuple<uint32, uint64, uint32>_SingleElement_64	4.08	3.91	95.83%
BM_Sort_tuple<uint32, uint64, uint32>_SingleElement_256	4.35	4.29	98.62%
BM_Sort_tuple<uint32, uint64, uint32>_SingleElement_1024	4.17	4.18	100.24%
BM_Sort_tuple<uint32, uint64, uint32>_SingleElement_16384	3.8	3.79	99.74%
BM_Sort_tuple<uint32, uint64, uint32>_SingleElement_262144	3.83	3.84	100.26%
BM_Sort_tuple<uint32, uint64, uint32>_PipeOrgan_1	3.47	3.88	111.82%
BM_Sort_tuple<uint32, uint64, uint32>_PipeOrgan_4	2.46	2.52	102.44%
BM_Sort_tuple<uint32, uint64, uint32>_PipeOrgan_16	6.48	5.76	88.89%
BM_Sort_tuple<uint32, uint64, uint32>_PipeOrgan_64	7.46	6.55	87.80%
BM_Sort_tuple<uint32, uint64, uint32>_PipeOrgan_256	10.2	8.11	79.51%
BM_Sort_tuple<uint32, uint64, uint32>_PipeOrgan_1024	11.4	9.95	87.28%
BM_Sort_tuple<uint32, uint64, uint32>_PipeOrgan_16384	13	11.6	89.23%
BM_Sort_tuple<uint32, uint64, uint32>_PipeOrgan_262144	16	14.6	91.25%
BM_Sort_tuple<uint32, uint64, uint32>_QuickSortAdversary_1	3.49	3.69	105.73%
BM_Sort_tuple<uint32, uint64, uint32>_QuickSortAdversary_4	2.83	2.65	93.64%
BM_Sort_tuple<uint32, uint64, uint32>_QuickSortAdversary_16	6.3	5.21	82.70%
BM_Sort_tuple<uint32, uint64, uint32>_QuickSortAdversary_64	10.8	9.47	87.69%
BM_Sort_tuple<uint32, uint64, uint32>_QuickSortAdversary_256	15.4	12.7	82.47%
BM_Sort_tuple<uint32, uint64, uint32>_QuickSortAdversary_1024	23.4	19.5	83.33%
BM_Sort_tuple<uint32, uint64, uint32>_QuickSortAdversary_16384	47	41.4	88.09%
BM_Sort_tuple<uint32, uint64, uint32>_QuickSortAdversary_262144	54.5	46.3	84.95%
BM_Sort_string_Random_1	4.25	4.5	105.88%
BM_Sort_string_Random_4	16.7	16.4	98.20%
BM_Sort_string_Random_16	45.8	45.5	99.34%
BM_Sort_string_Random_64	71.1	69.8	98.17%
BM_Sort_string_Random_256	90.1	88.4	98.11%
BM_Sort_string_Random_1024	108	109	100.93%
BM_Sort_string_Random_16384	172	174	101.16%
BM_Sort_string_Random_262144	283	285	100.71%
BM_Sort_string_Ascending_1	4.23	4.8	113.48%
BM_Sort_string_Ascending_4	9.8	9.51	97.04%
BM_Sort_string_Ascending_16	16.6	16.8	101.20%
BM_Sort_string_Ascending_64	21.9	21.7	99.09%
BM_Sort_string_Ascending_256	21.4	21.1	98.60%
BM_Sort_string_Ascending_1024	21.1	20.9	99.05%
BM_Sort_string_Ascending_16384	38.7	35.1	90.70%
BM_Sort_string_Ascending_262144	45.4	43.6	96.04%
BM_Sort_string_Descending_1	4.23	4.89	115.60%
BM_Sort_string_Descending_4	11.8	13.2	111.86%
BM_Sort_string_Descending_16	25.3	26.4	104.35%
BM_Sort_string_Descending_64	29.7	30.7	103.37%
BM_Sort_string_Descending_256	27.3	29.6	108.42%
BM_Sort_string_Descending_1024	31.6	31.4	99.37%
BM_Sort_string_Descending_16384	46.5	47	101.08%
BM_Sort_string_Descending_262144	78.5	77.5	98.73%
BM_Sort_string_SingleElement_1	4.21	4.57	108.55%
BM_Sort_string_SingleElement_4	9.06	9.64	106.40%
BM_Sort_string_SingleElement_16	18.3	17.9	97.81%
BM_Sort_string_SingleElement_64	26.8	28.4	105.97%
BM_Sort_string_SingleElement_256	22.3	21.7	97.31%
BM_Sort_string_SingleElement_1024	19.5	20.1	103.08%
BM_Sort_string_SingleElement_16384	17.5	52.6	300.57%
BM_Sort_string_SingleElement_262144	19	48.2	253.68%
BM_Sort_string_PipeOrgan_1	4.18	6.79	162.44%
BM_Sort_string_PipeOrgan_4	10.3	14.1	136.89%
BM_Sort_string_PipeOrgan_16	25	29.7	118.80%
BM_Sort_string_PipeOrgan_64	37.5	39.2	104.53%
BM_Sort_string_PipeOrgan_256	45	45.7	101.56%
BM_Sort_string_PipeOrgan_1024	52.8	52.3	99.05%
BM_Sort_string_PipeOrgan_16384	72.4	138	190.61%
BM_Sort_string_PipeOrgan_262144	122	317	259.84%
BM_Sort_string_QuickSortAdversary_1	4.2	6.63	157.86%
BM_Sort_string_QuickSortAdversary_4	16.2	23	141.98%
BM_Sort_string_QuickSortAdversary_16	44.7	67.2	150.34%
BM_Sort_string_QuickSortAdversary_64	69.2	103	148.84%
BM_Sort_string_QuickSortAdversary_256	87.9	127	144.48%
BM_Sort_string_QuickSortAdversary_1024	106	157	148.11%
BM_Sort_string_QuickSortAdversary_16384	170	176	103.53%
BM_Sort_string_QuickSortAdversary_262144	269	263	97.77%
BM_Sort_float_Random_1	6.56	3.65	55.64%
BM_Sort_float_Random_4	15.1	4.92	32.58%
BM_Sort_float_Random_16	31.5	8.83	28.03%
BM_Sort_float_Random_64	51.7	15.4	29.79%
BM_Sort_float_Random_256	68.7	21.7	31.59%
BM_Sort_float_Random_1024	85.6	27.9	32.59%
BM_Sort_float_Random_16384	121	40	33.06%
BM_Sort_float_Random_262144	150	92	61.33%
BM_Sort_float_Ascending_1	6.6	11.4	172.73%
BM_Sort_float_Ascending_4	9.04	3.73	41.26%
BM_Sort_float_Ascending_16	3.71	2.82	76.01%
BM_Sort_float_Ascending_64	6.04	3.48	57.62%
BM_Sort_float_Ascending_256	4.99	2.86	57.31%
BM_Sort_float_Ascending_1024	4.74	2.24	47.26%
BM_Sort_float_Ascending_16384	4.59	1.85	40.31%
BM_Sort_float_Ascending_262144	4.58	1.64	35.81%
BM_Sort_float_Descending_1	6.54	5.87	89.76%
BM_Sort_float_Descending_4	9.03	2.34	25.91%
BM_Sort_float_Descending_16	37.8	5.22	13.81%
BM_Sort_float_Descending_64	11.5	2.77	24.09%
BM_Sort_float_Descending_256	10.3	2.65	25.73%
BM_Sort_float_Descending_1024	12.3	2.92	23.74%
BM_Sort_float_Descending_16384	11.8	2.65	22.46%
BM_Sort_float_Descending_262144	11.7	2.65	22.65%
BM_Sort_float_SingleElement_1	6.6	4.68	70.91%
BM_Sort_float_SingleElement_4	9	1.65	18.33%
BM_Sort_float_SingleElement_16	3.72	1.34	36.02%
BM_Sort_float_SingleElement_64	4.89	1.45	29.65%
BM_Sort_float_SingleElement_256	4.45	1.54	34.61%
BM_Sort_float_SingleElement_1024	4.42	1.41	31.90%
BM_Sort_float_SingleElement_16384	4.26	1.29	30.28%
BM_Sort_float_SingleElement_262144	4.26	1.31	30.75%
BM_Sort_float_PipeOrgan_1	6.88	5.76	83.72%
BM_Sort_float_PipeOrgan_4	9.05	1.5	16.57%
BM_Sort_float_PipeOrgan_16	12.4	1.92	15.48%
BM_Sort_float_PipeOrgan_64	38	3.96	10.42%
BM_Sort_float_PipeOrgan_256	15.8	2.39	15.13%
BM_Sort_float_PipeOrgan_1024	20.1	3.13	15.57%
BM_Sort_float_PipeOrgan_16384	25.1	3.52	14.02%
BM_Sort_float_PipeOrgan_262144	30.6	4.11	13.43%
BM_Sort_float_QuickSortAdversary_1	6.54	3.19	48.78%
BM_Sort_float_QuickSortAdversary_4	9.15	2.6	28.42%
BM_Sort_float_QuickSortAdversary_16	3.77	2.93	77.72%
BM_Sort_float_QuickSortAdversary_64	62.8	34.6	55.10%
BM_Sort_float_QuickSortAdversary_256	117	48.5	41.45%
BM_Sort_float_QuickSortAdversary_1024	177	121	68.36%
BM_Sort_float_QuickSortAdversary_16384	250	226	90.40%
BM_Sort_float_QuickSortAdversary_262144	307	249	81.11%
19

FWIW, I usually do. I think copy-pasting is easiest (not just to write, but also to maintain) and there doesn't seem to be a strong reason to omit these annotations.

42–47

Thanks!

76

Do you have a specific approach in mind? I think subrange is a borrowing range regardless of whether it's an lvalue or an rvalue.

162

Thanks, it works (as long as it's a member function -- defining friend functions in local classes is apparently not allowed).

libcxx/test/support/almost_satisfies_types.h
330–335

Thanks!

var-const updated this revision to Diff 436697.Jun 14 2022, 1:28 AM

Add forgotten file.

Fix the CI.

Thanks for working on this, a few comments.

libcxx/include/__algorithm/sort.h
572–574

I think it makes sense to keep the _RandomAccessIterator name for documentation here.

libcxx/test/std/algorithms/alg.sorting/alg.sort/sort/ranges.sort.pass.cpp
19

I usually don't see the since annotation in the synopsis here. However I don't mind so feel free to keep them.

202

Please add a test for the complexity.

var-const added inline comments.Jun 14 2022, 10:43 PM
libcxx/test/std/algorithms/alg.sorting/alg.sort/sort/ranges.sort.pass.cpp
2

I did a few more runs of the benchmarks and got similar wide distribution in the results. This convinced me that there is too much variation between different runs, so I quickly hacked together a combined benchmark which runs the classic and the ranges versions right after each other for each input.

The results are a lot more reasonable: most are within 5% and almost all are within 10%, with just 2 outliers (BM_RangesSort_float_Ascending_16384_Ranges is 13.86% slower in the ranges version, and BM_RangesSort_float_Descending_1_Ranges is 25.73% faster in the ranges version). The outliers follow each other in quick succession, leading me to believe both of them are part of some random fluctuation in CPU load. Moreover, the ranges version outperforms the classic version more often than the other way round (though I don't see a reason for it and presume it's not meaningful).

All in all, I don't see a reason to worry (differences seem to be within the error margin, and the ranges version has a slight edge on average) -- but please point out if anything looks worrisome to you.

Raw data below. Columns are: benchmark name / CPU time, ns / CPU time for ranges divided by CPU time for classic, % / Previous column - 100% (negative number means the ranges version is faster):

BM_RangesSort_uint32_Random_1_Classic	4.15		
BM_RangesSort_uint32_Random_1_Ranges	3.76	90.60%	-9.40%
BM_RangesSort_uint32_Random_4_Classic	5		
BM_RangesSort_uint32_Random_4_Ranges	4.94	98.80%	-1.20%
BM_RangesSort_uint32_Random_16_Classic	8.03		
BM_RangesSort_uint32_Random_16_Ranges	8.06	100.37%	0.37%
BM_RangesSort_uint32_Random_64_Classic	14.5		
BM_RangesSort_uint32_Random_64_Ranges	14.5	100.00%	0.00%
BM_RangesSort_uint32_Random_256_Classic	20.4		
BM_RangesSort_uint32_Random_256_Ranges	20.4	100.00%	0.00%
BM_RangesSort_uint32_Random_1024_Classic	26.3		
BM_RangesSort_uint32_Random_1024_Ranges	26.3	100.00%	0.00%
BM_RangesSort_uint32_Random_16384_Classic	38		
BM_RangesSort_uint32_Random_16384_Ranges	38.1	100.26%	0.26%
BM_RangesSort_uint32_Random_262144_Classic	49.9		
BM_RangesSort_uint32_Random_262144_Ranges	50.4	101.00%	1.00%
BM_RangesSort_uint32_Ascending_1_Classic	4.12		
BM_RangesSort_uint32_Ascending_1_Ranges	3.83	92.96%	-7.04%
BM_RangesSort_uint32_Ascending_4_Classic	1.3		
BM_RangesSort_uint32_Ascending_4_Ranges	1.14	87.69%	-12.31%
BM_RangesSort_uint32_Ascending_16_Classic	0.865		
BM_RangesSort_uint32_Ascending_16_Ranges	0.887	102.54%	2.54%
BM_RangesSort_uint32_Ascending_64_Classic	0.948		
BM_RangesSort_uint32_Ascending_64_Ranges	0.961	101.37%	1.37%
BM_RangesSort_uint32_Ascending_256_Classic	1.23		
BM_RangesSort_uint32_Ascending_256_Ranges	1.05	85.37%	-14.63%
BM_RangesSort_uint32_Ascending_1024_Classic	0.896		
BM_RangesSort_uint32_Ascending_1024_Ranges	0.909	101.45%	1.45%
BM_RangesSort_uint32_Ascending_16384_Classic	0.817		
BM_RangesSort_uint32_Ascending_16384_Ranges	0.811	99.27%	-0.73%
BM_RangesSort_uint32_Ascending_262144_Classic	0.808		
BM_RangesSort_uint32_Ascending_262144_Ranges	0.805	99.63%	-0.37%
BM_RangesSort_uint32_Descending_1_Classic	4.27		
BM_RangesSort_uint32_Descending_1_Ranges	3.88	90.87%	-9.13%
BM_RangesSort_uint32_Descending_4_Classic	1.65		
BM_RangesSort_uint32_Descending_4_Ranges	1.58	95.76%	-4.24%
BM_RangesSort_uint32_Descending_16_Classic	4.68		
BM_RangesSort_uint32_Descending_16_Ranges	4.71	100.64%	0.64%
BM_RangesSort_uint32_Descending_64_Classic	1.68		
BM_RangesSort_uint32_Descending_64_Ranges	1.67	99.40%	-0.60%
BM_RangesSort_uint32_Descending_256_Classic	1.66		
BM_RangesSort_uint32_Descending_256_Ranges	1.62	97.59%	-2.41%
BM_RangesSort_uint32_Descending_1024_Classic	1.88		
BM_RangesSort_uint32_Descending_1024_Ranges	1.89	100.53%	0.53%
BM_RangesSort_uint32_Descending_16384_Classic	1.62		
BM_RangesSort_uint32_Descending_16384_Ranges	1.6	98.77%	-1.23%
BM_RangesSort_uint32_Descending_262144_Classic	1.6		
BM_RangesSort_uint32_Descending_262144_Ranges	1.61	100.63%	0.63%
BM_RangesSort_uint32_SingleElement_1_Classic	4.21		
BM_RangesSort_uint32_SingleElement_1_Ranges	3.94	93.59%	-6.41%
BM_RangesSort_uint32_SingleElement_4_Classic	1.29		
BM_RangesSort_uint32_SingleElement_4_Ranges	1.16	89.92%	-10.08%
BM_RangesSort_uint32_SingleElement_16_Classic	0.871		
BM_RangesSort_uint32_SingleElement_16_Ranges	0.91	104.48%	4.48%
BM_RangesSort_uint32_SingleElement_64_Classic	1.12		
BM_RangesSort_uint32_SingleElement_64_Ranges	1.11	99.11%	-0.89%
BM_RangesSort_uint32_SingleElement_256_Classic	1.12		
BM_RangesSort_uint32_SingleElement_256_Ranges	1.12	100.00%	0.00%
BM_RangesSort_uint32_SingleElement_1024_Classic	1.05		
BM_RangesSort_uint32_SingleElement_1024_Ranges	1.06	100.95%	0.95%
BM_RangesSort_uint32_SingleElement_16384_Classic	1.04		
BM_RangesSort_uint32_SingleElement_16384_Ranges	1.03	99.04%	-0.96%
BM_RangesSort_uint32_SingleElement_262144_Classic	1.04		
BM_RangesSort_uint32_SingleElement_262144_Ranges	1.03	99.04%	-0.96%
BM_RangesSort_uint32_PipeOrgan_1_Classic	4.24		
BM_RangesSort_uint32_PipeOrgan_1_Ranges	3.87	91.27%	-8.73%
BM_RangesSort_uint32_PipeOrgan_4_Classic	1.35		
BM_RangesSort_uint32_PipeOrgan_4_Ranges	1.16	85.93%	-14.07%
BM_RangesSort_uint32_PipeOrgan_16_Classic	1.86		
BM_RangesSort_uint32_PipeOrgan_16_Ranges	1.87	100.54%	0.54%
BM_RangesSort_uint32_PipeOrgan_64_Classic	4.58		
BM_RangesSort_uint32_PipeOrgan_64_Ranges	4.69	102.40%	2.40%
BM_RangesSort_uint32_PipeOrgan_256_Classic	2.47		
BM_RangesSort_uint32_PipeOrgan_256_Ranges	2.54	102.83%	2.83%
BM_RangesSort_uint32_PipeOrgan_1024_Classic	3.15		
BM_RangesSort_uint32_PipeOrgan_1024_Ranges	3.13	99.37%	-0.63%
BM_RangesSort_uint32_PipeOrgan_16384_Classic	3.49		
BM_RangesSort_uint32_PipeOrgan_16384_Ranges	3.54	101.43%	1.43%
BM_RangesSort_uint32_PipeOrgan_262144_Classic	4.19		
BM_RangesSort_uint32_PipeOrgan_262144_Ranges	4.19	100.00%	0.00%
BM_RangesSort_uint32_QuickSortAdversary_1_Classic	4.18		
BM_RangesSort_uint32_QuickSortAdversary_1_Ranges	3.82	91.39%	-8.61%
BM_RangesSort_uint32_QuickSortAdversary_4_Classic	1.28		
BM_RangesSort_uint32_QuickSortAdversary_4_Ranges	1.16	90.63%	-9.38%
BM_RangesSort_uint32_QuickSortAdversary_16_Classic	0.865		
BM_RangesSort_uint32_QuickSortAdversary_16_Ranges	0.882	101.97%	1.97%
BM_RangesSort_uint32_QuickSortAdversary_64_Classic	9.65		
BM_RangesSort_uint32_QuickSortAdversary_64_Ranges	9.59	99.38%	-0.62%
BM_RangesSort_uint32_QuickSortAdversary_256_Classic	13.3		
BM_RangesSort_uint32_QuickSortAdversary_256_Ranges	13.4	100.75%	0.75%
BM_RangesSort_uint32_QuickSortAdversary_1024_Classic	40		
BM_RangesSort_uint32_QuickSortAdversary_1024_Ranges	39.7	99.25%	-0.75%
BM_RangesSort_uint32_QuickSortAdversary_16384_Classic	69.4		
BM_RangesSort_uint32_QuickSortAdversary_16384_Ranges	69.1	99.57%	-0.43%
BM_RangesSort_uint32_QuickSortAdversary_262144_Classic	77.3		
BM_RangesSort_uint32_QuickSortAdversary_262144_Ranges	80.2	103.75%	3.75%
BM_RangesSort_uint64_Random_1_Classic	4.3		
BM_RangesSort_uint64_Random_1_Ranges	3.73	86.74%	-13.26%
BM_RangesSort_uint64_Random_4_Classic	4.91		
BM_RangesSort_uint64_Random_4_Ranges	4.83	98.37%	-1.63%
BM_RangesSort_uint64_Random_16_Classic	9.08		
BM_RangesSort_uint64_Random_16_Ranges	9.11	100.33%	0.33%
BM_RangesSort_uint64_Random_64_Classic	15.6		
BM_RangesSort_uint64_Random_64_Ranges	15.6	100.00%	0.00%
BM_RangesSort_uint64_Random_256_Classic	21.5		
BM_RangesSort_uint64_Random_256_Ranges	21.7	100.93%	0.93%
BM_RangesSort_uint64_Random_1024_Classic	27.7		
BM_RangesSort_uint64_Random_1024_Ranges	27.9	100.72%	0.72%
BM_RangesSort_uint64_Random_16384_Classic	39.9		
BM_RangesSort_uint64_Random_16384_Ranges	39.7	99.50%	-0.50%
BM_RangesSort_uint64_Random_262144_Classic	51		
BM_RangesSort_uint64_Random_262144_Ranges	51.3	100.59%	0.59%
BM_RangesSort_uint64_Ascending_1_Classic	4.24		
BM_RangesSort_uint64_Ascending_1_Ranges	3.91	92.22%	-7.78%
BM_RangesSort_uint64_Ascending_4_Classic	1.38		
BM_RangesSort_uint64_Ascending_4_Ranges	1.22	88.41%	-11.59%
BM_RangesSort_uint64_Ascending_16_Classic	1.07		
BM_RangesSort_uint64_Ascending_16_Ranges	1.08	100.93%	0.93%
BM_RangesSort_uint64_Ascending_64_Classic	1.03		
BM_RangesSort_uint64_Ascending_64_Ranges	1.03	100.00%	0.00%
BM_RangesSort_uint64_Ascending_256_Classic	1.17		
BM_RangesSort_uint64_Ascending_256_Ranges	1.15	98.29%	-1.71%
BM_RangesSort_uint64_Ascending_1024_Classic	1.02		
BM_RangesSort_uint64_Ascending_1024_Ranges	1.02	100.00%	0.00%
BM_RangesSort_uint64_Ascending_16384_Classic	0.919		
BM_RangesSort_uint64_Ascending_16384_Ranges	0.944	102.72%	2.72%
BM_RangesSort_uint64_Ascending_262144_Classic	0.972		
BM_RangesSort_uint64_Ascending_262144_Ranges	0.992	102.06%	2.06%
BM_RangesSort_uint64_Descending_1_Classic	4.28		
BM_RangesSort_uint64_Descending_1_Ranges	3.81	89.02%	-10.98%
BM_RangesSort_uint64_Descending_4_Classic	1.57		
BM_RangesSort_uint64_Descending_4_Ranges	1.56	99.36%	-0.64%
BM_RangesSort_uint64_Descending_16_Classic	4.39		
BM_RangesSort_uint64_Descending_16_Ranges	4.39	100.00%	0.00%
BM_RangesSort_uint64_Descending_64_Classic	1.8		
BM_RangesSort_uint64_Descending_64_Ranges	1.8	100.00%	0.00%
BM_RangesSort_uint64_Descending_256_Classic	1.85		
BM_RangesSort_uint64_Descending_256_Ranges	1.87	101.08%	1.08%
BM_RangesSort_uint64_Descending_1024_Classic	1.96		
BM_RangesSort_uint64_Descending_1024_Ranges	1.95	99.49%	-0.51%
BM_RangesSort_uint64_Descending_16384_Classic	1.63		
BM_RangesSort_uint64_Descending_16384_Ranges	1.64	100.61%	0.61%
BM_RangesSort_uint64_Descending_262144_Classic	1.78		
BM_RangesSort_uint64_Descending_262144_Ranges	1.84	103.37%	3.37%
BM_RangesSort_uint64_SingleElement_1_Classic	4.16		
BM_RangesSort_uint64_SingleElement_1_Ranges	4.01	96.39%	-3.61%
BM_RangesSort_uint64_SingleElement_4_Classic	1.4		
BM_RangesSort_uint64_SingleElement_4_Ranges	1.21	86.43%	-13.57%
BM_RangesSort_uint64_SingleElement_16_Classic	1.07		
BM_RangesSort_uint64_SingleElement_16_Ranges	1.08	100.93%	0.93%
BM_RangesSort_uint64_SingleElement_64_Classic	0.889		
BM_RangesSort_uint64_SingleElement_64_Ranges	0.908	102.14%	2.14%
BM_RangesSort_uint64_SingleElement_256_Classic	0.96		
BM_RangesSort_uint64_SingleElement_256_Ranges	0.969	100.94%	0.94%
BM_RangesSort_uint64_SingleElement_1024_Classic	0.824		
BM_RangesSort_uint64_SingleElement_1024_Ranges	0.845	102.55%	2.55%
BM_RangesSort_uint64_SingleElement_16384_Classic	0.838		
BM_RangesSort_uint64_SingleElement_16384_Ranges	0.83	99.05%	-0.95%
BM_RangesSort_uint64_SingleElement_262144_Classic	0.931		
BM_RangesSort_uint64_SingleElement_262144_Ranges	0.936	100.54%	0.54%
BM_RangesSort_uint64_PipeOrgan_1_Classic	4.36		
BM_RangesSort_uint64_PipeOrgan_1_Ranges	3.89	89.22%	-10.78%
BM_RangesSort_uint64_PipeOrgan_4_Classic	1.42		
BM_RangesSort_uint64_PipeOrgan_4_Ranges	1.33	93.66%	-6.34%
BM_RangesSort_uint64_PipeOrgan_16_Classic	2.06		
BM_RangesSort_uint64_PipeOrgan_16_Ranges	2	97.09%	-2.91%
BM_RangesSort_uint64_PipeOrgan_64_Classic	4.84		
BM_RangesSort_uint64_PipeOrgan_64_Ranges	4.77	98.55%	-1.45%
BM_RangesSort_uint64_PipeOrgan_256_Classic	2.68		
BM_RangesSort_uint64_PipeOrgan_256_Ranges	2.64	98.51%	-1.49%
BM_RangesSort_uint64_PipeOrgan_1024_Classic	3.38		
BM_RangesSort_uint64_PipeOrgan_1024_Ranges	3.29	97.34%	-2.66%
BM_RangesSort_uint64_PipeOrgan_16384_Classic	3.83		
BM_RangesSort_uint64_PipeOrgan_16384_Ranges	3.88	101.31%	1.31%
BM_RangesSort_uint64_PipeOrgan_262144_Classic	4.62		
BM_RangesSort_uint64_PipeOrgan_262144_Ranges	4.58	99.13%	-0.87%
BM_RangesSort_uint64_QuickSortAdversary_1_Classic	4.05		
BM_RangesSort_uint64_QuickSortAdversary_1_Ranges	3.86	95.31%	-4.69%
BM_RangesSort_uint64_QuickSortAdversary_4_Classic	1.35		
BM_RangesSort_uint64_QuickSortAdversary_4_Ranges	1.21	89.63%	-10.37%
BM_RangesSort_uint64_QuickSortAdversary_16_Classic	1.08		
BM_RangesSort_uint64_QuickSortAdversary_16_Ranges	1.08	100.00%	0.00%
BM_RangesSort_uint64_QuickSortAdversary_64_Classic	10.7		
BM_RangesSort_uint64_QuickSortAdversary_64_Ranges	10.8	100.93%	0.93%
BM_RangesSort_uint64_QuickSortAdversary_256_Classic	14.5		
BM_RangesSort_uint64_QuickSortAdversary_256_Ranges	14.6	100.69%	0.69%
BM_RangesSort_uint64_QuickSortAdversary_1024_Classic	36.6		
BM_RangesSort_uint64_QuickSortAdversary_1024_Ranges	36.9	100.82%	0.82%
BM_RangesSort_uint64_QuickSortAdversary_16384_Classic	65.4		
BM_RangesSort_uint64_QuickSortAdversary_16384_Ranges	65.5	100.15%	0.15%
BM_RangesSort_uint64_QuickSortAdversary_262144_Classic	81.3		
BM_RangesSort_uint64_QuickSortAdversary_262144_Ranges	81.7	100.49%	0.49%
BM_RangesSort_pair<uint32, uint32>_Random_1_Classic	4.52		
BM_RangesSort_pair<uint32, uint32>_Random_1_Ranges	4	88.50%	-11.50%
BM_RangesSort_pair<uint32, uint32>_Random_4_Classic	6.81		
BM_RangesSort_pair<uint32, uint32>_Random_4_Ranges	6.69	98.24%	-1.76%
BM_RangesSort_pair<uint32, uint32>_Random_16_Classic	22.6		
BM_RangesSort_pair<uint32, uint32>_Random_16_Ranges	22.3	98.67%	-1.33%
BM_RangesSort_pair<uint32, uint32>_Random_64_Classic	33.2		
BM_RangesSort_pair<uint32, uint32>_Random_64_Ranges	33.4	100.60%	0.60%
BM_RangesSort_pair<uint32, uint32>_Random_256_Classic	42.3		
BM_RangesSort_pair<uint32, uint32>_Random_256_Ranges	42.1	99.53%	-0.47%
BM_RangesSort_pair<uint32, uint32>_Random_1024_Classic	50.6		
BM_RangesSort_pair<uint32, uint32>_Random_1024_Ranges	49.9	98.62%	-1.38%
BM_RangesSort_pair<uint32, uint32>_Random_16384_Classic	67.1		
BM_RangesSort_pair<uint32, uint32>_Random_16384_Ranges	67.4	100.45%	0.45%
BM_RangesSort_pair<uint32, uint32>_Random_262144_Classic	84.3		
BM_RangesSort_pair<uint32, uint32>_Random_262144_Ranges	80.8	95.85%	-4.15%
BM_RangesSort_pair<uint32, uint32>_Ascending_1_Classic	4.02		
BM_RangesSort_pair<uint32, uint32>_Ascending_1_Ranges	3.97	98.76%	-1.24%
BM_RangesSort_pair<uint32, uint32>_Ascending_4_Classic	2.26		
BM_RangesSort_pair<uint32, uint32>_Ascending_4_Ranges	2.14	94.69%	-5.31%
BM_RangesSort_pair<uint32, uint32>_Ascending_16_Classic	2.75		
BM_RangesSort_pair<uint32, uint32>_Ascending_16_Ranges	2.67	97.09%	-2.91%
BM_RangesSort_pair<uint32, uint32>_Ascending_64_Classic	2.06		
BM_RangesSort_pair<uint32, uint32>_Ascending_64_Ranges	2.07	100.49%	0.49%
BM_RangesSort_pair<uint32, uint32>_Ascending_256_Classic	2.17		
BM_RangesSort_pair<uint32, uint32>_Ascending_256_Ranges	2.17	100.00%	0.00%
BM_RangesSort_pair<uint32, uint32>_Ascending_1024_Classic	2.03		
BM_RangesSort_pair<uint32, uint32>_Ascending_1024_Ranges	2.06	101.48%	1.48%
BM_RangesSort_pair<uint32, uint32>_Ascending_16384_Classic	1.98		
BM_RangesSort_pair<uint32, uint32>_Ascending_16384_Ranges	1.98	100.00%	0.00%
BM_RangesSort_pair<uint32, uint32>_Ascending_262144_Classic	1.97		
BM_RangesSort_pair<uint32, uint32>_Ascending_262144_Ranges	1.96	99.49%	-0.51%
BM_RangesSort_pair<uint32, uint32>_Descending_1_Classic	4.2		
BM_RangesSort_pair<uint32, uint32>_Descending_1_Ranges	3.96	94.29%	-5.71%
BM_RangesSort_pair<uint32, uint32>_Descending_4_Classic	3.32		
BM_RangesSort_pair<uint32, uint32>_Descending_4_Ranges	3.3	99.40%	-0.60%
BM_RangesSort_pair<uint32, uint32>_Descending_16_Classic	5.92		
BM_RangesSort_pair<uint32, uint32>_Descending_16_Ranges	5.87	99.16%	-0.84%
BM_RangesSort_pair<uint32, uint32>_Descending_64_Classic	4.27		
BM_RangesSort_pair<uint32, uint32>_Descending_64_Ranges	4.27	100.00%	0.00%
BM_RangesSort_pair<uint32, uint32>_Descending_256_Classic	4		
BM_RangesSort_pair<uint32, uint32>_Descending_256_Ranges	3.98	99.50%	-0.50%
BM_RangesSort_pair<uint32, uint32>_Descending_1024_Classic	5.18		
BM_RangesSort_pair<uint32, uint32>_Descending_1024_Ranges	5.2	100.39%	0.39%
BM_RangesSort_pair<uint32, uint32>_Descending_16384_Classic	5.05		
BM_RangesSort_pair<uint32, uint32>_Descending_16384_Ranges	5.01	99.21%	-0.79%
BM_RangesSort_pair<uint32, uint32>_Descending_262144_Classic	5.06		
BM_RangesSort_pair<uint32, uint32>_Descending_262144_Ranges	5.05	99.80%	-0.20%
BM_RangesSort_pair<uint32, uint32>_SingleElement_1_Classic	4.03		
BM_RangesSort_pair<uint32, uint32>_SingleElement_1_Ranges	3.95	98.01%	-1.99%
BM_RangesSort_pair<uint32, uint32>_SingleElement_4_Classic	2.22		
BM_RangesSort_pair<uint32, uint32>_SingleElement_4_Ranges	2.05	92.34%	-7.66%
BM_RangesSort_pair<uint32, uint32>_SingleElement_16_Classic	2.66		
BM_RangesSort_pair<uint32, uint32>_SingleElement_16_Ranges	2.62	98.50%	-1.50%
BM_RangesSort_pair<uint32, uint32>_SingleElement_64_Classic	2.85		
BM_RangesSort_pair<uint32, uint32>_SingleElement_64_Ranges	2.95	103.51%	3.51%
BM_RangesSort_pair<uint32, uint32>_SingleElement_256_Classic	3.07		
BM_RangesSort_pair<uint32, uint32>_SingleElement_256_Ranges	3.05	99.35%	-0.65%
BM_RangesSort_pair<uint32, uint32>_SingleElement_1024_Classic	2.96		
BM_RangesSort_pair<uint32, uint32>_SingleElement_1024_Ranges	2.94	99.32%	-0.68%
BM_RangesSort_pair<uint32, uint32>_SingleElement_16384_Classic	2.97		
BM_RangesSort_pair<uint32, uint32>_SingleElement_16384_Ranges	2.94	98.99%	-1.01%
BM_RangesSort_pair<uint32, uint32>_SingleElement_262144_Classic	2.93		
BM_RangesSort_pair<uint32, uint32>_SingleElement_262144_Ranges	2.96	101.02%	1.02%
BM_RangesSort_pair<uint32, uint32>_PipeOrgan_1_Classic	4.19		
BM_RangesSort_pair<uint32, uint32>_PipeOrgan_1_Ranges	4.36	104.06%	4.06%
BM_RangesSort_pair<uint32, uint32>_PipeOrgan_4_Classic	2.52		
BM_RangesSort_pair<uint32, uint32>_PipeOrgan_4_Ranges	2.45	97.22%	-2.78%
BM_RangesSort_pair<uint32, uint32>_PipeOrgan_16_Classic	5.66		
BM_RangesSort_pair<uint32, uint32>_PipeOrgan_16_Ranges	5.74	101.41%	1.41%
BM_RangesSort_pair<uint32, uint32>_PipeOrgan_64_Classic	6.19		
BM_RangesSort_pair<uint32, uint32>_PipeOrgan_64_Ranges	6.18	99.84%	-0.16%
BM_RangesSort_pair<uint32, uint32>_PipeOrgan_256_Classic	8.29		
BM_RangesSort_pair<uint32, uint32>_PipeOrgan_256_Ranges	8.11	97.83%	-2.17%
BM_RangesSort_pair<uint32, uint32>_PipeOrgan_1024_Classic	10.4		
BM_RangesSort_pair<uint32, uint32>_PipeOrgan_1024_Ranges	10.6	101.92%	1.92%
BM_RangesSort_pair<uint32, uint32>_PipeOrgan_16384_Classic	11.4		
BM_RangesSort_pair<uint32, uint32>_PipeOrgan_16384_Ranges	11.3	99.12%	-0.88%
BM_RangesSort_pair<uint32, uint32>_PipeOrgan_262144_Classic	13.7		
BM_RangesSort_pair<uint32, uint32>_PipeOrgan_262144_Ranges	13.8	100.73%	0.73%
BM_RangesSort_pair<uint32, uint32>_QuickSortAdversary_1_Classic	4.03		
BM_RangesSort_pair<uint32, uint32>_QuickSortAdversary_1_Ranges	4	99.26%	-0.74%
BM_RangesSort_pair<uint32, uint32>_QuickSortAdversary_4_Classic	2.93		
BM_RangesSort_pair<uint32, uint32>_QuickSortAdversary_4_Ranges	2.72	92.83%	-7.17%
BM_RangesSort_pair<uint32, uint32>_QuickSortAdversary_16_Classic	5.64		
BM_RangesSort_pair<uint32, uint32>_QuickSortAdversary_16_Ranges	5.6	99.29%	-0.71%
BM_RangesSort_pair<uint32, uint32>_QuickSortAdversary_64_Classic	8.99		
BM_RangesSort_pair<uint32, uint32>_QuickSortAdversary_64_Ranges	8.99	100.00%	0.00%
BM_RangesSort_pair<uint32, uint32>_QuickSortAdversary_256_Classic	12.5		
BM_RangesSort_pair<uint32, uint32>_QuickSortAdversary_256_Ranges	12.6	100.80%	0.80%
BM_RangesSort_pair<uint32, uint32>_QuickSortAdversary_1024_Classic	15.9		
BM_RangesSort_pair<uint32, uint32>_QuickSortAdversary_1024_Ranges	14.9	93.71%	-6.29%
BM_RangesSort_pair<uint32, uint32>_QuickSortAdversary_16384_Classic	34.3		
BM_RangesSort_pair<uint32, uint32>_QuickSortAdversary_16384_Ranges	35.1	102.33%	2.33%
BM_RangesSort_pair<uint32, uint32>_QuickSortAdversary_262144_Classic	40.2		
BM_RangesSort_pair<uint32, uint32>_QuickSortAdversary_262144_Ranges	40.1	99.75%	-0.25%
BM_RangesSort_tuple<uint32, uint64, uint32>_Random_1_Classic	4.88		
BM_RangesSort_tuple<uint32, uint64, uint32>_Random_1_Ranges	4.53	92.83%	-7.17%
BM_RangesSort_tuple<uint32, uint64, uint32>_Random_4_Classic	7.01		
BM_RangesSort_tuple<uint32, uint64, uint32>_Random_4_Ranges	7.1	101.28%	1.28%
BM_RangesSort_tuple<uint32, uint64, uint32>_Random_16_Classic	26.1		
BM_RangesSort_tuple<uint32, uint64, uint32>_Random_16_Ranges	26	99.62%	-0.38%
BM_RangesSort_tuple<uint32, uint64, uint32>_Random_64_Classic	37.8		
BM_RangesSort_tuple<uint32, uint64, uint32>_Random_64_Ranges	38.4	101.59%	1.59%
BM_RangesSort_tuple<uint32, uint64, uint32>_Random_256_Classic	48.1		
BM_RangesSort_tuple<uint32, uint64, uint32>_Random_256_Ranges	48.3	100.42%	0.42%
BM_RangesSort_tuple<uint32, uint64, uint32>_Random_1024_Classic	53.4		
BM_RangesSort_tuple<uint32, uint64, uint32>_Random_1024_Ranges	51.9	97.19%	-2.81%
BM_RangesSort_tuple<uint32, uint64, uint32>_Random_16384_Classic	65.5		
BM_RangesSort_tuple<uint32, uint64, uint32>_Random_16384_Ranges	64.5	98.47%	-1.53%
BM_RangesSort_tuple<uint32, uint64, uint32>_Random_262144_Classic	79.2		
BM_RangesSort_tuple<uint32, uint64, uint32>_Random_262144_Ranges	81.4	102.78%	2.78%
BM_RangesSort_tuple<uint32, uint64, uint32>_Ascending_1_Classic	5.01		
BM_RangesSort_tuple<uint32, uint64, uint32>_Ascending_1_Ranges	5.13	102.40%	2.40%
BM_RangesSort_tuple<uint32, uint64, uint32>_Ascending_4_Classic	2.77		
BM_RangesSort_tuple<uint32, uint64, uint32>_Ascending_4_Ranges	2.96	106.86%	6.86%
BM_RangesSort_tuple<uint32, uint64, uint32>_Ascending_16_Classic	3.29		
BM_RangesSort_tuple<uint32, uint64, uint32>_Ascending_16_Ranges	3.21	97.57%	-2.43%
BM_RangesSort_tuple<uint32, uint64, uint32>_Ascending_64_Classic	3.65		
BM_RangesSort_tuple<uint32, uint64, uint32>_Ascending_64_Ranges	3.54	96.99%	-3.01%
BM_RangesSort_tuple<uint32, uint64, uint32>_Ascending_256_Classic	3.85		
BM_RangesSort_tuple<uint32, uint64, uint32>_Ascending_256_Ranges	3.68	95.58%	-4.42%
BM_RangesSort_tuple<uint32, uint64, uint32>_Ascending_1024_Classic	3.52		
BM_RangesSort_tuple<uint32, uint64, uint32>_Ascending_1024_Ranges	3.62	102.84%	2.84%
BM_RangesSort_tuple<uint32, uint64, uint32>_Ascending_16384_Classic	3.31		
BM_RangesSort_tuple<uint32, uint64, uint32>_Ascending_16384_Ranges	3.3	99.70%	-0.30%
BM_RangesSort_tuple<uint32, uint64, uint32>_Ascending_262144_Classic	3.42		
BM_RangesSort_tuple<uint32, uint64, uint32>_Ascending_262144_Ranges	3.5	102.34%	2.34%
BM_RangesSort_tuple<uint32, uint64, uint32>_Descending_1_Classic	5.09		
BM_RangesSort_tuple<uint32, uint64, uint32>_Descending_1_Ranges	4.89	96.07%	-3.93%
BM_RangesSort_tuple<uint32, uint64, uint32>_Descending_4_Classic	3.61		
BM_RangesSort_tuple<uint32, uint64, uint32>_Descending_4_Ranges	3.62	100.28%	0.28%
BM_RangesSort_tuple<uint32, uint64, uint32>_Descending_16_Classic	5.79		
BM_RangesSort_tuple<uint32, uint64, uint32>_Descending_16_Ranges	5.75	99.31%	-0.69%
BM_RangesSort_tuple<uint32, uint64, uint32>_Descending_64_Classic	4.99		
BM_RangesSort_tuple<uint32, uint64, uint32>_Descending_64_Ranges	5.13	102.81%	2.81%
BM_RangesSort_tuple<uint32, uint64, uint32>_Descending_256_Classic	4.94		
BM_RangesSort_tuple<uint32, uint64, uint32>_Descending_256_Ranges	4.84	97.98%	-2.02%
BM_RangesSort_tuple<uint32, uint64, uint32>_Descending_1024_Classic	5.93		
BM_RangesSort_tuple<uint32, uint64, uint32>_Descending_1024_Ranges	6.2	104.55%	4.55%
BM_RangesSort_tuple<uint32, uint64, uint32>_Descending_16384_Classic	5.47		
BM_RangesSort_tuple<uint32, uint64, uint32>_Descending_16384_Ranges	5.41	98.90%	-1.10%
BM_RangesSort_tuple<uint32, uint64, uint32>_Descending_262144_Classic	6.53		
BM_RangesSort_tuple<uint32, uint64, uint32>_Descending_262144_Ranges	6.4	98.01%	-1.99%
BM_RangesSort_tuple<uint32, uint64, uint32>_SingleElement_1_Classic	4.85		
BM_RangesSort_tuple<uint32, uint64, uint32>_SingleElement_1_Ranges	4.41	90.93%	-9.07%
BM_RangesSort_tuple<uint32, uint64, uint32>_SingleElement_4_Classic	2.78		
BM_RangesSort_tuple<uint32, uint64, uint32>_SingleElement_4_Ranges	2.72	97.84%	-2.16%
BM_RangesSort_tuple<uint32, uint64, uint32>_SingleElement_16_Classic	3.84		
BM_RangesSort_tuple<uint32, uint64, uint32>_SingleElement_16_Ranges	3.64	94.79%	-5.21%
BM_RangesSort_tuple<uint32, uint64, uint32>_SingleElement_64_Classic	4.21		
BM_RangesSort_tuple<uint32, uint64, uint32>_SingleElement_64_Ranges	4.49	106.65%	6.65%
BM_RangesSort_tuple<uint32, uint64, uint32>_SingleElement_256_Classic	4.57		
BM_RangesSort_tuple<uint32, uint64, uint32>_SingleElement_256_Ranges	4.93	107.88%	7.88%
BM_RangesSort_tuple<uint32, uint64, uint32>_SingleElement_1024_Classic	4.37		
BM_RangesSort_tuple<uint32, uint64, uint32>_SingleElement_1024_Ranges	4.43	101.37%	1.37%
BM_RangesSort_tuple<uint32, uint64, uint32>_SingleElement_16384_Classic	4.04		
BM_RangesSort_tuple<uint32, uint64, uint32>_SingleElement_16384_Ranges	4	99.01%	-0.99%
BM_RangesSort_tuple<uint32, uint64, uint32>_SingleElement_262144_Classic	3.97		
BM_RangesSort_tuple<uint32, uint64, uint32>_SingleElement_262144_Ranges	4.01	101.01%	1.01%
BM_RangesSort_tuple<uint32, uint64, uint32>_PipeOrgan_1_Classic	5		
BM_RangesSort_tuple<uint32, uint64, uint32>_PipeOrgan_1_Ranges	4.58	91.60%	-8.40%
BM_RangesSort_tuple<uint32, uint64, uint32>_PipeOrgan_4_Classic	2.8		
BM_RangesSort_tuple<uint32, uint64, uint32>_PipeOrgan_4_Ranges	2.85	101.79%	1.79%
BM_RangesSort_tuple<uint32, uint64, uint32>_PipeOrgan_16_Classic	6.09		
BM_RangesSort_tuple<uint32, uint64, uint32>_PipeOrgan_16_Ranges	6.22	102.13%	2.13%
BM_RangesSort_tuple<uint32, uint64, uint32>_PipeOrgan_64_Classic	6.95		
BM_RangesSort_tuple<uint32, uint64, uint32>_PipeOrgan_64_Ranges	6.92	99.57%	-0.43%
BM_RangesSort_tuple<uint32, uint64, uint32>_PipeOrgan_256_Classic	8.61		
BM_RangesSort_tuple<uint32, uint64, uint32>_PipeOrgan_256_Ranges	8.63	100.23%	0.23%
BM_RangesSort_tuple<uint32, uint64, uint32>_PipeOrgan_1024_Classic	10.4		
BM_RangesSort_tuple<uint32, uint64, uint32>_PipeOrgan_1024_Ranges	10.3	99.04%	-0.96%
BM_RangesSort_tuple<uint32, uint64, uint32>_PipeOrgan_16384_Classic	12.1		
BM_RangesSort_tuple<uint32, uint64, uint32>_PipeOrgan_16384_Ranges	12	99.17%	-0.83%
BM_RangesSort_tuple<uint32, uint64, uint32>_PipeOrgan_262144_Classic	15.2		
BM_RangesSort_tuple<uint32, uint64, uint32>_PipeOrgan_262144_Ranges	15.3	100.66%	0.66%
BM_RangesSort_tuple<uint32, uint64, uint32>_QuickSortAdversary_1_Classic	4.8		
BM_RangesSort_tuple<uint32, uint64, uint32>_QuickSortAdversary_1_Ranges	5.01	104.38%	4.38%
BM_RangesSort_tuple<uint32, uint64, uint32>_QuickSortAdversary_4_Classic	2.95		
BM_RangesSort_tuple<uint32, uint64, uint32>_QuickSortAdversary_4_Ranges	3.25	110.17%	10.17%
BM_RangesSort_tuple<uint32, uint64, uint32>_QuickSortAdversary_16_Classic	5.58		
BM_RangesSort_tuple<uint32, uint64, uint32>_QuickSortAdversary_16_Ranges	5.5	98.57%	-1.43%
BM_RangesSort_tuple<uint32, uint64, uint32>_QuickSortAdversary_64_Classic	10		
BM_RangesSort_tuple<uint32, uint64, uint32>_QuickSortAdversary_64_Ranges	10.2	102.00%	2.00%
BM_RangesSort_tuple<uint32, uint64, uint32>_QuickSortAdversary_256_Classic	13.7		
BM_RangesSort_tuple<uint32, uint64, uint32>_QuickSortAdversary_256_Ranges	13.8	100.73%	0.73%
BM_RangesSort_tuple<uint32, uint64, uint32>_QuickSortAdversary_1024_Classic	21.7		
BM_RangesSort_tuple<uint32, uint64, uint32>_QuickSortAdversary_1024_Ranges	20.9	96.31%	-3.69%
BM_RangesSort_tuple<uint32, uint64, uint32>_QuickSortAdversary_16384_Classic	43		
BM_RangesSort_tuple<uint32, uint64, uint32>_QuickSortAdversary_16384_Ranges	43.2	100.47%	0.47%
BM_RangesSort_tuple<uint32, uint64, uint32>_QuickSortAdversary_262144_Classic	49.3		
BM_RangesSort_tuple<uint32, uint64, uint32>_QuickSortAdversary_262144_Ranges	49.4	100.20%	0.20%
BM_RangesSort_string_Random_1_Classic	4.74		
BM_RangesSort_string_Random_1_Ranges	4.75	100.21%	0.21%
BM_RangesSort_string_Random_4_Classic	17.1		
BM_RangesSort_string_Random_4_Ranges	17.1	100.00%	0.00%
BM_RangesSort_string_Random_16_Classic	46.8		
BM_RangesSort_string_Random_16_Ranges	46.6	99.57%	-0.43%
BM_RangesSort_string_Random_64_Classic	72.7		
BM_RangesSort_string_Random_64_Ranges	72.4	99.59%	-0.41%
BM_RangesSort_string_Random_256_Classic	92.7		
BM_RangesSort_string_Random_256_Ranges	93.2	100.54%	0.54%
BM_RangesSort_string_Random_1024_Classic	113		
BM_RangesSort_string_Random_1024_Ranges	112	99.12%	-0.88%
BM_RangesSort_string_Random_16384_Classic	179		
BM_RangesSort_string_Random_16384_Ranges	180	100.56%	0.56%
BM_RangesSort_string_Random_262144_Classic	293		
BM_RangesSort_string_Random_262144_Ranges	286	97.61%	-2.39%
BM_RangesSort_string_Ascending_1_Classic	4.81		
BM_RangesSort_string_Ascending_1_Ranges	4.8	99.79%	-0.21%
BM_RangesSort_string_Ascending_4_Classic	10		
BM_RangesSort_string_Ascending_4_Ranges	9.99	99.90%	-0.10%
BM_RangesSort_string_Ascending_16_Classic	17.2		
BM_RangesSort_string_Ascending_16_Ranges	17.3	100.58%	0.58%
BM_RangesSort_string_Ascending_64_Classic	22.6		
BM_RangesSort_string_Ascending_64_Ranges	23	101.77%	1.77%
BM_RangesSort_string_Ascending_256_Classic	21.9		
BM_RangesSort_string_Ascending_256_Ranges	21.7	99.09%	-0.91%
BM_RangesSort_string_Ascending_1024_Classic	21.9		
BM_RangesSort_string_Ascending_1024_Ranges	21.8	99.54%	-0.46%
BM_RangesSort_string_Ascending_16384_Classic	36		
BM_RangesSort_string_Ascending_16384_Ranges	36.1	100.28%	0.28%
BM_RangesSort_string_Ascending_262144_Classic	46.1		
BM_RangesSort_string_Ascending_262144_Ranges	46.2	100.22%	0.22%
BM_RangesSort_string_Descending_1_Classic	4.72		
BM_RangesSort_string_Descending_1_Ranges	4.77	101.06%	1.06%
BM_RangesSort_string_Descending_4_Classic	12.1		
BM_RangesSort_string_Descending_4_Ranges	12.1	100.00%	0.00%
BM_RangesSort_string_Descending_16_Classic	26.1		
BM_RangesSort_string_Descending_16_Ranges	26.2	100.38%	0.38%
BM_RangesSort_string_Descending_64_Classic	30.3		
BM_RangesSort_string_Descending_64_Ranges	29.2	96.37%	-3.63%
BM_RangesSort_string_Descending_256_Classic	30.1		
BM_RangesSort_string_Descending_256_Ranges	29.9	99.34%	-0.66%
BM_RangesSort_string_Descending_1024_Classic	33.8		
BM_RangesSort_string_Descending_1024_Ranges	33.5	99.11%	-0.89%
BM_RangesSort_string_Descending_16384_Classic	48.9		
BM_RangesSort_string_Descending_16384_Ranges	48.3	98.77%	-1.23%
BM_RangesSort_string_Descending_262144_Classic	83.6		
BM_RangesSort_string_Descending_262144_Ranges	88.7	106.10%	6.10%
BM_RangesSort_string_SingleElement_1_Classic	4.87		
BM_RangesSort_string_SingleElement_1_Ranges	4.7	96.51%	-3.49%
BM_RangesSort_string_SingleElement_4_Classic	9.02		
BM_RangesSort_string_SingleElement_4_Ranges	9.22	102.22%	2.22%
BM_RangesSort_string_SingleElement_16_Classic	18.1		
BM_RangesSort_string_SingleElement_16_Ranges	18.2	100.55%	0.55%
BM_RangesSort_string_SingleElement_64_Classic	26.7		
BM_RangesSort_string_SingleElement_64_Ranges	26.9	100.75%	0.75%
BM_RangesSort_string_SingleElement_256_Classic	22.1		
BM_RangesSort_string_SingleElement_256_Ranges	22.5	101.81%	1.81%
BM_RangesSort_string_SingleElement_1024_Classic	19.7		
BM_RangesSort_string_SingleElement_1024_Ranges	20	101.52%	1.52%
BM_RangesSort_string_SingleElement_16384_Classic	17.4		
BM_RangesSort_string_SingleElement_16384_Ranges	17.5	100.57%	0.57%
BM_RangesSort_string_SingleElement_262144_Classic	18.7		
BM_RangesSort_string_SingleElement_262144_Ranges	18.9	101.07%	1.07%
BM_RangesSort_string_PipeOrgan_1_Classic	4.72		
BM_RangesSort_string_PipeOrgan_1_Ranges	4.54	96.19%	-3.81%
BM_RangesSort_string_PipeOrgan_4_Classic	10.6		
BM_RangesSort_string_PipeOrgan_4_Ranges	10.6	100.00%	0.00%
BM_RangesSort_string_PipeOrgan_16_Classic	25.5		
BM_RangesSort_string_PipeOrgan_16_Ranges	25.3	99.22%	-0.78%
BM_RangesSort_string_PipeOrgan_64_Classic	37.9		
BM_RangesSort_string_PipeOrgan_64_Ranges	38.2	100.79%	0.79%
BM_RangesSort_string_PipeOrgan_256_Classic	46.5		
BM_RangesSort_string_PipeOrgan_256_Ranges	45.3	97.42%	-2.58%
BM_RangesSort_string_PipeOrgan_1024_Classic	52.9		
BM_RangesSort_string_PipeOrgan_1024_Ranges	53.7	101.51%	1.51%
BM_RangesSort_string_PipeOrgan_16384_Classic	73.4		
BM_RangesSort_string_PipeOrgan_16384_Ranges	72.2	98.37%	-1.63%
BM_RangesSort_string_PipeOrgan_262144_Classic	122		
BM_RangesSort_string_PipeOrgan_262144_Ranges	122	100.00%	0.00%
BM_RangesSort_string_QuickSortAdversary_1_Classic	4.59		
BM_RangesSort_string_QuickSortAdversary_1_Ranges	4.57	99.56%	-0.44%
BM_RangesSort_string_QuickSortAdversary_4_Classic	16.5		
BM_RangesSort_string_QuickSortAdversary_4_Ranges	16.8	101.82%	1.82%
BM_RangesSort_string_QuickSortAdversary_16_Classic	45.4		
BM_RangesSort_string_QuickSortAdversary_16_Ranges	47.8	105.29%	5.29%
BM_RangesSort_string_QuickSortAdversary_64_Classic	70.6		
BM_RangesSort_string_QuickSortAdversary_64_Ranges	70.1	99.29%	-0.71%
BM_RangesSort_string_QuickSortAdversary_256_Classic	89		
BM_RangesSort_string_QuickSortAdversary_256_Ranges	89.6	100.67%	0.67%
BM_RangesSort_string_QuickSortAdversary_1024_Classic	109		
BM_RangesSort_string_QuickSortAdversary_1024_Ranges	107	98.17%	-1.83%
BM_RangesSort_string_QuickSortAdversary_16384_Classic	173		
BM_RangesSort_string_QuickSortAdversary_16384_Ranges	173	100.00%	0.00%
BM_RangesSort_string_QuickSortAdversary_262144_Classic	272		
BM_RangesSort_string_QuickSortAdversary_262144_Ranges	276	101.47%	1.47%
BM_RangesSort_float_Random_1_Classic	3.82		
BM_RangesSort_float_Random_1_Ranges	3.27	85.60%	-14.40%
BM_RangesSort_float_Random_4_Classic	5.05		
BM_RangesSort_float_Random_4_Ranges	4.77	94.46%	-5.54%
BM_RangesSort_float_Random_16_Classic	9.14		
BM_RangesSort_float_Random_16_Ranges	9.07	99.23%	-0.77%
BM_RangesSort_float_Random_64_Classic	16.4		
BM_RangesSort_float_Random_64_Ranges	16.3	99.39%	-0.61%
BM_RangesSort_float_Random_256_Classic	23.4		
BM_RangesSort_float_Random_256_Ranges	23.2	99.15%	-0.85%
BM_RangesSort_float_Random_1024_Classic	30.1		
BM_RangesSort_float_Random_1024_Ranges	30.1	100.00%	0.00%
BM_RangesSort_float_Random_16384_Classic	43.6		
BM_RangesSort_float_Random_16384_Ranges	43.7	100.23%	0.23%
BM_RangesSort_float_Random_262144_Classic	57.2		
BM_RangesSort_float_Random_262144_Ranges	56.8	99.30%	-0.70%
BM_RangesSort_float_Ascending_1_Classic	3.71		
BM_RangesSort_float_Ascending_1_Ranges	3.24	87.33%	-12.67%
BM_RangesSort_float_Ascending_4_Classic	1.21		
BM_RangesSort_float_Ascending_4_Ranges	1.14	94.21%	-5.79%
BM_RangesSort_float_Ascending_16_Classic	1.05		
BM_RangesSort_float_Ascending_16_Ranges	1	95.24%	-4.76%
BM_RangesSort_float_Ascending_64_Classic	1.12		
BM_RangesSort_float_Ascending_64_Ranges	1.11	99.11%	-0.89%
BM_RangesSort_float_Ascending_256_Classic	1.16		
BM_RangesSort_float_Ascending_256_Ranges	1.16	100.00%	0.00%
BM_RangesSort_float_Ascending_1024_Classic	1.07		
BM_RangesSort_float_Ascending_1024_Ranges	1.08	100.93%	0.93%
BM_RangesSort_float_Ascending_16384_Classic	1.01		
BM_RangesSort_float_Ascending_16384_Ranges	1.15	113.86%	13.86%
BM_RangesSort_float_Ascending_262144_Classic	1.08		
BM_RangesSort_float_Ascending_262144_Ranges	1.15	106.48%	6.48%
BM_RangesSort_float_Descending_1_Classic	4.47		
BM_RangesSort_float_Descending_1_Ranges	3.32	74.27%	-25.73%
BM_RangesSort_float_Descending_4_Classic	1.48		
BM_RangesSort_float_Descending_4_Ranges	1.39	93.92%	-6.08%
BM_RangesSort_float_Descending_16_Classic	5.17		
BM_RangesSort_float_Descending_16_Ranges	5.11	98.84%	-1.16%
BM_RangesSort_float_Descending_64_Classic	1.96		
BM_RangesSort_float_Descending_64_Ranges	1.96	100.00%	0.00%
BM_RangesSort_float_Descending_256_Classic	1.98		
BM_RangesSort_float_Descending_256_Ranges	1.9	95.96%	-4.04%
BM_RangesSort_float_Descending_1024_Classic	2.14		
BM_RangesSort_float_Descending_1024_Ranges	2.13	99.53%	-0.47%
BM_RangesSort_float_Descending_16384_Classic	1.94		
BM_RangesSort_float_Descending_16384_Ranges	1.89	97.42%	-2.58%
BM_RangesSort_float_Descending_262144_Classic	1.88		
BM_RangesSort_float_Descending_262144_Ranges	1.88	100.00%	0.00%
BM_RangesSort_float_SingleElement_1_Classic	3.57		
BM_RangesSort_float_SingleElement_1_Ranges	3.15	88.24%	-11.76%
BM_RangesSort_float_SingleElement_4_Classic	1.22		
BM_RangesSort_float_SingleElement_4_Ranges	1.06	86.89%	-13.11%
BM_RangesSort_float_SingleElement_16_Classic	1.01		
BM_RangesSort_float_SingleElement_16_Ranges	0.986	97.62%	-2.38%
BM_RangesSort_float_SingleElement_64_Classic	0.831		
BM_RangesSort_float_SingleElement_64_Ranges	0.885	106.50%	6.50%
BM_RangesSort_float_SingleElement_256_Classic	1.05		
BM_RangesSort_float_SingleElement_256_Ranges	1.03	98.10%	-1.90%
BM_RangesSort_float_SingleElement_1024_Classic	1.02		
BM_RangesSort_float_SingleElement_1024_Ranges	0.963	94.41%	-5.59%
BM_RangesSort_float_SingleElement_16384_Classic	0.867		
BM_RangesSort_float_SingleElement_16384_Ranges	0.79	91.12%	-8.88%
BM_RangesSort_float_SingleElement_262144_Classic	0.796		
BM_RangesSort_float_SingleElement_262144_Ranges	0.824	103.52%	3.52%
BM_RangesSort_float_PipeOrgan_1_Classic	3.86		
BM_RangesSort_float_PipeOrgan_1_Ranges	3.54	91.71%	-8.29%
BM_RangesSort_float_PipeOrgan_4_Classic	1.32		
BM_RangesSort_float_PipeOrgan_4_Ranges	1.18	89.39%	-10.61%
BM_RangesSort_float_PipeOrgan_16_Classic	2.08		
BM_RangesSort_float_PipeOrgan_16_Ranges	2.1	100.96%	0.96%
BM_RangesSort_float_PipeOrgan_64_Classic	5.17		
BM_RangesSort_float_PipeOrgan_64_Ranges	5	96.71%	-3.29%
BM_RangesSort_float_PipeOrgan_256_Classic	2.55		
BM_RangesSort_float_PipeOrgan_256_Ranges	2.56	100.39%	0.39%
BM_RangesSort_float_PipeOrgan_1024_Classic	3.26		
BM_RangesSort_float_PipeOrgan_1024_Ranges	3.27	100.31%	0.31%
BM_RangesSort_float_PipeOrgan_16384_Classic	3.67		
BM_RangesSort_float_PipeOrgan_16384_Ranges	3.71	101.09%	1.09%
BM_RangesSort_float_PipeOrgan_262144_Classic	4.28		
BM_RangesSort_float_PipeOrgan_262144_Ranges	4.37	102.10%	2.10%
BM_RangesSort_float_QuickSortAdversary_1_Classic	3.63		
BM_RangesSort_float_QuickSortAdversary_1_Ranges	3.19	87.88%	-12.12%
BM_RangesSort_float_QuickSortAdversary_4_Classic	1.22		
BM_RangesSort_float_QuickSortAdversary_4_Ranges	1.06	86.89%	-13.11%
BM_RangesSort_float_QuickSortAdversary_16_Classic	1.02		
BM_RangesSort_float_QuickSortAdversary_16_Ranges	0.989	96.96%	-3.04%
BM_RangesSort_float_QuickSortAdversary_64_Classic	8.96		
BM_RangesSort_float_QuickSortAdversary_64_Ranges	8.87	99.00%	-1.00%
BM_RangesSort_float_QuickSortAdversary_256_Classic	11.8		
BM_RangesSort_float_QuickSortAdversary_256_Ranges	11.8	100.00%	0.00%
BM_RangesSort_float_QuickSortAdversary_1024_Classic	26.5		
BM_RangesSort_float_QuickSortAdversary_1024_Ranges	26.6	100.38%	0.38%
BM_RangesSort_float_QuickSortAdversary_16384_Classic	48.6		
BM_RangesSort_float_QuickSortAdversary_16384_Ranges	49.3	101.44%	1.44%
BM_RangesSort_float_QuickSortAdversary_262144_Classic	53.2		
BM_RangesSort_float_QuickSortAdversary_262144_Ranges	53.6	100.75%	0.75%
var-const added inline comments.Jun 14 2022, 10:47 PM
libcxx/test/std/algorithms/alg.sorting/alg.sort/sort/ranges.sort.pass.cpp
2

Note: I tried changing the order so that the ranges version goes before the classic version, thinking that perhaps caching gives the latter of the two an advantage. However, the results are comparable, the ranges version still seems to have a slight edge on average.

var-const marked an inline comment as done.

Address feedback, fix the CI.

libcxx/test/std/algorithms/alg.sorting/alg.sort/sort/ranges.sort.pass.cpp
202

sort doesn't perform a well-defined number of operations. Do you mean a test that checks that the number of comparisons is less than N log(N)? I'm not sure it's meaningful for a small N. Do we have any precedent for that? I don't see this being tested for the non-ranges version of sort. There are some complexity tests for the ranges algorithms, but all those that I remember were linear.

Fix the CI.

philnik accepted this revision as: philnik.Jun 15 2022, 8:16 AM

LGTM with CI passing.

libcxx/benchmarks/algorithms/ranges_sort.bench.cpp
30

I know it exists in the other benchmarks, but we don't have to continue this tradition.

libcxx/include/__algorithm/ranges_sort.h
42–46

Ignore my comment. It's true that cv-ref qualified versions have to compare the same way, but it's not guaranteed that the comparator has to accept a const version.

libcxx/test/std/algorithms/alg.sorting/alg.sort/sort/ranges.sort.pass.cpp
2

The problem were the external instantiations. Removing them let the numbers look more expected:

-------------------------------------------------------------------------------------------
Benchmark                                                            std Time   ranges Time
-------------------------------------------------------------------------------------------
BM_Sort_uint32_Random_1                                               3.66 ns       3.96 ns
BM_Sort_uint32_Random_4                                               1.44 ns       4.46 ns
BM_Sort_uint32_Random_16                                              6.67 ns       7.34 ns
BM_Sort_uint32_Random_64                                              12.5 ns       13.1 ns
BM_Sort_uint32_Random_256                                             18.1 ns       18.8 ns
BM_Sort_uint32_Random_1024                                            23.8 ns       24.6 ns
BM_Sort_uint32_Random_16384                                           35.9 ns       36.2 ns
BM_Sort_uint32_Random_262144                                          46.3 ns       47.6 ns
BM_Sort_uint32_Ascending_1                                            3.66 ns       3.89 ns
BM_Sort_uint32_Ascending_4                                            1.43 ns       1.19 ns
BM_Sort_uint32_Ascending_16                                          0.621 ns      0.723 ns
BM_Sort_uint32_Ascending_64                                          0.686 ns      0.715 ns
BM_Sort_uint32_Ascending_256                                         0.693 ns      0.693 ns
BM_Sort_uint32_Ascending_1024                                        0.605 ns      0.604 ns
BM_Sort_uint32_Ascending_16384                                       0.567 ns      0.574 ns
BM_Sort_uint32_Ascending_262144                                      0.569 ns      0.568 ns
BM_Sort_uint32_Descending_1                                           3.69 ns       3.93 ns
BM_Sort_uint32_Descending_4                                           1.44 ns       1.38 ns
BM_Sort_uint32_Descending_16                                          3.50 ns       3.51 ns
BM_Sort_uint32_Descending_64                                          1.42 ns       1.44 ns
BM_Sort_uint32_Descending_256                                         1.25 ns       1.20 ns
BM_Sort_uint32_Descending_1024                                        1.48 ns       1.49 ns
BM_Sort_uint32_Descending_16384                                       1.30 ns       1.30 ns
BM_Sort_uint32_Descending_262144                                      1.28 ns       1.27 ns
BM_Sort_uint32_SingleElement_1                                        3.68 ns       3.91 ns
BM_Sort_uint32_SingleElement_4                                        1.45 ns       1.20 ns
BM_Sort_uint32_SingleElement_16                                      0.632 ns      0.694 ns
BM_Sort_uint32_SingleElement_64                                      0.557 ns      0.564 ns
BM_Sort_uint32_SingleElement_256                                     0.575 ns      0.575 ns
BM_Sort_uint32_SingleElement_1024                                    0.502 ns      0.503 ns
BM_Sort_uint32_SingleElement_16384                                   0.478 ns      0.478 ns
BM_Sort_uint32_SingleElement_262144                                  0.477 ns      0.478 ns
BM_Sort_uint32_PipeOrgan_1                                            3.68 ns       3.90 ns
BM_Sort_uint32_PipeOrgan_4                                            1.44 ns       1.25 ns
BM_Sort_uint32_PipeOrgan_16                                           1.53 ns       1.69 ns
BM_Sort_uint32_PipeOrgan_64                                           3.19 ns       3.37 ns
BM_Sort_uint32_PipeOrgan_256                                          1.93 ns       2.05 ns
BM_Sort_uint32_PipeOrgan_1024                                         2.50 ns       2.70 ns
BM_Sort_uint32_PipeOrgan_16384                                        3.17 ns       3.16 ns
BM_Sort_uint32_PipeOrgan_262144                                       3.78 ns       3.71 ns
BM_Sort_uint32_QuickSortAdversary_1                                   3.91 ns       3.69 ns
BM_Sort_uint32_QuickSortAdversary_4                                   1.50 ns       1.13 ns
BM_Sort_uint32_QuickSortAdversary_16                                 0.638 ns      0.683 ns
BM_Sort_uint32_QuickSortAdversary_64                                  10.0 ns       9.91 ns
BM_Sort_uint32_QuickSortAdversary_256                                 16.6 ns       16.3 ns
BM_Sort_uint32_QuickSortAdversary_1024                                20.4 ns       19.9 ns
BM_Sort_uint32_QuickSortAdversary_16384                               32.8 ns       32.6 ns
BM_Sort_uint32_QuickSortAdversary_262144                              44.6 ns       44.5 ns
BM_Sort_uint64_Random_1                                               3.71 ns       3.91 ns
BM_Sort_uint64_Random_4                                               1.45 ns       4.51 ns
BM_Sort_uint64_Random_16                                              6.76 ns       7.52 ns
BM_Sort_uint64_Random_64                                              12.7 ns       13.2 ns
BM_Sort_uint64_Random_256                                             18.5 ns       19.1 ns
BM_Sort_uint64_Random_1024                                            24.3 ns       25.0 ns
BM_Sort_uint64_Random_16384                                           35.9 ns       36.6 ns
BM_Sort_uint64_Random_262144                                          48.2 ns       47.5 ns
BM_Sort_uint64_Ascending_1                                            3.75 ns       3.88 ns
BM_Sort_uint64_Ascending_4                                            1.45 ns       1.20 ns
BM_Sort_uint64_Ascending_16                                          0.738 ns      0.743 ns
BM_Sort_uint64_Ascending_64                                          0.718 ns      0.713 ns
BM_Sort_uint64_Ascending_256                                         0.739 ns      0.718 ns
BM_Sort_uint64_Ascending_1024                                        0.632 ns      0.623 ns
BM_Sort_uint64_Ascending_16384                                       0.584 ns      0.579 ns
BM_Sort_uint64_Ascending_262144                                      0.586 ns      0.573 ns
BM_Sort_uint64_Descending_1                                           3.92 ns       3.90 ns
BM_Sort_uint64_Descending_4                                           1.49 ns       1.38 ns
BM_Sort_uint64_Descending_16                                          3.51 ns       3.50 ns
BM_Sort_uint64_Descending_64                                          1.42 ns       1.52 ns
BM_Sort_uint64_Descending_256                                         1.27 ns       1.22 ns
BM_Sort_uint64_Descending_1024                                        1.50 ns       1.49 ns
BM_Sort_uint64_Descending_16384                                       1.32 ns       1.30 ns
BM_Sort_uint64_Descending_262144                                      1.28 ns       1.31 ns
BM_Sort_uint64_SingleElement_1                                        3.87 ns       3.91 ns
BM_Sort_uint64_SingleElement_4                                        1.48 ns       1.21 ns
BM_Sort_uint64_SingleElement_16                                      0.715 ns      0.718 ns
BM_Sort_uint64_SingleElement_64                                      0.592 ns      0.809 ns
BM_Sort_uint64_SingleElement_256                                     0.590 ns      0.782 ns
BM_Sort_uint64_SingleElement_1024                                    0.530 ns      0.740 ns
BM_Sort_uint64_SingleElement_16384                                   0.492 ns      0.717 ns
BM_Sort_uint64_SingleElement_262144                                  0.487 ns      0.719 ns
BM_Sort_uint64_PipeOrgan_1                                            3.67 ns       3.91 ns
BM_Sort_uint64_PipeOrgan_4                                            1.44 ns       1.26 ns
BM_Sort_uint64_PipeOrgan_16                                           1.33 ns       1.59 ns
BM_Sort_uint64_PipeOrgan_64                                           3.24 ns       3.46 ns
BM_Sort_uint64_PipeOrgan_256                                          1.99 ns       2.06 ns
BM_Sort_uint64_PipeOrgan_1024                                         2.64 ns       2.63 ns
BM_Sort_uint64_PipeOrgan_16384                                        3.18 ns       3.17 ns
BM_Sort_uint64_PipeOrgan_262144                                       3.76 ns       3.76 ns
BM_Sort_uint64_QuickSortAdversary_1                                   3.69 ns       3.70 ns
BM_Sort_uint64_QuickSortAdversary_4                                   1.45 ns       1.11 ns
BM_Sort_uint64_QuickSortAdversary_16                                 0.706 ns      0.694 ns
BM_Sort_uint64_QuickSortAdversary_64                                  9.92 ns       9.96 ns
BM_Sort_uint64_QuickSortAdversary_256                                 16.5 ns       16.3 ns
BM_Sort_uint64_QuickSortAdversary_1024                                20.0 ns       20.1 ns
BM_Sort_uint64_QuickSortAdversary_16384                               32.8 ns       33.0 ns
BM_Sort_uint64_QuickSortAdversary_262144                              45.0 ns       45.3 ns
BM_Sort_pair<uint32, uint32>_Random_1                                 3.91 ns       4.01 ns
BM_Sort_pair<uint32, uint32>_Random_4                                 5.73 ns       5.89 ns
BM_Sort_pair<uint32, uint32>_Random_16                                17.7 ns       17.5 ns
BM_Sort_pair<uint32, uint32>_Random_64                                27.4 ns       26.5 ns
BM_Sort_pair<uint32, uint32>_Random_256                               35.1 ns       34.0 ns
BM_Sort_pair<uint32, uint32>_Random_1024                              42.4 ns       41.0 ns
BM_Sort_pair<uint32, uint32>_Random_16384                             57.3 ns       55.2 ns
BM_Sort_pair<uint32, uint32>_Random_262144                            70.9 ns       68.6 ns
BM_Sort_pair<uint32, uint32>_Ascending_1                              3.94 ns       4.12 ns
BM_Sort_pair<uint32, uint32>_Ascending_4                              1.67 ns       1.79 ns
BM_Sort_pair<uint32, uint32>_Ascending_16                             2.18 ns       1.91 ns
BM_Sort_pair<uint32, uint32>_Ascending_64                             1.67 ns       1.54 ns
BM_Sort_pair<uint32, uint32>_Ascending_256                            1.73 ns       1.60 ns
BM_Sort_pair<uint32, uint32>_Ascending_1024                           1.63 ns       1.51 ns
BM_Sort_pair<uint32, uint32>_Ascending_16384                          1.58 ns       1.47 ns
BM_Sort_pair<uint32, uint32>_Ascending_262144                         1.57 ns       1.46 ns
BM_Sort_pair<uint32, uint32>_Descending_1                             4.17 ns       4.01 ns
BM_Sort_pair<uint32, uint32>_Descending_4                             2.40 ns       2.39 ns
BM_Sort_pair<uint32, uint32>_Descending_16                            5.09 ns       4.39 ns
BM_Sort_pair<uint32, uint32>_Descending_64                            3.58 ns       2.97 ns
BM_Sort_pair<uint32, uint32>_Descending_256                           3.15 ns       2.71 ns
BM_Sort_pair<uint32, uint32>_Descending_1024                          4.05 ns       3.58 ns
BM_Sort_pair<uint32, uint32>_Descending_16384                         3.84 ns       3.36 ns
BM_Sort_pair<uint32, uint32>_Descending_262144                        3.74 ns       3.28 ns
BM_Sort_pair<uint32, uint32>_SingleElement_1                          4.15 ns       3.77 ns
BM_Sort_pair<uint32, uint32>_SingleElement_4                          1.79 ns       1.79 ns
BM_Sort_pair<uint32, uint32>_SingleElement_16                         1.91 ns       1.83 ns
BM_Sort_pair<uint32, uint32>_SingleElement_64                         1.80 ns       1.81 ns
BM_Sort_pair<uint32, uint32>_SingleElement_256                        1.76 ns       1.67 ns
BM_Sort_pair<uint32, uint32>_SingleElement_1024                       1.68 ns       1.60 ns
BM_Sort_pair<uint32, uint32>_SingleElement_16384                      1.64 ns       1.56 ns
BM_Sort_pair<uint32, uint32>_SingleElement_262144                     1.63 ns       1.55 ns
BM_Sort_pair<uint32, uint32>_PipeOrgan_1                              3.90 ns       4.01 ns
BM_Sort_pair<uint32, uint32>_PipeOrgan_4                              1.87 ns       1.91 ns
BM_Sort_pair<uint32, uint32>_PipeOrgan_16                             5.27 ns       4.89 ns
BM_Sort_pair<uint32, uint32>_PipeOrgan_64                             5.41 ns       4.90 ns
BM_Sort_pair<uint32, uint32>_PipeOrgan_256                            7.26 ns       6.14 ns
BM_Sort_pair<uint32, uint32>_PipeOrgan_1024                           8.95 ns       7.45 ns
BM_Sort_pair<uint32, uint32>_PipeOrgan_16384                          9.95 ns       8.89 ns
BM_Sort_pair<uint32, uint32>_PipeOrgan_262144                         12.2 ns       10.7 ns
BM_Sort_pair<uint32, uint32>_QuickSortAdversary_1                     3.94 ns       4.12 ns
BM_Sort_pair<uint32, uint32>_QuickSortAdversary_4                     2.00 ns       2.02 ns
BM_Sort_pair<uint32, uint32>_QuickSortAdversary_16                    4.81 ns       4.24 ns
BM_Sort_pair<uint32, uint32>_QuickSortAdversary_64                    8.56 ns       7.43 ns
BM_Sort_pair<uint32, uint32>_QuickSortAdversary_256                   12.5 ns       10.9 ns
BM_Sort_pair<uint32, uint32>_QuickSortAdversary_1024                  14.6 ns       13.0 ns
BM_Sort_pair<uint32, uint32>_QuickSortAdversary_16384                 28.9 ns       27.3 ns
BM_Sort_pair<uint32, uint32>_QuickSortAdversary_262144                34.7 ns       32.4 ns
BM_Sort_tuple<uint32, uint64, uint32>_Random_1                        4.09 ns       4.59 ns
BM_Sort_tuple<uint32, uint64, uint32>_Random_4                        6.62 ns       6.36 ns
BM_Sort_tuple<uint32, uint64, uint32>_Random_16                       19.9 ns       20.7 ns
BM_Sort_tuple<uint32, uint64, uint32>_Random_64                       30.3 ns       30.8 ns
BM_Sort_tuple<uint32, uint64, uint32>_Random_256                      37.8 ns       38.2 ns
BM_Sort_tuple<uint32, uint64, uint32>_Random_1024                     44.8 ns       44.9 ns
BM_Sort_tuple<uint32, uint64, uint32>_Random_16384                    59.0 ns       58.9 ns
BM_Sort_tuple<uint32, uint64, uint32>_Random_262144                   71.9 ns       73.0 ns
BM_Sort_tuple<uint32, uint64, uint32>_Ascending_1                     4.04 ns       4.59 ns
BM_Sort_tuple<uint32, uint64, uint32>_Ascending_4                     2.07 ns       2.11 ns
BM_Sort_tuple<uint32, uint64, uint32>_Ascending_16                    2.39 ns       2.35 ns
BM_Sort_tuple<uint32, uint64, uint32>_Ascending_64                    2.07 ns       1.97 ns
BM_Sort_tuple<uint32, uint64, uint32>_Ascending_256                   2.01 ns       2.00 ns
BM_Sort_tuple<uint32, uint64, uint32>_Ascending_1024                  1.88 ns       1.88 ns
BM_Sort_tuple<uint32, uint64, uint32>_Ascending_16384                 1.72 ns       1.73 ns
BM_Sort_tuple<uint32, uint64, uint32>_Ascending_262144                1.72 ns       1.67 ns
BM_Sort_tuple<uint32, uint64, uint32>_Descending_1                    4.28 ns       4.20 ns
BM_Sort_tuple<uint32, uint64, uint32>_Descending_4                    3.00 ns       2.94 ns
BM_Sort_tuple<uint32, uint64, uint32>_Descending_16                   5.35 ns       5.25 ns
BM_Sort_tuple<uint32, uint64, uint32>_Descending_64                   3.93 ns       3.72 ns
BM_Sort_tuple<uint32, uint64, uint32>_Descending_256                  3.25 ns       3.16 ns
BM_Sort_tuple<uint32, uint64, uint32>_Descending_1024                 4.13 ns       4.06 ns
BM_Sort_tuple<uint32, uint64, uint32>_Descending_16384                3.84 ns       3.73 ns
BM_Sort_tuple<uint32, uint64, uint32>_Descending_262144               3.96 ns       3.67 ns
BM_Sort_tuple<uint32, uint64, uint32>_SingleElement_1                 4.03 ns       4.25 ns
BM_Sort_tuple<uint32, uint64, uint32>_SingleElement_4                 1.99 ns       2.02 ns
BM_Sort_tuple<uint32, uint64, uint32>_SingleElement_16                2.67 ns       2.56 ns
BM_Sort_tuple<uint32, uint64, uint32>_SingleElement_64                2.71 ns       2.50 ns
BM_Sort_tuple<uint32, uint64, uint32>_SingleElement_256               2.35 ns       2.26 ns
BM_Sort_tuple<uint32, uint64, uint32>_SingleElement_1024              2.22 ns       2.16 ns
BM_Sort_tuple<uint32, uint64, uint32>_SingleElement_16384             2.12 ns       2.07 ns
BM_Sort_tuple<uint32, uint64, uint32>_SingleElement_262144            2.08 ns       2.06 ns
BM_Sort_tuple<uint32, uint64, uint32>_PipeOrgan_1                     4.06 ns       4.25 ns
BM_Sort_tuple<uint32, uint64, uint32>_PipeOrgan_4                     2.17 ns       2.25 ns
BM_Sort_tuple<uint32, uint64, uint32>_PipeOrgan_16                    5.68 ns       5.49 ns
BM_Sort_tuple<uint32, uint64, uint32>_PipeOrgan_64                    5.87 ns       5.78 ns
BM_Sort_tuple<uint32, uint64, uint32>_PipeOrgan_256                   7.21 ns       7.08 ns
BM_Sort_tuple<uint32, uint64, uint32>_PipeOrgan_1024                  8.61 ns       8.37 ns
BM_Sort_tuple<uint32, uint64, uint32>_PipeOrgan_16384                 10.5 ns       9.99 ns
BM_Sort_tuple<uint32, uint64, uint32>_PipeOrgan_262144                12.2 ns       11.6 ns
BM_Sort_tuple<uint32, uint64, uint32>_QuickSortAdversary_1            4.07 ns       3.99 ns
BM_Sort_tuple<uint32, uint64, uint32>_QuickSortAdversary_4            2.38 ns       2.31 ns
BM_Sort_tuple<uint32, uint64, uint32>_QuickSortAdversary_16           5.03 ns       5.10 ns
BM_Sort_tuple<uint32, uint64, uint32>_QuickSortAdversary_64           10.2 ns       10.0 ns
BM_Sort_tuple<uint32, uint64, uint32>_QuickSortAdversary_256          14.2 ns       14.0 ns
BM_Sort_tuple<uint32, uint64, uint32>_QuickSortAdversary_1024         16.2 ns       15.8 ns
BM_Sort_tuple<uint32, uint64, uint32>_QuickSortAdversary_16384        36.9 ns       37.0 ns
BM_Sort_tuple<uint32, uint64, uint32>_QuickSortAdversary_262144       43.0 ns       42.5 ns
BM_Sort_string_Random_1                                               4.45 ns       5.12 ns
BM_Sort_string_Random_4                                               21.2 ns       20.4 ns
BM_Sort_string_Random_16                                              45.4 ns       45.8 ns
BM_Sort_string_Random_64                                              62.3 ns       62.6 ns
BM_Sort_string_Random_256                                             77.8 ns       77.5 ns
BM_Sort_string_Random_1024                                            96.8 ns       97.6 ns
BM_Sort_string_Random_16384                                            139 ns        142 ns
BM_Sort_string_Random_262144                                           234 ns        247 ns
BM_Sort_string_Ascending_1                                            4.45 ns       5.11 ns
BM_Sort_string_Ascending_4                                            15.1 ns       15.2 ns
BM_Sort_string_Ascending_16                                           24.8 ns       25.8 ns
BM_Sort_string_Ascending_64                                           23.0 ns       24.0 ns
BM_Sort_string_Ascending_256                                          21.6 ns       22.0 ns
BM_Sort_string_Ascending_1024                                         25.3 ns       25.2 ns
BM_Sort_string_Ascending_16384                                        29.0 ns       28.8 ns
BM_Sort_string_Ascending_262144                                       55.5 ns       59.7 ns
BM_Sort_string_Descending_1                                           4.44 ns       4.91 ns
BM_Sort_string_Descending_4                                           17.6 ns       17.6 ns
BM_Sort_string_Descending_16                                          32.2 ns       32.2 ns
BM_Sort_string_Descending_64                                          29.7 ns       29.8 ns
BM_Sort_string_Descending_256                                         27.9 ns       27.8 ns
BM_Sort_string_Descending_1024                                        35.3 ns       35.6 ns
BM_Sort_string_Descending_16384                                       41.8 ns       41.8 ns
BM_Sort_string_Descending_262144                                      82.6 ns       82.5 ns
BM_Sort_string_SingleElement_1                                        4.59 ns       4.98 ns
BM_Sort_string_SingleElement_4                                        8.39 ns       8.78 ns
BM_Sort_string_SingleElement_16                                       19.1 ns       19.5 ns
BM_Sort_string_SingleElement_64                                       17.9 ns       18.5 ns
BM_Sort_string_SingleElement_256                                      12.1 ns       12.2 ns
BM_Sort_string_SingleElement_1024                                     10.4 ns       10.1 ns
BM_Sort_string_SingleElement_16384                                    9.49 ns       9.14 ns
BM_Sort_string_SingleElement_262144                                   10.5 ns       10.0 ns
BM_Sort_string_PipeOrgan_1                                            4.44 ns       4.92 ns
BM_Sort_string_PipeOrgan_4                                            17.0 ns       16.6 ns
BM_Sort_string_PipeOrgan_16                                           32.7 ns       32.5 ns
BM_Sort_string_PipeOrgan_64                                           35.6 ns       35.2 ns
BM_Sort_string_PipeOrgan_256                                          39.6 ns       38.8 ns
BM_Sort_string_PipeOrgan_1024                                         48.5 ns       47.3 ns
BM_Sort_string_PipeOrgan_16384                                        59.1 ns       58.1 ns
BM_Sort_string_PipeOrgan_262144                                        117 ns        114 ns
BM_Sort_string_QuickSortAdversary_1                                   4.46 ns       4.93 ns
BM_Sort_string_QuickSortAdversary_4                                   20.1 ns       19.6 ns
BM_Sort_string_QuickSortAdversary_16                                  45.9 ns       46.6 ns
BM_Sort_string_QuickSortAdversary_64                                  64.1 ns       63.0 ns
BM_Sort_string_QuickSortAdversary_256                                 77.0 ns       77.8 ns
BM_Sort_string_QuickSortAdversary_1024                                96.5 ns       97.0 ns
BM_Sort_string_QuickSortAdversary_16384                                140 ns        142 ns
BM_Sort_string_QuickSortAdversary_262144                               230 ns        253 ns
BM_Sort_float_Random_1                                                3.53 ns       3.82 ns
BM_Sort_float_Random_4                                                1.31 ns       4.93 ns
BM_Sort_float_Random_16                                               8.51 ns       9.03 ns
BM_Sort_float_Random_64                                               15.9 ns       16.6 ns
BM_Sort_float_Random_256                                              23.2 ns       24.1 ns
BM_Sort_float_Random_1024                                             30.3 ns       31.5 ns
BM_Sort_float_Random_16384                                            44.8 ns       46.3 ns
BM_Sort_float_Random_262144                                           57.5 ns       59.9 ns
BM_Sort_float_Ascending_1                                             3.77 ns       3.76 ns
BM_Sort_float_Ascending_4                                             1.38 ns       1.19 ns
BM_Sort_float_Ascending_16                                           0.659 ns      0.615 ns
BM_Sort_float_Ascending_64                                           0.836 ns      0.946 ns
BM_Sort_float_Ascending_256                                          0.818 ns      0.909 ns
BM_Sort_float_Ascending_1024                                         0.689 ns      0.778 ns
BM_Sort_float_Ascending_16384                                        0.629 ns      0.718 ns
BM_Sort_float_Ascending_262144                                       0.624 ns      0.718 ns
BM_Sort_float_Descending_1                                            3.50 ns       3.91 ns
BM_Sort_float_Descending_4                                            1.31 ns       1.42 ns
BM_Sort_float_Descending_16                                           3.77 ns       3.79 ns
BM_Sort_float_Descending_64                                           1.41 ns       1.61 ns
BM_Sort_float_Descending_256                                          1.42 ns       1.44 ns
BM_Sort_float_Descending_1024                                         1.64 ns       1.68 ns
BM_Sort_float_Descending_16384                                        1.38 ns       1.47 ns
BM_Sort_float_Descending_262144                                       1.35 ns       1.42 ns
BM_Sort_float_SingleElement_1                                         3.55 ns       3.87 ns
BM_Sort_float_SingleElement_4                                         1.32 ns       1.18 ns
BM_Sort_float_SingleElement_16                                       0.636 ns      0.609 ns
BM_Sort_float_SingleElement_64                                       0.842 ns      0.843 ns
BM_Sort_float_SingleElement_256                                      0.868 ns      0.849 ns
BM_Sort_float_SingleElement_1024                                     0.804 ns      0.793 ns
BM_Sort_float_SingleElement_16384                                    0.788 ns      0.777 ns
BM_Sort_float_SingleElement_262144                                   0.778 ns      0.776 ns
BM_Sort_float_PipeOrgan_1                                             3.55 ns       3.86 ns
BM_Sort_float_PipeOrgan_4                                             1.32 ns       1.25 ns
BM_Sort_float_PipeOrgan_16                                            1.29 ns       1.28 ns
BM_Sort_float_PipeOrgan_64                                            4.19 ns       4.25 ns
BM_Sort_float_PipeOrgan_256                                           2.14 ns       2.28 ns
BM_Sort_float_PipeOrgan_1024                                          2.92 ns       2.93 ns
BM_Sort_float_PipeOrgan_16384                                         3.53 ns       3.62 ns
BM_Sort_float_PipeOrgan_262144                                        4.17 ns       4.25 ns
BM_Sort_float_QuickSortAdversary_1                                    3.54 ns       3.54 ns
BM_Sort_float_QuickSortAdversary_4                                    1.31 ns       1.10 ns
BM_Sort_float_QuickSortAdversary_16                                  0.630 ns      0.583 ns
BM_Sort_float_QuickSortAdversary_64                                   9.83 ns       9.53 ns
BM_Sort_float_QuickSortAdversary_256                                  13.1 ns       13.0 ns
BM_Sort_float_QuickSortAdversary_1024                                 23.7 ns       22.6 ns
BM_Sort_float_QuickSortAdversary_16384                                52.6 ns       52.4 ns
BM_Sort_float_QuickSortAdversary_262144                               57.9 ns       57.7 ns

I think these numbers look very good, so we might want to think about sharing the same template instantiations for the same input, but we definitely don't have to worry about performance.

202

I think the are also a few that aren't linear, but we never check complexity requirements for algorithms with big-O notation complexity.

Mordante added inline comments.Jun 15 2022, 9:09 AM
libcxx/benchmarks/algorithms/ranges_sort.bench.cpp
30

What would you propose instead?

libcxx/test/std/algorithms/alg.sorting/alg.sort/sort/ranges.sort.pass.cpp
202

The interesting part is this is the only sort algorithm expressed in terms of big-O :-(

I still think its good to test the number of comparisons and projections, but not a blocker.

var-const marked 3 inline comments as done.

Address feedback, fix the CI.

var-const added inline comments.Jun 15 2022, 12:16 PM
libcxx/benchmarks/algorithms/ranges_sort.bench.cpp
30

You mean the extraneous semicolon after the function, right? Removed.

libcxx/include/__algorithm/ranges_sort.h
42–46

Restored the previous version. Thanks for double-checking!

libcxx/test/std/algorithms/alg.sorting/alg.sort/sort/ranges.sort.pass.cpp
2

The problem were the external instantiations

Can you please elaborate on this?

ldionne accepted this revision.Jun 15 2022, 1:08 PM
ldionne added a subscriber: ldionne.
ldionne added inline comments.
libcxx/include/__algorithm/ranges_sort.h
38

Another option would be to create a named struct instead of a lambda, and specialize __is_simple_comparator in sort.h with it. I think it's an inferior solution, just mentioning it for completeness.

However, I think we should do this optimization from the get go, not in a separate patch. IMO it's important (and easy) enough to be done here.

Edit
Also note that we'll have to handle std::__less, std::less and ranges::less in this optimization. It might make sense to introduce traits to describe comparators and projections more generally and use them in both std::sort and ranges::sort (they would basically replace __is_simple_comparator). If that ends up being complicated, I guess that would justify making this change in a separate patch.

40

I would make this a static function instead of const, since it doesn't need to have access to *this.

libcxx/include/__algorithm/sort.h
587

ADL. I guess that means we need a test, too! Look for robust_against_adl.pass.cpp in the test suite, we have a couple.

libcxx/test/std/algorithms/alg.sorting/alg.sort/sort/ranges.sort.pass.cpp
2

You must have been compiling the dylib with optimizations disabled, which means that anything instantiated in the dylib was very slow. That would only apply to the STL classic algorithms (until you optimize ranges::sort for default projector+comparison), because all the external instantiations use __less, and ranges::sort would pass a lambda.

202

After discussing during live review, we don't see a good and not-too-complicated way to implement this complexity check. I think the most realistic thing we could do here is count the exact number of comparisons that libc++'s implementation does and assert that, but that seems of limited usefulness, and it would also be somewhat brittle.

libcxx/test/support/almost_satisfies_types.h
330–335

This seems to have been forgotten.

This revision is now accepted and ready to land.Jun 15 2022, 1:08 PM
var-const updated this revision to Diff 437434.Jun 15 2022, 9:00 PM
var-const marked 9 inline comments as done.

Address feedback, fix the CI.

libcxx/include/__algorithm/ranges_sort.h
38

I think we don't actually need to check the comparator in the ranges version -- it is enough to pass it as is, without a wrapper lambda, if the projection is std::identity, and let the classic version decide based on that. I added specializations for ranges::less/greater to __is_simple_comparator. I think this achieves our goals, but please let me know if I'm missing something.

libcxx/include/__algorithm/sort.h
587

Fixed, thanks for spotting this!

Hmm, the approach we're using in test/std/algorithms/ranges_robust_against_adl.compile.pass.cpp doesn't work because Incomplete ends up being instantiated when the concepts are instantiated and checked.

libcxx/test/std/algorithms/alg.sorting/alg.sort/sort/ranges.sort.pass.cpp
2

Thanks for explaining! Indeed, I was building without optimizations enabled. This time, I tried running CMake in release mode and verified in ninja output that it compiles with -O3. This gave more consistent numbers between two separate runs (first all ~300 benchmark cases with the classic version, then all of them with the ranges version). There is, however, still more variation than if running classic and ranges versions "interleaved".

It seems that most difference is within 10%, although there are some outliers in the 25%-50% range (they tend to be clustered together, too). Attaching a scatter graph{F23468573} (the numbers are differences in performance in percent, positive numbers mean the classic version is faster and negative numbers mean the ranges version is faster).

Raw numbers:

Name | Classic, ns | Ranges, ns | Ranges/classic, % | Difference (negative means ranges are faster)
BM_Sort_uint32_Random_1	3.77	3.37	89.39%	-10.61%
BM_Sort_uint32_Random_4	1.7	1.67	98.24%	-1.76%
BM_Sort_uint32_Random_16	8.15	7.51	92.15%	-7.85%
BM_Sort_uint32_Random_64	14.9	14.5	97.32%	-2.68%
BM_Sort_uint32_Random_256	21.4	21.1	98.60%	-1.40%
BM_Sort_uint32_Random_1024	27.8	28	100.72%	0.72%
BM_Sort_uint32_Random_16384	42.1	41.1	97.62%	-2.38%
BM_Sort_uint32_Random_262144	54.6	54	98.90%	-1.10%
BM_Sort_uint32_Ascending_1	3.77	3.82	101.33%	1.33%
BM_Sort_uint32_Ascending_4	1.7	1.74	102.35%	2.35%
BM_Sort_uint32_Ascending_16	0.691	0.931	134.73%	34.73%
BM_Sort_uint32_Ascending_64	1.31	1.36	103.82%	3.82%
BM_Sort_uint32_Ascending_256	1.41	1.43	101.42%	1.42%
BM_Sort_uint32_Ascending_1024	1.36	1.35	99.26%	-0.74%
BM_Sort_uint32_Ascending_16384	1.29	1.29	100.00%	0.00%
BM_Sort_uint32_Ascending_262144	1.28	1.26	98.44%	-1.56%
BM_Sort_uint32_Descending_1	3.79	3.89	102.64%	2.64%
BM_Sort_uint32_Descending_4	1.71	1.75	102.34%	2.34%
BM_Sort_uint32_Descending_16	3.12	4.01	128.53%	28.53%
BM_Sort_uint32_Descending_64	2.4	2.41	100.42%	0.42%
BM_Sort_uint32_Descending_256	2.37	2.39	100.84%	0.84%
BM_Sort_uint32_Descending_1024	2.73	2.7	98.90%	-1.10%
BM_Sort_uint32_Descending_16384	2.52	2.42	96.03%	-3.97%
BM_Sort_uint32_Descending_262144	2.53	2.41	95.26%	-4.74%
BM_Sort_uint32_SingleElement_1	3.81	3.77	98.95%	-1.05%
BM_Sort_uint32_SingleElement_4	1.74	1.77	101.72%	1.72%
BM_Sort_uint32_SingleElement_16	0.724	0.942	130.11%	30.11%
BM_Sort_uint32_SingleElement_64	0.829	0.845	101.93%	1.93%
BM_Sort_uint32_SingleElement_256	0.909	0.901	99.12%	-0.88%
BM_Sort_uint32_SingleElement_1024	0.883	0.885	100.23%	0.23%
BM_Sort_uint32_SingleElement_16384	0.793	0.797	100.50%	0.50%
BM_Sort_uint32_SingleElement_262144	0.806	0.802	99.50%	-0.50%
BM_Sort_uint32_PipeOrgan_1	3.76	3.89	103.46%	3.46%
BM_Sort_uint32_PipeOrgan_4	1.74	1.73	99.43%	-0.57%
BM_Sort_uint32_PipeOrgan_16	1.42	1.74	122.54%	22.54%
BM_Sort_uint32_PipeOrgan_64	3.65	4.79	131.23%	31.23%
BM_Sort_uint32_PipeOrgan_256	2.6	2.84	109.23%	9.23%
BM_Sort_uint32_PipeOrgan_1024	3.34	3.48	104.19%	4.19%
BM_Sort_uint32_PipeOrgan_16384	4.39	3.96	90.21%	-9.79%
BM_Sort_uint32_PipeOrgan_262144	4.63	4.67	100.86%	0.86%
BM_Sort_uint32_QuickSortAdversary_1	3.83	3.8	99.22%	-0.78%
BM_Sort_uint32_QuickSortAdversary_4	1.72	1.75	101.74%	1.74%
BM_Sort_uint32_QuickSortAdversary_16	0.697	0.918	131.71%	31.71%
BM_Sort_uint32_QuickSortAdversary_64	11.1	11	99.10%	-0.90%
BM_Sort_uint32_QuickSortAdversary_256	16.1	15.5	96.27%	-3.73%
BM_Sort_uint32_QuickSortAdversary_1024	22.2	22.1	99.55%	-0.45%
BM_Sort_uint32_QuickSortAdversary_16384	36.3	35.7	98.35%	-1.65%
BM_Sort_uint32_QuickSortAdversary_262144	50.2	49.9	99.40%	-0.60%
BM_Sort_uint64_Random_1	3.55	3.75	105.63%	5.63%
BM_Sort_uint64_Random_4	1.57	1.38	87.90%	-12.10%
BM_Sort_uint64_Random_16	9.37	7.43	79.30%	-20.70%
BM_Sort_uint64_Random_64	15.6	14.3	91.67%	-8.33%
BM_Sort_uint64_Random_256	21.5	21.1	98.14%	-1.86%
BM_Sort_uint64_Random_1024	27.4	27.4	100.00%	0.00%
BM_Sort_uint64_Random_16384	38.8	40.6	104.64%	4.64%
BM_Sort_uint64_Random_262144	50.3	53.5	106.36%	6.36%
BM_Sort_uint64_Ascending_1	3.52	3.38	96.02%	-3.98%
BM_Sort_uint64_Ascending_4	1.49	1.39	93.29%	-6.71%
BM_Sort_uint64_Ascending_16	1.12	0.767	68.48%	-31.52%
BM_Sort_uint64_Ascending_64	1.36	1.03	75.74%	-24.26%
BM_Sort_uint64_Ascending_256	1.55	1.09	70.32%	-29.68%
BM_Sort_uint64_Ascending_1024	1.47	1.02	69.39%	-30.61%
BM_Sort_uint64_Ascending_16384	1.38	0.914	66.23%	-33.77%
BM_Sort_uint64_Ascending_262144	1.39	0.986	70.94%	-29.06%
BM_Sort_uint64_Descending_1	3.57	3.38	94.68%	-5.32%
BM_Sort_uint64_Descending_4	1.48	1.4	94.59%	-5.41%
BM_Sort_uint64_Descending_16	3.53	4.41	124.93%	24.93%
BM_Sort_uint64_Descending_64	1.92	1.97	102.60%	2.60%
BM_Sort_uint64_Descending_256	1.91	2.03	106.28%	6.28%
BM_Sort_uint64_Descending_1024	2.25	2.1	93.33%	-6.67%
BM_Sort_uint64_Descending_16384	2.03	1.88	92.61%	-7.39%
BM_Sort_uint64_Descending_262144	2.24	2	89.29%	-10.71%
BM_Sort_uint64_SingleElement_1	3.52	3.3	93.75%	-6.25%
BM_Sort_uint64_SingleElement_4	1.6	1.4	87.50%	-12.50%
BM_Sort_uint64_SingleElement_16	1.11	0.761	68.56%	-31.44%
BM_Sort_uint64_SingleElement_64	1.28	0.891	69.61%	-30.39%
BM_Sort_uint64_SingleElement_256	1.28	0.892	69.69%	-30.31%
BM_Sort_uint64_SingleElement_1024	1.25	0.75	60.00%	-40.00%
BM_Sort_uint64_SingleElement_16384	1.22	0.741	60.74%	-39.26%
BM_Sort_uint64_SingleElement_262144	1.22	0.872	71.48%	-28.52%
BM_Sort_uint64_PipeOrgan_1	3.55	3.38	95.21%	-4.79%
BM_Sort_uint64_PipeOrgan_4	1.48	1.55	104.73%	4.73%
BM_Sort_uint64_PipeOrgan_16	1.68	1.73	102.98%	2.98%
BM_Sort_uint64_PipeOrgan_64	3.75	4.64	123.73%	23.73%
BM_Sort_uint64_PipeOrgan_256	2.57	2.7	105.06%	5.06%
BM_Sort_uint64_PipeOrgan_1024	3.33	3.4	102.10%	2.10%
BM_Sort_uint64_PipeOrgan_16384	3.88	3.74	96.39%	-3.61%
BM_Sort_uint64_PipeOrgan_262144	4.75	4.64	97.68%	-2.32%
BM_Sort_uint64_QuickSortAdversary_1	3.58	3.44	96.09%	-3.91%
BM_Sort_uint64_QuickSortAdversary_4	1.48	1.42	95.95%	-4.05%
BM_Sort_uint64_QuickSortAdversary_16	1.09	0.763	70.00%	-30.00%
BM_Sort_uint64_QuickSortAdversary_64	10.6	11.2	105.66%	5.66%
BM_Sort_uint64_QuickSortAdversary_256	16	15.9	99.38%	-0.62%
BM_Sort_uint64_QuickSortAdversary_1024	22.4	22.5	100.45%	0.45%
BM_Sort_uint64_QuickSortAdversary_16384	36.2	36.6	101.10%	1.10%
BM_Sort_uint64_QuickSortAdversary_262144	55.7	58.1	104.31%	4.31%
BM_Sort_pair<uint32,uint32>_Random_1	3.35	3.31	98.81%	-1.19%
BM_Sort_pair<uint32,uint32>_Random_4	6.08	6.04	99.34%	-0.66%
BM_Sort_pair<uint32,uint32>_Random_16	21.6	21.7	100.46%	0.46%
BM_Sort_pair<uint32,uint32>_Random_64	32.2	31.6	98.14%	-1.86%
BM_Sort_pair<uint32,uint32>_Random_256	40.2	39.8	99.00%	-1.00%
BM_Sort_pair<uint32,uint32>_Random_1024	47.6	48.2	101.26%	1.26%
BM_Sort_pair<uint32,uint32>_Random_16384	63	63.1	100.16%	0.16%
BM_Sort_pair<uint32,uint32>_Random_262144	81.6	80.6	98.77%	-1.23%
BM_Sort_pair<uint32,uint32>_Ascending_1	3.36	3.88	115.48%	15.48%
BM_Sort_pair<uint32,uint32>_Ascending_4	1.92	2.07	107.81%	7.81%
BM_Sort_pair<uint32,uint32>_Ascending_16	2.5	2.61	104.40%	4.40%
BM_Sort_pair<uint32,uint32>_Ascending_64	2.09	2.01	96.17%	-3.83%
BM_Sort_pair<uint32,uint32>_Ascending_256	2.08	2.07	99.52%	-0.48%
BM_Sort_pair<uint32,uint32>_Ascending_1024	1.98	1.94	97.98%	-2.02%
BM_Sort_pair<uint32,uint32>_Ascending_16384	1.91	1.93	101.05%	1.05%
BM_Sort_pair<uint32,uint32>_Ascending_262144	1.89	1.93	102.12%	2.12%
BM_Sort_pair<uint32,uint32>_Descending_1	3.34	3.87	115.87%	15.87%
BM_Sort_pair<uint32,uint32>_Descending_4	2.87	2.69	93.73%	-6.27%
BM_Sort_pair<uint32,uint32>_Descending_16	5.75	5.49	95.48%	-4.52%
BM_Sort_pair<uint32,uint32>_Descending_64	4.23	4.13	97.64%	-2.36%
BM_Sort_pair<uint32,uint32>_Descending_256	3.82	3.67	96.07%	-3.93%
BM_Sort_pair<uint32,uint32>_Descending_1024	4.98	4.95	99.40%	-0.60%
BM_Sort_pair<uint32,uint32>_Descending_16384	4.91	4.64	94.50%	-5.50%
BM_Sort_pair<uint32,uint32>_Descending_262144	4.93	4.68	94.93%	-5.07%
BM_Sort_pair<uint32,uint32>_SingleElement_1	3.35	3.78	112.84%	12.84%
BM_Sort_pair<uint32,uint32>_SingleElement_4	2	1.92	96.00%	-4.00%
BM_Sort_pair<uint32,uint32>_SingleElement_16	2.56	2.95	115.23%	15.23%
BM_Sort_pair<uint32,uint32>_SingleElement_64	2.72	2.78	102.21%	2.21%
BM_Sort_pair<uint32,uint32>_SingleElement_256	2.9	2.94	101.38%	1.38%
BM_Sort_pair<uint32,uint32>_SingleElement_1024	2.85	2.84	99.65%	-0.35%
BM_Sort_pair<uint32,uint32>_SingleElement_16384	2.78	2.79	100.36%	0.36%
BM_Sort_pair<uint32,uint32>_SingleElement_262144	2.77	2.75	99.28%	-0.72%
BM_Sort_pair<uint32,uint32>_PipeOrgan_1	3.38	3.7	109.47%	9.47%
BM_Sort_pair<uint32,uint32>_PipeOrgan_4	2.3	2.25	97.83%	-2.17%
BM_Sort_pair<uint32,uint32>_PipeOrgan_16	5.51	5.25	95.28%	-4.72%
BM_Sort_pair<uint32,uint32>_PipeOrgan_64	5.81	5.75	98.97%	-1.03%
BM_Sort_pair<uint32,uint32>_PipeOrgan_256	7.94	7.74	97.48%	-2.52%
BM_Sort_pair<uint32,uint32>_PipeOrgan_1024	9.94	9.87	99.30%	-0.70%
BM_Sort_pair<uint32,uint32>_PipeOrgan_16384	10.8	10.8	100.00%	0.00%
BM_Sort_pair<uint32,uint32>_PipeOrgan_262144	13.2	13.2	100.00%	0.00%
BM_Sort_pair<uint32,uint32>_QuickSortAdversary_1	3.35	3.76	112.24%	12.24%
BM_Sort_pair<uint32,uint32>_QuickSortAdversary_4	2.53	2.35	92.89%	-7.11%
BM_Sort_pair<uint32,uint32>_QuickSortAdversary_16	5.65	5.3	93.81%	-6.19%
BM_Sort_pair<uint32,uint32>_QuickSortAdversary_64	9.07	8.54	94.16%	-5.84%
BM_Sort_pair<uint32,uint32>_QuickSortAdversary_256	12.2	11.9	97.54%	-2.46%
BM_Sort_pair<uint32,uint32>_QuickSortAdversary_1024	14.5	14.5	100.00%	0.00%
BM_Sort_pair<uint32,uint32>_QuickSortAdversary_16384	34.6	34.1	98.55%	-1.45%
BM_Sort_pair<uint32,uint32>_QuickSortAdversary_262144	40.6	39.4	97.04%	-2.96%
BM_Sort_tuple<uint32,uint64,uint32>_Random_1	3.64	3.69	101.37%	1.37%
BM_Sort_tuple<uint32,uint64,uint32>_Random_4	6.64	6.71	101.05%	1.05%
BM_Sort_tuple<uint32,uint64,uint32>_Random_16	25.9	26.2	101.16%	1.16%
BM_Sort_tuple<uint32,uint64,uint32>_Random_64	36.7	39.3	107.08%	7.08%
BM_Sort_tuple<uint32,uint64,uint32>_Random_256	43.5	47.7	109.66%	9.66%
BM_Sort_tuple<uint32,uint64,uint32>_Random_1024	49.6	57.7	116.33%	16.33%
BM_Sort_tuple<uint32,uint64,uint32>_Random_16384	63.8	71.5	112.07%	12.07%
BM_Sort_tuple<uint32,uint64,uint32>_Random_262144	78.2	88.6	113.30%	13.30%
BM_Sort_tuple<uint32,uint64,uint32>_Ascending_1	3.69	3.66	99.19%	-0.81%
BM_Sort_tuple<uint32,uint64,uint32>_Ascending_4	2.44	2.49	102.05%	2.05%
BM_Sort_tuple<uint32,uint64,uint32>_Ascending_16	3.12	3.56	114.10%	14.10%
BM_Sort_tuple<uint32,uint64,uint32>_Ascending_64	3.51	3.35	95.44%	-4.56%
BM_Sort_tuple<uint32,uint64,uint32>_Ascending_256	3.51	3.35	95.44%	-4.56%
BM_Sort_tuple<uint32,uint64,uint32>_Ascending_1024	3.48	3.19	91.67%	-8.33%
BM_Sort_tuple<uint32,uint64,uint32>_Ascending_16384	3.16	3	94.94%	-5.06%
BM_Sort_tuple<uint32,uint64,uint32>_Ascending_262144	3.41	3.22	94.43%	-5.57%
BM_Sort_tuple<uint32,uint64,uint32>_Descending_1	3.65	3.67	100.55%	0.55%
BM_Sort_tuple<uint32,uint64,uint32>_Descending_4	3.43	3.42	99.71%	-0.29%
BM_Sort_tuple<uint32,uint64,uint32>_Descending_16	5.55	6.57	118.38%	18.38%
BM_Sort_tuple<uint32,uint64,uint32>_Descending_64	4.93	5.44	110.34%	10.34%
BM_Sort_tuple<uint32,uint64,uint32>_Descending_256	4.72	4.95	104.87%	4.87%
BM_Sort_tuple<uint32,uint64,uint32>_Descending_1024	5.68	6.43	113.20%	13.20%
BM_Sort_tuple<uint32,uint64,uint32>_Descending_16384	5.37	6.01	111.92%	11.92%
BM_Sort_tuple<uint32,uint64,uint32>_Descending_262144	6.47	6.7	103.55%	3.55%
BM_Sort_tuple<uint32,uint64,uint32>_SingleElement_1	3.66	3.59	98.09%	-1.91%
BM_Sort_tuple<uint32,uint64,uint32>_SingleElement_4	2.46	2.62	106.50%	6.50%
BM_Sort_tuple<uint32,uint64,uint32>_SingleElement_16	3.43	3.66	106.71%	6.71%
BM_Sort_tuple<uint32,uint64,uint32>_SingleElement_64	4.36	4.28	98.17%	-1.83%
BM_Sort_tuple<uint32,uint64,uint32>_SingleElement_256	4.67	4.48	95.93%	-4.07%
BM_Sort_tuple<uint32,uint64,uint32>_SingleElement_1024	4.44	4.23	95.27%	-4.73%
BM_Sort_tuple<uint32,uint64,uint32>_SingleElement_16384	3.95	3.87	97.97%	-2.03%
BM_Sort_tuple<uint32,uint64,uint32>_SingleElement_262144	3.96	3.93	99.24%	-0.76%
BM_Sort_tuple<uint32,uint64,uint32>_PipeOrgan_1	3.71	3.68	99.19%	-0.81%
BM_Sort_tuple<uint32,uint64,uint32>_PipeOrgan_4	2.57	2.61	101.56%	1.56%
BM_Sort_tuple<uint32,uint64,uint32>_PipeOrgan_16	5.89	6.85	116.30%	16.30%
BM_Sort_tuple<uint32,uint64,uint32>_PipeOrgan_64	6.85	7.96	116.20%	16.20%
BM_Sort_tuple<uint32,uint64,uint32>_PipeOrgan_256	8.66	9.83	113.51%	13.51%
BM_Sort_tuple<uint32,uint64,uint32>_PipeOrgan_1024	10.5	11.8	112.38%	12.38%
BM_Sort_tuple<uint32,uint64,uint32>_PipeOrgan_16384	11.9	13.8	115.97%	15.97%
BM_Sort_tuple<uint32,uint64,uint32>_PipeOrgan_262144	15	20	133.33%	33.33%
BM_Sort_tuple<uint32,uint64,uint32>_QuickSortAdversary_1	3.64	4.32	118.68%	18.68%
BM_Sort_tuple<uint32,uint64,uint32>_QuickSortAdversary_4	2.89	3.39	117.30%	17.30%
BM_Sort_tuple<uint32,uint64,uint32>_QuickSortAdversary_16	5.41	6.67	123.29%	23.29%
BM_Sort_tuple<uint32,uint64,uint32>_QuickSortAdversary_64	9.81	11.9	121.30%	21.30%
BM_Sort_tuple<uint32,uint64,uint32>_QuickSortAdversary_256	13.7	16.8	122.63%	22.63%
BM_Sort_tuple<uint32,uint64,uint32>_QuickSortAdversary_1024	21	26	123.81%	23.81%
BM_Sort_tuple<uint32,uint64,uint32>_QuickSortAdversary_16384	43.3	50.1	115.70%	15.70%
BM_Sort_tuple<uint32,uint64,uint32>_QuickSortAdversary_262144	49	58.2	118.78%	18.78%
BM_Sort_string_Random_1	4.39	4.39	100.00%	0.00%
BM_Sort_string_Random_4	16.9	16.9	100.00%	0.00%
BM_Sort_string_Random_16	47.2	48.3	102.33%	2.33%
BM_Sort_string_Random_64	75.5	72.9	96.56%	-3.44%
BM_Sort_string_Random_256	93.8	94.8	101.07%	1.07%
BM_Sort_string_Random_1024	115	115	100.00%	0.00%
BM_Sort_string_Random_16384	184	182	98.91%	-1.09%
BM_Sort_string_Random_262144	302	296	98.01%	-1.99%
BM_Sort_string_Ascending_1	4.43	4.41	99.55%	-0.45%
BM_Sort_string_Ascending_4	9.78	9.44	96.52%	-3.48%
BM_Sort_string_Ascending_16	16.6	16.5	99.40%	-0.60%
BM_Sort_string_Ascending_64	23.1	22.3	96.54%	-3.46%
BM_Sort_string_Ascending_256	22.2	21.2	95.50%	-4.50%
BM_Sort_string_Ascending_1024	21.9	21	95.89%	-4.11%
BM_Sort_string_Ascending_16384	36.2	35.2	97.24%	-2.76%
BM_Sort_string_Ascending_262144	46.5	44.6	95.91%	-4.09%
BM_Sort_string_Descending_1	4.34	4.72	108.76%	8.76%
BM_Sort_string_Descending_4	12	14.1	117.50%	17.50%
BM_Sort_string_Descending_16	27.1	33.8	124.72%	24.72%
BM_Sort_string_Descending_64	31.3	34.8	111.18%	11.18%
BM_Sort_string_Descending_256	29.3	30.1	102.73%	2.73%
BM_Sort_string_Descending_1024	33.9	34.1	100.59%	0.59%
BM_Sort_string_Descending_16384	49	57.1	116.53%	16.53%
BM_Sort_string_Descending_262144	84.4	87.2	103.32%	3.32%
BM_Sort_string_SingleElement_1	4.4	4.57	103.86%	3.86%
BM_Sort_string_SingleElement_4	9.5	9.36	98.53%	-1.47%
BM_Sort_string_SingleElement_16	19	18.9	99.47%	-0.53%
BM_Sort_string_SingleElement_64	28.5	27.8	97.54%	-2.46%
BM_Sort_string_SingleElement_256	23	22.5	97.83%	-2.17%
BM_Sort_string_SingleElement_1024	20.1	20.9	103.98%	3.98%
BM_Sort_string_SingleElement_16384	17.9	19.1	106.70%	6.70%
BM_Sort_string_SingleElement_262144	19.6	20	102.04%	2.04%
BM_Sort_string_PipeOrgan_1	4.59	4.72	102.83%	2.83%
BM_Sort_string_PipeOrgan_4	11.4	10.8	94.74%	-5.26%
BM_Sort_string_PipeOrgan_16	26.5	26.7	100.75%	0.75%
BM_Sort_string_PipeOrgan_64	42.1	41.8	99.29%	-0.71%
BM_Sort_string_PipeOrgan_256	51.3	51.7	100.78%	0.78%
BM_Sort_string_PipeOrgan_1024	58	59.7	102.93%	2.93%
BM_Sort_string_PipeOrgan_16384	80.3	82.5	102.74%	2.74%
BM_Sort_string_PipeOrgan_262144	135	143	105.93%	5.93%
BM_Sort_string_QuickSortAdversary_1	4.5	4.7	104.44%	4.44%
BM_Sort_string_QuickSortAdversary_4	17.3	17.7	102.31%	2.31%
BM_Sort_string_QuickSortAdversary_16	49.8	48.3	96.99%	-3.01%
BM_Sort_string_QuickSortAdversary_64	76.9	77.6	100.91%	0.91%
BM_Sort_string_QuickSortAdversary_256	97.2	98	100.82%	0.82%
BM_Sort_string_QuickSortAdversary_1024	118	119	100.85%	0.85%
BM_Sort_string_QuickSortAdversary_16384	186	191	102.69%	2.69%
BM_Sort_string_QuickSortAdversary_262144	293	302	103.07%	3.07%
BM_Sort_float_Random_1	3.69	3.9	105.69%	5.69%
BM_Sort_float_Random_4	1.38	1.33	96.38%	-3.62%
BM_Sort_float_Random_16	9.23	8.87	96.10%	-3.90%
BM_Sort_float_Random_64	16.3	15.9	97.55%	-2.45%
BM_Sort_float_Random_256	22.7	22.4	98.68%	-1.32%
BM_Sort_float_Random_1024	29.6	29.5	99.66%	-0.34%
BM_Sort_float_Random_16384	43.2	42.8	99.07%	-0.93%
BM_Sort_float_Random_262144	54.5	55.1	101.10%	1.10%
BM_Sort_float_Ascending_1	3.57	4.06	113.73%	13.73%
BM_Sort_float_Ascending_4	1.4	1.36	97.14%	-2.86%
BM_Sort_float_Ascending_16	0.91	0.851	93.52%	-6.48%
BM_Sort_float_Ascending_64	0.955	1.34	140.31%	40.31%
BM_Sort_float_Ascending_256	1.06	1.43	134.91%	34.91%
BM_Sort_float_Ascending_1024	0.943	1.34	142.10%	42.10%
BM_Sort_float_Ascending_16384	0.878	1.28	145.79%	45.79%
BM_Sort_float_Ascending_262144	0.878	1.28	145.79%	45.79%
BM_Sort_float_Descending_1	3.64	4.02	110.44%	10.44%
BM_Sort_float_Descending_4	1.39	1.31	94.24%	-5.76%
BM_Sort_float_Descending_16	3.64	3.54	97.25%	-2.75%
BM_Sort_float_Descending_64	1.73	2.06	119.08%	19.08%
BM_Sort_float_Descending_256	1.66	2.09	125.90%	25.90%
BM_Sort_float_Descending_1024	1.95	2.33	119.49%	19.49%
BM_Sort_float_Descending_16384	1.73	2.14	123.70%	23.70%
BM_Sort_float_Descending_262144	1.78	2.15	120.79%	20.79%
BM_Sort_float_SingleElement_1	3.56	4.02	112.92%	12.92%
BM_Sort_float_SingleElement_4	1.38	1.33	96.38%	-3.62%
BM_Sort_float_SingleElement_16	0.894	0.852	95.30%	-4.70%
BM_Sort_float_SingleElement_64	0.886	0.896	101.13%	1.13%
BM_Sort_float_SingleElement_256	1.02	1.03	100.98%	0.98%
BM_Sort_float_SingleElement_1024	0.974	1.01	103.70%	3.70%
BM_Sort_float_SingleElement_16384	0.901	0.927	102.89%	2.89%
BM_Sort_float_SingleElement_262144	0.9	0.921	102.33%	2.33%
BM_Sort_float_PipeOrgan_1	3.59	3.99	111.14%	11.14%
BM_Sort_float_PipeOrgan_4	1.38	1.34	97.10%	-2.90%
BM_Sort_float_PipeOrgan_16	1.67	1.81	108.38%	8.38%
BM_Sort_float_PipeOrgan_64	3.99	4.89	122.56%	22.56%
BM_Sort_float_PipeOrgan_256	2.28	2.58	113.16%	13.16%
BM_Sort_float_PipeOrgan_1024	3.07	3.28	106.84%	6.84%
BM_Sort_float_PipeOrgan_16384	3.55	3.77	106.20%	6.20%
BM_Sort_float_PipeOrgan_262144	4.18	4.4	105.26%	5.26%
BM_Sort_float_QuickSortAdversary_1	3.5	4.06	116.00%	16.00%
BM_Sort_float_QuickSortAdversary_4	1.39	1.34	96.40%	-3.60%
BM_Sort_float_QuickSortAdversary_16	0.895	0.858	95.87%	-4.13%
BM_Sort_float_QuickSortAdversary_64	10.2	10.3	100.98%	0.98%
BM_Sort_float_QuickSortAdversary_256	14.3	14.5	101.40%	1.40%
BM_Sort_float_QuickSortAdversary_1024	38.2	38.8	101.57%	1.57%
BM_Sort_float_QuickSortAdversary_16384	56.6	58.1	102.65%	2.65%
BM_Sort_float_QuickSortAdversary_262144	68.6	67.9	98.98%	-1.02%
libcxx/test/support/almost_satisfies_types.h
330–335

Thanks for spotting this!

var-const updated this revision to Diff 437435.Jun 15 2022, 9:03 PM

Rebase on main.

Mordante accepted this revision.Jun 16 2022, 9:43 AM

LGTM when the CI passes.

ldionne added inline comments.Jun 16 2022, 11:00 AM
libcxx/include/__algorithm/ranges_common.h
6 ↗(On Diff #437435)

make_projected.h? ranges_common.h means that this will likely become a dumping ground, which we're trying to avoid with the header "modularization".

30 ↗(On Diff #437435)

I would only add this when you actually need it, otherwise it's basically adding a never used function (without tests, because nothing's using it).

40–42 ↗(On Diff #437435)

How about this instead:

template <class _Comp, class _Proj>
_LIBCPP_HIDE_FROM_ABI constexpr static
decltype(auto) __make_projected_comp(_Comp& __comp, _Proj& __proj) {
  if constexpr (same_as<_Proj, identity>) {
    return __comp;
  } else {
    return <lambda>;
  }
}

and then from the caller side, use:

auto&& __projected_comp = __make_projected_comp(__comp, __proj);

I'm not sure which one is better, but this is another option. The benefit with this version is that we can forego the if constexpr inside __sort_fn_impl (and possibly other algorithms in the future).

You can also centralize your comment about // Avoid creating the lambda [...] in __sort_fn_impl here.

libcxx/include/__algorithm/sort.h
116

While we're at it, can you please add a comment explaining what's the purpose of this trait?

var-const marked 5 inline comments as done.

Address the feedback.

libcxx/include/__algorithm/ranges_common.h
40–42 ↗(On Diff #437435)

Thanks!

Fix the CI.

This revision was automatically updated to reflect the committed changes.