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

[Sergey]

On 11 Jul 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.

Hey, you saw at least two of us complaining: me and that guy! :)

> 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.

Thank you for reviewing the code. Even for just reviewing the
"explanation".

> 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.

The real C code was doing "CheckExact" for `start`, but subclass
"Check" for `item`. Because that's what __add__ for list and tuple
checked.

> 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'>

And that was a good example. I had to dig deep in sources to
understand why:
  >>> type( [1] + A([2]) )
  <class '__main__.A'>
but:
  >>> type( [1].__add__(A([2])) )
  <class 'list'>

So I updated the patch [1], now it does exact type check and falls
back to general code otherwise. Now it's a little less general, but
more safe.

> 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.

Basically, that's what str.join() is doing. You can try:
  ''.join('' for _ in xrange(100000000))
and watch you free memory being eaten. :) So if this is good for join
I assumed that a smarter version of it for sum() should also be fine.

> 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.

Thank you. I appreciate your words.

-- 

[1]
http://bugs.python.org/file30897/fastsum-special-tuplesandlists.patch