3 ms·

Related to the point about worse performance, I'm pretty sure I was there when reduce was "banished" from Python 3 -- demoted to functools.reduce(), instead of

by chubot 10d ago

Related to the point about worse performance, I'm pretty sure I was there when reduce was "banished" from Python 3 -- demoted to functools.reduce(), instead of the builtin reduce() in Python 2 The story is that sometime in 2006 or 2007, Guido van Rossum was debugging why a web page in Google's internal code review tool (which he wrote) was taking 30+ seconds to render. This is basically a "production" incident, since thousands of Google engineers relied on the tool. Requests like this were probably tying up threads and exhausting thread pools, perhaps Eventually it was tracked down to a line wrapping algorithm written with reduce(). I don't think he wrote it -- it may have come in through a dependency. As many know, reduce() is basically: s1 + s2 s1 + s2 + s3 s1 + s2 + s3 + s4 ... And that's O(n^2) when s_i are strings. And I think it showed up if you viewed a 5000+ line diff, or a 5000+ line file. (Newer programs like Github also suffer here) I believe, in Python at that time, += was already optimized to avoid this (just like essentially all JS VMs are). Or you can use the idiom of append() to list and join() after. But reduce() basically forces the inefficient implementation, and I'm sure this is still true in Python 3. --- So basically Guido spent a long time debugging a performance problem related to reduce(), and made the decision to eject it, to help users avoid "footguns". I was his officemate at the time, so I recall this, but I wasn't involved directly Also, somebody contributed reduce() to Python way back in the 90's, as well as other functional idioms. He wouldn't have added that himself -- it was never his preferred style. He preferred a more imperative style. But he allowed those contributions, and then slightly regretted it later. https://docs.python.org/3/library/functools.html#functools.reduce https://docs.python.org/3/library/functools.html#functools.r...

taeric 10d ago
This always feels odd to me. It would seem a fairly straight forward optimization of the interpreter to special case the different types that it can reduce. That is, why couldn't they have done the essentially same trick that you reference for += with reduce?
- kelipso 10d ago
  [flagged]
- justonceokay 10d ago
  That sounds nice but in practice it’s probably not super helpful. Yes you could make a special case for reducing “+” over integers. But in python you can generally not promise that all the inputs are strictly integers, and you can’t even promise that your “+” function has no side effects.
- bmandale 10d ago
  There is no such trick. Python is only now getting those sort of JIT style optimizations, and that one in particular still hasn't hit. Do not use += on strings in a loop unless you are certain the iteration count will be small. There is an optimization for lists, and maybe that's what GP is remembering. l += is functionally different from l = l +. The former mutates l, whereas the latter creates a new l. The difference matters when the line above is m = l. The mutation version will mutate m as well (they're the same reference), the creates new version will not. This optimization can just as easily turn into a footgun if the programmer is unaware of it, and in that sense is unpythonic.
  - Maxatar 10d ago
    Python has optimized string appending in the form of: s = s + "foo" and s += "foo" Since 2005 with the release of Python 2.4: https://docs.python.org/3/whatsnew/2.4.html#optimizations https://docs.python.org/3/whatsnew/2.4.html#optimizations
  - kenferry 10d ago
    I’m not a fan of this kind of “fancy” optimization anyway. It’s too fragile. I may make some innocuous change, now the compiler cannot recognize the pattern and performance falls off the cliff. I’d rather have the reliabile performance than the absolute fastest possible result. Then if there’s an issue I can catch and fix it reliably with profiling, not deal with a heisenbug based on whether the compiler can match the pattern.
bjourne 10d ago
Maybe you are misremembering the story? += deferred concatenation requires lazy strings and that didn't come until 10-15 years later. However, concatenating string lists with sum() was a common Python idiom at the time and it indeed incurred O(n^2) complexity. Gvr's reduce dislike was more about its syntax. It doesn't mesh well with Python's lambda syntax.
- Maxatar 10d ago
  > += deferred concatenation requires lazy strings and that didn't come until 10-15 years later. CPython's += does not perform deferred concatenation and CPython does not use lazy strings. The optimization uses an eager in-place realloc if the string's ref-count is 1. This remains the optimization used even to this day and was introduced in 2005: https://docs.python.org/3/whatsnew/2.4.html#optimizations https://docs.python.org/3/whatsnew/2.4.html#optimizations >However, concatenating string lists with sum() was a common Python idiom at the time It could not possibly have been a common Python idiom since sum() explicitly rejected strings by throwing a TypeError. This was explicitly special cased to avoid the degenerate performance and the TypeError even has an error message saying "TypeError: sum() can't sum strings [use ''.join(seq) instead]". >Gvr's reduce dislike was more about its syntax. It doesn't mesh well with Python's lambda syntax. No it had nothing to do with mixing with lambda syntax, on the contrary GvR actually wanted to remove reduce and lambda (and map and filter as well). Here is the actual article by GvR regarding removing reduce, absolutely nothing in it involves how it mixes with lambda expressions. https://www.artima.com/weblogs/viewpost.jsp?thread=98196 https://www.artima.com/weblogs/viewpost.jsp?thread=98196 >So now reduce(). This is actually the one I've always hated most, because, apart from a few examples involving + or *, almost every time I see a reduce() call with a non-trivial function argument, I need to grab pen and paper to diagram what's actually being fed into that function before I understand what the reduce() is supposed to do. So in my mind, the applicability of reduce() is pretty much limited to associative operators, and in all other cases it's better to write out the accumulation loop explicitly.
  - chubot 10d ago
    Yes thanks for finding the Python 2.4 release page which shows the optimization! So I remembered correctly -- Python already had that optimization back then. (There seems to be a large amount of confusion on that in this subthread) And the March 2005 Artima post is also a very good reference! That actually predates my story, since Guido hadn't joined Google by then. I recall that he joined in December 2005. So maybe the bug I remember was more of a "push" in the direction he had already thought of, not the direct inspiration. It's clear from the blog post that he disliked all of map / filter / reduce, and then I'm sure that users or python-dev pushed back on removing them, so he settled for banishing reduce() to the stdlib.
hn_go_brrrrr 10d ago
2006...would that have been Mondrian?
- chubot 10d ago
  Yes!
rienbdj 10d ago
So rather than provide a runtime or compiler optimization, we force the programmer to do it by hand. This is why I don’t like Python philosophically.
- j2kun 10d ago
  I don't believe Python had a compiler in 2006...
  - paradox460 10d ago
    It had a runtime
  - chubot 10d ago
    Python has always had a bytecode compiler that did some minor optimizations, since its inception in the 90's. The issue is that optimizations are very hard to do correctly in the compiler because Python is so dynamic. Any piece of code could suddenly redefine mytype.__add__() and so forth.
  - Digit-Al 8d ago
    Python 2.0 was released in October 2000. Maybe you're thinking of Python 3.0.
Zak 10d ago
I find that decision a bit odd given that accumulating a string with a loop is also quadratic in Python if you use = instead of +=, or even if you use += when the left operand isn't provably unshared. I don't believe removing loops was seriously considered. The footgun isn't `reduce` in particular, but failing to use `join`.
- edflsafoiewq 10d ago
  Doesn't reduce force the accumulator to be shared though? Both the reduce and the lambda are holding onto references to acc, which defeats any "single reference" optimizations.
  - ndriscoll 10d ago
    def reduce(acc, f): for v in self: acc = f(acc, v) return acc The current acc goes out of scope each time you call f. There's no shared reference (assuming f doesn't sneak store it elsewhere, which for string combining, f should just be `return a+b`?).
    - edflsafoiewq 9d ago
      The binding for acc in the reduce call is still active during the f call, which means there are at least two references to acc.
      - ndriscoll 9d ago
        Why is it still active? Even an interpreter with no lookahead could see that it goes out of scope immediately when f returns (it gets shadowed on that line), so as long as there's no guarantee about when finalizers get called, it should be able to mark it dead inside of reduce as soon as it's passed to f. Like move semantics here should be a general pattern for optimization, no?
        edflsafoiewq 9d ago
TZubiri 10d ago
The way I understand it, the map,filter,reduce functions in python exist as pythonic language constructs: -map: [x*2 for x in xs] -filter: [x for x in xs if x%0==2] -reduce: ummm.. Maybe something like: sum = x+ret for x in xs from ret=0
- anitil 10d ago
  Maybe the closest is 'join' similar to `",".join([...])`? If we could replace the string with an operator
- Izkata 9d ago
  That one is built in: sum([1, 2, 3]) == 6
z500 9d ago
> Also, somebody contributed reduce() to Python way back in the 90's, as well as other functional idioms. He wouldn't have added that himself -- it was never his preferred style. > He preferred a more imperative style. But he allowed those contributions, and then slightly regretted it later. That would explain why they're so inconvenient to chain.

by chubot 10d ago

taeric 10d ago

This always feels odd to me. It would seem a fairly straight forward optimization of the interpreter to special case the different types that it can reduce. That is, why couldn't they have done the essentially same trick that you reference for += with reduce?

kelipso 10d ago
[flagged]
justonceokay 10d ago
That sounds nice but in practice it’s probably not super helpful. Yes you could make a special case for reducing “+” over integers. But in python you can generally not promise that all the inputs are strictly integers, and you can’t even promise that your “+” function has no side effects.
bmandale 10d ago
There is no such trick. Python is only now getting those sort of JIT style optimizations, and that one in particular still hasn't hit. Do not use += on strings in a loop unless you are certain the iteration count will be small. There is an optimization for lists, and maybe that's what GP is remembering. l += is functionally different from l = l +. The former mutates l, whereas the latter creates a new l. The difference matters when the line above is m = l. The mutation version will mutate m as well (they're the same reference), the creates new version will not. This optimization can just as easily turn into a footgun if the programmer is unaware of it, and in that sense is unpythonic.
- Maxatar 10d ago
  Python has optimized string appending in the form of: s = s + "foo" and s += "foo" Since 2005 with the release of Python 2.4: https://docs.python.org/3/whatsnew/2.4.html#optimizations https://docs.python.org/3/whatsnew/2.4.html#optimizations
- kenferry 10d ago
  I’m not a fan of this kind of “fancy” optimization anyway. It’s too fragile. I may make some innocuous change, now the compiler cannot recognize the pattern and performance falls off the cliff. I’d rather have the reliabile performance than the absolute fastest possible result. Then if there’s an issue I can catch and fix it reliably with profiling, not deal with a heisenbug based on whether the compiler can match the pattern.

bjourne 10d ago

Maybe you are misremembering the story? += deferred concatenation requires lazy strings and that didn't come until 10-15 years later. However, concatenating string lists with sum() was a common Python idiom at the time and it indeed incurred O(n^2) complexity. Gvr's reduce dislike was more about its syntax. It doesn't mesh well with Python's lambda syntax.

Maxatar 10d ago
> += deferred concatenation requires lazy strings and that didn't come until 10-15 years later. CPython's += does not perform deferred concatenation and CPython does not use lazy strings. The optimization uses an eager in-place realloc if the string's ref-count is 1. This remains the optimization used even to this day and was introduced in 2005: https://docs.python.org/3/whatsnew/2.4.html#optimizations https://docs.python.org/3/whatsnew/2.4.html#optimizations >However, concatenating string lists with sum() was a common Python idiom at the time It could not possibly have been a common Python idiom since sum() explicitly rejected strings by throwing a TypeError. This was explicitly special cased to avoid the degenerate performance and the TypeError even has an error message saying "TypeError: sum() can't sum strings [use ''.join(seq) instead]". >Gvr's reduce dislike was more about its syntax. It doesn't mesh well with Python's lambda syntax. No it had nothing to do with mixing with lambda syntax, on the contrary GvR actually wanted to remove reduce and lambda (and map and filter as well). Here is the actual article by GvR regarding removing reduce, absolutely nothing in it involves how it mixes with lambda expressions. https://www.artima.com/weblogs/viewpost.jsp?thread=98196 https://www.artima.com/weblogs/viewpost.jsp?thread=98196 >So now reduce(). This is actually the one I've always hated most, because, apart from a few examples involving + or *, almost every time I see a reduce() call with a non-trivial function argument, I need to grab pen and paper to diagram what's actually being fed into that function before I understand what the reduce() is supposed to do. So in my mind, the applicability of reduce() is pretty much limited to associative operators, and in all other cases it's better to write out the accumulation loop explicitly.
- chubot 10d ago
  Yes thanks for finding the Python 2.4 release page which shows the optimization! So I remembered correctly -- Python already had that optimization back then. (There seems to be a large amount of confusion on that in this subthread) And the March 2005 Artima post is also a very good reference! That actually predates my story, since Guido hadn't joined Google by then. I recall that he joined in December 2005. So maybe the bug I remember was more of a "push" in the direction he had already thought of, not the direct inspiration. It's clear from the blog post that he disliked all of map / filter / reduce, and then I'm sure that users or python-dev pushed back on removing them, so he settled for banishing reduce() to the stdlib.

hn_go_brrrrr 10d ago

2006...would that have been Mondrian?

chubot 10d ago
Yes!

rienbdj 10d ago

So rather than provide a runtime or compiler optimization, we force the programmer to do it by hand. This is why I don’t like Python philosophically.

j2kun 10d ago
I don't believe Python had a compiler in 2006...
- paradox460 10d ago
  It had a runtime
- chubot 10d ago
  Python has always had a bytecode compiler that did some minor optimizations, since its inception in the 90's. The issue is that optimizations are very hard to do correctly in the compiler because Python is so dynamic. Any piece of code could suddenly redefine mytype.__add__() and so forth.
- Digit-Al 8d ago
  Python 2.0 was released in October 2000. Maybe you're thinking of Python 3.0.

Zak 10d ago

I find that decision a bit odd given that accumulating a string with a loop is also quadratic in Python if you use = instead of +=, or even if you use += when the left operand isn't provably unshared. I don't believe removing loops was seriously considered. The footgun isn't `reduce` in particular, but failing to use `join`.

edflsafoiewq 10d ago
Doesn't reduce force the accumulator to be shared though? Both the reduce and the lambda are holding onto references to acc, which defeats any "single reference" optimizations.
- ndriscoll 10d ago
  def reduce(acc, f): for v in self: acc = f(acc, v) return acc The current acc goes out of scope each time you call f. There's no shared reference (assuming f doesn't sneak store it elsewhere, which for string combining, f should just be `return a+b`?).
  - edflsafoiewq 9d ago
    The binding for acc in the reduce call is still active during the f call, which means there are at least two references to acc.
    - ndriscoll 9d ago
      Why is it still active? Even an interpreter with no lookahead could see that it goes out of scope immediately when f returns (it gets shadowed on that line), so as long as there's no guarantee about when finalizers get called, it should be able to mark it dead inside of reduce as soon as it's passed to f. Like move semantics here should be a general pattern for optimization, no?
      - edflsafoiewq 9d ago

TZubiri 10d ago

The way I understand it, the map,filter,reduce functions in python exist as pythonic language constructs: -map: [x*2 for x in xs] -filter: [x for x in xs if x%0==2] -reduce: ummm.. Maybe something like: sum = x+ret for x in xs from ret=0

anitil 10d ago
Maybe the closest is 'join' similar to `",".join([...])`? If we could replace the string with an operator
Izkata 9d ago
That one is built in: sum([1, 2, 3]) == 6

z500 9d ago

> Also, somebody contributed reduce() to Python way back in the 90's, as well as other functional idioms. He wouldn't have added that himself -- it was never his preferred style. > He preferred a more imperative style. But he allowed those contributions, and then slightly regretted it later. That would explain why they're so inconvenient to chain.