Optimize sum() for bools

[serhiy-storchaka]

BPO	36781
Nosy	@rhettinger, @DinoV, @serhiy-storchaka, @MojoVampire, @vedgar
PRs	bpo-36781: Optimize sum() for bools. #13074

^{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-09-10.18:11:46.989>
created_at = <Date 2019-05-03.09:49:33.952>
labels = ['interpreter-core', '3.9', 'performance']
title = 'Optimize sum() for bools'
updated_at = <Date 2019-09-10.18:11:46.982>
user = 'https://github.com/serhiy-storchaka'

bugs.python.org fields:

activity = <Date 2019-09-10.18:11:46.982>
actor = 'serhiy.storchaka'
assignee = 'none'
closed = True
closed_date = <Date 2019-09-10.18:11:46.989>
closer = 'serhiy.storchaka'
components = ['Interpreter Core']
creation = <Date 2019-05-03.09:49:33.952>
creator = 'serhiy.storchaka'
dependencies = []
files = []
hgrepos = []
issue_num = 36781
keywords = ['patch']
message_count = 7.0
messages = ['341330', '344255', '351649', '351660', '351669', '351726', '351734']
nosy_count = 5.0
nosy_names = ['rhettinger', 'dino.viehland', 'serhiy.storchaka', 'josh.r', 'veky']
pr_nums = ['13074']
priority = 'normal'
resolution = 'fixed'
stage = 'resolved'
status = 'closed'
superseder = None
type = 'performance'
url = 'https://bugs.python.org/issue36781'
versions = ['Python 3.9']

[serhiy-storchaka]

To count the number of items that satisfy certain condition you can use either

    sum(1 for x in data if pred(x))

or

sum(pred(x) for x in data)

where pred(x) is a boolean expression.

The latter case is shorter but slower. There are two causes for this:

1. The generator expression needs to generate more items, not only when pred(x) is true, but also when pred(x) is false.

2. sum() is optimized for integers and floats, but not for bools.

The first cause is out of the scope of this issue, but sum() can optimized for bools.

$ ./python -m timeit -s "a = [True] * 10**6" -- "sum(a)"
Unpatched:  10 loops, best of 5: 22.3 msec per loop
Patched:    50 loops, best of 5: 6.26 msec per loop

$ ./python -m timeit -s "a = list(range(10**6))" -- "sum(x % 2 == 0 for x in a)"
Unpatched:  5 loops, best of 5: 89.8 msec per loop
Patched:    5 loops, best of 5: 67.5 msec per loop

$ ./python -m timeit -s "a = list(range(10**6))" -- "sum(1 for x in a if x % 2 == 0)"
5 loops, best of 5: 53.9 msec per loop

[serhiy-storchaka]

I am not sure that this optimization should be added. sum(pred(x) for x in data) will be always slower than sum(1 for x in data if pred(x)) because more items is passed to sun() in the former case. It can be considered as an anti-pattern.

[DinoV]

New changeset 88bdb92 by Dino Viehland (Serhiy Storchaka) in branch 'master':
bpo-36781: Optimize sum() for bools. (bpo-13074)
88bdb92

[serhiy-storchaka]

Oh, I was going to withdraw this.

[DinoV]

Sorry, it seemed like a perfectly reasonable change when I was looking at the PR!

[vedgar]

I don't think anything _bad_ can happen with that optimization, if it's already written. And people (me included) do like to write shorter expressions instead of longer ones.

[serhiy-storchaka]

Well, it is good for people who already sum bools. But if you are concerned about microoptimization, sum(1 for ... if ...) can be better variant.