BorlandTalk.com

Gary · Guest

I created a BASM function that searches through an array of integers for
a value. To my surprise, it benchmarks at about 10 times slower than
the equivalent PAS version. Why is it so slow?

{----------------------------------------------------------
Searches an array of integers (or pointers) for a value.
Returns the position of the value, or -1 if not found.

On entry, EAX will contain P, EDX will contain Value,
and ECX will contain Count.
-----------------------------------------------------------}
function ScanArray(const P : Pointer;
const Value : Integer;
const Count : Integer) : Integer;
asm
jcxz @@Done // check for Count=0

// The following MUST be done in this order,
// since the parameters are actually in registers.

push EDI // must preserve EDI
mov EDI, P
mov EAX, Value
mov EDX, Count // remember the count for later

repne scasd // search!
jnz @@NotFound // success?

mov EAX, EDX // get the original count
sub EAX, ECX // subtract the end count
dec EAX // subtract 1 more for origin 0

pop EDI
ret

@@NotFound:
mov EAX, -1 // not found
pop EDI

@@Done:
end;

{ Pascal version }

function ScanArrayPAS(const P : array of integer;
const Value : Integer;
const Count : Integer) : Integer;
var
i : integer;
begin
Result := -1;

for i := Count - 1 downto 0 do
if P[i] = Value then
begin
Result := i;
break;
end;

end;

Rudy Velthuis [TeamB] · Guest

At 00:17:55, 14.05.2005, Gary wrote:

Martin James · Guest

Dunno. REPNZ SCASD should be plenty fast.

Why not look at the assembly in the Delphi CPU window, find out & tell us?

Rgds,
Martin :)

Gary · Guest

The code produced by the PAS function is big and ugly. I can't imagine
why it's faster. Is there a way to copy it to the clipboard from the
CPU window?

Rudy Velthuis [TeamB] wrote:

Rudy Velthuis [TeamB] · Guest

At 00:40:52, 14.05.2005, Gary wrote:

Rudy Velthuis [TeamB] · Guest

At 00:40:52, 14.05.2005, Gary wrote:

Gary · Guest

Rudy Velthuis [TeamB] wrote:

Pierre le Riche · Guest

Hi Gary,

Pierre le Riche · Guest

Hi Again,

You can make it even shorter if you change the order of parameters and
change the definition of the return value from "-1 if not found" to
"negative if the value is not found". The return value will be -1 for all 0
or positive values of ACount, but will be (ACount - 1) if ACount was
negative on entry. Here goes:

{Scans a list of integers starting at address AFirstItem for ASearchValue,
returning the index of item if it was found or < 0 if not}
function ScanArray(ACount, ASearchValue: Integer; AFirstItem: Pointer):
Integer;
asm
{On entry: eax = ACount, edx = ASearchValue, ecx = @AFirstItem}
@CompareLoop:
sub eax, 1
js @Done
cmp [ecx + eax * 4], edx
jne @CompareLoop
@Done:
end;

Regards,
Pierre

Robert Houdart · Guest

Gary · Guest

Wonderful, thank you!

I found that my original tests were not using truly random samples, and
since the ASM code searched forward through the array while the PAS
version searched backward through the array, that accounted for the huge
difference. When my samples were more random, the timings were closer,
but the PAS version was still faster. Your version is the fastest.

I wasn't aware that the string instructions were so slow.

Thanks!

....Gary

Gary · Guest

I'm finding that I have to check the count before calling the ASM
routine because passing the address of the first element generates an
exception if the array is empty. For example, the following will
generate an exception if MyArray has no elements:

Result := ScanArray(Length(MyArray), Value, @MyArray[0]);

So I find that I have to do this, even though ScanArray would safely
handle it:

if Length(MyArray) > 0 then
Result := ScanArray(Length(MyArray), Value, @MyArray[0])
else
Result := -1;

Is there a simpler way to accomplish this? Do I have to turn off range
checking?

Lee_Nover · Guest

Result := ScanArray(Length(MyArray), Value, @MyArray);
should work as well

Gary · Guest

Does that work with dynamic arrays, as well?

Lee_Nover wrote:

Pierre le Riche · Guest

Hi Gary,