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

[Steven D'Aprano]

On 11/07/13 02:10, Sergey wrote:
> On Jul 9, 2013 Steven D'Aprano wrote:
>
>> The fact that sum(lists) has had quadratic performance since sum
>> was first introduced in Python 2.3, and I've *never* seen anyone
>> complain about it being slow, suggests very strongly that this is not
>> a use-case that matters.
>
> Never seen? Are you sure? ;)
>> http://article.gmane.org/gmane.comp.python.general/658630
>> From: Steven D'Aprano @ 2010-03-29
>> In practical terms, does anyone actually ever use sum on more than a
>> handful of lists? I don't believe this is more than a hypothetical
>> problem.

Yes, and I stand by what I wrote back then.


> Not too many, right? And among those someone should be the first.
> Well, I am. :) How many do you need?
>
>> No no no. The objection is that complicating the implementation of
>> a function in order to optimize a use-case that doesn't come up in
>> real-world use is actually harmful. Maintaining sum will be harder,
>> for the sake of some benefit that very possibly nobody will actually
>> receive.
>
> Are you sure it complicates the implementation?

No, I'm not sure.


> Here's how sum function looks NOW, without my patches
> (well, it looks different in C, but idea is the same):
[snip code]

> Alternative to that patch is one more special case for "known slow
> types" i.e. lists and tuples. That was my second patch. In python that
> would be like:
>    if isinstance(start, list) or isinstance(start, tuple):
>      optimize_for = type(start)
>      l_result = list(start)
>      try:
>        while True:
>          item = next(it)
>          if not isinstance(item, optimize_for):
>            start = optimize_for(l_result)
>            start = start + item
>            break
>          l_result.extend(item)
>      except StopIteration:
>        return optimize_for(l_result)
>
> Yes, that's not just one line, but does it really complicates
> existing code that much?

Of course, I understand that this is not the actual C code your patch contains. But I can see at least three problems with the above Python version, and I assume your C version will have the same flaws.

1) You test start using isinstance(start, list), but it should be "type(start) is list". If start is a subclass of list that overrides __add__ (or __iadd__), you should call the overridden methods. But your code does not, it calls list.extend instead. (Same applies for tuples.)

2) You assume that summing a sequence must return the type of the start argument. But that is not correct. See example below.

3) This can use twice as much memory as the current implementation. You build a temporary list containing the result, then you make a copy using the original type. If the result is very large, you might run out of memory trying to make the copy.

So there are three potential problems with your patch. One will potentially cause code that currently works to fail with MemoryError. The other two will potentially cause code to return different results. These are exactly the sort of subtle, and unintended, changes in behaviour that I consider bugs.

Here is an example of a multi-type sum:


py> class A(list):
...     def __add__(self, other):
...             return type(self)(super().__add__(other))
...     def __radd__(self, other):
...             return type(self)(other) + self
...
py> result = sum([[1], [2], A([3]), [4]], [])
py> type(result)
<class '__main__.A'>


It looks to me that your code will return a list instead of an A.

By the way, Sergey, I should say that even though I have been hard on your suggestion, I do thank you for spending the time on this and value your efforts.



-- 
Steven