3 ms·

And I always thought sort functions are always tested with millions of randomly generated sequences and the results are compared with the results of other imple

And I always thought sort functions are always tested with millions of randomly generated sequences and the results are compared with the results of other implementations known to be good.

thomasahle 12y ago
Very often random sequences are very different from sequences encountered in the wild.
TillE 12y ago
As long as your < operator works, you don't really need another sort implementation to compare with. Also, it seems like the bug is only truly present in the Java version due to a slightly different implementation, even though the original Python (and the "fixed" Java) is technically incorrect.
- imaginenore 12y ago
  > As long as your < operator works That's not true. sort() can be broken in many different ways. For instance sort([3, 7, 5]) -> [1, 2, 3] The result it sorted and has the correct length, but it's wrong.
  - lmm 12y ago
    The parametricity (edit: thanks imaginenore, I misremembered the name) theorem implies that a generic sort function written in a safe subset of the language could never do that though.
    - Robin_Message 12y ago
      Is that the idea that since the code should neither invent new values, nor duplicate values, it will always end up returning a permutation? It seems like inventing values not being possible is fine, but duplicating a value seems very plausible - what safe subset of Java would ensure that doesn't happen?
      - lmm 12y ago
        Maybe http://types.cs.washington.edu/checker-framework/current/checker-framework-manual.html#linear-checker http://types.cs.washington.edu/checker-framework/current/che... ? (I've used other parts of the checkers framework, but not that one yet)
    - imaginenore 12y ago
      The parameterization theorem doesn't imply such thing. http://en.wikipedia.org/wiki/Smn_theorem http://en.wikipedia.org/wiki/Smn_theorem
      - Chinjut 12y ago
        That's different from what is being referred to, which is (very briefly) described at http://en.wikipedia.org/wiki/Parametricity#History http://en.wikipedia.org/wiki/Parametricity#History. Edit: Ah, I didn't realize that there was an edit involved in the post you were referring to. At any rate, things are hopefully now clear to all.
  - fnord123 12y ago
    Terasort handles this by taking a sum of md5sums for each value. The teravalidate program then checks that all the items are in order and that the checksum is the same. It's so unlikely that could generate data that passes teravalidate but not really be correct that it would probably be an important work of computational science in it's own right.
dagw 12y ago
Sure, but what is the probability that you generate exactly the type of sequence needed to trigger this bug.
maxerickson 12y ago
That was done. It's talked about here: http://svn.python.org/projects/python/trunk/Objects/listsort.txt http://svn.python.org/projects/python/trunk/Objects/listsort... The bug would only be triggered by generating a truly massive array (the implementation mentions that it will work for up to 2^64 elements: http://svn.python.org/projects/python/trunk/Objects/listobject.c http://svn.python.org/projects/python/trunk/Objects/listobje... search for MAX_MERGE_PENDING).
- e12e 12y ago
  As mentioned by another commenter, the bug is that it's (for python) documented to work for 2^64 elements, but "only" works for 2^49. 2^49 is still pretty big... note that for 64-bit integers, 2^49 integers is 2^(49+3)=2^52 bytes... or 4 petabytes of raw data. Even if you're sorting single bits (one and zero) it's quite a bit of data to chew through. [ed: Hm, that's not quite right. A 64-bit integer is 2^6, so that should be 2^(49+6)=2^55, or 32 petabytes). I think :-) ]

And I always thought sort functions are always tested with millions of randomly generated sequences and the results are compared with the results of other implementations known to be good.

thomasahle 12y ago

Very often random sequences are very different from sequences encountered in the wild.

TillE 12y ago

As long as your < operator works, you don't really need another sort implementation to compare with. Also, it seems like the bug is only truly present in the Java version due to a slightly different implementation, even though the original Python (and the "fixed" Java) is technically incorrect.

imaginenore 12y ago
> As long as your < operator works That's not true. sort() can be broken in many different ways. For instance sort([3, 7, 5]) -> [1, 2, 3] The result it sorted and has the correct length, but it's wrong.
- lmm 12y ago
  The parametricity (edit: thanks imaginenore, I misremembered the name) theorem implies that a generic sort function written in a safe subset of the language could never do that though.
  - Robin_Message 12y ago
    Is that the idea that since the code should neither invent new values, nor duplicate values, it will always end up returning a permutation? It seems like inventing values not being possible is fine, but duplicating a value seems very plausible - what safe subset of Java would ensure that doesn't happen?
    - lmm 12y ago
      Maybe http://types.cs.washington.edu/checker-framework/current/checker-framework-manual.html#linear-checker http://types.cs.washington.edu/checker-framework/current/che... ? (I've used other parts of the checkers framework, but not that one yet)
  - imaginenore 12y ago
    The parameterization theorem doesn't imply such thing. http://en.wikipedia.org/wiki/Smn_theorem http://en.wikipedia.org/wiki/Smn_theorem
    - Chinjut 12y ago
      That's different from what is being referred to, which is (very briefly) described at http://en.wikipedia.org/wiki/Parametricity#History http://en.wikipedia.org/wiki/Parametricity#History. Edit: Ah, I didn't realize that there was an edit involved in the post you were referring to. At any rate, things are hopefully now clear to all.
- fnord123 12y ago
  Terasort handles this by taking a sum of md5sums for each value. The teravalidate program then checks that all the items are in order and that the checksum is the same. It's so unlikely that could generate data that passes teravalidate but not really be correct that it would probably be an important work of computational science in it's own right.

dagw 12y ago

Sure, but what is the probability that you generate exactly the type of sequence needed to trigger this bug.

maxerickson 12y ago

That was done. It's talked about here: http://svn.python.org/projects/python/trunk/Objects/listsort.txt http://svn.python.org/projects/python/trunk/Objects/listsort... The bug would only be triggered by generating a truly massive array (the implementation mentions that it will work for up to 2^64 elements: http://svn.python.org/projects/python/trunk/Objects/listobject.c http://svn.python.org/projects/python/trunk/Objects/listobje... search for MAX_MERGE_PENDING).

e12e 12y ago
As mentioned by another commenter, the bug is that it's (for python) documented to work for 2^64 elements, but "only" works for 2^49. 2^49 is still pretty big... note that for 64-bit integers, 2^49 integers is 2^(49+3)=2^52 bytes... or 4 petabytes of raw data. Even if you're sorting single bits (one and zero) it's quite a bit of data to chew through. [ed: Hm, that's not quite right. A 64-bit integer is 2^6, so that should be 2^(49+6)=2^55, or 32 petabytes). I think :-) ]