6 ms·

Proving that Android’s, Java’s and Python’s sorting algorithm is broken (2015)

46 points by CarolineW 9y ago

gleenn 9y ago
Pretty remarkable this has been sitting in production on millions of devices and nobody noticed until someone tried to formally verify it. Nobody at Google notice the stacktraces in TimSort code? Almost every mobile app I've written in production phones home when the app crashes. Is it just that unlikely to occur?
- Paraesthetic 9y ago
  Fairly likely
- realslimjd 9y ago
  It was literally impossible for it to occur. The numbers it required were so large that there's no device with enough memory for the bug to show up.
  - goldfire 9y ago
    Unless I misunderstand their test code, the article says they could reproduce the problem using an array of 67108864 Integer objects. That doesn't sound like an impossible amount of memory.
    - sli 9y ago
      It's also noted in the relevant thread on the Python mailing list[1], which also says that this is different from Java with regards to whether or not it can be triggered: "Since it's impossible to trigger the error on any current machine anyway (no machine has enough memory), increasing the size of the stack would be absurd. If you read the paper, they note that this is what the Java folks first did (they changed this part of timsort in a way that _did_ make it possible to provoke the stack overflow on current hardware)." [1]: https://bugs.python.org/msg236603 https://bugs.python.org/msg236603
      - detaro 9y ago
        It was impossible in the Python version. Not in Java.
- otempomores 9y ago
  Its was constant factor rich edge case
mangatmodi 9y ago
I read this long time back. I believe that Java rolled out a fix later to make it impossible to reproduce.
- realslimjd 9y ago
  Not only was it fixed in Java, but Python patched the bug in one day. https://bugs.python.org/issue23515 https://bugs.python.org/issue23515
otempomores 9y ago
I want to see a profiling before and after.
btown 9y ago
Can mods add a [2015] tag to the title? While this is an impressive analysis, it’s not a cause for panic now as it has long been patched.

46 points by CarolineW 9y ago

Pretty remarkable this has been sitting in production on millions of devices and nobody noticed until someone tried to formally verify it. Nobody at Google notice the stacktraces in TimSort code? Almost every mobile app I've written in production phones home when the app crashes. Is it just that unlikely to occur?

Paraesthetic 9y ago
Fairly likely
realslimjd 9y ago
It was literally impossible for it to occur. The numbers it required were so large that there's no device with enough memory for the bug to show up.
- goldfire 9y ago
  Unless I misunderstand their test code, the article says they could reproduce the problem using an array of 67108864 Integer objects. That doesn't sound like an impossible amount of memory.
  - sli 9y ago
    It's also noted in the relevant thread on the Python mailing list[1], which also says that this is different from Java with regards to whether or not it can be triggered: "Since it's impossible to trigger the error on any current machine anyway (no machine has enough memory), increasing the size of the stack would be absurd. If you read the paper, they note that this is what the Java folks first did (they changed this part of timsort in a way that _did_ make it possible to provoke the stack overflow on current hardware)." [1]: https://bugs.python.org/msg236603 https://bugs.python.org/msg236603
    - detaro 9y ago
      It was impossible in the Python version. Not in Java.
otempomores 9y ago
Its was constant factor rich edge case

mangatmodi 9y ago

I read this long time back. I believe that Java rolled out a fix later to make it impossible to reproduce.

realslimjd 9y ago
Not only was it fixed in Java, but Python patched the bug in one day. https://bugs.python.org/issue23515 https://bugs.python.org/issue23515

otempomores 9y ago

I want to see a profiling before and after.

btown 9y ago

Can mods add a [2015] tag to the title? While this is an impressive analysis, it’s not a cause for panic now as it has long been patched.