[issue36229] Linear-time ops for some mutable collections.

[Brandt Bucher]

New submission from Brandt Bucher <brandtbucher at gmail.com>:

Binary operations on collections are, in general, of quadratic complexity. However, we can sometimes operate in-place if we know that we hold the only reference to the object. This allows us to avoid making many intermediate copies when summing many lists (or dicts ;), taking the union of many sets, or working with literals.

The attached PR adds a simple 2-line refcount check which delegates to the corresponding in-place operation for: list_concat, list_repeat, set_and, set_or, set_xor, set_sub, bytearray_concat, and bytearray_repeat.

----------
components: Interpreter Core
messages: 337442
nosy: brandtbucher
priority: normal
severity: normal
status: open
title: Linear-time ops for some mutable collections.
type: performance
versions: Python 3.8

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