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?
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?
NecroSOFT - End of line -
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.
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:
would compile to code equivalent to a series of IF-statements:Code:case i of 1 : ... ; 500 : ... ; 1000..2000 :... ; end;
So higher case hit values gets executed a bit slower than lower values because the CPU process more branches.Code:if i=1 then else if i=500 then else if ((i>=1000) and (i<=2000)) then
However a "tight" list of values such as this:
generates a jump into a look-up table (a constant array of addresses) so every value takes the same time to execute.Code:case i of 0 : 1 : 2 : 3 : 4 : etc
OK thanks, I need the second , case 1: 2: 3: etc of
(I'm gonna use it for a scripting engine, to execute instructions)
NecroSOFT - End of line -
You should use a procedure jump table array for this :-)Originally Posted by NecroDOME
[pascal]
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;
[/pascal]
where OpcodeJumpTab is defined by
[pascal]
OpcodeJumpTab:array[0..LastOpcodeIndex] of procedure of object;
[/pascal]
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.Originally Posted by VilleK
Overall it does a good job I think.
however when I sort of have my "compiler" working I will make a little speed test...
NecroSOFT - End of line -
That is exactly what I did when I was working on a scripting language and it worked great!Originally Posted by BeRo
cheers,
Paul.
Games:
Seafox
Pages:
Syntax Error Software
itch.io page
Online Chess
http://gameknot.com/#paul_nicholls
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.
- Jeremy
http://www.eonclash.com/
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.
Bookmarks