[SOLVED] "for" loop optimization question

[440bx]

Hello,

I believe that sometimes the compiler chooses to invert the sequence in which "items" are visited as an optimization. 

I have a simple case where there is an unsorted array of 16 numeric elements, used elements are non-zero, unused elements are zero (the value zero is used as a sentinel).  This means that in a search from low(array) to high(array), the search can be terminated when a zero is found (since the appearance of a zero indicates there are no more used elements).

I'd like to know if doing a search such as (pseudocode)

Code: Pascal  [Select][+][-]

1. for i := low(array) to high(array) do
2. begin
3.   if element[i] = 0 then break;  { no more used elements }
4.  
5.   < use the value of element[i] to test additional conditions >
6. end;
7.  

may cause an inverted search (high to low instead of low to high.)

My concern is that if the "for" inverts the sequence, it is likely to find a zero element before it finds the non-zero ones causing it to end without applying the necessary conditions to the non-zero elements.

Thank you for your help.

[jamie]

There should be no inverting if the presents of a GOTO, BREAK is in place that breaks the loop.

In your case, you should be using the DOWNTO.

Code: Pascal  [Select][+][-]

1. For i:= high(Ar) downto low(ar) do if ar[i]=0 Then break;
2.  

 The compiler is supposed to preserve the index in the case of break, goto etc, without that al bets are off.
  This works well with Delphi but recently I noticed that in fpc within a event handler for GUI it didn't seem to work so I reverted to something else. It could of been something else but normally it works.

jamie

 


 

[TBMan]

Hello,

I believe that sometimes the compiler chooses to invert the sequence in which "items" are visited as an optimization. 

I have a simple case where there is an unsorted array of 16 numeric elements, used elements are non-zero, unused elements are zero (the value zero is used as a sentinel).  This means that in a search from low(array) to high(array), the search can be terminated when a zero is found (since the appearance of a zero indicates there are no more used elements).

If the array is unsorted then your loop is meaningless.  If you sort the array low to high then the first item is your result.

[440bx]

If the array is unsorted then your loop is meaningless.  If you sort the array low to high then the first item is your result.

There is nothing meaningless about searching an unsorted list.  It's an extremely common action.

In addition to that, when the number of elements is small, such as 16 elements, it is faster to just scan the unsorted array than sort it every time a new element is added (not all elements are added to the array at once.)


@Jamie,

I cannot use downto because elements are added from the beginning towards the end (i.e, the normal thing to do.)  Starting at the end would find the last sentinel causing the loop to terminate when inspecting the first element (which in this case is the last sentinel.)


Anyway, none of that stuff answers the question... should I be concerned that FPC may invert the loop sequence, that's what I really want to know.

If the compiler _never_ inverts the sequence then the loop from low to high is perfectly fine.

[Thaddy]

If a loop contains conditions related to the index the loop will not be reversed.
Otherwise the compiler may - depending on optimization level - choose to invert the loop if this leads to optimized code.
I think that optimization is not implemented yet. (As opposed to GNU C(++) or msvc )
So in your case it is safe anyway.

[Zvoni]

Convert the For-Loop to a Repeat-Loop?
In the end they boil down to pretty much the same/similiar Assembler-Instructions
https://stackoverflow.com/questions/28665528/while-do-while-for-loops-in-assembly-language-emu8086

Or encase the For-Loop in a {$OPTIMIZATION OFF} Directive

[440bx]

@Zvoni,

All reasonable suggestions but, I'd like to know if that is a real potential problem or can the compiler be trusted to generated code that will work without having to "massage" the code. 

[Zvoni]

@Zvoni,

All reasonable suggestions but, I'd like to know if that is a real potential problem or can the compiler be trusted to generated code that will work without having to "massage" the code.

Ahh... OK, got you.
Well, not my expertise

[Martin_fr]

Afaik:

Yes the complier can optimize a for loop, in a way that changes the (internal) loopcounter. E.g.
   for i :=  5 to 9
can (in very specific cases) become
   for i := 4 downto 0

But only if there is no access to the loop variable. That is, if the above loop simple repeatedly executes something that has no dependency on "i".

If you access (read or write) "i" inside the loop, then that should not happen.

The one thing I don't know is, if it will see access to "i" if that happens in a nested procedure, which is called inside the loop.

[440bx]

@Martin,

Thank you.  That's what I needed to know and since the loops I'm using do reference the index variable then I can rely on the sequence occurring as declared (which in this case is important.)

What created the concern was a recent question about having to turn off optimizations to get the code to work right.  I remembered seeing the compiler  inverting the sequence in a "for" loop but, I didn't know the conditions that triggered that optimization.  I wondered if that was one the cases when it was necessary to turn optimizations off.  Now, I know when (and why) the compiler optimizes the code, your answer made it clear and, I don't have to worry about it. 

Thanks again.