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 // _______________________________________________
fpc-devel maillist - fpc-devel@lists.freepascal.org
http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-devel
