Pls help to optimize this WideChar buffer search lazarus / 21-General ---------------------------------------------------------------------- AlexTP · 2022-01-02 11:33 This is to optimize CudaText. I want to replace TStringList.Find (on a sorted list) with my custom search func (app won't allocate string for the search subject, but will use WideChar buffer). Custom function includes 'binary search' (copy/paste from FPC). Current results show that custom func is slower. StrList.Find: 73 / custom find: 100 StrList.Find: 63 / custom find: 113 StrList.Find: 74 / custom find: 102 Can I optimize custom-find? Attached the test. EDITED: attached version 2 of the test. ---------------------------------------------------------------------- Josh · 2022-01-02 12:52 just ran your code win 11 trunk 64 bit StrList.Find: 1061 / custom find: 111 with O2 StrList.Find: 1094 / custom find: 93 ---------------------------------------------------------------------- paweld · 2022-01-02 13:21 run on Windows 10: x86: StrList.Find: 984 / custom find: 16 StrList.Find: 907 / custom find: 78 StrList.Find: 906 / custom find: 63 StrList.Find: 952 / custom find: 32 StrList.Find: 906 / custom find: 78 StrList.Find: 906 / custom find: 63 StrList.Find: 968 / custom find: 32 StrList.Find: 937 / custom find: 47 StrList.Find: 970 / custom find: 30 StrList.Find: 954 / custom find: 31 x86_64: StrList.Find: 891 / custom find: 62 StrList.Find: 891 / custom find: 16 StrList.Find: 814 / custom find: 92 StrList.Find: 874 / custom find: 48 StrList.Find: 891 / custom find: 31 StrList.Find: 859 / custom find: 47 StrList.Find: 892 / custom find: 45 StrList.Find: 843 / custom find: 79 StrList.Find: 890 / custom find: 32 StrList.Find: 812 / custom find: 94 ---------------------------------------------------------------------- AlexTP · 2022-01-02 16:20 Ah, maybe I need to disable 'locale dependant' search:   sl.UseLocale:= false; Perhaps with this, you will have timing like me. ---------------------------------------------------------------------- tetrastes · 2022-01-02 17:43 Under linux (Debian 10, fpc 3.2.0 x86_64) I have timings like yours (with initial cmp_buf.lpr) and memory leak also: StrList.Find: 193 / custom find: 274 Heap dump by heaptrc unit of /home/wf/work/lazarus/FindStr/cmp_buf 1028 memory blocks allocated : 41034/44536 1026 memory blocks freed     : 39866/43368 2 unfreed memory blocks : 1168 True heap size : 425984 True free heap : 424384 Should be : 424432 Call trace for block $00007FE7BC30C110 size 1024 Call trace for block $00007FE7BC34C100 size 144 ---------------------------------------------------------------------- marcov · 2022-01-02 19:20 Use compareword in the custom proc ? It might use repe cmpsw ---------------------------------------------------------------------- AlexTP · 2022-01-02 23:26 CompareWord is not suitable - we compare AnsiChar and WideChar buffers. I guess it's optimal already. Even pointer math won't help. ---------------------------------------------------------------------- paweld · 2022-01-04 09:22 with sl.userLocale := False x86: StrList.Find: 62 / custom find: 63 StrList.Find: 48 / custom find: 62 StrList.Find: 16 / custom find: 77 StrList.Find: 63 / custom find: 31 StrList.Find: 31 / custom find: 78 StrList.Find: 31 / custom find: 79 StrList.Find: 63 / custom find: 46 StrList.Find: 46 / custom find: 48 StrList.Find: 31 / custom find: 63 StrList.Find: 61 / custom find: 48 x86_64: StrList.Find: 47 / custom find: 78 StrList.Find: 15 / custom find: 79 StrList.Find: 32 / custom find: 61 StrList.Find: 0 / custom find: 125 StrList.Find: 32 / custom find: 62 StrList.Find: 47 / custom find: 62 StrList.Find: 47 / custom find: 47 StrList.Find: 47 / custom find: 47 StrList.Find: 31 / custom find: 62 StrList.Find: 47 / custom find: 63 ---------------------------------------------------------------------- 440bx · 2022-01-04 12:26 the generated 64bit code produced with -O3+ is as follows:Code: ASM  [Select][+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i cmp_buf.lpr:39                            CompareRes := CompareFunc(AList[I]);00000001000016C0 4189f8                   mov    %edi,%r8d00000001000016C3 488d95e8feffff           lea    -0x118(%rbp),%rdx00000001000016CA 4c89e9                   mov    %r13,%rcx00000001000016CD 4c89e8                   mov    %r13,%rax00000001000016D0 488b00                   mov    (%rax),%rax00000001000016D3 ff90f0000000             callq  *0xf0(%rax)00000001000016D9 4c8b85e8feffff           mov    -0x118(%rbp),%r800000001000016E0 488d8df0feffff           lea    -0x110(%rbp),%rcx00000001000016E7 48baff00000000000000     movabs $0xff,%rdx00000001000016F1 e88a460000               callq  0x100005d80 00000001000016F6 488d95f0feffff           lea    -0x110(%rbp),%rdx00000001000016FD 4889e9                   mov    %rbp,%rcx0000000100001700 e87b000000               callq  0x100001780 0000000100001705 4863c0                   movslq %eax,%rax0000000100001708 4989c4                   mov    %rax,%r12cmp_buf.lpr:40                            if (CompareRes>0) then000000010000170B 4983fc00                 cmp    $0x0,%r12000000010000170F 7e08                     jle    0x100001719  That code shows that the CompareFunc is not inlined (see call at line 14), that's likely because the CompareFunc is nested and takes parameters at different nesting levels. It's quite possible that a noticeable increase in performance can be gained by declaring a record with fields ABuf and ABufLen (both set only once) and SItem (set to AList every time a comparison is needed) and passing a pointer to that record to the CompareFunc (no longer nested) . The gain in performance is achieved because access to ABuf and BufLen no longer have to use the stack pointer of the previous frame (StringList_FindWideBuffer.) It's also likely that the compiler may be able to inline the CompareFunc since there will not be cross stack frame variable references. DISCLAIMER: I haven't tried it but, just the fact that there will not be an additional stack frame reference will increase performance. HTH. ---------------------------------------------------------------------- engkin · 2022-01-04 18:08 Quote from: 440bx on January 04, 2022, 01:26:02 pmThat code shows that the CompareFunc is not inlined (see call at line 14), that's likely because the CompareFunc is nested and takes parameters at different nesting levels. It will not be inlined because, as you stated, it has a nested proc, has more than 10 nodes, I believe, and uses out var. I don't know if this is the case today, but the reasons I found were here. His code is ten times faster on my old laptop using 32bit. He could gain more speed by not using the property to read the strings. Unfortunately the pointer is in a private section. That's the first field in TStringList. ---------------------------------------------------------------------- AlexTP · 2022-01-04 18:36 I just updated the file in the 1st post: added {$H+} and made the CompareFunc not nested. And .s file shows that it's inlined (it seems). The results are similar. StrList.Find: 75 / custom find: 90 StrList.Find: 79 / custom find: 80 StrList.Find: 78 / custom find: 87 ---------------------------------------------------------------------- engkin · 2022-01-04 19:14 Wait, you are comparing a WideChar buffer (UTF16) with a String (UTF8)? Both are supposed to hold/limited to ASCII chars? ---------------------------------------------------------------------- AlexTP · 2022-01-04 19:29 Yes, WideChar buffer with AnsiString; widechar buffer can have any text, but StringList has only ASCII text. ---------------------------------------------------------------------- engkin · 2022-01-04 19:45 Why do you have assert inside the timing loops? ---------------------------------------------------------------------- AlexTP · 2022-01-04 19:53 Asserts do not break the result, they are to test my compareFunc. ---------------------------------------------------------------------- marcov · 2022-01-04 20:02 Quote from: Alextp on January 04, 2022, 08:29:15 pmYes, WideChar buffer with AnsiString; widechar buffer can have any text, but StringList has only ASCII text. Why do I see shortstr conversions then? Are you sure you enabled $h+ ? Code: [Select] callq  0x100005d80  00000001000016F6 488d95f0feffff           lea    -0x110(%rbp),%rdx 00000001000016FD 4889e9                   mov    %rbp,%rcx 0000000100001700 e87b000000               callq  0x100001780 [/code ---------------------------------------------------------------------- AlexTP · 2022-01-04 20:16 Quote Are you sure you enabled $h+ ? $H+ was forgotten in original test; now it's there in test version2. ---------------------------------------------------------------------- marcov · 2022-01-04 21:12 I played a bit and came to this ( very quick and dirty): Code: Delphi  [Select][+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i //compares String item with WideChar buffer (ASCII string in wide buffer)function CompareFunc(ABuf: PWideChar; ABufLen: integer; const SItem: AnsiString): integer; inline;var  NCmp,hb: integer;  i: PtrInt;  pp : pchar;begin  //compare 1st char  NCmp:= Ord(ABuf[0])-Ord(SItem[1]);  if NCmp<>0 then Exit(NCmp);   //compare others  hb:=Min(ABufLen, Length(SItem));  pp:=@sitem[2];  inc(abuf);  for i:= 1{>0} to hb-1 do  begin    NCmp:= ord(abuf^)-ord(pp^) ;    inc(abuf); inc(pp);    if NCmp<>0 then break; // avoid an additional jump due to preparing exit() argument  end; if NCmp<>0 then exit(ncmp);    Result:= ABufLen- Length(SItem);end;  it seems to be slightly better, but the results of both vary too much,  (maybe because I'm on a laptop?) ---------------------------------------------------------------------- AlexTP · 2022-01-04 21:16 @macrov, thanks but the result is almost the same (custom find is even slower now, seems). Quoteuser@PC:~/Documents/stringlist_widebuffer$ ./cmp_buf StrList.Find: 77 / custom find: 84 StrList.Find/bad: 86 / custom find/bad: 91 user@PC:~/Documents/stringlist_widebuffer$ ./cmp_buf StrList.Find: 68 / custom find: 105 StrList.Find/bad: 86 / custom find/bad: 79 user@PC:~/Documents/stringlist_widebuffer$ ./cmp_buf StrList.Find: 85 / custom find: 96 StrList.Find/bad: 80 / custom find/bad: 79 ---------------------------------------------------------------------- balazsszekely · 2022-01-05 14:14 @Alextp Did you try a HashList as in the attachment? Is much faster at my side. QuoteD:\Test>cmp_buf_2 StrList.Find: 517 / custom find: 16 StrList.Find/bad: 546 / custom find/bad: 15 ---------------------------------------------------------------------- AlexTP · 2022-01-05 15:34 @GetMem Nice idea.... but result (after you add 'sl.UseLocale:= False') is faster only in 'bad case', search for non-existing str. QuoteStrList.Find: 79 / custom find: 89 StrList.Find/bad: 74 / custom find/bad: 64 StrList.Find: 75 / custom find: 88 StrList.Find/bad: 82 / custom find/bad: 67 StrList.Find: 76 / custom find: 86 StrList.Find/bad: 81 / custom find/bad: 71 ---------------------------------------------------------------------- balazsszekely · 2022-01-05 16:09 @Alextp QuoteNice idea.... but result (after you add 'sl.UseLocale:= False') is faster only in 'bad case', search for non-existing str.Yes, with X86_64 you get similar results, however on X86 is way faster. I'm trying to figure out why is much slower on 64 bit, also I'm wondering what would happen with a few optimization(-o, ...), unfortunately it's not my area of expertise(to be perfectly honest I suck at it ). PS: Please note that as the list grows, the hash method will be increasingly faster. You will see the difference when the list is bigger then 10k. ---------------------------------------------------------------------- AlexTP · 2022-01-05 16:47 My app has StringList with 30 to e.g. 500 items. Not 10k items. Also a note for HashList: I am not sure you do it correct: Code: Pascal  [Select][+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i   for I := 0 to ASL.Count - 1 do  begin    Hash := MD5Print(MD5String(ASL.Strings[I]));    New(PStr);    PStr^ := ASL.Strings[I];    AHL.Add(Hash, PStr);  end; because on collision (same hash str for different long strings) it fails, yes? ---------------------------------------------------------------------- balazsszekely · 2022-01-05 16:58 @Alextp QuoteMy app has StringList with 30 to e.g. 500 items. Not 10k items.Then I don't see the point of optimization. QuoteAlso a note for HashList: I am not sure you do it correct: because on collision (same hash str for different long strings) it fails, yes?Different strings cannot have the same hash, even with md5 the chances of random collisions are incredibly small. You put sl.Duplicates:= dupIgnore, so there will be no collision. ---------------------------------------------------------------------- AlexTP · 2022-01-05 17:25 @GetMem Search-str will be the 'words' from source code, and StrList (HashList) will have list of 'std IDs of syntax'. Collisions are possible - hashes may be equal but strings are not. ---------------------------------------------------------------------- balazsszekely · 2022-01-05 17:46 @Alextp QuoteSearch-str will be the 'words' from source code, and StrList (HashList) will have list of 'std IDs of syntax'. Collisions are possible - hashes may be equal but strings are not.Now I have no idea what are you talking about. There is a surjective relation between the stringlist and hashlist. Each string has a unique hash equivalent, more over the hashlist also contains the original strings too: Code: Pascal  [Select][+][-]window.onload = function(){var x1 = document.getElementById("main_content_section"); if (x1) { var x = document.getElementsByClassName("geshi");for (var i = 0; i Hash := HL.NameOfIndex(I);PStr := HL.Items[I]; OrigStr := PStr^ Hash and OrigStr are in pair, that's the whole point. Searching in Hash list is much faster because it was build for speed. I have nothing more to say, good luck with the optimization. ---------------------------------------------------------------------- AlexTP · 2022-01-05 18:10 Thanks, you gave a useful direction for me. I will think about this more. (I am not sure I was right about collision)