[Python-ideas] Fast sum() for non-numbers

[Steven D'Aprano]

On 09/07/13 06:22, Sergey wrote:
> On Jul 5, 2013 Andrew Barnert wrote:
>
>>> Yes, you can! You just need to implement a fast __iadd__ or __add__
>>> for your type to make it O(n) summable.
>>
>> Well, in Python 3.3, or even 2.3, you just need to implement a
>> fast __add__. So, if that's an acceptable answer, then we don't need
>> to do anything.
> [...]
>>> And you can always do that, can't you?
>>
>> No. You can't implement a fast __iadd__ for tuple.
>
> Well... Yes, I can! I can't make __iadd__ faster, because tuple has
> no __iadd__, however I can make a faster __add__.


And how do you expect to do that? Tuples are immutable, you have to create a new tuple. So when adding a sequence of N tuples together, you end up making and throwing away N-1 intermediate results.


> But as long as sum()
> is the only (?) function suffering from this problem it was easier to
> do that optimization in sum() instead.

That's the big question though. Is summing a sequence of tuples important and common enough to justify special-casing it in sum? Just how many special cases can be justified?


>> If that's going to be extendable to other types
>
> Are there any other types (except strings, that are blocked anyway)?
>
> Looks like tuple is the only built-in type having no fast __iadd__,

I don't think so:

py> for type in (str, bytes, bytearray, tuple, frozenset, object):
...     print(type.__name__, hasattr(type, '__iadd__'))
...
str False
bytes False
bytearray True
tuple False
frozenset False
object False


Okay, you can't sum() frozensets at all, but there's at least three types that support + that don't support __iadd__ (str, bytes, tuple), and by default anything inheriting from object will not have __iadd__ either.



> and sum() is the only function suffering from that. So, to make sum()
> "fast for everything by default" we only need to make sum use __iadd__
> and write a special case for sum+tuples.
>
>>>    To make advantage of faster __iadd__ implementation sum() uses it
>>>    if possible. sum() has linear time complexity for built-in types
>>>    and all types providing constant-time `__iadd__` or `__add__`.
>
>> Note that integer addition isn't actually constant, it's linear on
>> the word size of the integers. Which means sum isn't linear for
>> integers.

I don't think that strictly matters, since the N in O(N) we're talking about is the number of ints being added, not the number of bits in each int. What is true is that adding a pair of ints is only constant-time if they are sufficiently small (and maybe not even then).



-- 
Steven