On Saturday, 20 June 2020 at 21:11:57 UTC, tastyminerals wrote:
I am not sure that this is a question about D or a more general
one. I have watched this nice presentation "Speed Is Found In
The Minds of People" by Andrei:
https://www.youtube.com/watch?v=FJJTYQYB1JQ&feature=youtu.be?t=2596 and on 43:20 he says that "push_heap" is slow because of structured loops and finite for (throughout the presentation Andrei shows algorithm examples with infinite loops). I wonder why is that?
Is it because the finite loop needs to keep track of the number
of iterations it performs?
Yes, indeed. Simple way of looking at it is that for the
'infinite' loop, each loop checks for N exit conditions, whereas
the 'finite' loop checks for N+1 conditions. The extra check (and
calculating the extra condition) of the 'finite' loop is what can
lead to noticable performance drop. For example in the case of
linear search, the work of inserting a 'sentinel' at the end and
some extra logic can outweigh the work of 'length' check upon
each loop iteration. It is a highly predictable branch though, so
perf cost may be very small depending on the architecture. If you
like this kind of stuff you should play with code and llvm-mca.
See https://youtu.be/Czr5dBfs72U?t=2352 for an introduction to
it. llvm-mca is available on https://d.godbolt.org.
Wouldn't the compiler optimize it better than the infinite one
because it knows the number of iterations the for loop needs?
Both "infinite" and "finite" loop are, in fact, finite. For both
cases, the number of iterations often depends on runtime
parameters and is thus unknown to the compile-time optimizer.
Even if the number of iterations is known exactly, there aren't
really any optimizations one can do that would help performance
(except when the number of iterations is really small, like < 10
or so).
-Johan
