4 ms·

> that argues it's the users responsibility to be careful, If you try to sort with a function that's not a valid comparison operator, I don't know what to tel

> that argues it's the users responsibility to be careful, If you try to sort with a function that's not a valid comparison operator, I don't know what to tell you. What should it do? Semantics cannot be validated at compile time. The best that can be done is to annotate the function as "yes this should have the right semantics" as is done in Rust and C++ concepts, but that's still not a guarantee.

fluoridation 3y ago
There are still ways for a sort function to not work properly with the comparer, even if the criterion is correct. As mentioned in the article, the comparer might have internal state that the sorter duplicates during intermediate steps, thus breaking assumptions made by the caller. The example the article gives is a comparer that increments a variable each time it's called, to count the number of comparisons. Depending on how this is done and how the sorter is implemented, copying the comparer may break this behavior.
- deleted 3y ago
  [deleted]
jeffbee 3y ago
In C++ your relational operators can return std::partial_ordering etc which is a bit more semantically meaningful, for the reader and the compiler.
- prosqlinjector 3y ago
  Agreed. And I think that's a good idea to do. It's still possible to do wrong.
itishappy 3y ago
> What should it do? If I'm reading the article correctly, the user can be informed at runtime with little to no performance impact. That certainly sounds preferable to returning an unsorted list (that may not even match the input). Almost every Rust sort does this, but no C/C++ sorts do. That appears to support that author's conclusion that this is a cultural thing.
- prosqlinjector 3y ago
  > If I'm reading the article correctly, the user can be informed at runtime with little to no performance impact. It's not possible to verify a function is a strict weak ordering without enumerating the entire domain.
  - itishappy 3y ago
    Right, but restricting the domain to just the list you're already enumerating makes things easier.
    - prosqlinjector 3y ago
      Yep, so now your sort function isn't just a sort. It's a sort with a unit test at the beginning. This burden is placed on EVERY use.
  - Voultapher 3y ago
    I'm not sure enumerating the entire domain is even possible in this setting, as the comparison function could return random values for each call. The idea is that the implementation doesn't promise it will detect a strict weak ordering violation, but it has code that will detect the effects of such violations with a high probability. It's not a sampled approach, but rather as part of the small-sort a bi-directional merge is performed and if the pointers don't line up, the only explanation is a strict weak ordering violation, the result of the merge is discarded and a panic is raised.

fluoridation 3y ago

There are still ways for a sort function to not work properly with the comparer, even if the criterion is correct. As mentioned in the article, the comparer might have internal state that the sorter duplicates during intermediate steps, thus breaking assumptions made by the caller. The example the article gives is a comparer that increments a variable each time it's called, to count the number of comparisons. Depending on how this is done and how the sorter is implemented, copying the comparer may break this behavior.

deleted 3y ago
[deleted]

jeffbee 3y ago

In C++ your relational operators can return std::partial_ordering etc which is a bit more semantically meaningful, for the reader and the compiler.

prosqlinjector 3y ago
Agreed. And I think that's a good idea to do. It's still possible to do wrong.

itishappy 3y ago

> What should it do? If I'm reading the article correctly, the user can be informed at runtime with little to no performance impact. That certainly sounds preferable to returning an unsorted list (that may not even match the input). Almost every Rust sort does this, but no C/C++ sorts do. That appears to support that author's conclusion that this is a cultural thing.

prosqlinjector 3y ago
> If I'm reading the article correctly, the user can be informed at runtime with little to no performance impact. It's not possible to verify a function is a strict weak ordering without enumerating the entire domain.
- itishappy 3y ago
  Right, but restricting the domain to just the list you're already enumerating makes things easier.
  - prosqlinjector 3y ago
    Yep, so now your sort function isn't just a sort. It's a sort with a unit test at the beginning. This burden is placed on EVERY use.
- Voultapher 3y ago
  I'm not sure enumerating the entire domain is even possible in this setting, as the comparison function could return random values for each call. The idea is that the implementation doesn't promise it will detect a strict weak ordering violation, but it has code that will detect the effects of such violations with a high probability. It's not a sampled approach, but rather as part of the small-sort a bi-directional merge is performed and if the pointers don't line up, the only explanation is a strict weak ordering violation, the result of the merge is discarded and a panic is raised.