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

[Terry Reedy]

On 7/17/2013 10:28 AM, Sergey wrote:
> On Jul 16, 2013 Steven D'Aprano wrote:
>
>> Right now, sum() behaves in a certain way. There are certain things
>> which people expect sum() to do. Some of those things are documented
>> explicitly. Some of them are implied. Some of them have regression
>> tests. Some of them don't. But regardless, we can tell how sum() behaves
>> right now by running it and seeing what it does.
>>
>> Your suggested optimizations change that behaviour. It does not just
>> speed sum() up, they lead to an actual semantic change. So we are not
>> just arguing about speed, we are arguing about behaviour as well.
>
> All my suggestions produce NO behaviour change. If they lead to some
> semantic changes — it's a bug, that should be fixed, or the patch
> should be removed from suggestions list.
>
>> You are worried about sum() being slow for people who call it with list
>> arguments. That is a valid concern. Nobody here *wants* sum() to be
>> slow. If it was a pure speed optimization, then we would all be 100%
>> behind it. But it is not a pure speed optimization, it also changes
>> behaviour, sometimes in subtle, hard to see ways.
>>
>> So there are three approaches we can take:
>>
>> - Do nothing. sum() continues to work exactly the same way as it
>>    currently works, even if that means sometimes it is slow.
>>
>> - Accept your patches. sum() changes its behaviour, which will break
>>    somebody's working code, but it will be fast, at least for some
>>    objects.
>
> If you talk about "+=" patch then I already removed it from my
> suggestion list exactly because it changed the behaviour. Others
> should not change sum() in any way except performance.
>
>> - Accept a compromise position. We can make sum() faster for built-in
>>    lists, and maybe built-in tuples, while keeping the same behaviour.
>>    Everything else, including subclasses of list and tuple, keep the
>>    same behaviour, which may mean it remains slow.
>
> That would probably cover most of use-cases, at least most of those I
> could find, but yes, it does not help other types and subclasses.
> (are there some known use cases of tuple subclasses additions?)
>
>> They are the only choices.
>
> No, there're lots of others! That's what I'm trying to do here! I'm
> searching for the best choice to make sum performance consistent.
>
> If while doing that we'll also improve overall python performance,
> reduce its memory usage or find a "more obvious" way for sequences
> concatenation — great!
>
>> You are concerned more about sum() being slow than you are about
>> breaking code that today works. Some of us here disagree, and
>> think that breaking code is worse than slow code, especially for
>> something as uncommon as sum(list_of_lists).
>
> Then I agree with some of us. :) Because I believe that backward
> compatibility is more important, than speed. That's why I'm mainly
> focused on those options, that do not break it.
>
>> But, a compromise patch that speeds up some code without breaking any
>> code may be acceptable.
>
> Yes, but which one?
> * Special case for lists and tuples is easy to do and breaks nothing,
>    but does nothing good for subclasses and other types.
> * Direct optimization of lists/tuples looks like a great idea, works
>    for subclasses, should also change nothing, but it's a large patch,
>    that is harder to write and test compared to a special case one.
> * Universal concatenation interface (which one? there were at least
>    3 suggested) looks interesting, but needs lots of additional
>    polishing.
>
>>> Same applies to sum(): even if it's impossible to make if fast for
>>> all collection types, it does not mean that it should not be fast for
>>> some of them, e.g. lists and tuples.
>>
>> That is change from your previous posts where you said you could make it
>> fast for "everything". I am glad to see you have accepted this.
>
> I have not really changed my mind about that. :) I still think that
> for every real-world type you name I can probably find a way to make
> it O(N) summable with sum() patch or without it.
>
> But of course, I do not expect that any of my suggestions implemented
> will instantly make all the types in the world O(N) summable. It may
> help them become O(N) however.
>
>>> [1] http://bugs.python.org/file30917/fasttuple.py
>
>> I do not like that implementation, because it shares the underlying
>> storage. This means that tuples which ought to be small will grow and
>> grow and grow just because you have called __add__ on a different tuple.
>>
>> Using Python 2.7 and your implementation above:
>>
>> py> a = ft([])  # empty tuple
>> py> len(a._store)
>> 0
>> py> b = ft([1])
>> py> c = a + b
>> py> d = ft([2]*10000)
>> py> c = c + d
>> py> len(a._store)
>> 10001
>>
>> So adding a big tuple to c changes the internal storage of a.
>
> Yes, that's right. All 3 variables `a`, `b` and `c` share the same
> storage, so you effectively get 3 variables for the price of one. :)
> That's the concept. Why is that bad?

What happens to len(a._store) after del c?


-- 
Terry Jan Reedy