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

Groups > comp.lang.python > #86421

Re: Bug in timsort!?

Path csiph.com!usenet.pasdenom.info!news.redatomik.org!newsfeed.xs4all.nl!newsfeed2.news.xs4all.nl!xs4all!newsgate.cistron.nl!newsgate.news.xs4all.nl!post.news.xs4all.nl!not-for-mail
Return-Path <ckaynor@zindagigames.com>
X-Original-To python-list@python.org
Delivered-To python-list@mail.python.org
X-Spam-Status OK 0.008
X-Spam-Evidence '*H*': 0.98; '*S*': 0.00; 'broken': 0.04; 'cpython': 0.05; 'widely': 0.05; '(so': 0.07; 'fixes': 0.07; 'made.': 0.07; 'arrays': 0.09; 'indicates': 0.09; 'cc:addr:python-list': 0.11; 'python': 0.11; 'bug': 0.12; '"community".': 0.16; 'far)': 0.16; 'underlying': 0.16; 'elements': 0.16; 'fix': 0.17; 'wrote:': 0.18; 'wed,': 0.18; 'feb': 0.22; 'cc:addr:python.org': 0.22; '(such': 0.24; 'large,': 0.24; 'guys': 0.24; 'java': 0.24; 'cc:2**0': 0.24; 'post': 0.26; 'gets': 0.27; 'header:In-Reply-To:1': 0.27; 'am,': 0.29; 'array': 0.29; 'possibility': 0.29; 'originally': 0.30; 'message-id:@mail.gmail.com': 0.30; 'code': 0.31; 'that.': 0.31; '25,': 0.31; 'piece': 0.31; 'received:74.125.82': 0.34; 'problem': 0.35; 'received:google.com': 0.35; 'should': 0.36; 'implement': 0.38; 'thank': 0.38; 'handle': 0.38; 'rather': 0.38; 'received:74.125': 0.39; 'even': 0.60; 'most': 0.60; 'extended': 0.61; 'length': 0.61; 'today.': 0.61; 'full': 0.61; 'today,': 0.61; 'you.': 0.62; 'developed': 0.63; 'more': 0.64; 'to:addr:gmail.com': 0.65; 'within': 0.65; 'computers': 0.72; 'million': 0.74; '2015': 0.84; 'bow': 0.84; 'otten': 0.84; 'dealt': 0.91
X-Google-DKIM-Signature v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:mime-version:in-reply-to:references:from:date :message-id:subject:to:cc:content-type; bh=oqeO8Cx/bShI1d6QmDgwoPtk2vjITcUE2+blLg9sGPc=; b=XypT50Ti903H/E4/yezdTJZ22MzXKgrtcukH8Sgs9ADXzpqsm7+POABRsEzd7DQAXY aepZEH0F/k6WZD0lJev12xKPfZLUWSVuQwNJ9ZkxJ1O0QVLQqZeyWj2rl/n37qZQoiwr fKEU7QIedX+grVYMOVcq0vcCQ0jkgz7e4xtYr5eFJqs2cKBIm77FIh9Ei6I1/9DE1Asm yMUS1fT80XdV+yxzT2u3RTpGyzLoF7Rv8yOdywCeM5bndqdoXKIxFSGtdz0CcyUl62xS jgKM9yzzPjt4BHhu/BcnDRzAoDvTpiBI9fIqo+IBdzhzU2/Upjv3do5TkXDwmC6vM4bw hZ4A==
X-Gm-Message-State ALoCoQl8u8rhUyTXUe8KuazhFIAEb0pTpz0G6a9NizFv2eC4h7JDtItrTmQpJctMVCoikXTC7KLV
X-Received by 10.194.86.135 with SMTP id p7mr8009092wjz.89.1424883390098; Wed, 25 Feb 2015 08:56:30 -0800 (PST)
MIME-Version 1.0
In-Reply-To <mcku4g$tq8$1@ger.gmane.org>
References <1cf84559-3a63-4799-a879-ae8e513d387e@googlegroups.com> <mckke8$con$1@ger.gmane.org> <mckrpt$j10$1@ger.gmane.org> <mcku4g$tq8$1@ger.gmane.org>
From Chris Kaynor <ckaynor@zindagigames.com>
Date Wed, 25 Feb 2015 08:56:09 -0800
Subject Re: Bug in timsort!?
To Sturla Molden <sturla.molden@gmail.com>
Content-Type text/plain; charset=UTF-8
Cc "python-list@python.org" <python-list@python.org>
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.19202.1424883392.18130.python-list@python.org> (permalink)
Lines 23
NNTP-Posting-Host 2001:888:2000:d::a6
X-Trace 1424883392 news.xs4all.nl 2881 [2001:888:2000:d::a6]:40738
X-Complaints-To abuse@xs4all.nl
Xref csiph.com comp.lang.python:86421

Show key headers only | View raw

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...).

Back to comp.lang.python | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

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

csiph-web