<HTML>
<style> BODY { font-family:Arial, Helvetica, sans-serif;font-size:12px; }</style>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.<br>
<br>
Using my code sample to demonstrate:<br>
<br>
****<br>
<br>
type<br>
TBinList = record<br>
Key: Integer;<br>
Data: CodePointer;<br>
end;<br>
PBinList = ^TBinList;<br>
<br>
function SearchBinList(List: PBinList; ListSize: Cardinal; Key: Integer; out Data: CodePointer): Boolean;<br>
var<br>
LoIndex, MidIndex, HiIndex: Cardinal;<br>
begin<br>
LoIndex := 0;<br>
HiIndex := ListSize;<br>
<br>
{ Search binary list }<br>
while LoIndex + 1 < HiIndex do<br>
begin<br>
MidIndex := (LoIndex + HiIndex) shr 1;<br>
<br>
if List[MidIndex].Key > Key then<br>
HiIndex := MidIndex<br>
else<br>
LoIndex := MidIndex;<br>
<br>
end;<br>
<br>
Data := List[LoIndex].Data;<br>
Result := (List[LoIndex].Key = Key);<br>
end;<br>
<br>
****<br>
<br>
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.<br>
<br>
The generated assembly (-O3) for the while loop is as follows:<br>
<br>
****<br>
xorl %r10d,%r10d<br>
jmp .Lj6<br>
.balign 8,0x90<br>
.Lj5:<br>
movl %r10d,%eax<br>
movl %edx,%r11d<br>
addq %r11,%rax<br>
shrq $1,%rax<br>
movl %eax,%ebx<br>
andl $4294967295,%eax<br>
shlq $4,%rax<br>
cmpl (%rcx,%rax),%r8d<br>
cmovll %ebx,%edx<br>
cmovnll %ebx,%r10d<br>
.Lj6:<br>
movl %r10d,%eax<br>
leaq 1(%rax),%r11<br>
movl %edx,%eax<br>
cmpq %rax,%r11<br>
jl .Lj5<br>
...<br>
****<br>
<br>
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:<br>
<br>
xorl %r10d,%r10d // <-- The line that appears before "jmp .Lj6"<br>
movl $1,%r11d // <-- Optimised from "movl %r10d,%eax", "leaq 1(%rax),%r11", since %r10d, and hence %rax, are known to be zero<br>
movl %edx,%eax<br>
cmpq %rax,%r11<br>
jge .Lj7 // <-- Or whatever label is given for a position right after "jl .Lj5"<br>
.balign 8,0x90<br>
.Lj5:<br>
...<br>
<br>
In this case, no jumps occur upon entering the while loop when the condition is true.<br>
<br>
(Ignore the fact that there could be a lot of other potential optimizations if the constant switching between 32-bit and 64-bit registers can be sorted)<br>
<br>
Gareth aka. Kit<br>
</HTML>