[issue46868] Improve performance of math.prod with bignums (and functools.reduce?)

[Tim Peters]

Tim Peters <tim at python.org> added the comment:

About runtime, you're right. I did a ballpark "OK, if there are N incoming values, the inner loop has to go around, for each one, looking for a NULL, across a vector of at most log2(N) entries. So N * log2(N)". But, in fact, it's highly skewed toward getting out early, and 2*N is an upper bound on the total number of inner loop iterations. Strongly related to that the total number of trailing 1 bits in the integers from 1 through N inclusive is N - N.bit_count().

For the rest, I'll only repeat that if this goes in, it should be as a new function. Special-casing, e.g., math.prod() is a Bad Idea. We can have no idea in advance whether the iterable is type-homogenous, or even whether the __mul__ methods the types involved implement are even intended to be associative. 

functools.reduce() clearly documents strict "left to right" evaluation.

But a new treereduce() can do anything it feels like promising.

----------

_______________________________________
Python tracker <report at bugs.python.org>
<https://bugs.python.org/issue46868>
_______________________________________