Contest: fastest IsAnagram function

[Martin_fr]

Also, if my solution is changed to using integer instead of smallint, then test with both SMALL_LOOP on and off.  (On my System it becomes equal, but on others it may still differ)

[Fibonacci]

@Martin_fr: I moved your code to a separate unit because of the switches and defines.

EDIT: Update because the results were from the debug version, now its release mode with full optimizations, x64.

Code: Text  [Select][+][-]

1. *** ROUND 1 ***
2. s1 = s tate
3. s2 = t a  s t  e
4.  
5.                 Bart IgnoreSpaces ExceptionOnError |  1562 ms | result 25000000
6.            Fibonacci IgnoreSpaces ExceptionOnError |   813 ms | result 25000000
7.               ASerge IgnoreSpaces ExceptionOnError |   937 ms | result 25000000
8.                Zvoni IgnoreSpaces ExceptionOnError | 16141 ms | result 25000000
9.            Zvoni (2) IgnoreSpaces ExceptionOnError |  6640 ms | result 25000000
10.            ALLIGATOR IgnoreSpaces ExceptionOnError |  1453 ms | result 25000000
11.        silvercoder70 IgnoreSpaces ExceptionOnError |  3438 ms | result 25000000
12.                  avk IgnoreSpaces ExceptionOnError |  1547 ms | result 25000000
13.            Martin_fr IgnoreSpaces ExceptionOnError |  1453 ms | result 25000000
14.               BrunoK IgnoreSpaces ExceptionOnError |  2406 ms | result 25000000
15.                                  Bart IgnoreSpaces |  1422 ms | result 25000000
16.                             Fibonacci IgnoreSpaces |   797 ms | result 25000000
17.                                ASerge IgnoreSpaces |   922 ms | result 25000000
18.                                 Zvoni IgnoreSpaces | 16875 ms | result 25000000
19.                             Zvoni (2) IgnoreSpaces |  7375 ms | result 25000000
20.                             ALLIGATOR IgnoreSpaces |   625 ms | result 25000000
21.                         silvercoder70 IgnoreSpaces |  2750 ms | result 25000000
22.                                   avk IgnoreSpaces |  1562 ms | result 25000000
23.                             Martin_fr IgnoreSpaces |  1250 ms | result 25000000
24.                                BrunoK IgnoreSpaces |  2438 ms | result 25000000
25.                                               Bart |  1312 ms | result 0
26.                                          Fibonacci |   672 ms | result 0
27.                                             ASerge |   719 ms | result 0
28.                                              Zvoni |  2906 ms | result 0
29.                                          Zvoni (2) |   750 ms | result 0
30.                                          ALLIGATOR |  1266 ms | result 0
31.                                      silvercoder70 |  1109 ms | result 0
32.                                                avk |   938 ms | result 0
33.                                          Martin_fr |   812 ms | result 0
34.                                             BrunoK |   438 ms | result 0

[BrunoK]

What is the problem with my routine in your comparison ?

Does it have a BUG ?

[Fibonacci]

What is the problem with my routine in your comparison ?

Does it have a BUG ?

Oh so sorry! I must have missed it somehow Just updated the previous post, and it now includes your routine.

[Bart]

A few observations from some separate testing:

• Using Default(TFreq) is as fast as using FillDWord or assigning a predefined constant (tested with 50 million cycles).
• You cannot replace LowerCase() with simply or-ing with $20 (at least not for all characters. If you do then e.g. ~ (tilde) and ^ (caret) will both turn into ~, so you cannot distinguish between them anymore.)

Bart

[ASerge]

Why is noreturn commented out?

tests.lpr(98,75) Error: Raise in subroutines declared as noreturn is not allowed

And what is the FPC version? I don't have such a error. FPC 3.2.2.

Trunk 3.3.1

Degradation? With this approach, the meaning of the directive is lost, since it is possible not to return only from the procedure that generates an exception.

[BrunoK]

IsAnagram_fibo breaks with :

Code: Pascal  [Select][+][-]

1.   s := 's tate ^';
2.   d := 't a  s t  e  `';

[Window Title]
Error

[Content]
Project tests raised exception class 'External: ACCESS VIOLATION' with message:
Access violation reading from address $FFFFFFFFFFFFFFFF.

 In file 'tests.lpr' at line 73:
for i := 1 to Length(S1) do begin

[OK]

[Fibonacci]

@BrunoK: Yeah, my whole routine is buggy and got even more bugs with the changes, but I don't feel like playing with it anymore

[BrunoK]

@Fibonacci, what processor / OS do you have. It's quite a racer.

For my Win10 11th Gen Intel(R) Core(TM) i5-1135G7 @ 2.40GHz   2.42 GHz I'm 5 times slower.

My results for 5'000'000 iterations in -O2 are :

Code: Text  [Select][+][-]

1. Number of iterations : 5'000'000
2.  
3. *** ROUND 1 ***
4. s1 = s tate
5. s2 = t a  s t  e
6.  
7.                 Bart IgnoreSpaces ExceptionOnError |  1094 ms | result 5000000
8.            Fibonacci IgnoreSpaces ExceptionOnError |   453 ms | result 5000000
9.               ASerge IgnoreSpaces ExceptionOnError |  1000 ms | result 5000000
10.                Zvoni IgnoreSpaces ExceptionOnError |  2719 ms | result 5000000
11.            Zvoni (2) IgnoreSpaces ExceptionOnError |  1563 ms | result 5000000
12.            ALLIGATOR IgnoreSpaces ExceptionOnError |   906 ms | result 5000000
13.        silvercoder70 IgnoreSpaces ExceptionOnError |  1000 ms | result 5000000
14.                  avk IgnoreSpaces ExceptionOnError |   344 ms | result 5000000
15.            Martin_fr IgnoreSpaces ExceptionOnError |   421 ms | result 5000000
16.               BrunoK IgnoreSpaces ExceptionOnError |   219 ms | result 5000000
17.                                  Bart IgnoreSpaces |  1094 ms | result 5000000
18.                             Fibonacci IgnoreSpaces |   469 ms | result 5000000
19.                                ASerge IgnoreSpaces |   984 ms | result 5000000
20.                                 Zvoni IgnoreSpaces |  2719 ms | result 5000000
21.                             Zvoni (2) IgnoreSpaces |  1562 ms | result 5000000
22.                             ALLIGATOR IgnoreSpaces |   922 ms | result 5000000
23.                         silvercoder70 IgnoreSpaces |   985 ms | result 5000000
24.                                   avk IgnoreSpaces |   343 ms | result 5000000
25.                             Martin_fr IgnoreSpaces |   438 ms | result 5000000
26.                                BrunoK IgnoreSpaces |   234 ms | result 5000000
27.                                               Bart |   313 ms | result 0
28.                                          Fibonacci |   235 ms | result 0
29.                                             ASerge |   218 ms | result 0
30.                                              Zvoni |   532 ms | result 0
31.                                          Zvoni (2) |   234 ms | result 0
32.                                          ALLIGATOR |   156 ms | result 0
33.                                      silvercoder70 |   313 ms | result 0
34.                                                avk |   125 ms | result 0
35.                                          Martin_fr |   375 ms | result 0
36.                                             BrunoK |   156 ms | result 0
37.  
38. [/quote]
39. [/quote]

[Fibonacci]

@BrunoK: Thanks! My CPU is AMD Ryzen 7 5800X at 3.80 GHz, Windows 10 x64

[Martin_fr]

Just run the test myself.

Some implementations return different results (for night/thing) when compiled with -gt or -gtt

[Martin_fr]

Also, please change my file

Line 41:

From
  FillChar(Cnt, sizeof(Cnt), 0);

To
  FillChar(Cnt, sizeof(Cnt[0])*128, 0);


Doesn't make a big diff, but anyway.

[Martin_fr]

And from my side, congrats to BrunoK

[avk]

@Fibonacci, curious what the results would look like if the strings were at least 100 characters long?

[Warfley]

I took Fibonnaccis code from the first comparison, and added some spice, because comparing only short phrases is doesn't really tell much:

Code: Pascal  [Select][+][-]

1. procedure main;
2. const
3.   ITERATIONS = 1000*100;
4.   STRSIZE = 1024;
5. var
6.   i, c: integer;
7.   s, d: string;
8.   u: ptruint;
9.   x: Byte;
10.   p: SizeInt;
11. begin
12.   Randomize;
13.   s:='';
14.   d:='';
15.   setlength(s, STRSIZE);
16.   setlength(d, STRSIZE);
17.   FillChar(s[1],STRSIZE,#00);
18.   FillChar(d[1],STRSIZE,#00);
19.   for i:=1 to STRSIZE do
20.   begin
21.     x:=Random(26)+65;
22.     if x = 91 then
23.       x := 32;
24.     s[i]:=chr(x or ord(x<>32)*random(2)*$20);
25.   end;
26.   d:=s;
27.   UniqueString(d);
28.  
29.   i:=1;
30.   while i <= STRSIZE do
31.   begin
32.     p:=random(STRSIZE)+1;
33.     x:=ord(d[p]);
34.     d[p]:=d[i];
35.     d[i]:=chr(x);
36.     if random(2) = 0 then
37.     begin
38.       d[i]:=chr(x or ord(x in [65..90])*$20);
39.       d[i]:=chr(x and not (ord(x in [97..122])*$20));
40.     end;
41.     if random(2) = 0 then
42.       inc(i);
43.   end;
44.  
45.   writeln('s1 = ', s);
46.   writeln('s2 = ', d);
47.   writeln;

This now creates a randomized string of the predefined length (1024 in this case).

And also here is my approach to it:

Code: Pascal  [Select][+][-]

1. function IsAnagram_warf(const S1, S2: String; IgnoreSpaces: Boolean = True; ExceptionOnError: Boolean = False): Boolean;
2. var
3.   s1c, s1e, s2c, s2e: PChar;
4.   ctr : array[Byte] of SizeInt;
5.   pcmp:PSizeInt;
6. begin
7.   s1c:=pchar(s1);
8.   s1e:=s1c+length(s1);
9.   s2c:=pchar(s2);
10.   s2e:=s2c+length(s2);
11.   fillchar(ctr,SizeOf(ctr),#00);
12.   try
13.   repeat
14.     if ignorespaces then
15.     begin
16.       while (s1c<s1e) and (s1c^<=#32) do
17.         inc(s1c);
18.       while (s2c<s2e) and (s2c^<=#32) do
19.         inc(s2c);
20.     end;
21.     if (s1c=s1e) or (s2c=s2e) then
22.       break;
23.     if not (s1c^ in [#32..#127]) then
24.       raise ERangeError.CreateFmt('IsAnagram: illegal character in S1 %c', [s1c^]);
25.     if not (s2c^ in [#32..#127]) then
26.       raise ERangeError.CreateFmt('IsAnagram: illegal character in S2 %c', [s2c^]);
27.     inc(ctr[Ord(s1c^) or $20*ord(s1c^ in [#65..#90])]);
28.     dec(ctr[Ord(s2c^) or $20*ord(s2c^ in [#65..#90])]);
29.     inc(s1c);
30.     inc(s2c);
31.   until false;
32.   pcmp:=@ctr;
33.   result:=(s1c=s1e) and (s2c=s2e);
34.   while result and (pcmp<@ctr+sizeof(ctr)) do
35.   begin
36.     result:=pcmp^=0;
37.     inc(pcmp);
38.   end;
39.   except on E: ERangeError do
40.     if ExceptionOnError then
41.       raise E
42.     else
43.       Result:=False;
44.   end;
45. end;

Sucks on shorter strings but is quite good on longer ones. To perform better on shorter strings just change the line:

Code: Pascal  [Select][+][-]

1.   ctr : array[Byte] of SizeInt;

to

Code: Pascal  [Select][+][-]

1.   ctr : array[Byte] of Byte;

I know it's cheating but it works