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

[Ronald Oussoren]

On 5 Jul, 2013, at 11:20, Paul Moore <p.f.moore at gmail.com> wrote:

> On 5 July 2013 09:36, Steven D'Aprano <steve at pearwood.info> wrote:
>> 
>> Sergey's suggestion also has a more subtle behavioural change. In order to
>> guarantee that sum is fast, i.e. O(N) instead of O(N**2), the semantics of
>> sum have to change from "support anything which supports __add__" to
>> "support anything which supports fast __iadd__".
>> 
> 
> Whoa. That's a non-trivial change. I thought the proposal was "guarantee
> O(N) for types with a constant-time __iadd__ and don't impact performance
> for other types". But that of course begs the question of what happens in
> pathological cases where __iadd__ is (say) O(N^3). There's no way to
> programatically detect whether __iadd__ or __add__ gives the best
> performance, so what I had thought of course cannot be the case :-(

It's not that bad, any type where __iadd__ has (significantly) worse performance
that __add__ is IMHO broken, as you could just not have implemented __iadd__
in the first place.

I'm only +O on using __iadd__ in sum because it is unclear how useful this
would be in real-world code, but does have a simple enough implementation that
is still easily explained. I'd be -1 on adding custom hooks to improve
the performance of specific types (such, adding tricks for speeding up
joining a sequence of tuples or strings) as that makes the implementation
harder and increases the conceptual complexity of the function as well.

Ronald