www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - Why infinite loops are faster than finite loops?

reply tastyminerals <tastyminerals gmail.com> writes:
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? Wouldn't the compiler optimize it
better than the infinite one because it knows the number of iterations the for
loop needs?
Jun 20 2020
next sibling parent Stanislav Blinov <stanislav.blinov gmail.com> writes:
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? Wouldn't the compiler optimize it
better than the infinite one because it knows the number of iterations the for
loop needs?
He explains it there and then. When the number of iterations is *small*, overhead of each iteration can be significant. He's not talking about known *number* of iterations, but known exit conditions. If you put those exit conditions in the loop's test, you have to go through till the end and then test them, while if you put the tests in the loop body you can bail early and skip some unnecessary operations. Don't take it too literally. As he himself says "always use infinite loops, except in most cases" :) He's simply emphasizing the importance of looking at code critically and not taking things for granted.
Jun 20 2020
prev sibling next sibling parent =?UTF-8?B?0JLQuNGC0LDQu9C40Lkg0KTQsNC0?= =?UTF-8?B?0LXQtdCy?= writes:
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? Wouldn't the compiler optimize it
better than the infinite one because it knows the number of iterations the for
loop needs?
I think the Answer depended from the Task. I think Alexandrescu is joking. :) "Always* Use Infinite Loops. (*Except in most cases)" :) For code: di = "String"; needle = "A"; ascan = di.ptr; for( int cx = di.length; cx != 0; cx--, scan++ ) { if ( *scan == neelde ) goto found; } return; found: // Found! in best case generated instructions will be like this: CLD ;Scan string in forward direction MOV AL,'A' ;Scan for 'A' LEA DI, STRING ;Address to start scanning at MOV CX,100 ;Scanning 100 bytes REPNE SCASB ; ...and scan it JE found ; JMP exit ; found: DEC DI ;Back up DI to point to the 'A' ...var CX translated to register CX. ...pointer translated to register DI. ...needle translated to register AX. All in registers! What asm-code generaged for C-code showed by Alexandrescu ?
Jun 21 2020
prev sibling parent Johan <j j.nl> writes:
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
Jun 21 2020