Path: csiph.com!v102.xanadu-bbs.net!xanadu-bbs.net!feeder.erje.net!eu.feeder.erje.net!newsfeed.xs4all.nl!newsfeed4.news.xs4all.nl!xs4all!newsgate.cistron.nl!newsgate.news.xs4all.nl!post.news.xs4all.nl!not-for-mail
Return-Path: <python-python-list@m.gmane.org>
X-Original-To: python-list@python.org
Delivered-To: python-list@mail.python.org
X-Spam-Status: OK 0.002
X-Spam-Evidence: '*H*': 1.00; '*S*': 0.00; 'broken': 0.04; 'elements.': 0.07; 'arrays': 0.09; 'overflow': 0.09; 'received:80.91': 0.09; 'received:80.91.229': 0.09; 'received:gmane.org': 0.09; 'received:list': 0.09; 'galaxy': 0.16; 'phones.': 0.16; 'received:80.91.229.3': 0.16; 'received:plane.gmane.org': 0.16; 'roy': 0.16; 'fix': 0.17; 'wrote:': 0.18; 'stack': 0.19; 'header:User-Agent:1': 0.23; 'bytes': 0.24; 'pointer': 0.24; 'mention': 0.26; 'header:X -Complaints-To:1': 0.27; 'header:In-Reply-To:1': 0.27; 'next': 0.36; 'url:eu': 0.37; 'to:addr:python-list': 0.38; 'to:addr:python.org': 0.39; 'received:org': 0.40; 'how': 0.40; 'devices': 0.61; 'more': 0.64; 'charset:windows-1252': 0.65; 'due': 0.66; 'smith': 0.68; 'samsung': 0.84
X-Injected-Via-Gmane: http://gmane.org/
To: python-list@python.org
From: Sturla Molden <sturla.molden@gmail.com>
Subject: Re: Bug in timsort!?
Date: Wed, 25 Feb 2015 14:58:31 +0100
References: <1cf84559-3a63-4799-a879-ae8e513d387e@googlegroups.com>
Mime-Version: 1.0
Content-Type: text/plain; charset=windows-1252; format=flowed
Content-Transfer-Encoding: 7bit
X-Gmane-NNTP-Posting-Host: 164-74-11.connect.netcom.no
User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.9; rv:31.0) Gecko/20100101 Thunderbird/31.4.0
In-Reply-To: <1cf84559-3a63-4799-a879-ae8e513d387e@googlegroups.com>
X-BeenThere: python-list@python.org
X-Mailman-Version: 2.1.15
Precedence: list
List-Id: General discussion list for the Python programming language <python-list.python.org>
List-Unsubscribe: <https://mail.python.org/mailman/options/python-list>, <mailto:python-list-request@python.org?subject=unsubscribe>
List-Archive: <http://mail.python.org/pipermail/python-list/>
List-Post: <mailto:python-list@python.org>
List-Help: <mailto:python-list-request@python.org?subject=help>
List-Subscribe: <https://mail.python.org/mailman/listinfo/python-list>, <mailto:python-list-request@python.org?subject=subscribe>
Newsgroups: comp.lang.python
Message-ID: <mailman.19183.1424872728.18130.python-list@python.org>
Lines: 17
NNTP-Posting-Host: 2001:888:2000:d::a6
X-Trace: 1424872728 news.xs4all.nl 2851 [2001:888:2000:d::a6]:38918
X-Complaints-To: abuse@xs4all.nl
Xref: csiph.com comp.lang.python:86398

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