Case (Speed) of

[NecroDOME]

I was wondering how fast case ... of would be with 255 case entry's... How does the compiler handle this type? how does the CPU handle it?

[WILL]

Wow, great question. I might seek this one out myself if none of our FPC friends come to answer it.

It's likely to come down to how it's compiled into assembly code though. FPC has several optimizations that it uses, but they are not the same as what the dcc32.exe compiler in Delphi would do. So I guess you could say that the answer would be different from compiler to compiler.

I can't go more in depth than that unfortunately so hopefully someone with experience in either the FreePascal or Delphi compiler can give us some more insight.

[VilleK]

I'm guessing here, but usually for compilers they have different set of rules for generating code for case-statements.

Highly spread out values such as this:

case i of
1 : ... ;
500 : ... ;
1000..2000 :... ;
end;

would compile to code equivalent to a series of IF-statements:

if i=1 then
else if i=500 then
else if &#40;&#40;i>=1000&#41; and &#40;i<=2000&#41;&#41; then


So higher case hit values gets executed a bit slower than lower values because the CPU process more branches.

However a "tight" list of values such as this:

case i of
0 &#58;
1 &#58;
2 &#58;
3 &#58;
4 &#58;
etc

generates a jump into a look-up table (a constant array of addresses) so every value takes the same time to execute.

[NecroDOME]

OK thanks, I need the second , case 1: 2: 3: etc of :P

(I'm gonna use it for a scripting engine, to execute instructions)

[BeRo]

OK thanks, I need the second , case 1: 2: 3: etc of :P

(I'm gonna use it for a scripting engine, to execute instructions)

You should use a procedure jump table array for this :-)


constructor TMyVM.Create;
begin
inherited Create;
OpcodeJumpTab[0]:=Opcode0;
OpcodeJumpTab[1]:=Opcode1;
// ...
end;

procedure TMyVM.Opcode0;
begin
// ...
end;

procedure TMyVM.Opcode1;
begin
// ...
end;

procedure TMyVM.ExecuteOpcode(Opcode:integer);
begin
OpcodeJumpTab[Opcode]();
end;


where OpcodeJumpTab is defined by


OpcodeJumpTab:array[0..LastOpcodeIndex] of procedure of object;

[Mirage]

Highly spread out values such as this:

case i of
1 &#58; ... ;
500 &#58; ... ;
1000..2000 &#58;... ;
end;

would compile to code equivalent to a series of IF-statements:

if i=1 then
else if i=500 then
else if &#40;&#40;i>=1000&#41; and &#40;i<=2000&#41;&#41; then


So higher case hit values gets executed a bit slower than lower values because the CPU process more branches.

However a "tight" list of values such as this:

case i of
0 &#58;
1 &#58;
2 &#58;
3 &#58;
4 &#58;
etc

generates a jump into a look-up table (a constant array of addresses) so every value takes the same time to execute.

Actually, the Delphi 7 compiler use look-up tables even for "tight" parts of case list as well as a kind of binary search for optimizing more spreaded values.
Overall it does a good job I think.

[NecroDOME]

however when I sort of have my "compiler" working I will make a little speed test...

[paul_nicholls]

OK thanks, I need the second , case 1: 2: 3: etc of :P

(I'm gonna use it for a scripting engine, to execute instructions)

You should use a procedure jump table array for this :-)


constructor TMyVM.Create;
begin
inherited Create;
OpcodeJumpTab[0]:=Opcode0;
OpcodeJumpTab[1]:=Opcode1;
// ...
end;

procedure TMyVM.Opcode0;
begin
// ...
end;

procedure TMyVM.Opcode1;
begin
// ...
end;

procedure TMyVM.ExecuteOpcode(Opcode:integer);
begin
OpcodeJumpTab[Opcode]();
end;


where OpcodeJumpTab is defined by


OpcodeJumpTab:array[0..LastOpcodeIndex] of procedure of object;


That is exactly what I did when I was working on a scripting language and it worked great! :)
cheers,
Paul.

[jdarling]

Actually, in Delphi and C/C++ switch or case statements are compiled down to a pointer list. So instead of if statements the compiler does a test to see if the pointer index is set and valid, if so then it jumps to the handler with a return at the end. If not then it bypasses and goes to the fallout point.

I don't know if this is how FPC handles it or not, never actually took the time to look at the generated code :). But, I would guess that it would be close.

[dmantione]

FPC has several ways to handle a case statement. It generates exactly the code you want, without asking :) To go in more details, the exact method depends a bit on the situation, but most of the time you will see FPC generating a decrement list, i.e.:

dec eax
jz @case_label_1
dec eax
jz @case_label_2
dec eax
jz @case_label_3
dec eax
jz @case_label_4
dec eax
jz @case_label_5
dec eax
jz @case_label_6

This is a quite fast solution. If the amount of case labels gets large, FPC switches to a jump table. There are more algorithms are available, they get used in more specific cases.

[WILL]

So in short the case statement is WAY faster than a bunch of if statements. :)

[NecroDOME]

cool :)

[marmin]

If you have 255 unique symbols/whatever inside a case statement, (if that's what you mean) i'd make some simple optimalization beforehand to eliminate the lot you don't need, i'd never make a case statement with more than let's say.. 25 entries. Some might say it becomes unreadable then! :D So not a question of speed but of nice looking code :lol:

[dmantione]

It is often better not to hand-optimize case statements. Free Pascal definately knows how to handle a case statement with 255 entries efficiently.