Title: Bad logic in timsort's merge_collapse
Type: crash Stage: resolved
Components: Interpreter Core Versions: Python 3.5, Python 3.4, Python 2.7
Status: closed Resolution: fixed
Dependencies: Superseder:
Assigned To: Nosy List: DragonFireCK, alex, cvrebert, python-dev, serhiy.storchaka, terry.reedy, tim.peters
Priority: low Keywords:

Created on 2015-02-24 19:32 by tim.peters, last changed 2015-02-25 20:33 by tim.peters. This issue is now closed.

Messages (8)
msg236533 - (view) Author: Tim Peters (tim.peters) * (Python committer) Date: 2015-02-24 19:32
Some researchers found an error in the logic of merge_collapse, explained here, and with corrected code shown in section 3.2:

This affects all current versions of Python.  However, I marked the priority "low" because, as the article also notes, there's currently no machine in existence with enough memory to hold an array large enough for a contrived input to trigger an overflow of the pending-runs stack. 

It should be fixed anyway, and their suggested fix looks good to me.
msg236583 - (view) Author: Roundup Robot (python-dev) Date: 2015-02-25 15:17
New changeset 325aec842e3e by Benjamin Peterson in branch '2.7':
fix merge_collapse to actually maintain the invariant it purports to (closes #23515)

New changeset 620cb13008b7 by Benjamin Peterson in branch '3.4':
fix merge_collapse to actually maintain the invariant it purports to (closes #23515)

New changeset be5ddc8b6a88 by Benjamin Peterson in branch 'default':
merge 3.4 (#23515)
msg236586 - (view) Author: Tim Peters (tim.peters) * (Python committer) Date: 2015-02-25 16:04
@Benjamin, bless you for changing their "n-1 > 0" to "n > 1", and for adding parentheses to make the intended grouping obvious instead of a puzzle, and for swapping the addends on the RHS of the new test.  Thank you - perfect :-)
msg236591 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2015-02-25 16:22
How additional test affects performance? May be just increase MAX_MERGE_PENDING?
msg236603 - (view) Author: Tim Peters (tim.peters) * (Python committer) Date: 2015-02-25 17:09
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).  And they got it wrong, not increasing it enough.  Without the _intended_ invariant, it's difficult to figure out how much is enough.

It's not worth measuring performance.  If there are a total of R runs in the input array, a total of R-1 merges will be performed (with or without the change).  As explained in listsort.txt, per-merge overheads don't matter at all unless they're outrageous, because there are at most ceiling(len(array)/32) runs.  So the total number of merges is a small fraction of the number of array elements (call that `N`), in an N*log(N) process.  Adding a few native C integer comparisons per merge (as the change essentially does) is trivial.

It may be possible to contrive inputs which run significantly slower (or faster!) with the change, because the order in which runs are merged may change.  But then you'd just be chasing patterns of HW and OS layers-of-caching behavior specific to the box the test is running on.
msg236604 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2015-02-25 17:14
Thank you for your explanation Tim.
msg236616 - (view) Author: Terry J. Reedy (terry.reedy) * (Python committer) Date: 2015-02-25 20:27
I sent a note to the lead author Stijn de Gouw and mentioned that the repository has moved from svn to

This change may be moot, but I think it worth our effort to keep our code as clean as possible and to encourage automated code checks, as we have by responding to issues raised by Coverity.  Maybe next time, this group will find a bug that does matter now.
msg236618 - (view) Author: Tim Peters (tim.peters) * (Python committer) Date: 2015-02-25 20:33
Thanks, Terry!  Absolutely agreed:  a logical error is an error, and will bite us eventually, regardless of whether it does so today.  I'm very glad the researchers went to all the trouble to analyze this one :-)
Date User Action Args
2015-02-25 20:33:02tim.peterssetmessages: + msg236618
2015-02-25 20:27:12terry.reedysetnosy: + terry.reedy

messages: + msg236616
versions: + Python 2.7, Python 3.4, Python 3.5
2015-02-25 17:14:55serhiy.storchakasetmessages: + msg236604
2015-02-25 17:09:36tim.peterssetmessages: + msg236603
2015-02-25 16:22:22serhiy.storchakasetnosy: + serhiy.storchaka
messages: + msg236591
2015-02-25 16:04:24tim.peterssetmessages: + msg236586
2015-02-25 15:17:18python-devsetstatus: open -> closed

nosy: + python-dev
messages: + msg236583

resolution: fixed
stage: needs patch -> resolved
2015-02-24 21:57:58DragonFireCKsetnosy: + DragonFireCK
2015-02-24 21:45:17cvrebertsetnosy: + cvrebert
2015-02-24 19:33:06alexsetnosy: + alex
2015-02-24 19:32:12tim.peterscreate