This is an archive of the discontinued LLVM Phabricator instance.

[Support] Change std::sort to llvm::sort in response to r327219
ClosedPublic

Authored by mgrang on Mar 31 2018, 7:26 PM.

Details

Summary

r327219 added wrappers to std::sort which randomly shuffle the container before sorting.
This will help in uncovering non-determinism caused due to undefined sorting
order of objects having the same key.

To make use of that infrastructure we need to invoke llvm::sort instead of std::sort.

Note: This patch is one of a series of patches to replace *all* std::sort to llvm::sort.
Refer the comments section in D44363 for a list of all the required patches.

Diff Detail

Repository
rL LLVM

Event Timeline

mgrang created this revision.Mar 31 2018, 7:26 PM

I'm a little disappointed that llvm::sort got added without providing a range-based variant, the way we did for llvm::none_of and llvm::find and others. (I wasn't watching the original thread.) I see no problem with these changes, though!

bkramer accepted this revision.Apr 4 2018, 7:42 AM

this is trivially fine.

This revision is now accepted and ready to land.Apr 4 2018, 7:42 AM
mgrang added a comment.Apr 6 2018, 6:48 PM

I'm a little disappointed that llvm::sort got added without providing a range-based variant, the way we did for llvm::none_of and llvm::find and others. (I wasn't watching the original thread.) I see no problem with these changes, though!

@jordan_rose Thanks for your suggestion. Are there instances in llvm where we perform range-based sorting? I see that std has an experimental range-based sort (std::experimental::ranges::sort) which I don't see being used in llvm.

Also what should be the semantics of a range-based shuffle sort? Will it just shuffle the given range? Or should it shuffle the entire container but just sort the range?

This revision was automatically updated to reflect the committed changes.

Are there instances in llvm where we perform range-based sorting? I see that std has an experimental range-based sort (std::experimental::ranges::sort) which I don't see being used in llvm.

I think in practice almost *every* sort we do would be range-based (i.e. we almost always sort an entire container). We generally don't use std::experimental things in LLVM because they're not reliably present across platforms, but that doesn't mean we don't provide our own implementations for good ideas.

Also what should be the semantics of a range-based shuffle sort? Will it just shuffle the given range? Or should it shuffle the entire container but just sort the range?

I don't understand this question. You can't get to the entire container from a range.

Are there instances in llvm where we perform range-based sorting? I see that std has an experimental range-based sort (std::experimental::ranges::sort) which I don't see being used in llvm.

I think in practice almost *every* sort we do would be range-based (i.e. we almost always sort an entire container). We generally don't use std::experimental things in LLVM because they're not reliably present across platforms, but that doesn't mean we don't provide our own implementations for good ideas.

Also what should be the semantics of a range-based shuffle sort? Will it just shuffle the given range? Or should it shuffle the entire container but just sort the range?

I don't understand this question. You can't get to the entire container from a range.

I think in practice almost *every* sort we do would be range-based (i.e. we almost always sort an entire container).

Exactly that's what I thought too, and llvm::sort already accepts a range (Container.begin(), Container.end()). In that case, could you please clarify what exactly do you mean by a "range-based variant" and its use cases in LLVM?
My idea of range-based was maybe you wanted to sort a subset of the container. Apologies if I did not understand the original requirement :)

Exactly that's what I thought too, and llvm::sort already accepts a range (Container.begin(), Container.end()). In that case, could you please clarify what exactly do you mean by a "range-based variant" and its use cases in LLVM?

Ah, sorry! A "range-based" collection algorithm means one that takes a "range" as an argument instead of a pair of iterators. The "range" is anything that has begin and end iterators. ("Container-based algorithm" might have been a better name, since usually the "range" you pass is the entire container, but "range" is already an accepted term in C++ language and library discussions.)

So in this case, the call would look like this:

llvm::sort(TimersToPrint);

You can check out the implementation of llvm::none_of in include/llvm/ADT/STLExtras.h to see how this works. It just forwards on to the regular implementation.

None of this is related to your shuffling work, by the way; it's just odd and a bit inconsistent that there's an llvm:: algorithm that only takes iterators.

Exactly that's what I thought too, and llvm::sort already accepts a range (Container.begin(), Container.end()). In that case, could you please clarify what exactly do you mean by a "range-based variant" and its use cases in LLVM?

Ah, sorry! A "range-based" collection algorithm means one that takes a "range" as an argument instead of a pair of iterators. The "range" is anything that has begin and end iterators. ("Container-based algorithm" might have been a better name, since usually the "range" you pass is the entire container, but "range" is already an accepted term in C++ language and library discussions.)

So in this case, the call would look like this:

llvm::sort(TimersToPrint);

You can check out the implementation of llvm::none_of in include/llvm/ADT/STLExtras.h to see how this works. It just forwards on to the regular implementation.

None of this is related to your shuffling work, by the way; it's just odd and a bit inconsistent that there's an llvm:: algorithm that only takes iterators.

Ah, got it! Thanks a lot for your clarification. I will explore adding a range-based version of llvm::sort when I have some cycles.