Delphi Optimize IndexOf Function

Question

Could someone help me speed up my Delphi function To find a value in a byte array without using binary search.

I call this function thousands of times, is it possible to optimize it with assembly?

Thank you so much.

function IndexOf(const List: TArray< Byte >; const Value: byte): integer;
var
  I: integer;
begin
  for I := Low( List ) to High( List ) do begin
   if List[ I ] = Value then
    Exit ( I );
  end;
  Result := -1;
end;

The length of the array is about 15 items.

Answer 1

If your arrays are long, you can use the x86 built in string scan REP SCAS.
It is coded in microcode and has a moderate start-up time, but it is heavily optimized in the CPU and runs fast given long enough data structures (>= 100 bytes).
In fact on a modern CPU it frequently outperforms very clever RISC code.

If your arrays are short, then no amount of optimization of this routine will help, because then your problem is in code not shown in the question, so there is no answer I can give you.

See: http://docwiki.embarcadero.com/RADStudio/Tokyo/en/Internal_Data_Formats_(Delphi)

function IndexOf({$ifndef RunInSeperateThread} const {$endif} List: TArray<byte>; const Value: byte): integer;
//Lock the array if you run this in a separate thread.
{$ifdef CPUX64}
asm
  //RCX = List
  //DL = byte.
  mov r8,[rcx-8]        //3 - get the length ASAP.
  push rdi              //0 - hidden in mov r,m
  mov eax,edx           //0 - rename
  mov rdi,rcx           //0 - rename
  mov rcx,r8            //0 - rename
  mov rdx,r8            //0 - remember the length
  //8 cycles setup
  repne scasb           //2n - repeat until byte found.
  pop rdi               //1 
  neg rcx               //0
  lea rax,[rdx+rcx]     //1 result = length - bytes left.
end;
{$ENDIF}
{$ifdef CPUX86}
asm
  //EAX = List
  //DL = byte.
  push edi
  mov edi,eax
  mov ecx,[eax-4]        //get the length
  mov eax,edx
  mov edx,ecx            //remember the length
  repne scasb            //repeat until byte found.
  pop edi
  neg ecx
  lea eax,[edx+ecx]      //result = length - bytes left.
end;     

Timings
On my laptop using an array of 1KB with the target byte at the end this gives the following timings (lowest time using a 100.0000 runs)

Code                           | CPU cycles
                               | Len=1024 | Len=16      
-------------------------------+----------+---------
Your code optimizations off    | 5775     | 146
Your code optimizations on     | 4540     |  93
X86 my code                    | 2726     |  60
X64 my code                    | 2733     |  69

The speed-up is OK (ish), but hardly worth the effort.

If your array's are short, then this code will not help you and you'll have to resort to better other options to optimize your code.

Speed up possible when using binary search
Binary search is a O(log n) operation, vs O(n) for naive search.
Using the same array this will find your data in log2(1024) * CPU cycles per search = 10 * 20 +/- 200 cycles. A 10+ times speed up over my optimized code.

Answer 2

Well, let's think. At first, please edit this line:

For I := Low( List ) to High( List ) do

(you forgot 'do' at the end). When we compile it without optimization, here is the assembly code for this loop:

Unit1.pas.29: If List [I] = Value then
005C5E7A 8B45FC           mov eax,[ebp-$04]
005C5E7D 8B55F0           mov edx,[ebp-$10]
005C5E80 8A0410           mov al,[eax+edx]
005C5E83 3A45FB           cmp al,[ebp-$05]
005C5E86 7508             jnz $005c5e90
Unit1.pas.30: Exit (I);
005C5E88 8B45F0           mov eax,[ebp-$10]
005C5E8B 8945F4           mov [ebp-$0c],eax
005C5E8E EB0F             jmp $005c5e9f
005C5E90 FF45F0           inc dword ptr [ebp-$10]
Unit1.pas.28: For I := Low (List) to High (List) do
005C5E93 FF4DEC           dec dword ptr [ebp-$14]
005C5E96 75E2             jnz $005c5e7a

This code is far from being optimal: local variable i is really local variable, that is: it is stored in RAM, in stack (you can see it by [ebp-$10] adresses, ebp is stack pointer).

So at each new iteration we see how we load address of array into eax register (mov eax, [ebp-$04]), then we load i from stack into edx register (mov edx, [ebp-$10]), then we at least load List[i] into al register which is lower byte of eax (mov al, [eax+edx]) after which compare it with argument 'Value' taken again from memory, not from register!

This implementation is extremely slow.

But let's turn optimization on at last! It's done in Project options -> compiling -> code generation. Let's look at new code:

Unit1.pas.29: If List [I] = Value then
005C5E5A 3A1408           cmp dl,[eax+ecx]
005C5E5D 7504             jnz $005c5e63
Unit1.pas.30: Exit (I);
005C5E5F 8BC1             mov eax,ecx
005C5E61 5E               pop esi
005C5E62 C3               ret 
005C5E63 41               inc ecx
Unit1.pas.28: For I := Low (List) to High (List) do
005C5E64 4E               dec esi
005C5E65 75F3             jnz $005c5e5a

now there are just 4 lines of code which gets repeated over and over.

Value is stored inside dl register (lower byte of edx register), address of 0-th element of array is stored in eax register, i is stored in ecx register.

So the line 'if List[i] = Value' converts into just 1 assembly line:

005C5E5A 3A1408           cmp dl,[eax+ecx]

the next line is conditional jump, 3 lines after that are executed just once or never (it's if condition is true), and at last there is increment of i, decrement of loop variable (it's easier to compare it with zero then with anything else)

So, there is little we can do which Delphi compiler with optimizer didn't!

If it's permitted by your program, you can try to reverse direction of search, from last element to first:

For I := High( List ) downto Low( List ) do

this way compiler will be happy to compare i with zero to indicate that we checked everything (this operation is free: when we decrement i and got zero, CPU zero flag turns on!)

But in such implementation behaviour may be different: if you have several entries = Value, you'll get not the first one, but the last one!

Another very easy thing is to declare this IndexOf function as inline: this way you'll probably have no function call here: this code will be inserted at each place where you call it. Function calls are rather slow things.

There are also some crazy methods described in Knuth how to search in simple array as fast as possible, he introduces 'dummy' last element of array which equals your 'Value', that way you don't have to check boundaries (it will alway find something before going out of range), so there is just 1 condition inside loop instead of 2. Another method is 'unrolling' of loop: you write down 2 or 3 or more iterations inside a loop, so there are less jumps per each check, but this has even more downsides: it will be beneficial only for rather large arrays while may make it even slower for arrays with 1 or 2 elements.

As others said: the biggest improvement would be to understand what kind of data you store: does it change frequently or stays the same for long time, do you look for random elements or there are some 'leaders' which gets the most attention. Must these elements be in the same order as you put them or it's allowed to rearrange them as you wish? Then you can choose data structure accordingly. If you look for some 1 or 2 same entries all the time and they can be rearranged, a simple 'Move-to-front' method would be great: you don't just return index but first move element to first place, so it will be found very quickly the next time.