sum() relies on C signed overflow behaviour

[serhiy-storchaka]

BPO	36791
Nosy	@rhettinger, @mdickinson, @serhiy-storchaka, @miss-islington
PRs	bpo-36791: Safer detection of integer overflow in sum(). #13080 [3.7] bpo-36791: Safer detection of integer overflow in sum(). (GH-13080) #13262

^{Note: these values reflect the state of the issue at the time it was migrated and might not reflect the current state.}

Show more details

GitHub fields:

assignee = None
closed_at = <Date 2019-05-12.09:39:22.573>
created_at = <Date 2019-05-04.05:54:49.017>
labels = ['interpreter-core', '3.8', 'type-bug', '3.7']
title = 'sum() relies on C signed overflow behaviour'
updated_at = <Date 2019-05-12.09:39:22.573>
user = 'https://github.com/serhiy-storchaka'

bugs.python.org fields:

activity = <Date 2019-05-12.09:39:22.573>
actor = 'serhiy.storchaka'
assignee = 'none'
closed = True
closed_date = <Date 2019-05-12.09:39:22.573>
closer = 'serhiy.storchaka'
components = ['Interpreter Core']
creation = <Date 2019-05-04.05:54:49.017>
creator = 'serhiy.storchaka'
dependencies = []
files = []
hgrepos = []
issue_num = 36791
keywords = ['patch']
message_count = 5.0
messages = ['341374', '341384', '341430', '342248', '342250']
nosy_count = 4.0
nosy_names = ['rhettinger', 'mark.dickinson', 'serhiy.storchaka', 'miss-islington']
pr_nums = ['13080', '13262']
priority = 'normal'
resolution = 'fixed'
stage = 'resolved'
status = 'closed'
superseder = None
type = 'behavior'
url = 'https://bugs.python.org/issue36791'
versions = ['Python 3.7', 'Python 3.8']

[serhiy-storchaka]

sum() assumes that an arithmetic operation on signed longs will wrap modulo 2**(bits_in_long) on overflow. However, signed overflow causes undefined behaviour according to the C standards (e.g., C99 6.5, para. 5), and gcc is known to assume that signed overflow never occurs in correct code, and to make use of this assumption when optimizing.

See also bpo-7406.

[serhiy-storchaka]

I tested few cases (all positive, all negative, mixed), and did not found any performance difference after this change.

./python -m perf timeit -s "a = list(range(10**4))" -- "sum(a)"
./python -m perf timeit -s "a = [-i for i in range(10**4)]" -- "sum(a)"
./python -m perf timeit -s "a = [i*(-1)**i for i in range(10**4)]" -- "sum(a)"

[serhiy-storchaka]

New changeset 2950073 by Serhiy Storchaka in branch 'master':
bpo-36791: Safer detection of integer overflow in sum(). (GH-13080)
2950073

[mdickinson]

Can this be closed, or does the fix need to be backported?

[miss-islington]

New changeset b7e483b by Miss Islington (bot) in branch '3.7':
bpo-36791: Safer detection of integer overflow in sum(). (GH-13080)
b7e483b