classification
Title: Replace size_t with Py_ssize_t as the type of local variable in list_resize
Type: enhancement Stage: resolved
Components: Interpreter Core Versions: Python 3.7
process
Status: closed Resolution: fixed
Dependencies: Superseder:
Assigned To: xiang.zhang Nosy List: Mariatta, mark.dickinson, martin.panter, r.david.murray, rhettinger, serhiy.storchaka, tim.peters, vstinner, xiang.zhang
Priority: low Keywords: patch

Created on 2016-07-31 17:40 by xiang.zhang, last changed 2017-02-22 04:32 by xiang.zhang. This issue is now closed.

Files
File name Uploaded Description Edit
list_resize.patch xiang.zhang, 2016-07-31 17:40 review
list_resize_v2.patch xiang.zhang, 2016-08-02 16:23 review
list_resize_v3.patch xiang.zhang, 2016-08-23 03:26 review
Pull Requests
URL Status Linked Edit
PR 189 merged xiang.zhang, 2017-02-20 07:38
Messages (22)
msg271746 - (view) Author: Xiang Zhang (xiang.zhang) * (Python committer) Date: 2016-07-31 17:40
In list_resize, new_allocated is of type size_t but I think don't have to be now since it finally have to assign back to self->allocated which is of type Py_ssize_t. With Py_ssize_t, we can check some overflows in the first overflow check and don't need the second overflow check.
msg271748 - (view) Author: R. David Murray (r.david.murray) * (Python committer) Date: 2016-07-31 19:12
ob->allocated is temporarily set to -1 by list.sort to detect mutations, so the restriction of new_allocated to size_t is probably intentional.  If so, though, there ought to be a comment making that clear.
msg271749 - (view) Author: R. David Murray (r.david.murray) * (Python committer) Date: 2016-07-31 19:14
Oh, I got that backward didn't I.  My rusty C skills :(
msg271765 - (view) Author: Xiang Zhang (xiang.zhang) * (Python committer) Date: 2016-08-01 02:57
:( Sorry David, my poor English doesn't enable me understand your message totally. Is list.sort related to this problem? Do I miss something?
msg271784 - (view) Author: R. David Murray (r.david.murray) * (Python committer) Date: 2016-08-01 14:40
No, I was the one who missed something.  Just ignore my comment and lets wait for someone with more current C chops to answer :)
msg271785 - (view) Author: R. David Murray (r.david.murray) * (Python committer) Date: 2016-08-01 14:42
Erg.  You mention your English proficiency and then I go using a colequialism :(  "better C chops" means someone with more skill than I am currently exhibiting.
msg271799 - (view) Author: Martin Panter (martin.panter) * (Python committer) Date: 2016-08-02 01:56
The patch looks okay to me.
msg271806 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2016-08-02 06:10
Unsigned type can be used for more efficient checking on integer overflow.

    new_allocated = (newsize >> 3) + (newsize < 9 ? 3 : 6);
    new_allocated += (size_t)newsize;
    if (new_allocated < (size_t)newsize) {
        PyErr_NoMemory();
        return -1;
    }

Checking "new_allocated < (size_t)newsize" can be more efficient than "new_allocated > PY_SSIZE_T_MAX - newsize".
msg271808 - (view) Author: Xiang Zhang (xiang.zhang) * (Python committer) Date: 2016-08-02 06:36
But if you use size_t, you are checking overflow against PY_SIZE_MAX, not PY_SSIZE_T_MAX.
msg271827 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2016-08-02 15:51
True. Then we should use the condition "new_allocated > PY_SSIZE_T_MAX". This can be even more efficient.
msg271829 - (view) Author: Xiang Zhang (xiang.zhang) * (Python committer) Date: 2016-08-02 16:23
So how about list_resize_v2.patch?
msg273378 - (view) Author: Xiang Zhang (xiang.zhang) * (Python committer) Date: 2016-08-22 13:53
Ping.
msg273398 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2016-08-22 19:48
This is low priority.  I will look at it during the sprint.  As far as I know there is no bug here or performance problem; instead, the patch alters stable code and transfers responsibilities.
msg273401 - (view) Author: STINNER Victor (vstinner) * (Python committer) Date: 2016-08-22 20:27
I reviewed list_resize_v2.patch.
msg273418 - (view) Author: Xiang Zhang (xiang.zhang) * (Python committer) Date: 2016-08-23 03:26
v3 applies haypo's suggestion.
msg288187 - (view) Author: Xiang Zhang (xiang.zhang) * (Python committer) Date: 2017-02-20 07:40
I opened a PR on GitHub for this issue. Hope Raymond you could review it some time.
msg288256 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2017-02-21 03:19
It was a little mind-numbing to check this code, but it looks correct.

Please fix two nits for better readability.   For review purposes, it was nice to have changes stand-out, but for the final code I would like to combine the two comments and the two new_allocated assignments into a single comment and single assignment:

      /* The growth pattern is:  0, 4, 8, 16, 25, 35, 46, 58, 72, 88, ...
         Note: new_allocated won't overflow because the largest possible value
               is PY_SSIZE_T_MAX * (9 / 8) + 6 which always fits in a size_t.
      */
     new_allocated = (size_t)newsize + (newsize >> 3) + (newsize < 9 ? 3 : 6);

Secondly, please rename the "size" variable to something like "num_allocated_bytes".  It is confusing to have "newsize" mean the number of elements actually used while having "size" mean the number of bytes actually allocated (including the overallocation).
msg288260 - (view) Author: Xiang Zhang (xiang.zhang) * (Python committer) Date: 2017-02-21 03:36
Thanks for your time Raymond. :-) I applied your suggestions in the PR.
msg288264 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2017-02-21 04:18
Mariatta, would you like to run this against the test suite and then apply it.  I don't think a MISC/NEWS entry is needed (it is just a code simplification) and Xiang is already in MISC/ACKS.
msg288266 - (view) Author: Xiang Zhang (xiang.zhang) * (Python committer) Date: 2017-02-21 04:53
Sorry, I have the commit bit and know what to do with a commit. So I assign it to myself and wait someone approve the PR on GitHub.
msg288268 - (view) Author: Raymond Hettinger (rhettinger) * (Python committer) Date: 2017-02-21 05:34
Okay, go ahead.  I was hoping to give Mariatta some practice applying C patches (she's new).
msg288328 - (view) Author: Xiang Zhang (xiang.zhang) * (Python committer) Date: 2017-02-22 04:32
New changeset 4cee049f5b6864066b8315e9b54de955e5487dfc by GitHub in branch 'master':
bpo-27660: remove unnecessary overflow checks in list_resize (GH-189)
https://github.com/python/cpython/commit/4cee049f5b6864066b8315e9b54de955e5487dfc
History
Date User Action Args
2017-02-22 04:32:53xiang.zhangsetstatus: open -> closed
resolution: fixed
stage: commit review -> resolved
2017-02-22 04:32:32xiang.zhangsetmessages: + msg288328
2017-02-21 05:34:18rhettingersetmessages: + msg288268
2017-02-21 04:53:41xiang.zhangsetassignee: Mariatta -> xiang.zhang
messages: + msg288266
stage: patch review -> commit review
2017-02-21 04:18:38rhettingersetassignee: rhettinger -> Mariatta

messages: + msg288264
nosy: + Mariatta
2017-02-21 03:36:39xiang.zhangsetmessages: + msg288260
2017-02-21 03:19:17rhettingersetmessages: + msg288256
2017-02-20 07:40:14xiang.zhangsetmessages: + msg288187
versions: + Python 3.7, - Python 3.6
2017-02-20 07:38:15xiang.zhangsetpull_requests: + pull_request155
2016-08-23 03:26:37xiang.zhangsetfiles: + list_resize_v3.patch

messages: + msg273418
2016-08-22 20:27:31vstinnersetnosy: + vstinner
messages: + msg273401
2016-08-22 19:48:35rhettingersetpriority: normal -> low

messages: + msg273398
2016-08-22 13:53:33xiang.zhangsetmessages: + msg273378
2016-08-02 16:23:33xiang.zhangsetfiles: + list_resize_v2.patch

messages: + msg271829
2016-08-02 15:51:38serhiy.storchakasetmessages: + msg271827
2016-08-02 06:36:30xiang.zhangsetmessages: + msg271808
2016-08-02 06:10:56serhiy.storchakasetmessages: + msg271806
2016-08-02 06:08:43rhettingersetnosy: + mark.dickinson
2016-08-02 05:47:51rhettingersetassignee: rhettinger

nosy: + serhiy.storchaka, rhettinger, tim.peters
2016-08-02 01:56:58martin.pantersetmessages: + msg271799
stage: patch review
2016-08-01 14:42:31r.david.murraysetmessages: + msg271785
2016-08-01 14:40:12r.david.murraysetmessages: + msg271784
2016-08-01 02:57:42xiang.zhangsetmessages: + msg271765
2016-07-31 19:14:30r.david.murraysetmessages: + msg271749
2016-07-31 19:12:12r.david.murraysetnosy: + r.david.murray
messages: + msg271748
2016-07-31 17:40:09xiang.zhangcreate