Why is CharInSet faster than Case statement?

Why is CharInSet faster than Case statement?

I'm perplexed. At CodeRage today, Marco Cantu said that CharInSet was slow and I should try a Case statement instead. I did so in my parser and then checked with AQTime what the speedup was. I found the Case statement to be much slower.

4,894,539 executions of:

while not CharInSet (P^, [' ', #10,#13, #0]) do inc(P);

was timed at 0.25 seconds.

But the same number of executions of:

while True do
case P^ of
' ', #10, #13, #0: break;
else inc(P);
end;

takes .16 seconds for the "while True", .80 seconds for the first case, and .13 seconds for the else case, totaling 1.09 seconds, or over 4 times as long.

The assembler code for the CharInSet statement is:

add edi,$02
mov edx,$0064b290
movzx eax,[edi]
call CharInSet
test a1,a1
jz $00649f18 (back to the add statement)

whereas the case logic is simply this:

movzx eax,[edi]
sub ax,$01
jb $00649ef0
sub ax,$09
jz $00649ef0
sub ax,$03
jz $00649ef0
add edi,$02
jmp $00649ed6 (back to the movzx statement)

The case logic looks to me to be using very efficient assembler, whereas the CharInSet statement actually has to make a call to the CharInSet function, which is in SysUtils and is also simple, being:

function CharInSet(C: AnsiChar; const CharSet: TSysCharSet): Boolean;
begin
Result := C in CharSet;
end;

I think the only reason why this is done is because P^ in [' ', #10, #13, #0] is no longer allowed in Delphi 2009 so the call does the conversion of types to allow it.

None-the-less I am very surprised by this and still don't trust my result.

Is AQTime measuring something wrong, am I missing something in this comparison, or is CharInSet truly an efficient function worth using?

---

Conclusion:

I think you got it, Barry. Thank you for taking the time and doing the detailed example. I tested your code on my machine and got .171, .066 and .052 seconds (I guess my desktop is a bit faster than your laptop).

Testing that code in AQTime, it gives: 0.79, 1.57 and 1.46 seconds for the three tests. There you can see the large overhead from the instrumentation. But what really surprises me is that this overhead changes the apparent "best" result to be the CharInSet function which is actually the worst.

So Marcu is correct and CharInSet is slower. But you've inadvertently (or maybe on purpose) given me a better way by pulling out what CharInSet is doing with the AnsiChar(P^) in Set method. Other than the minor speed advantage over the case method, it is also less code and more understandable than using the cases.

You've also made me aware of the possibility of incorrect optimization using AQTime (and other instrumenting profilers). Knowing this will help my decision re Profiler and Memory Analysis Tools for Delphi and it also is another answer to my question How Does AQTime Do It?. Of course, AQTime doesn't change the code when it instruments, so it must use some other magic to do it.

So the answer is that AQTime is showing results that lead to the incorrect conclusion.

---

Followup: I left this question with the "accusation" that AQTime results may be misleading. But to be fair, I should direct you to read through this question: Is There A Fast GetToken Routine For Delphi? which started off thinking AQTime gave misleading results, and concludes that it does not.

Answer by Barry Kelly for Why is CharInSet faster than Case statement?

AQTime is an instrumenting profiler. Instrumenting profilers often aren't suitable for measuring code time, particularly in microbenchmarks like yours, because the cost of the instrumentation often outweighs the cost of the thing being measured. Instrumenting profilers, on the other hand, excel at profiling memory and other resource usage.

Sampling profilers, which periodically check the location of the CPU, are usually better for measuring code time.

In any case, here's another microbenchmark which indeed shows that a case statement is faster than CharInSet. However, note that the set check can still be used with a typecast to eliminate the truncation warning (actually this is the only reason that CharInSet exists):

{$apptype console}    uses Windows, SysUtils;    const    SampleString = 'foo bar baz blah de;blah de blah.';    procedure P1;  var    cp: PChar;  begin    cp := PChar(SampleString);    while not CharInSet(cp^, [#0, ';', '.']) do      Inc(cp);  end;    procedure P2;  var    cp: PChar;  begin    cp := PChar(SampleString);    while True do      case cp^ of        '.', #0, ';':          Break;      else        Inc(cp);      end;  end;    procedure P3;  var    cp: PChar;  begin    cp := PChar(SampleString);    while not (AnsiChar(cp^) in [#0, ';', '.']) do      Inc(cp);  end;    procedure Time(const Title: string; Proc: TProc);  var    i: Integer;    start, finish, freq: Int64;  begin    QueryPerformanceCounter(start);    for i := 1 to 1000000 do      Proc;    QueryPerformanceCounter(finish);    QueryPerformanceFrequency(freq);    Writeln(Format('%20s: %.3f seconds', [Title, (finish - start) / freq]));  end;    begin    Time('CharInSet', P1);    Time('case stmt', P2);    Time('set test', P3);  end.  

Its output on my laptop here is:

CharInSet: 0.261 seconds  case stmt: 0.077 seconds   set test: 0.060 seconds  

Answer by Din for Why is CharInSet faster than Case statement?

As I know call takes same amount of processor operations as jump does if they are both using short pointers. With long pointers may be different. Call in assembler does not use stack by default. If there is enough free registers used register. So stack operations take zero time too. It is just registers which is very fast.

In contrast case variant as I see uses add and sub operations which are quite slow and probably add most of extratime.

Answer by PatrickvL for Why is CharInSet faster than Case statement?

Barry, I'd like to point out that your benchmark does not reflect the actual performance of the various methods, because the structure of the implementations differ. Instead, all methods should use a "while True do" construct, to better reflect the impact of the differing ways to do a char-in-set check.

Here a replacement for the test-methods (P2 is unchanged, P1 and P3 now use the "while True do" construct) :

procedure P1;  var    cp: PChar;  begin    cp := PChar(SampleString);    while True do      if CharInSet(cp^, [#0, ';', '.']) then        Break      else        Inc(cp);  end;    procedure P2;  var    cp: PChar;  begin    cp := PChar(SampleString);    while True do      case cp^ of        '.', #0, ';':          Break;      else        Inc(cp);      end;  end;    procedure P3;  var    cp: PChar;  begin    cp := PChar(SampleString);    while True do      if AnsiChar(cp^) in [#0, ';', '.'] then        Break      else        Inc(cp);  end;  

My workstation gives :

CharInSet: 0.099 seconds  case stmt: 0.043 seconds   set test: 0.043 seconds  

Which better matches the expected results. To me, it seems using the 'case in' construct doesn't really help. I'm sorry Marco!

Answer by user45336 for Why is CharInSet faster than Case statement?

A free sampling profiler for Delphi can be found there:

https://forums.codegear.com/thread.jspa?messageID=18506

Apart from the issue of incorrect time measurement of instrumenting profilers, it should be noted that which is faster will also depend on how predictable the "case" branches are. If the tests in the "case" have all a similar probability of being encountered, performance of "case" can end up lower than that of CharInSet.

Answer by jackey for Why is CharInSet faster than Case statement?

The code in the function"CharInSet" is faster than 'case', the time is spent on 'call', use while not (cp^ in [..]) then

you will see this is the fasted.

Fatal error: Call to a member function getElementsByTagName() on a non-object in D:\XAMPP INSTALLASTION\xampp\htdocs\endunpratama9i\www-stackoverflow-info-proses.php on line 72