I've come across an interesting situation with the compiler when it comes to while loops.  It's not necessary erroneous, but I wonder if it incurs a speed penalty.

Using my code sample to demonstrate:

****

 type
   TBinList = record
     Key: Integer;
     Data: CodePointer;
   end;
   PBinList = ^TBinList;
 function SearchBinList(List: PBinList; ListSize: Cardinal; Key: Integer;
out Data: CodePointer): Boolean;
 var
   LoIndex, MidIndex, HiIndex: Cardinal;
 begin
   LoIndex := 0;
   HiIndex := ListSize;
   { Search binary list }
   while LoIndex + 1 < HiIndex do
     begin
       MidIndex := (LoIndex + HiIndex) shr 1;
       if List[MidIndex].Key > Key then
         HiIndex := MidIndex
       else
         LoIndex := MidIndex;
     end;
   Data := List[LoIndex].Data;
   Result := (List[LoIndex].Key = Key);
 end;

****

This is a binary search algorithm that I've streamlined as much as I can for speed (e.g. there's no sanity check for ListSize being zero, and it doesn't immediately exit the loop if it finds a match.

The generated assembly (-O3) for the while loop is as follows:

****
    xorl    %r10d,%r10d
    jmp    .Lj6
    .balign 8,0x90
.Lj5:
    movl    %r10d,%eax
    movl    %edx,%r11d
    addq    %r11,%rax
    shrq    $1,%rax
    movl    %eax,%ebx
    andl    $4294967295,%eax
    shlq    $4,%rax
    cmpl    (%rcx,%rax),%r8d
    cmovll    %ebx,%edx
    cmovnll    %ebx,%r10d
.Lj6:
    movl    %r10d,%eax
    leaq    1(%rax),%r11
    movl    %edx,%eax
    cmpq    %rax,%r11
    jl    .Lj5
    ...
****

In this case, the ".balign" hint adds 2 bytes to pad the loop.  However, my question is this... why does it immediately jump to the end of the loop to check the condition (which is very likely to be true on the first iteration), only to jump to the beginning again? Granted, in this case the condition is relatively simple, but why not simply check the condition where the "jmp" instruction is, and jumping to the line after the "jl" instruction if it's false? For example:

    xorl    %r10d,%r10d //

Good call on using "repeat...until" in my own code, thanks!

I wasn't clear, but my intention was also keeping the conditional check at the end of the loop, but duplicating it at the start with the condition inverted.  In other words, having both these example code segments:

****
    xorl    %r10d,%r10d
    movl    $1,%r11d
    movl    %edx,%eax
    cmpq    %rax,%r11
    jge  .Lj7
    .balign 8,0x90
.Lj5:
    ...
.Lj6: //

(Apologies if anyone has received multiple copies of this reply - I was having trouble with the e-mail client and the message formatting)

----

Good call on using "repeat...until" in my own code, thanks!

I wasn't clear, but my intention was also keeping the conditional check at the end of the loop, but duplicating it at the start with the condition inverted.  In other words, having both these example code segments:

****
    xorl    %r10d,%r10d
    movl    $1,%r11d
    movl    %edx,%eax
    cmpq    %rax,%r11
    jge  .Lj7
    .balign 8,0x90
.Lj5:
    ...
.Lj6: //

J. Gareth Moreton schrieb am Mo., 28. Mai 2018,
02:55:

The following is only guess work of mine: I think that the idea is to avoid a jump back once the condition is false. Also it might be too keep the difference between "while ... do ..." and "repeat ... until ..." minimal (namely only that initial jump).

Speaking of which: if you assume that the list isn't empty and thus the loop is entered at least once why don't you use a repeat-loop instead of a while-loop?

Regards,
Sven

That seems fair. Thank you for your
answer. I'm still learning about the
nuances of branch prediction and the like.

On Tue 29/05/18 21:27 , Florian Klämpfl
sent:

Am 28.05.2018 um 01:55 schrieb J. Gareth

Moreton:

question is this... why

> does it immediately jump to the end of

the loop

to check the condition (which is very

likely to be

> true on the first iteration), only to

jump to

heuristics when the condition should be

checked twice - two conditional jumps waste an extra

branch prediction table entry

little overhead of an extra

unconditional jump, we decided to use the currently used code generation

strategy.

J. Gareth Moreton wrote

In this case, the ".balign" hint adds 2 bytes to pad the loop.  However, my question is this... why does it immediately jump to the end of the loop to check the condition (which is very likely to be true on the first iteration), only to jump to the beginning again?

Several reasons:
- it is not that easy to find a heuristics when the condition should be checked twice
- two conditional jumps waste an extra branch prediction table entry
- bigger code, higher cache usage

Weigthing these reasons against the little overhead of an extra unconditional jump, we decided to use the currently used code generation strategy.

J. Gareth Moreton wrote

That seems fair. Thank you for your answer. I'm still learning about the nuances of branch prediction and the like.

Do be honest, I never investigated this particular case in detail, but years I ago we just decided based on the reasons I mentioned.