6 ms·
> 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 s
by 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 agoRight, but restricting the domain to just the list you're already enumerating makes things easier.
- prosqlinjector 3y agoYep, 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 agoI'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.