4 ms·

Have you seen this before in person? It would make a great blog post. I haven't personally encountered a buggy comparator without a total order.

layer8 2y ago
I have seen a lot of incorrect Comparators and Comparable implementations in existing code, but haven’t personally come across the infinite-loop situation yet. To give one example, a common error is to compare two int values via subtraction, which can give incorrect results due to overflow and modulo semantics, instead of using Integer::compare (or some equivalent of its implementation).
- smarks 2y ago
  Interesting. I haven’t seen an infinite loop either, but I can imagine one if a comparator tries to be too “clever” for example if it bases its comparison logic on some external state. Another common source of comparator bugs is when people compare floats or doubles and they don’t account for NaN, which is unequal to everything, including itself! In Java, the usual symptom of comparator bugs is that sort throws the infamous “Comparison method violates its general contract!” exception.
hollowcelery 2y ago
I knew someone who missed out on a gold medal at the International Olympiad of Informatics because his sort comparator didn’t have a total order.
- TYMorningCoffee 2y ago
  Ouch. Any idea which problem? Those problems are public: https://ioinformatics.org/page/contests/10 https://ioinformatics.org/page/contests/10
sunshowers 2y ago
When Rust's sort algorithm changed to detect total order violations, it caused some breakage. See for example: https://github.com/mitsuhiko/insta/pull/586 https://github.com/mitsuhiko/insta/pull/586 I recently wrote a blog post which (while not the main focus) includes a discussion on randomized testing of sort algorithms in the face of inconsistent comparators: https://sunshowers.io/posts/monads-through-pbt/ https://sunshowers.io/posts/monads-through-pbt/ section 2.

layer8 2y ago

I have seen a lot of incorrect Comparators and Comparable implementations in existing code, but haven’t personally come across the infinite-loop situation yet. To give one example, a common error is to compare two int values via subtraction, which can give incorrect results due to overflow and modulo semantics, instead of using Integer::compare (or some equivalent of its implementation).

smarks 2y ago
Interesting. I haven’t seen an infinite loop either, but I can imagine one if a comparator tries to be too “clever” for example if it bases its comparison logic on some external state. Another common source of comparator bugs is when people compare floats or doubles and they don’t account for NaN, which is unequal to everything, including itself! In Java, the usual symptom of comparator bugs is that sort throws the infamous “Comparison method violates its general contract!” exception.

hollowcelery 2y ago

I knew someone who missed out on a gold medal at the International Olympiad of Informatics because his sort comparator didn’t have a total order.

TYMorningCoffee 2y ago
Ouch. Any idea which problem? Those problems are public: https://ioinformatics.org/page/contests/10 https://ioinformatics.org/page/contests/10

sunshowers 2y ago

When Rust's sort algorithm changed to detect total order violations, it caused some breakage. See for example: https://github.com/mitsuhiko/insta/pull/586 https://github.com/mitsuhiko/insta/pull/586 I recently wrote a blog post which (while not the main focus) includes a discussion on randomized testing of sort algorithms in the face of inconsistent comparators: https://sunshowers.io/posts/monads-through-pbt/ https://sunshowers.io/posts/monads-through-pbt/ section 2.