Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.python > #86345 > unrolled thread

Bug in timsort!?

Back to article view | Back to comp.lang.python

Contents

  Bug in timsort!? Roy Smith <roy@panix.com> - 2015-02-24 13:34 -0800
    Re: Bug in timsort!? Zachary Ware <zachary.ware+pylist@gmail.com> - 2015-02-24 15:40 -0600
    Re: Bug in timsort!? Mark Lawrence <breamoreboy@yahoo.co.uk> - 2015-02-24 21:49 +0000
      Re: Bug in timsort!? sohcahtoa82@gmail.com - 2015-02-24 14:36 -0800
        Re: Bug in timsort!? Mark Lawrence <breamoreboy@yahoo.co.uk> - 2015-02-25 00:38 +0000
    Re: Bug in timsort!? Grant Edwards <invalid@invalid.invalid> - 2015-02-24 22:45 +0000
      Re: Bug in timsort!? Ian Kelly <ian.g.kelly@gmail.com> - 2015-02-24 15:59 -0700
      Re: Bug in timsort!? Robert Kern <robert.kern@gmail.com> - 2015-02-25 11:34 +0000
        Re: Bug in timsort!? Grant Edwards <invalid@invalid.invalid> - 2015-02-25 15:49 +0000
    Re: Bug in timsort!? Chris Angelico <rosuav@gmail.com> - 2015-02-25 10:33 +1100
    Re: Bug in timsort!? MRAB <python@mrabarnett.plus.com> - 2015-02-24 23:38 +0000
    Re: Bug in timsort!? Skip Montanaro <skip.montanaro@gmail.com> - 2015-02-24 17:50 -0600
    Re: Bug in timsort!? Chris Angelico <rosuav@gmail.com> - 2015-02-25 11:07 +1100
      Re: Bug in timsort!? Paddy <paddy3118@gmail.com> - 2015-02-25 01:10 -0800
        Re: Bug in timsort!? Chris Angelico <rosuav@gmail.com> - 2015-02-25 21:11 +1100
    Re: Bug in timsort!? Chris Kaynor <ckaynor@zindagigames.com> - 2015-02-24 16:38 -0800
    Re: Bug in timsort!? Terry Reedy <tjreedy@udel.edu> - 2015-02-24 21:52 -0500
    Re: Bug in timsort!? Dave Angel <davea@davea.name> - 2015-02-24 21:41 -0500
    Re: Bug in timsort!? Ned Deily <nad@acm.org> - 2015-02-25 01:04 -0800
    Re: Bug in timsort!? Sturla Molden <sturla.molden@gmail.com> - 2015-02-25 14:58 +0100
      Re: Bug in timsort!? alister <alister.nospam.ware@ntlworld.com> - 2015-02-25 15:03 +0000
        Re: Bug in timsort!? Zachary Ware <zachary.ware+pylist@gmail.com> - 2015-02-25 09:23 -0600
        Re: Bug in timsort!? Terry Reedy <tjreedy@udel.edu> - 2015-02-25 16:08 -0500
      Re: Bug in timsort!? Roy Smith <roy@panix.com> - 2015-02-25 19:12 -0500
    Re: Bug in timsort!? Jonas Wielicki <jonas@wielicki.name> - 2015-02-25 15:07 +0100
    Re: Bug in timsort!? Chris Angelico <rosuav@gmail.com> - 2015-02-26 01:33 +1100
    Re: Bug in timsort!? Sturla Molden <sturla.molden@gmail.com> - 2015-02-25 16:05 +0100
    Re: Bug in timsort!? Chris Angelico <rosuav@gmail.com> - 2015-02-26 02:11 +1100
    Re: Bug in timsort!? Peter Otten <__peter__@web.de> - 2015-02-25 17:04 +0100
      Re: Bug in timsort!? Mario Figueiredo <marfig@gmail.com> - 2015-02-25 18:22 +0100
        Re: Bug in timsort!? Sturla Molden <sturla.molden@gmail.com> - 2015-02-25 19:41 +0100
        Re: Bug in timsort!? Jonas Wielicki <jonas@wielicki.name> - 2015-02-25 19:46 +0100
        Re: Bug in timsort!? Mark Lawrence <breamoreboy@yahoo.co.uk> - 2015-02-25 20:07 +0000
    Re: Bug in timsort!? Sturla Molden <sturla.molden@gmail.com> - 2015-02-25 17:44 +0100
      Re: Bug in timsort!? Mario Figueiredo <marfig@gmail.com> - 2015-02-25 18:29 +0100
      Re: Bug in timsort!? Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2015-02-26 10:13 +1100
        Re: Bug in timsort!? Ian Kelly <ian.g.kelly@gmail.com> - 2015-02-25 22:51 -0700
    Re: Bug in timsort!? Mark Lawrence <breamoreboy@yahoo.co.uk> - 2015-02-25 16:50 +0000
    Re: Bug in timsort!? Mark Lawrence <breamoreboy@yahoo.co.uk> - 2015-02-25 16:55 +0000
    Re: Bug in timsort!? Chris Kaynor <ckaynor@zindagigames.com> - 2015-02-25 08:56 -0800
    Re: Bug in timsort!? Chris Angelico <rosuav@gmail.com> - 2015-02-26 04:18 +1100
    Re: Bug in timsort!? Peter Otten <__peter__@web.de> - 2015-02-25 18:21 +0100
    Re: Bug in timsort!? Ian Kelly <ian.g.kelly@gmail.com> - 2015-02-25 12:42 -0700
    Re: Bug in timsort!? Serhiy Storchaka <storchaka@gmail.com> - 2015-02-26 09:33 +0200

Page 2 of 3 — ← Prev page 1 [2] 3  Next page →

#86405

On Wed, 25 Feb 2015 14:58:31 +0100, Sturla Molden wrote:

> On 24/02/15 22:34, Roy Smith wrote:
>> http://envisage-project.eu/proving-android-java-and-python-sorting-
algorithm-is-broken-and-how-to-fix-it/
>>
>>
> This is awful. It is broken for arrays longer than 2**49 elements. With
> 8 bytes per PyObject* pointer this is >4096 terabytes of RAM. I don't
> see how we can fix this in time.
> 
> Oh yes, and they mention that TimSort is used on billions of devices due
> to Android mobile phones. This is clearly very relevant for mobile
> phones. Next thing you know your litte Samsung Galaxy with more than
> 4096 terabytes breaks down from a stack overflow in TimSort.
> 
> 
> Sturla

the oh well it wont affect current devices attitude is a very poor 
attitude to big fixes.
if a bug is reported it should be resolved a quickly as practical sot hat 
it never does become a real world issue

much better to bolt the door BEFORE the horse bolts (even if the horse 
has not actually been borne yet)



-- 
1: No code table for op: ++post

[toc] | [prev] | [next] | [standalone]

#86408

On Wed, Feb 25, 2015 at 9:03 AM, alister
<alister.nospam.ware@ntlworld.com> wrote:
> the oh well it wont affect current devices attitude is a very poor
> attitude to big fixes.
> if a bug is reported it should be resolved a quickly as practical sot hat
> it never does become a real world issue
>
> much better to bolt the door BEFORE the horse bolts (even if the horse
> has not actually been borne yet)

Just to be clear, this has already been fixed, and the fix will be
released in Python 2.7.10, 3.4.4, and 3.5.0.

-- 
Zach

[toc] | [prev] | [next] | [standalone]

#86441

On 2/25/2015 10:23 AM, Zachary Ware wrote:

> Just to be clear, this has already been fixed, and the fix will be
> released in Python 2.7.10, 3.4.4, and 3.5.0.

I think the important effect of the fix is to encourage automatic code 
verification both by the group that found this bug and by and others. 
Future verifier developers can check their code by trying to verify the 
fixed code.

The C half of the CPython code base has been improved by responding to 
issues raised by the Coverity checker.  I hope we can get free code 
reviews both of C and Python code from others.

-- 
Terry Jan Reedy

[toc] | [prev] | [next] | [standalone]

#86452

In article <mailman.19183.1424872728.18130.python-list@python.org>,
 Sturla Molden <sturla.molden@gmail.com> wrote:

> On 24/02/15 22:34, Roy Smith wrote:
> > http://envisage-project.eu/proving-android-java-and-python-sorting-algorithm
> > -is-broken-and-how-to-fix-it/
> >
> 
> This is awful. It is broken for arrays longer than 2**49 elements. With 
> 8 bytes per PyObject* pointer this is >4096 terabytes of RAM. I don't 
> see how we can fix this in time.
> 
> Oh yes, and they mention that TimSort is used on billions of devices due 
> to Android mobile phones. This is clearly very relevant for mobile 
> phones. Next thing you know your litte Samsung Galaxy with more than 
> 4096 terabytes breaks down from a stack overflow in TimSort.

Keep in mind that the phone I cary around today has more memory (and 
probably more CPU) than the biggest supercomputers that existed when I 
was in college.

[toc] | [prev] | [next] | [standalone]

#86399

[Multipart message — attachments visible in raw view] — view raw

On 25.02.2015 14:58, Sturla Molden wrote:
> On 24/02/15 22:34, Roy Smith wrote:
>> http://envisage-project.eu/proving-android-java-and-python-sorting-algorithm-is-broken-and-how-to-fix-it/
>>
>>
> […]
>
> Oh yes, and they mention that TimSort is used on billions of devices due
> to Android mobile phones. This is clearly very relevant for mobile
> phones. Next thing you know your litte Samsung Galaxy with more than
> 4096 terabytes breaks down from a stack overflow in TimSort.

The Java version of the bug is reproducible with just 67108864 elements,
if I read the article correctly.

jwi

[toc] | [prev] | [next] | [standalone]

#86400

On Thu, Feb 26, 2015 at 12:58 AM, Sturla Molden <sturla.molden@gmail.com> wrote:
> This is awful. It is broken for arrays longer than 2**49 elements. With 8
> bytes per PyObject* pointer this is >4096 terabytes of RAM. I don't see how
> we can fix this in time.

It's even worse than that. Unless you have a list of 2**49 references
to the same few objects, you're going to need to have some actual
content for each one. The absolute best you could do is to sort
integers, which would take 32 bytes each [1]; if you're sorting
strings, they'll be 90 bytes each, so the integers are our best bet.
So add another *five* powers of two to the RAM requirements.

Also, who has that many elements to sort, and wouldn't do better to
stick 'em into an indexed database of some description? I mean, good
to know that this'll be fixed, but it really isn't likely to come up
any time soon.

ChrisA

[1] Calculated using Python 3.5 amd64 Linux, your figures may vary.
Small integers (less than 2**30) take only 28 bytes, but that's
dwarfed by the rest of them taking 32.

[toc] | [prev] | [next] | [standalone]

#86406

On 25/02/15 15:33, Chris Angelico wrote:

> It's even worse than that. Unless you have a list of 2**49 references
> to the same few objects, you're going to need to have some actual
> content for each one. The absolute best you could do is to sort
> integers, which would take 32 bytes each [1]; if you're sorting
> strings, they'll be 90 bytes each, so the integers are our best bet.
> So add another *five* powers of two to the RAM requirements.

In that case you also need to add the PyObject_HEAD overhead for each 
object. ;-)

Sturla

[toc] | [prev] | [next] | [standalone]

#86407

On Thu, Feb 26, 2015 at 2:05 AM, Sturla Molden <sturla.molden@gmail.com> wrote:
> On 25/02/15 15:33, Chris Angelico wrote:
>
>> It's even worse than that. Unless you have a list of 2**49 references
>> to the same few objects, you're going to need to have some actual
>> content for each one. The absolute best you could do is to sort
>> integers, which would take 32 bytes each [1]; if you're sorting
>> strings, they'll be 90 bytes each, so the integers are our best bet.
>> So add another *five* powers of two to the RAM requirements.
>
>
> In that case you also need to add the PyObject_HEAD overhead for each
> object. ;-)

Not sure about that, because the figure of 32 bytes came from
sys.getsizeof(). So assuming there's no significant malloc overhead
(there shouldn't be any alignment padding, for instance), 32 bytes
ought to be it - pack 'em all in.

ChrisA

[toc] | [prev] | [next] | [standalone]

#86412

Sturla Molden wrote:

> On 24/02/15 22:34, Roy Smith wrote:
>> http://envisage-project.eu/proving-android-java-and-python-sorting-algorithm-is-broken-and-how-to-fix-it/
>>
> 
> This is awful. It is broken for arrays longer than 2**49 elements. With
> 8 bytes per PyObject* pointer this is >4096 terabytes of RAM. I don't
> see how we can fix this in time.
> 
> Oh yes, and they mention that TimSort is used on billions of devices due
> to Android mobile phones. This is clearly very relevant for mobile
> phones. Next thing you know your litte Samsung Galaxy with more than
> 4096 terabytes breaks down from a stack overflow in TimSort.

Yeah, I'm looking forward to see comparable bugs being closed as "cannot 
reproduce" by some of the jokers. I suppose that you all had a note 
scribbled on the margin of your copy of Arithmetica that this cannot happen 
with arrays of lengths seen in practice until 2038 or so.

These guys found a bug that is subtler than what most of us have dealt with 
in a widely used piece of code originally developed by one of the smarter 
members of the python "community".

I bow my head to them and say thank you.

[toc] | [prev] | [next] | [standalone]

#86428

On Wed, 25 Feb 2015 17:04:10 +0100, Peter Otten <__peter__@web.de>
wrote:
>
>These guys found a bug that is subtler than what most of us have dealt with 
>in a widely used piece of code originally developed by one of the smarter 
>members of the python "community".
>
>I bow my head to them and say thank you.

And also presented a solution.

Thank you for a little of sanity and common sense in this discussion.
TYhe levcel of smugness by some of the posters surely can't be a
representation of the python community.

[toc] | [prev] | [next] | [standalone]

#86434

On 25/02/15 18:22, Mario Figueiredo wrote:

> And also presented a solution.

Which also was incorrect :-D

But now Benjamin Peterson has finally fixed it, it appears:

http://bugs.python.org/issue23515



Sturla

[toc] | [prev] | [next] | [standalone]

#86435

[Multipart message — attachments visible in raw view] — view raw

On 25.02.2015 19:41, Sturla Molden wrote:
> On 25/02/15 18:22, Mario Figueiredo wrote:
> 
>> And also presented a solution.
> 
> Which also was incorrect :-D
> 
> But now Benjamin Peterson has finally fixed it, it appears:
> 
> http://bugs.python.org/issue23515

It would be too great if anyone replying to a discussion read the mails
before posting ...

https://mail.python.org/pipermail/python-list/2015-February/699420.html

I support that view, the changes do not change behaviour and merely
cosmetic, if I understand that statement correctly

regards,
jwi

[toc] | [prev] | [next] | [standalone]

#86437

On 25/02/2015 17:22, Mario Figueiredo wrote:
> On Wed, 25 Feb 2015 17:04:10 +0100, Peter Otten <__peter__@web.de>
> wrote:
>>
>> These guys found a bug that is subtler than what most of us have dealt with
>> in a widely used piece of code originally developed by one of the smarter
>> members of the python "community".
>>
>> I bow my head to them and say thank you.
>
> And also presented a solution.
>
> Thank you for a little of sanity and common sense in this discussion.
> TYhe levcel of smugness by some of the posters surely can't be a
> representation of the python community.
>

I don't believe that any technical community with exactly 4,750 open 
issues on its bug tracker regards itself as smug.

-- 
My fellow Pythonistas, ask not what our language can do for you, ask
what you can do for our language.

Mark Lawrence

[toc] | [prev] | [next] | [standalone]

#86416

On 25/02/15 17:04, Peter Otten wrote:

> These guys found a bug that is subtler than what most of us have dealt with
> in a widely used piece of code originally developed by one of the smarter
> members of the python "community".
>
> I bow my head to them and say thank you.

I am not joking about that. It is more the hype this gets that indicates 
TimSort is already broken today, and even on your cell phone.


Sturla

[toc] | [prev] | [next] | [standalone]

#86430

On Wed, 25 Feb 2015 17:44:04 +0100, Sturla Molden
<sturla.molden@gmail.com> wrote:


>I am not joking about that. It is more the hype this gets that indicates 
>TimSort is already broken today, and even on your cell phone.
>

But it IS broken.The only hype I'm witnessing is this fantasy created
by some that there's a hype around this issue.

The team that found the bug produce a non sensationalist  and
comprehensive report. So it couldn't be them. The other perople
discussing the issue are software developers who already know the
scope pof this bug from the very beginning of this thread.

So I'm not seeing the hype. What I'm seeing is this apparent attempt
at reductio ad absurdum to disqualify this bug.

[toc] | [prev] | [next] | [standalone]

#86446

Sturla Molden wrote:

> On 25/02/15 17:04, Peter Otten wrote:
> 
>> These guys found a bug that is subtler than what most of us have dealt
>> with in a widely used piece of code originally developed by one of the
>> smarter members of the python "community".
>>
>> I bow my head to them and say thank you.
> 
> I am not joking about that. It is more the hype this gets that indicates
> TimSort is already broken today, and even on your cell phone.

TimSort is an algorithm, and it is not broken. The algorithm is correct.

Any specific implementation of that algorithm may or may not be correct. As
Zachary has pointed out, the implementation used in CPython has already
been fixed, for versions 2.7.10, 3.4.4, and 3.5.0, and is now correct (as
far as anyone can tell).

Other implementations -- including Java and Android phones -- are not our
responsibility or concern, except so far as they may effect Jython or other
Python code.



-- 
Steven

[toc] | [prev] | [next] | [standalone]

#86477

On Wed, Feb 25, 2015 at 4:13 PM, Steven D'Aprano
<steve+comp.lang.python@pearwood.info> wrote:
> TimSort is an algorithm, and it is not broken. The algorithm is correct.

The algorithm asserted an invariant but failed to actually establish
it. That sounds broken to me.

[toc] | [prev] | [next] | [standalone]

#86419

On 25/02/2015 13:58, Sturla Molden wrote:
> On 24/02/15 22:34, Roy Smith wrote:
>> http://envisage-project.eu/proving-android-java-and-python-sorting-algorithm-is-broken-and-how-to-fix-it/
>>
>>
>
> This is awful. It is broken for arrays longer than 2**49 elements. With
> 8 bytes per PyObject* pointer this is >4096 terabytes of RAM. I don't
> see how we can fix this in time.
>
> Oh yes, and they mention that TimSort is used on billions of devices due
> to Android mobile phones. This is clearly very relevant for mobile
> phones. Next thing you know your litte Samsung Galaxy with more than
> 4096 terabytes breaks down from a stack overflow in TimSort.
>
>
> Sturla
>
>

When I were a lad we only had one bit of data, and we were only able to 
utilise half of that.

-- 
My fellow Pythonistas, ask not what our language can do for you, ask
what you can do for our language.

Mark Lawrence

[toc] | [prev] | [next] | [standalone]

#86420

On 25/02/2015 16:04, Peter Otten wrote:
> Sturla Molden wrote:
>
>> On 24/02/15 22:34, Roy Smith wrote:
>>> http://envisage-project.eu/proving-android-java-and-python-sorting-algorithm-is-broken-and-how-to-fix-it/
>>>
>>
>> This is awful. It is broken for arrays longer than 2**49 elements. With
>> 8 bytes per PyObject* pointer this is >4096 terabytes of RAM. I don't
>> see how we can fix this in time.
>>
>> Oh yes, and they mention that TimSort is used on billions of devices due
>> to Android mobile phones. This is clearly very relevant for mobile
>> phones. Next thing you know your litte Samsung Galaxy with more than
>> 4096 terabytes breaks down from a stack overflow in TimSort.
>
> Yeah, I'm looking forward to see comparable bugs being closed as "cannot
> reproduce" by some of the jokers. I suppose that you all had a note
> scribbled on the margin of your copy of Arithmetica that this cannot happen
> with arrays of lengths seen in practice until 2038 or so.
>
> These guys found a bug that is subtler than what most of us have dealt with
> in a widely used piece of code originally developed by one of the smarter
> members of the python "community".
>
> I bow my head to them and say thank you.
>

Reading the bug report http://bugs.python.org/issue23515, specifically 
msg236586, it looks as if the proposed fix was wrong and one of the 
smarter members of the python community fixed it.

-- 
My fellow Pythonistas, ask not what our language can do for you, ask
what you can do for our language.

Mark Lawrence

[toc] | [prev] | [next] | [standalone]

#86421

On Wed, Feb 25, 2015 at 8:44 AM, Sturla Molden <sturla.molden@gmail.com> wrote:
>
> On 25/02/15 17:04, Peter Otten wrote:
>
>> These guys found a bug that is subtler than what most of us have dealt with
>> in a widely used piece of code originally developed by one of the smarter
>> members of the python "community".
>>
>> I bow my head to them and say thank you.
>
>
> I am not joking about that. It is more the hype this gets that indicates TimSort is already broken today, and even on your cell phone.

While the CPython implementation was only broken for arrays of length
larger than 2**49, aka, practically not broken, the Java
implementation (such as used on Android phones) was broken with arrays
of length > 67,108,864 at the time the post was made. While still very
large, an array of 67 million elements is well within the realm of
possibility today. The Java fixes (so far) have only extended the
number out, rather than actually fix the underlying problem - the
CPython fixes that were committed implement the full proven fix, so
CPython should now be able to handle infinite length arrays (once we
can build computers with that much storage...).

[toc] | [prev] | [next] | [standalone]

Page 2 of 3 — ← Prev page 1 [2] 3  Next page →

Back to top | Article view | comp.lang.python

csiph-web