[New-bugs-announce] [issue36380] collections.Counter in-place operators are unexpectedly slow

[Никита Сметанин]

New submission from Никита Сметанин <nikitozzz.pl at gmail.com>:

All of collections.Counter in-place operators: +=, -=, |= and &= are obviously expected to have time complexity O(b) as in the following example:

a = Counter(...)  # e.g 1M elements
b = Counter(...)  # e.g. 10 elements
a += b

But in fact, all of them are having O(a + b) time complexity due to inefficient implementation of _keep_positive method, which checks ALL of the elements of "a" counter after modification while it's required only to check CHANGED elements (no more than a size of "b") having time complexity O(b).

See https://github.com/python/cpython/blob/master/Lib/collections/__init__.py#L819 

It also unclear if there's even a need to check for non-positives with _keep_positive in ops like __iadd__, __iand__ and __ior__ (except __isub__) as it expects Counters which are always positive.

This unobvious inefficiency leads to unnecessary large execution times while, for example, iteratively accumulating some small Counters into a large one (frequent case). In this case .update method works much faster, but it doesn't check for zeros or negatives for some reason (is this a bug too?).

----------
components: Library (Lib)
messages: 338461
nosy: Никита Сметанин
priority: normal
severity: normal
status: open
title: collections.Counter in-place operators are unexpectedly slow
type: performance
versions: Python 2.7, Python 3.5, Python 3.6, Python 3.7, Python 3.8

_______________________________________
Python tracker <report at bugs.python.org>
<https://bugs.python.org/issue36380>
_______________________________________