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

[Joshua Landau]

On 12 July 2013 02:34, Sergey <sergemp at mail.ru> wrote:
> On Jul 9, 2013 Andrew Barnert wrote:
>
> but we could at least start discussing options, instead of
> repeating excuses.

This is rude, and I'd rather you try to avoid being rude.

>>> Theoretically it's possible to rewrite a tuple type to internally use
>>> list type for storage, and additionally have a `localcount` variable
>>> saying how many items from that list belong to this tuple. Then
>>> __add__ for such tuple would just create a new tuple with exactly
>>> same internal list (with incremented ref.count) extended. This way,
>>> technically, __add__ would modify all the tuples around, but due to
>>> internal `localcount` variable you won't notice that.
>>
>> I was going to point out the side effects of such a change, but
>> someone beat me to it.
>
> Yes, as a side-effect it would sometimes use less memory (and it could
> also use more memory, however I can't think of any real-world cases
> where that could be a problem).

Is this similar to the shared-memory thing for dictionaries? If so, it
might be a good proposal in and of itself.


>>> Which is just one type — tuple. There's no other summable standard
>>> types in python having O(N) __add__, is it?
>>
>> Does nobody ever use types from the stdlib, third-party libs, or
>> their own code in your world? Builtin types are not generally
>> magical. A function that works well for all builtin types, but not
>> types in the stdlib, is a recipe for confusion.
>
> What types from stdlib it does not work for?

Shall I list some stdlib types; you can tell me what it's fast for:

# do this later


>>>> So, if you're suggesting that sum can be fast for anything
>>>> reasonable, you're just wrong.
>>>
>>> I suggested two ways how to do that. First, one can use the approach
>>> above, i.e. use mutable type internally. Second, for internal cpython
>>> types we have a simpler option to implement optimization directly
>>> in sum(). And there may be many others, specific to the types in
>>> question.
>>
>> Using a mutable type internally will almost always have side
>> effects, or at least complicate the implementation.
>
> Yes, optimization may or may not complicate implementation. Nothing new
> here. For example "optimizing" tuple most probably won't complicate
> implementation, it would just make it different, but faster to __add__.

But you also make it complicated for everyone who subclasses, for
example. It's not good to make lives harder for this.


>> And again, what would be the benefit?
>
> Hm. Benefits of O(N)-summable builtin types?
> * No more surprises "Oh, sum() is O(N**2) Why?"

Only you haven't removed that, as when people use a list subclass
instead it comes back -- in a much more devastating fashion. Then they
have to rewrite their code.

> * People can use whatever builtin functions they want with any built-in
>   types they want in any obvious to them way and nobody would say them
>   that it will be too slow. A little slower, maybe, but not too much.

No they can't. You're conflating sum() with *all* builtins.

> * Programs become faster

Some. But not many.

> * Code becomes simpler and easier to read

Hardly. If "my_type(chain.from_iterable(iterable))" is the hardest
part of code for you to read, you're doing it wrong.

>>> Maybe, then we (or
>>> their authors) will deal with them later (and I tried to show you
>>> the options for your single linked list example).
>>
>> And you only came up with options that destroy vital features of
>> the type, making it useless for most people who would want to use it.
>
> I did not. Or are you saying that STL developers also destroyed vital
> features of your the because they have not implemented std::list the
> same way? Have python destroyed those vital features with it's list?
> Your type is not summable. You asked for the type that is summable.
> I suggested one to you, you did not liked it. That's it, nothing is
> destroyed.

I think you need to re-read those posts.

>> But, more importantly, it is very simple to design and implement
>> new collection types in Python today. Adding a new requirement that's
>> hard enough to reach--one that you haven't been able to pull it off
>> for the first example you were given--implies that it would no longer
>> be easy.
>
> What requirements are you talking about?

Surely he means that extra flab you have to write to make it
fast-summable. Otherwise other people's code that uses sum() because
you said it was the "one true way" suddenly becomes painfully slow. Or
they could have written the current method and it would've worked
immediately.

>> Then you misunderstood it. Tuples were offered as one example, out
>> of many, that won't be fast. Solving that one example by adding a
>> special case in the C code doesn't help the general problem
>
> That's why I explained how this can also be done without writing
> a special case in sum(). It's just if you have a goal and two ways
> to reach it, one of them is extremely complicated, and another one
> is easy, other than that they're equal, which one will you choose?

No matter which way you write it, it doesn't solve the problem.


> In that case to use sum you won't need __add__ in your list at all.
>
>>> Then, what way you suggest to be preferred? For example how would you
>>> do that in py4k? I guess you would prefer sum() to reject lists and
>>> tuples as it now rejects strings and use some other function for them
>>> instead? Or what? What is YOUR preferred way?
>>
>> I've already answered this, but I'll repeat it.
>>
>> sum is not the obvious way to concatenate sequences today, and my
>> preferred way is for that to stay true. So, I'm: [...]
>
> You're saying what IS NOT your preferred way. But I'm asking what IS
> your preferred way. Do you prefer to have a slow sum in python and
> people asking why it's slow forever? Do you see that as a best
> possible case for python?

YES. Godamnit YES. 100% true-to-form YES.

Now stop asking us.

>>> Really, I don't understand that point. Are you saying, that sum()
>>> must remain slow for FREQUENTLY USED standard types just because
>>> there MAY BE some other types for which it would still be slow?
>>
>> You're twisting the emphasis drastically, but basically yes.
>
> And that's the only reason? What if I solve that too? E.g. what if
> there would be a common way exposed to all the types in a world?
> For example imaging a special case (or is it "general case" now)
...
> ld be able to implement an optional
> __init_concatenable_sequence_from_iterable__ method to benefit from
> optimized sum(). If they won't do that sum() would use general code.
> And of course it would be trivial to implement it for e.g. tuples.
> Is that what you want?

So your solution to make sum faster is to make everything else harder?

>> Today, sum is not the best way to concatenate sequences. Making it
>> work better for some sequences but not others would mean it's still
>> not the best way to concatenate sequences, but it would _appear_ to
>> be. That's the very definition of an attractive nuisance.
>
> Today python is not the best language in the world, because it still
> has bugs. Fixing some bugs but not others would mean that it's still
> not the best language in the world, but it would _appear_ to be. So,
> let's never fix any bugs?
>
> Don't you think that your logic is flawed? ;)

Does that actually seem like a good counterargument? It's a massively
flawed analogy.

Bugs are not the same as something being not-the-standard. A good
analogy would be if Python was bad for <task>. If Python changed
itself so it was good at <task> for one thing, that would be an
attractive nuisance. Because as soon as you try to use Python, you
find it isn't good for all things you need it for any you just
implemented a useless program.

If code uses sum() it needs to work for *all types* that the code
receives. Python is duck-typed - so if you only want an indexable
sequence then it needs to be fast for indexable sequences. There is no
way to solve this without making people implement loads more code.
When they could just use list(chain.from_iterable(...)) instead, sum
looks like a really dumb idea.