new | ask | show | jobs
Zak 13 hours 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`.

OJFord 3 hours ago  [ - ]

I suppose `reduce` as built-in is the footgun because it's too easy to reach for. Now if someone doesn't know about `join` perhaps they look up how to do it because they think 'surely there's a better way than a loop without an import'.

edflsafoiewq 11 hours 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.

vhcr 8 hours ago  [ - ]

The problem with:

    ret = ""
    for s in strings:
        ret += s
is that it re-allocates O(n) times, even if ret is referenced only once.
edflsafoiewq 7 hours ago  [ - ]

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.

ndriscoll 11 hours 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 9 hours 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 9 hours 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 9 hours ago  [ - ]

Does Python actually do that? If the f call throws, you can still observe the (unchanged) binding of acc in reduce.

ndriscoll 9 hours ago  [ - ]

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.

Zak 11 hours ago  [ - ]

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.