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

[Andrew Barnert]

Let's split this into parts. What you have is (a) a patch to make iaddable types sum faster, (b) a patch to make tuples sum faster, and (c) 37 different half-baked ideas for how to maybe come up with a patch to make either all iterables or all addable types sum faster, most of which you later deny having ever offered.

If you drop all the stuff related to sequences, and come up with a numeric case that's helped by (a), I'm pretty sure you could get that approved with little to no objection, and then come back to the rest later. And there probably are such types. Someone suggested some C-implemented quaternion library. I suggested numpy.matrix. Someone else suggested a different vector class. And there are plenty of other obvious things to try--huge pygmp ints, a BCD class, ... All you have to do is try them out and show that at least one of them gets a significant speedup.

Once you get (a) accepted (or fail to find any good use for it besides lists, which I think is less likely), come back to the rest, and pick an argument and stick to it. Either (b) is good on its own because tuples are special and there's no reason to make it general, or tuples aren't special and it should be general and therefore you have a concrete proposal that actually works as expected on a variety of types that you've actually tested.

On Jul 10, 2013, at 9:10, Sergey <sergemp at mail.ru> wrote:

> On Jul 9, 2013 Steven D'Aprano wrote:
> 
>> 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?

The iadd case doesn't complicate it much. But the tuple case, halfway hacked up toward a more general solution that you haven't quite envisioned, does.

Meanwhile, the fact that ints and floats _also_ complicate things isn't a good argument here. Adding ints is the paradigm use case for sum, so it's arguably worth extra complexity. Also, the fact that it's been maintained for over a decade, through the int/ long unification and py3k, means nobody has to guess whether it will be a maintenance burden.

> 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?
> 
> Theoretically this code could be extended to any iterable. So,
> *theoretically* it could be:
>  if start_is_iterable:
>    optimize_for = type(start)
>    ... same code here ...

No it can't. Or, rather, it would be a very bad idea. Matrices would be unraveled and concatenated into vectors instead of added, types that aren't addable for good reason like dicts and files would do various different odd things instead of raising, intentionally lazy (and potentially infinite) types would be forced strict, types that can append faster than list like deque would slow down (as would set if it became addable) and/or use much more memory, ...

> but there's a technical problem in the line:
>          start = optimize_for(l_result)
> This line works for lists and tuples. It will even work for set and
> frozenset, if needed. But the problem is that I cannot guarantee that
> it will work for arbitrary type. For example it does not work for
> strings (even worse, it works, but not as I would want it to).
> In my patch I also showed how strings can be handled for that case.
> 
> Basically, this very single line is the only line holding me from
> making my "special case" into "general case" for all iterables in
> the world.

And that's lucky, because as a general case it would be a very bad thing.

>> I don't care that sum() is O(N**2) on strings, linked lists,
>> tuples, lists. I don't think we should care. Sergey thinks we should
>> care, and is willing to change the semantics of sum AND include as
>> many special cases as needed in order to "guarantee" that sum will be
>> "always fast". I don't believe that guarantee can possibly hold, and
> 
> Just ONE special case is needed — the one for iterables. And yes,
> the "guarantee" can hold, because it only affects built-in types,
> and my patch covers all of them, even those that are not supported
> by sum() yet.

A guarantee that only holds for builtin types and cannot be extended in any way to other types is more misleading than useful. Today, a few people misuse sum on sequences and get quadratic behavior. That's exactly what you want to fix. But with your change, many more people would use sum on sequences and get quadratic behavior, because the whole point of your patch is to make sum the obvious way to concatenate sequences. And, while today, it's a bug in their code that can be explained with a simple link to the docs, with your change, it will be a bug in python requiring a workaround explained by a link to some FAQ or blog post.

And if that isn't what you intend, then you don't intend for sum to be the obvious way to concatenate sequences, and your patch is just bending over backward to make buggy code run better.

You can't have it both ways.

> But it's also good for third-party types, because it
> gives them an option to implement a fast __iadd__. They don't have
> this option now.

The first patch alone does that for all fast-iaddable types, including non-sequences as well as list-like sequences.

The second patch adds nothing to it, nor do any of your attempts to generalize it. It only works for mutable types that can iadd faster than they can add. You've already been given examples of types that isn't true for--any immutable type, cons lists, etc. Even if you could find a theoretical answer for those cases--which so far you haven't, but there's no harm in continuing to try--that won't actually help anyone using an actual python interpreter rather than some vague theoretically possible one.

>> Flattening sequences is not sum. You have to consider ...
> 
> Yet people think [1] that sum() is useful for that.

People also think that "if ('foo' or 'bar') in baz" is useful. It comes up every few days, not just a few times a year like summing tuples. It's even the basis of a running joke on StackOverflow. Does this mean we should change Python so it does what they expect?

And again, your patch doesn't solve the problem, it makes it worse. If people mistakenly think that sum is useful for tuples, they're also going to think that it's useful for all kinds of other sequences. They'll still be wrong--but now the docs, and their early experiences, will tell them otherwise.