[Python-ideas] Fast sum summary [was Re: Fast sum() for non-numbers - why so much worries?]

[Joshua Landau]

On 12 July 2013 01:52, Steven D'Aprano <steve at pearwood.info> wrote:
> After spending so much time explaining why I don't think sum *should*
> optimize the list case, I'm now going to suggest a way which (I think) sum
> *could* optimize the list case without changing behaviour.
>
<explains>
>
> Since we cannot *guarantee* that sum is fast for all classes, we should not
> promise what we can't guarantee. Better to deliver more than you promise,
> than to make grandiose promises of "fast for everything" that you cannot
> live up to.

That is true. however, I don't believe that a sharp cliff where there
should be a gradient is the right approach.

> Arguments in favour of this suggestion:
>
<basically just "it works">
>
> Arguments against:
>
> - If sum of lists is fast, it will lull people into a false sense of
> security. sum remains an attractive nuisance, since you cannot rely on it
> being fast. As soon as you add one list subclass, it falls back to the slow
> code again.

The subclass thing matters a lot to me. When the discussion was about
"+=", I was for it -- a subclass that keeps behaviour consistent
should not be treated like a second-class citizen, and so we should do
everything we can to prevent people from using sum there.

A three-line solution is miles better than a half-line one which bombs
as soon as you make tiny should-be-irrelevant changes.

> - But on the other hand, that's not much worse than the situation now.
> People are already lulled into a false sense of security, because
> "Everything is fast for small enough N".

I don't agree that that's the same thing. That's being blindly
uninterested in asymptotic performance whereas this change to sum
actively tricks you into thinking that your algorithm has better
asymptotic performance than it does.

> Further questions:
>
> 1) Can we be less conservative about subclasses? E.g. if a subclass does not
> override __add__ or __iadd__, can we safely use the fast path, and only fall
> back on the slow path for those that override?

I'm not sure how __add__ and __iadd__ are implemented -- do they call
other methods on the class?

> 2) Sergey wants to do something similar for tuples, using a temporary list
> accumulator. I've raised the possibility that if the accumulated list is
> huge enough, you might get a MemoryError trying to copy it back to a tuple.
> Does anyone care about this hypothetical case? If not, then we could extend
> the optimization to tuples (at least those that don't override __add__).

Personally I do not care much; Python makes no guarantees about memory
usage. Additionally, the alternative involves a lot of memory holding
partially-added tuples which will be at worst no better than the
list-accumulation method.

> 3) And the critical question: with this (theoretical) patch in place, do the
> test suites still pass? I asked Sergey this same question about his patch
> some days ago, but haven't seen an answer.