4 ms·
My favourite TimSort story is of ex-Sun employee, Joshua Bloch of Effective Java fame. J Bloch was in audience at the time when Tim Peters presented his new alg
by ignoramous 7y ago
My favourite TimSort story is of ex-Sun employee, Joshua Bloch of Effective Java fame. J Bloch was in audience at the time when Tim Peters presented his new algorithm to sort a list, and he was so blown away that he started porting Tim's implementation right there with an intent to commit it to the JDK mainline [0], which he eventually did [1].
[0] Some of the core JDK developers are really on another level. The JDK code, post 1.5, is a joy to read, though verbose. Compilers and Languages seems to attract a certain caliber of engineers, I think.
[1] https://bugs.openjdk.java.net/browse/JDK-6804124 https://bugs.openjdk.java.net/browse/JDK-6804124
- stefan_ 7y agoThen, many years later, input was found that made the Java version crash: https://link.springer.com/chapter/10.1007/978-3-319-21690-4_16 https://link.springer.com/chapter/10.1007/978-3-319-21690-4_...
- kevingadd 7y agoI found a similar problem using a fairly battle-tested C# implementation of timsort. Felt lucky that I had managed to reproduce it in a dev environment instead of it being a mysterious crash for users.
- lqet 7y agoMany years ago, I copied an implementation of the Cohen-Sutherland algorithm (for line clipping) to C++ from pseudo code (I don't remember where I got this pseudo code from, but other sources used equivalent pseudo code). The code (it was a backend server code for a web app) was heavily tested with ab [0] and JMeter [1] against extreme load, everything seemed to worked fine. Fast-forward 6 months, when we had a sudden peak in users (for a few days, we went from around 500 visitors a day to around 500.000, which roughly meant > 5 million requests per day). Suddenly, the backend, which ran without problems for half a year, crashed in production every 5 hours or so with a segmentation fault. I could not for the life of me reproduce this. After some panicking, I let the backend run in gdb in production against the ~50 requests per second we were still getting. After a few hours, the segfault occurred again, and I figured out that on extremely rare edge cases, the pseudo code I copied to C++ divided by 0, which lead to chain of problems afterwards, eventually resulting in said segfault. If I remember correctly, the fix was trivial. [0] https://httpd.apache.org/docs/2.4/programs/ab.html https://httpd.apache.org/docs/2.4/programs/ab.html [1] https://jmeter.apache.org/ https://jmeter.apache.org/
- eru 7y agoIt seems like a standard library sort-function is the ideal candidate for investing in proving correctness.
- ziggity 7y agoAnd then 3 years later we have [0] and 6 years after that we have [1]. I appreciate Masters of the Universe types like Bloch and Lea contributing wickedly-efficient code, but somehow it's always mere mortals who end up mopping things up after the fact. Whether it's a bug in the actual algorithm or a "Comparison method violates its general contract!" exception that happens once in a blue moon, I think putting TimSort in Java was a mistake. [0] https://dertompson.com/2012/11/23/sort-algorithm-changes-in-java-7/ https://dertompson.com/2012/11/23/sort-algorithm-changes-in-... [1] https://bugs.openjdk.java.net/browse/JDK-8203864 https://bugs.openjdk.java.net/browse/JDK-8203864
- jonas21 7y agoThe "Comparison method violates its general contract!" exception is due to a bug in the caller's code, not in the sort implementation. If you have a bug in your code, just because you're able to get away with it today doesn't mean you should expect to get away with it forever.
- ziggity 7y agoI agree in theory. But in practice that specific caller's code bug was so widespread and Timsort broke so much existing code that it warranted offering a "-Djava.util.Arrays.useLegacyMergeSort=true" option. The specific line from the Javadoc you're alluding to [0] is: > The implementor must ensure sgn(x.compareTo(y)) == -sgn(y.compareTo(x)) for all x and y. The problem is the second implied half of that statement: Pre-Timsort it was ", and if you don't, results might not be sorted in the correct order" while with Timsort it was ", and if you don't, you will get a RuntimeException." It's way too easy to accidentally violate that condition: System.currentTimeMillis(), incorrect null handling, random numbers. Sometimes not even in the Comparator itself. The condition I posted, plus the other two: > The implementor must also ensure that the relation is transitive: (x.compareTo(y)>0 && y.compareTo(z)>0) implies x.compareTo(z)>0. > Finally, the implementor must ensure that x.compareTo(y)==0 implies that sgn(x.compareTo(z)) == sgn(y.compareTo(z)), for all z. Are just way too easy for someone to inadvertently violate to justify a RuntimeException when it occurs. [0] https://docs.oracle.com/javase/7/docs/api/java/lang/Comparable.html#compareTo(T) https://docs.oracle.com/javase/7/docs/api/java/lang/Comparab...
- shiblukhan 7y agoThis looks effective. I will try it out and thanks for posting.
- dpifke 7y agoTimSort—more specifically, Bloch's 9 line "rangecheck" function from his reimplementation—figured into Oracle's claims that Google copied Java code into Android: http://www.groklaw.net/articlebasic.php?story=20120419221941261 http://www.groklaw.net/articlebasic.php?story=20120419221941... As best as I can remember, those 9 lines are the only literal copying Oracle was able to find; the rest of their suit centers around whether the design of an API (e.g. parameter names) can be copyrighted. (And unless the Supreme Court steps in, the answer is "maybe.")