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.
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`.
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.
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`?).
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?
Fair, I suppose there's no end to the level of insanity that a programmer can do in a dynamic language. I'd think it could perhaps still look to see there's no catch, but maybe eval makes even that impossible.
It might - let's assume it does. My point is that it's better to use the explicit optimized method for joining strings in a performance-sensitive context than to try to meet the conditions for an implicit optimization.
If the s are small the usual geometric buffer growth mitigates that. Of course you can compute the final buffer size in this case, but often you have a bunch of dynamically-generated strings of different sizes.
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...
Zak · · focus · HN ↗
The footgun isn't `reduce` in particular, but failing to use `join`.
edflsafoiewq · · focus · HN ↗
ndriscoll · · focus · HN ↗
edflsafoiewq · · focus · HN ↗
ndriscoll · · focus · HN ↗
edflsafoiewq · · focus · HN ↗
ndriscoll · · focus · HN ↗
Zak · · focus · HN ↗
vhcr · · focus · HN ↗
edflsafoiewq · · focus · HN ↗