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.
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?
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.
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.
chubot · · focus · HN ↗
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:
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.
<a href="https://docs.python.org/3/library/functools.html#functools.reduce" rel="nofollow">https://docs.python.org/3/library/functools.html#functools.r...
taeric · · focus · HN ↗
That is, why couldn't they have done the essentially same trick that you reference for += with reduce?
bmandale · · focus · HN ↗
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.
kenferry · · focus · HN ↗
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.