Author: Matt Taylor
Date: 23:40:43 02/28/03
Go up one level in this thread
On February 28, 2003 at 23:28:20, Robert Hyatt wrote: >On February 28, 2003 at 19:15:24, Gareth McCaughan wrote: > >>On February 28, 2003 at 13:58:48, Vincent Diepeveen wrote: >> >>> less instructions within the 'invariant' (i fear it might be a dutch word of a >>> dutch professor who theoretically proved software and 'invariant' is describing >>> all instructions which are getting executed within a loop) is excellent of >>> course. Not doing the loading of the pointer within the invariant is trivially >>> faster for most loops. >> >>"invariant" is a perfectly good English word, and loops have invariants, >>and there's at least one (recently deceased, alas) Dutch professor who >>used them a lot. But they aren't anything like what you seem to mean here. >> >>A loop invariant is a statement that is always true at a particular >>point in the execution of a loop. They're very important when reasoning >>about programs. So, for instance, in the following routine > >This isn't the classic definition of "loop invariant" as used in compiler >texts. There "loop invariant" means "an expression whose result does not >change _inside_ the loop." As a result, the computations for the invariant >expression are moved out of the loop to avoid doing the same calculations >over and over. GCC can even treat a memory reference as a "loop invariant" >since a memory reference is so costly. If you reference a memory address inside >a loop, but the value doesn't change inside the loop, the memory load is moved >out of the loop to avoid the wasted memory cycles. No, he is giving the definition of a loop invariant as talked about by Gries and Dijkstra. In compiler terminology, the loop invariant is as you say. One is a theoretical concept, the other is a practical concept. I attended a lecture last Dec. given by Gries on the topic of loop invariants. In other words, he was talking about how to "compute" a loop given the loop invariant that described it. It was very methodical and mathematical, and it was very unlike programming as I (and presumably many others) have learned it. Programming is art, not science or mathematics. If it were otherwise, how could it be so buggy? :-) -Matt
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.