classification
Title: Optimize sum() for bools
Type: performance Stage: resolved
Components: Interpreter Core Versions: Python 3.9
process
Status: closed Resolution: fixed
Dependencies: Superseder:
Assigned To: Nosy List: dino.viehland, josh.r, rhettinger, serhiy.storchaka, veky
Priority: normal Keywords: patch

Created on 2019-05-03 09:49 by serhiy.storchaka, last changed 2019-09-10 18:11 by serhiy.storchaka. This issue is now closed.

Pull Requests
URL Status Linked Edit
PR 13074 merged serhiy.storchaka, 2019-05-05 13:12
Messages (7)
msg341330 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2019-05-03 09:49
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
msg344255 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2019-06-02 06:08
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.
msg351649 - (view) Author: Dino Viehland (dino.viehland) * (Python committer) Date: 2019-09-10 13:31
New changeset 88bdb9280b251d753f1b1c8d9183de0fff003622 by Dino Viehland (Serhiy Storchaka) in branch 'master':
bpo-36781: Optimize sum() for bools. (#13074)
https://github.com/python/cpython/commit/88bdb9280b251d753f1b1c8d9183de0fff003622
msg351660 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2019-09-10 13:45
Oh, I was going to withdraw this.
msg351669 - (view) Author: Dino Viehland (dino.viehland) * (Python committer) Date: 2019-09-10 14:20
Sorry, it seemed like a perfectly reasonable change when I was looking at the PR!
msg351726 - (view) Author: Vedran Čačić (veky) * Date: 2019-09-10 16:34
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.
msg351734 - (view) Author: Serhiy Storchaka (serhiy.storchaka) * (Python committer) Date: 2019-09-10 18:11
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.
History
Date User Action Args
2019-09-10 18:11:46serhiy.storchakasetstatus: open -> closed
versions: + Python 3.9, - Python 3.8
messages: + msg351734

resolution: fixed
stage: patch review -> resolved
2019-09-10 16:34:04vekysetnosy: + veky
messages: + msg351726
2019-09-10 14:20:57dino.viehlandsetmessages: + msg351669
2019-09-10 13:45:49serhiy.storchakasetmessages: + msg351660
2019-09-10 13:31:05dino.viehlandsetnosy: + dino.viehland
messages: + msg351649
2019-06-02 06:08:31serhiy.storchakasetmessages: + msg344255
2019-05-05 22:14:13josh.rsetnosy: + josh.r
2019-05-05 13:12:04serhiy.storchakasetkeywords: + patch
stage: patch review
pull_requests: + pull_request13010
2019-05-03 09:49:33serhiy.storchakacreate