3 ms·
I'm not sure about other implementations, but "optimizing" CPython ends up being optimizing against counter-intuitive interpreter internals rather than time-com
by paavoova 8y ago
I'm not sure about other implementations, but "optimizing" CPython ends up being optimizing against counter-intuitive interpreter internals rather than time-complexity of the code.
For example, in CPython 3.6,
n = 0
d = 100
for i in range(10**6):
n += i
if n >= d:
n %= d
is slower than
n = (n + i) % d
This counter to lower level languages, where dividing by a variable is costly, and the CPU can predict the pipeline to be false most of the time in the conditional and thus skip it.
- viraptor 8y ago> can predict the pipeline to be false most of the time in the conditional and thus skip it. I think there's a bug in the code then. It will be skipped a few times, but for i between 100 and 10^6, the condition is guaranteed true every time.