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

[Andrew Barnert]

First, let me summarize my position, because you're tangling up my separate points, and even tangling other people's points up with mine.

I'm -1 on adding special-casing for tuples that would not be available for any other immutable type.


I'm -0.75 on adding flexible special-casing that could be extended to other types from Python.


I'm -1 on encouraging people to treat sum as the obvious way to concatenate any kind of sequence.

I'm -0 on adding explicit code to sum to raise when start is a non-number (as Alex Martelli wanted), a sequence, or something that can't do 0+start.

I'm between +1 and -0 on changing sum to use copy.copy(start) and __iadd__, depending on whether there are any types that seem like they should be obviously summable and would gain from this change. Adding a bunch of numpy.arrays starting from 0 seems like a reasonable use for sum, as does adding a bunch of timedeltas to a datetime; would either of those benefit from the __iadd__ optimization? If so, I'd be behind that.

From: Sergey <sergemp at mail.ru>

Sent: Monday, July 8, 2013 1:22 PM


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

No, you can't. You can do something different, but only by modifying the C source to sum.

> I can't make __iadd__ faster, because tuple has
> no __iadd__, however I can make a faster __add__.

No, you can't make tuple.__add__ faster either. (If you can, please submit a patch, because that would be useful completely independent of sum.)

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

No, because that requires putting an optimization into sum for _any_ type that's fast-summable but not by using its __add__ or __iadd__, and that's not feasible.

>>  If that's going to be extendable to other types
> 
> Are there any other types (except strings, that are blocked anyway)?

Yes. Every single immutable type. Immutable types do not have __iadd__, for the obvious reason. Whether they're builtin, stdlib, third-party, or part of the application, they will not be fast-summable, and there will be no way to make them fast-summable without patching the interpreter.

blist.btuple has the same problem. You wanted sets to be addable? Then frozenset would have this problem. Strings obviously have this problem, and any third-party immutable string type will as well.

So, if you're suggesting that sum can be fast for anything reasonable, you're just wrong. Adding a custom optimization for tuple only helps tuple; it does not help immutable types in general. And that's why I think it's a bad idea to add custom code to sum for tuples.

>>>  Personally I don't think such implementation would be very useful.
>> 
>>  Given that nearly every program every written in Lisp and its
>>  successors makes heavy use of such an implementation, I submit
>>  that your intuition may be wrong.
> 
> They don't have much choice. And they're not using sum().

Of course they have a choice. You think you can't use dynamic arrays, doubly-linked lists, balanced trees, etc. in Lisp? They use cons lists because there are some algorithms that are natural and fast with cons lists—and because those algorithms work well with appropriate fold/reduce-type functions. 

And Python's sum (like Common Lisp's sum) is a reduce-type function. In fact, other than the optimization for numbers, sum(iterable, start=0) really is just reduce(operator.__add__, iterable, start).

> We're talking about python, and discussing use of sum() in python for
> such lists in particular.

No. You insisted that every collection type is O(N) summable with your design. Others argued that this isn't true. You asked for an example. I offered cons lists. Instead of accepting that, you began arguing that nobody would ever want to use such a type, and then suggesting that if you just changed the implementation and all of the performance characteristics of the type, it would become O(N) summable. Now you've come around to the very position you were arguing against. If you agree that your design is not a general solution for al sequences, then all of your misunderstandings about cons lists are a red herring, and we can drop them.

>It's just you said:
> 
>>  I'm hostile to any attempt to encourage people to treat sum() as
>>  the preferred way to concatenate large amounts of data, because
>>  that will surely lead them into bad habits and will end with them
>>  trying to sum() a lot of tuples or linked lists or something and
>>  getting O(n**2) performance.

First, that wasn't me; please try to keep your attributions straight.

But I agree with the sentiment. There is an efficient way to concatenate a lot of cons lists (basically, just fold backward instead of forward), but sum is not it. Similarly, there is an efficient way to concatenate a lot of tuples or other immutable types, but sum is not it. So, whoever said that is right—encouraging people to treat sum() as the preferred way to concatenate large amounts of data is a bad idea.

Here's how to concatenate a bunch of cons lists in linear rather than quadratic time (on the resulting list length): Walk to the end of the first list, link the next pointer to the start of the second list, walk to the end of that, etc. Easy and efficient, and completely impossible to implement in terms of a repeated __add__ or __iadd__ on the head node (or separate list object).

> Which implies that using such implementation with sum could lead to
> O(N**2) performance. But it could not, because such implementation
> is not addable. So, no problem.
> 
> To have a problem you must modify your implementation. And if you're
> changing it anyway, you have the power to solve this problem too.

No, you don't. It's very easy to add an O(N) extend or __add__ to a cons list type, but it's very hard to make it O(N) summable with the sum function.

>>>  (It's certainly unusual for python's “batteries included” 
> philosophy).
>> 
>>  What does "batteries included" have to do with excluding data 
> types?
> 
> Excluding data types? What do you mean?
> 
> I wasn't sure what you meant when you said about problems with linked
> lists, so I was thinking that you mean something like "if one day
> linked lists get their way into python standard libraries and people
> will try using sum() on them..." That's why I said that such
> implementation would be too skimped.

That's nonsense. If Python were to add something like a cons list—which I don't think would ever happen, but if it did—it would certainly not be a defective version that wasn't useful with the algorithms that people want cons lists for. "Batteries included" doesn't imply that every collection has to implement the same API as list with the same performance guarantees.

You clearly don't understand how people use cons lists, and therefore you don't understand why your suggested "improvement" makes them much weaker.

>>>  What I would call a linked-list is a separate type where your nodes

>>>  are just its internal representation.
>> 
>>  If you make the lists and nodes separate types, and the nodes
>>  private, you have to create yet a third type, like the list::iterator
>>  type in C++
> 
> If there would be a need for it, why not?

Agreed. That makes the APIs a little more complicated (you need to a list and a list::iterator instead of just a node), but that's not a big deal. And, with (list, list::iterator) being equivalent to a node, it leads to exactly the same issues as you started with in having just a node type.

> Or maybe I won't need it
> (then I get something like collections.deque, a good tool by the way).

Yes, deque is a great tool, but it's not the same tool as a linked list, and doesn't support the same algorithms. (Note that C++ has both of them, as separate types.) 

>>>  I don't like the idea that `a` implicitly changes when I change 
> `b`.
>> 
>>  Then you don't like linked lists. Saying "There is a way to make
>>  it work, just make it do something different, which is O(N) instead
>>  of O(1) and won't work with the algorithms you want to use" is not 
> an
>>  answer.
> 
> That wasn't saying "just make it do something different". That was
> saying "you can have linked lists in python, that are O(N) summable".

Which is exactly the point you were arguing against. If you now agree with everyone else, fine. There are types that can be efficiently concatenated, but not with sum. That's why everyone else thinks you shouldn't encourage people to use sum for general concatenation.

>>>  But you CAN have a fast __iadd__ even for your simple a.next case!

>>>  You only need to initialize `tail` before calling sum() and update
>>>  it inside __iadd__
>> 
>>  Initialize tail where exactly? In a global variable?
> 
> Wherever you want. In a global variable, or in a class variable near
> 'next'.

Using a global variable (or a class attribute, which is the same thing) means that sum isn't reentrant, or thread-safe, or generator-safe. Trying to sum two completely different iterables at the same time will break. You really think that's a sensible design? Why even have a list type; just make the head and tail into global variables and everything is fine, right?