What am I doing wrong? Similar FPC code runs 1.5x slower than CPython?!?!

[kveroneau]

Thank you everyone for your helpful feedback.  I attempted to compile the newer version of the program but ran into some compilation errors.  I solved the first one regarding "Result" not being an identifier...  But this next one is stumping me as the code looks correct, it's complaining that "try" of all things isn't an identifier...  Isn't this part of the core language?  I am using FPC 2.6.4 currently, I thought the Try statement was available in this version.

Free Pascal Compiler version 2.6.4 [2014/03/03] for x86_64
Copyright (c) 1993-2014 by Florian Klaempfl and others
Target OS: Linux for x86-64
Compiling chkblock2.pas
chkblock2.pas(15,5) Error: Identifier not found "Try"
chkblock2.pas(15,5) Fatal: Syntax error, ";" expected but "identifier MS" found
Fatal: Compilation aborted
Error: /home/kveroneau/fpc-2.6.4/bin/ppcx64 returned an error exitcode (normal if you did not specify a source file to be compiled)

Any ideas why these errors would be occurring?

[balazsszekely]

Just remove try finally end, leave everything else intact, it should work just fine without. Tell us how fast is the new version? Did we beat python. 

[Leledumbo]

Any ideas why these errors would be occurring?

You don't have either {$mode objfpc} in the source or corresponding command line switch (-S2). Read this.

[kveroneau]

Still having some trouble after removing the Try/Finally blocks, and I believe {$M OBJPAS} should enable exceptions, and that option is enabled.

Got past a few other random errors, and now it's saying GetTickCount is not a valid Identifier, doing further research shows that this function has been deprecated:
http://www.freepascal.org/docs-html/rtl/sysutils/gettickcount.html

So, in the meantime to test this code, I will comment out the timing stuff for now.

Which version of FPC is everybody here using, namely the one who wrote the more optimized code?

[Leledumbo]

Still having some trouble after removing the Try/Finally blocks, and I believe {$M OBJPAS} should enable exceptions, and that option is enabled.

I can't use that shorthand, I don't know where it comes from since {$M means this.

Got past a few other random errors, and now it's saying GetTickCount is not a valid Identifier, doing further research shows that this function has been deprecated:
http://www.freepascal.org/docs-html/rtl/sysutils/gettickcount.html

Use this instead:

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

1. uses SysUtils,DateUtils
2. ...
3. var st,et: TDateTime;
4. ...
5. st := Now;
6. // do the code to measure here
7. et := Now;
8. WriteLn(SecondSpan(st,et):1:6); // should display seconds elapsed up to 6 decimal points
9.  

Which version of FPC is everybody here using, namely the one who wrote the more optimized code?

Latest trunk (main) + latest stable (fallback).

[balazsszekely]

FPC 3.0.0. But soon I will run a few test under 2.6.4.

PS: Other then GetTickCount not found, the code works fine under 2.6.4. You can replace GetTickCount with your original timing.

[balazsszekely]

I just realised, that your are using the FPC IDE(2.6.4) not Lazarus. This will work, just don't forget to copy IPs.txt and Blocking.txt in the same folder as your executable:

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

1. Program ChkBlock;
2. {$mode objfpc}{$H+}
3.  
4. uses classes, sysutils, dateutils;
5.  
6. function FileToString(const AFile: String; var Str: String): Boolean;
7. var
8.   MS: TMemoryStream;
9. begin
10.   Result := False;
11.   if not FileExists(AFile) then
12.     Exit;
13.   MS := TMemoryStream.Create;
14.   try
15.     MS.LoadFromFile(AFile);
16.     if MS.Size > 0 then
17.     begin
18.       SetLength(Str, MS.Size div SizeOf(Char));
19.       MS.ReadBuffer(Pointer(Str)^, MS.Size div SizeOf(Char));
20.       Result := True;
21.     end;
22.   finally
23.     MS.Free;
24.   end;
25. end;
26.  
27. function StringToFile(const AFile, Str: String): Boolean;
28. var
29.   MS: TMemoryStream;
30. begin
31.   Result := False;
32.   MS := TMemoryStream.Create;
33.   try
34.     MS.Write(Pointer(Str)^, Length(Str) div SizeOf(Char));
35.     MS.Position := 0;
36.     MS.SaveToFile(AFile);
37.     Result := FileExists(AFile);
38.   finally
39.     MS.Free;
40.   end;
41. end;
42.  
43. function GetTickCount: Cardinal;
44. begin
45.   Result := Cardinal(Trunc(Now * 24 * 60 * 60 * 1000));
46. end;
47.  
48. var
49.   IPs: String;
50.   Blocking: String;
51.   Matches: String;
52.   SL: TStringList;
53.   Ellapsed: Cardinal;
54.   P, I: Integer;
55. begin
56.   Ellapsed := GetTickCount;
57.   IPs := '';
58.   Blocking := '';
59.   Matches := '';
60.   FileToString(ExtractFilePath(ParamStr(0)) + 'IPs.txt', IPs);
61.   FileToString(ExtractFilePath(ParamStr(0)) + 'Blocking.txt', Blocking);
62.   SL := TStringList.Create;
63.   try
64.     SL.Text := Blocking;
65.     for I := 0 to SL.Count - 1 do
66.     begin
67.       P := Pos(SL[I], IPs);
68.       if P > 0 then
69.         Matches := Matches + Sl[I] + sLineBreak;
70.     end;
71.   finally
72.     SL.Free;
73.   end;
74.   StringToFile(ExtractFilePath(ParamStr(0)) + 'Matches.txt', Matches);
75.   Ellapsed := GetTickCount - Ellapsed;
76.   Writeln('Took ', Ellapsed, ' ms');
77.   Readln;
78. end.

[kveroneau]

That was the main problem for the errors I was seeing was that I was using $M rather than $MODE.   

I am running the code now to see the difference in speed.

The new code actually performs worse it seems...  12 minutes now.  Also comparing results from my previous code, the output of matches is also different...

$ wc -l matches.txt
13319 matches.txt
$ wc -l Matches.txt
13769 Matches.txt

Here's the amount of IPs in both lists for those interested on knowing the dataset size being filtered:
$ wc -l blocking.txt
255811 blocking.txt
$ wc -l ips.txt
101325 ips.txt

[balazsszekely]

@kveroneau
The new code actually performs worse it seems...  12 minutes now.

Apparently the big optimizations failed. 
By the way, this is really interesting. In my original tests IPs.txt was much larger then Blocking.txt. I thought there are a lot of IP addresses and some of them are blocked. So I did the test with the following values:
    2 099 873 ips.txt(yes, two million)
    3 685  blocking.txt
In this configuration the new method is much faster then the one with TStringList

On the other hand, if I change the values to:
    101 325  ips.txt
    255 811  blocking.txt
The TStringList method is faster, especially if the textfiles are somewhat sorted.

 Now I'm confused! I would like tho hear some explanation, perhaps alternative solutions.

[Leledumbo]

Try this one (FPC 3.0.0 or trunk required):

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

1. {$mode objfpc}{$H+}
2.  
3. uses
4.   classes,ghashset,bufstream,streamio,fileutil {this belongs to lazutils package};
5.  
6. type
7.   TFNV1AHash = class
8.     class function Hash(s: String; n: SizeUInt): SizeUInt;
9.   end;
10.  
11.   TStringHashSet = specialize THashSet<String,TFNV1AHash>;
12.  
13. class function TFNV1AHash.Hash(s: String; n: SizeUInt): SizeUInt;
14. const
15.   {$ifdef CPU32}
16.   OffsetBasis = 2166136261;
17.   FNVPrime = 16777619;
18.   {$endif}
19.   {$ifdef CPU64}
20.   OffsetBasis = 14695981039346656037;
21.   FNVPrime = 1099511628211;
22.   {$endif}
23. var
24.   c: Char;
25. begin
26.   Hash := OffsetBasis;
27.   for c in s do begin
28.     Hash := Hash xor SizeUInt(c);
29.     Hash := Hash * FNVPrime;
30.   end;
31.   Hash := Hash mod n;
32. end;
33.  
34. function FileToBufStream(const FN: String; const Mode: Integer): TBufStream;
35. begin
36.   Result := TReadBufStream.Create(TFileStream.Create(FN,Mode),FileSize(FN));
37.   Result.SourceOwner := true;
38. end;
39.  
40. function FileToHashSet(const FN: String): TStringHashSet;
41. var
42.   f: Text;
43.   s: TStream;
44.   l: String;
45. begin
46.   Result := nil;
47.   s := FileToBufStream(FN,fmOpenRead);
48.   try
49.     AssignStream(f,s);
50.     Reset(f);
51.     Result := TStringHashSet.Create;
52.     while not EOF(f) do begin
53.       ReadLn(f,l);
54.       Result.Insert(l);
55.     end;
56.   finally
57.     s.Free;
58.   end;
59. end;
60.  
61. procedure StringToFile(const AFile, Str: String);
62. var
63.   MS: TMemoryStream;
64. begin
65.   MS := TMemoryStream.Create;
66.   try
67.     MS.Write(Pointer(Str)^, Length(Str) div SizeOf(Char));
68.     MS.Position := 0;
69.     MS.SaveToFile(AFile);
70.   finally
71.     MS.Free;
72.   end;
73. end;
74.  
75. var
76.   BlockingSet: TStringHashSet;
77.   s: TStream;
78.   f: Text;
79.   l,Matches: String;
80. begin
81.   try
82.     BlockingSet := FileToHashSet('Blocking.txt');
83.     s := FileToBufStream('IPs.txt',fmOpenRead);
84.     Matches := '';
85.     AssignStream(f,s);
86.     Reset(f);
87.     while not EOF(f) do begin
88.       ReadLn(f,l);
89.       if BlockingSet.Contains(l) then begin
90.         Write('.');
91.         Matches := Matches + l + LineEnding;
92.       end;
93.     end;
94.     StringToFile('Matches.txt',Matches);
95.   finally
96.     s.Free;
97.     BlockingSet.Free;
98.   end;
99. end.
100.  

[SymbolicFrank]

If they actually contain IP addresses: convert them to integers and use that as the index.

If the idea is to find if an IP address is on the "blocked" list, FAST, I would probably use nodes: convert the addresses into integers, split those up into byte portions, and make a node list that contains node lists, each having an ID of 0-255. And an Add and (semi-recursive) IndexOf (or Find) function. Works with IP6 as well, you just have twice as many levels.

First read the blocked list, and add them all as nodes. A lookup is quite fast after that.

But I guess it depends on what you want to do with it. The big picture.

And if the above was the main goal, I would give each node a serialize/deserialize method as well, so it can be written to a text file and read back into memory.

[balazsszekely]

@Leledumbo
Yeah, that code performs very well, especially on this configuration:
 101 325  ips.txt
 255 811  blocking.txt

@SymbolicFrank
Yes, it depends on many things, however @Leledumbo's code it's a good generic solution(which will work in most cases).

[Leledumbo]

@GetMem:
Do you have the actual ips.txt and blocking.txt that the OP uses? I'd like to know the actual performance compared to the original code. The FNV-1a hash function should work great in general, however the n parameter could result in higher collision. Just my random thought, though.

[balazsszekely]

@Leledumbo
Do you have the actual ips.txt and blocking.txt that the OP uses?

No, I don't! I created my own(actually just two txt files with random text, not real IP's). Let's hope the OP can upload somewhere those files, or run the test again with your code, however he/she doesn't have FPC 3.0.0. 

[BrunoK]

I have generated ipv4 looking ips.txt and blocking.txt but zipped they are nearly 2MB sized. Is it allowed on the forum.
There are, if things worked as expected, 101'325 lines in ips.txt and 255'811 lines in blocking.txt with an intersection of the pseudo IP's of 13'769 lines between the two files.

Leledumbo's, solution is, by my judgement, on the same track I thought, except I have my personal version of FNV  hash algorithm.

12 minutes for intersect of the two files as kveroneau has implemented is in my opinion really ridiculously long. It should be in the order of seconds with more or less regular tricks.