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

[Sergey]

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?

--