Lazarus

Programming => General => Topic started by: Amir61 on January 17, 2025, 07:08:50 pm

Title: How to avoid copying
Post by: Amir61 on January 17, 2025, 07:08:50 pm
Hi,

 I have a record of records data structure, like, the following:
Code: Pascal  [Select][+][-]
  1. type TTuple = record
  2.   Entry: TEntry; // TEntry is a record
  3.   Other fields
  4. end;
  5.  
and I have a function that gets a 'TTuple' and does some stuff with its Entry. For my case, it does not make sense to define a separate function that gets 'Entry' as its input.

Code: Pascal  [Select][+][-]
  1. function F(constref Tuple: TTuple): Boolean;
  2.  

Since this function is going to be called a lot, in my code, I am looking for an efficient (and readable) implementation to access 'Tuple.Entry'.

Here are my few options (none of them is great!).
Code: Pascal  [Select][+][-]
  1. function F(constref Tuple: TTuple): Boolean;
  2. var
  3.   Entry: TEntry;
  4. begin
  5.   Entry := Tuple.Entry;
  6.   // Work with Entry rather than Tuple.Entry
  7.  

This requires memory allocation as well as run time overhead of  copying of Tuple.Entry to Entry.

The other option is to use Tuple.Entry through out the function (which is not really a nice solution).

Another option is use EntryPtr := @Tuple.Entry; , but this requires to use EntryPtr^ in the function. I believe this is the best option.

Wondering if there is any other solution? 
Title: Re: How to avoid copying
Post by: cdbc on January 17, 2025, 07:19:31 pm
Hi
I'd stay with the pointer-solution and then at the top of the unit add this:
Code: Pascal  [Select][+][-]
  1. {$modeswitch autoderef}
That way you don't have to write a lot of 'hats' ^
HTH
Regards Benny
Title: Re: How to avoid copying
Post by: Martin_fr on January 17, 2025, 07:25:38 pm
Code: Pascal  [Select][+][-]
  1.     function F(constref Tuple: TTuple): Boolean;
  2.     var
  3.       Entry: TEntry absolute Tuple.Entry;
  4.     begin
  5.  
Title: Re: How to avoid copying
Post by: Amir61 on January 17, 2025, 07:55:16 pm
Thanks!
Title: Re: How to avoid copying
Post by: PascalDragon on January 18, 2025, 05:02:08 pm
Quote from: Amir61 on January 17, 2025, 07:08:50 pm
Code: Pascal  [Select][+][-]
  1. function F(constref Tuple: TTuple): Boolean;
  2.  

Not related to your question, but I'd suggest you to use const instead of constref. While for this specific example it does not make a difference there are cases where you don't want to enforce a reference, because the compiler could instead pass it in a register or two (e.g. if you have a record containing two 32-bit values). Use constref only if you really need a constant reference.
Title: Re: How to avoid copying
Post by: Amir61 on February 14, 2025, 06:02:23 am
How about this case:

Code: Pascal  [Select][+][-]
  1. TPair = record
  2.   First: TKey;
  3.    Second: Tvalue;
  4. end;
  5.  
  6. PPair = ^TPair;
  7.  
  8. function Compare(P1, P2: Pointer): Integer;
  9. var
  10.   K1, K2: TKey;
  11.  
  12. begin
  13.   K1 := PPair(P1).Key;
  14.   K2 := PPair(P2).Key;
  15.  
  16.   // ....
  17.  
  18. end;
  19.  

The best I could do is the following:

Code: Pascal  [Select][+][-]
  1. function CompareTPairs(const P1, P2: TPair): Integer; inline;
  2. var
  3.   Key1: TKey absolute P1.First;
  4.   Key2: TKey absolute P2.First;
  5.  
  6. begin
  7. ....
  8. end;
  9.  
  10. function ComparePPairs(P1, P2: PPair): Integer; inline;
  11. begin
  12.   Result := CompareTPairs(P1^, P2^);
  13.  
  14. end;
  15.  
  16. function ComparePointers(P1, P2: Pointer): Integer;
  17. begin
  18.   Result := ComparePPairs(PPair(P1), PPair(P2));
  19. end;
  20.  
  21.  
Title: Re: How to avoid copying
Post by: cdbc on February 14, 2025, 12:22:01 pm
Wow!
That's a whole heap of beating around the bush ...for a simple compare?!?
How about this:
Code: Pascal  [Select][+][-]
  1. function PairKeyCompare(P1, P2: Pointer): Integer;
  2. var
  3.   pa1: PPair absolute P1;
  4.   pa2: PPair absolute P2;
  5. begin
  6.   if pa1^.Key.First < pa2^.Key.First then Result:= -1
  7.   else if pa1^.Key.First = pa2^.Key.First then Result:= 0
  8.   else Result:= 1;
  9. end;
No copying of data, just pointers - should be snappy  ;D
Regards Benny
edited: added '.First' to the comparison, 'cause 'Key' is a record <15.02>
Title: Re: How to avoid copying
Post by: Amir61 on February 14, 2025, 06:39:10 pm
Since I am using inline, I assume the final generated code for the two approaches are going to be very similar if not the same.
Title: Re: How to avoid copying
Post by: cdbc on February 14, 2025, 06:48:17 pm
Hi
Hmmm... I think the call to your last 'CompareTPairs' will result in a copy..., but I could be mistaken.
Regards Benny
Title: Re: How to avoid copying
Post by: BrunoK on February 14, 2025, 06:49:51 pm
Quote from: Amir61 on February 14, 2025, 06:39:10 pm
Since I am using inline, I assume the final generated code for the two approaches are going to be very similar if not the same.
Quote from: cdbc on February 14, 2025, 12:22:01 pm
Wow!
That's a whole heap of beating around the bush ...for a simple compare?!?
cdbc's code is much cleaner and is very likely faster. Check his/your version in assembler window.
Title: Re: How to avoid copying
Post by: Amir61 on February 15, 2025, 06:11:54 am
It is not cleaner if Key is a record itself
Title: Re: How to avoid copying
Post by: cdbc on February 15, 2025, 10:06:43 am
Hi
edit: Sorry, two words: {$advancedrecords}  ...and
One word: "class operators"
HTH
Regards Benny
Title: Re: How to avoid copying
Post by: cdbc on February 15, 2025, 10:14:55 am
Hi again
Another way is to write the code like I've changed post #6 into...
Regards Benny
Title: Re: How to avoid copying
Post by: d2010 on February 15, 2025, 10:26:36 am
Quote from: Amir61 on February 14, 2025, 06:02:23 am
How about this case:
Code: Pascal  [Select][+][-]
  1. TPair = record
  2.   First: TKey;
  3.    Second: Tvalue;
  4. end;
  5. Const RTFAIL=-5103;
  6.          RTGOOD= 5200;
  7.  
  8.  
  9.  
  10. PPair = ^TPair;
  11.  
  12. function Compare(P1, P2: Pointer): Integer;
  13. var
  14.   K1, K2: TKey;
  15.  
  16. begin
  17.   if (P1=nil) or (P2=Nil) then Begin result:=RTFAIL; exit;end;
  18.   K1 := PPair(P1).Key;
  19.   K2 := PPair(P2).Key;
  20.  
  21.   // ....
  22.    result:=RTGOOD;
  23. end;
  24.  
The best I could do is the following:
Eu multumesc tie ArsenieBoca.
Code: Pascal  [Select][+][-]
  1. function ComparePointers(P1, P2: Pointer;ElseError): Integer;
  2. begin
  3.    result:=ElseError;
  4.    if (P1=nil) or (P2=nil) then  else
  5.      if (P1<>NIL) and (P2<>nil) and (Cardinal(P1)=Cardinal (P2)) then
  6.     Begin  Writeln('More BetterSpeed Here');  
  7.              result:=RTEQUAL; End else
  8.     Result := ComparePPairs(PPair(P1), PPair(P2));
  9. end;
  10.  
Title: Re: How to avoid copying
Post by: cdbc on February 15, 2025, 10:39:37 am
Hi
@d2010: What a load of utter crap and nonsense!!!
I think you're in over your paygrade, sorry mate...
Regards Benny
Title: Re: How to avoid copying
Post by: BrunoK on February 15, 2025, 04:34:59 pm
Quote from: Amir61 on February 15, 2025, 06:11:54 am
It is not cleaner if Key is a record itself
That would be (untested) :
Code: Pascal  [Select][+][-]
  1. type
  2.   TKey = record
  3.     FTheValue: integer;
  4.   end;
  5.   pKey = ^TKey;
  6.  
  7.   TPair = record
  8.     First: TKey;
  9.     Second: TKey; // Some valid field
  10.   end;
  11.   PPair = ^TPair;
  12.  
  13.   function PairKeyCompare(P1, P2: Pointer): integer;
  14.   var
  15.     pa1: PPair absolute P1;
  16.     pa2: PPair absolute P2;
  17.     pk1, pk2: pKey;
  18.   begin
  19.     pk1 := @pa1^.First;
  20.     pk2 := @pa2^.First;
  21.     if pk1^.FTheValue < pk2^.FTheValue then
  22.       Result := -1
  23.     else if pk1^.FTheValue = pk2^.FTheValue then
  24.       Result := 0
  25.     else
  26.       Result := 1;
  27.   end;
  28.  
Title: Re: How to avoid copying
Post by: d2010 on February 15, 2025, 04:52:39 pm
Quote from: cdbc on February 15, 2025, 10:39:37 am
Hi
@d2010: What a load of utter crap and nonsense!!!
I think you're in over your paygrade, sorry mate...
Regards Benny

If you use   inside any DLL+exe then  your source  PairKeyCompare(P1, P2: Pointer) hangup the memory of cpkunzip.dll
Code: [Select]
Library cpkunzip;
Interface
Function PairCompare(p1,p2:pointer):integer;
var
  pa1: PPair absolute P1;
  pa2: PPair absolute P2;
begin
  if pa1^.Key.First < pa2^.Key.First then Result:= -1
  else if pa1^.Key.First = pa2^.Key.First then Result:= 0
  else Result:= 1;
end;

Var boca:word=000;
Procedure ClearSource_str_Files(dir:String);
Begin
...
  boca:=ord(PairCompare(Dir1,Dir2) = 01 )*1 +
           ord(PairCompare(NamF1,Namf2)=01)*64;
...
End;

Function dfn_clear0dir(dirname:string):integer;
Begin udm_free10spincount:=00;
      odutWcMatch:='*';
      odutWcMatch:='*';
      ClearSource_str_Files(dirname);
      result:=RTGOOD;
End;
Export dfn_clear0dir;
Begin
     boca:=00;
End.
{--}
Title: Re: How to avoid copying
Post by: cdbc on February 15, 2025, 05:01:25 pm
Hi
@d2010: What the H*LL is this:
Code: Pascal  [Select][+][-]
  1. Library cpkunzip;
  2. Interface
  3. Function PairCompare(p1,p2:pointer):integer;
  4. var
  5.   pa1: PPair absolute P1;
  6.   pa2: PPair absolute P2;
  7. begin
  8.   if pa1^.Key.First < pa2^.Key.First then Result:= -1
  9.   else if pa1^.Key.First = pa2^.Key.First then Result:= 0
  10.   else Result:= 1;
  11. end;
  12.  
  13. Var boca:word;
  14. Function ClearSource_str_Files(dir:String);
  15.  
  16. Begin
  17. ...
  18.   boca:=(PairCompare(Dir1,Dir2) = 01 )*1 +
  19.            (PairCompare(NamF1,Namf2)=01)*2;
  20. ...
  21. End;
  22.  
  23. Function dfn_clear0dir(dirname:string):integer;
  24. Begin udm_free10spincount:=00;
  25.       odutWcMatch:='*';
  26.       odutWcMatch:='*';
  27.       ClearSource_str_Files(dirname);
  28.       result:=RTGOOD;
  29. End;
  30. Export dfn_clear0dir;
  31. Begin
  32.      boca:=f00;
  33. End.
  34. {--}
Do you even try to compile these 'Mushroom Dreams' of yours?!?
Oh, I know, it's Saturday and you're smokin' tha weed....
Well, then have fun mate \ö/
Regards Benny
Title: Re: How to avoid copying
Post by: Amir61 on February 16, 2025, 06:32:16 am
@BrunoK

What you are suggesting is equivalent of the pointer approach I described in my starting post, right?
Title: Re: How to avoid copying
Post by: 440bx on February 16, 2025, 07:23:14 am
Here are a couple of modified/simplified versions of @BrunoK's code:
Code: Pascal  [Select][+][-]
  1. program _PointerAbsolute;
  2.  
  3. type
  4.   TKey = record
  5.     FTheValue : integer;
  6.   end;
  7.   pKey = ^TKey;
  8.  
  9.   TPair = record
  10.     First   : TKey;
  11.     Second  : TKey; // Some valid field
  12.   end;
  13.   PPair = ^TPair;
  14.  
  15. function PairKeyCompare1(P1, P2 : Pointer): integer;
  16. var
  17.   pa1    : PPair absolute P1;
  18.   pa2    : PPair absolute P2;
  19.  
  20.   v1, v2 : integer;
  21.  
  22. begin
  23.   { making a copy of the FTheValue fields                                     }
  24.  
  25.   v1 := pa1^.First.FTheValue;
  26.   v2 := pa2^.First.FTheValue;
  27.  
  28.   if v1 < v2 then exit(-1);
  29.   if v1 = v2 then exit(-0);
  30.  
  31.   result := 1;
  32. end;
  33.  
  34. function PairKeyCompare2(P1, P2 : Pointer): integer;
  35. var
  36.   pa1    : PPair absolute P1;
  37.   pa2    : PPair absolute P2;
  38.  
  39. begin
  40.   { without making a copy                                                     }
  41.  
  42.   if pa1^.First.FTheValue < pa2^.First.FTheValue then exit(-1);
  43.   if pa1^.First.FTheValue = pa2^.First.FTheValue then exit(-0);
  44.  
  45.   result := 1;
  46. end;
  47.  
  48. var
  49.   v1, v2 : TPair;
  50.  
  51. begin
  52.   PairKeyCompare1(@v1, @v2);
  53.   PairKeyCompare2(@v1, @v2);
  54.  
  55.   readln;
  56. end.                        
  57.  
Compiled with O4 (max optimization), it produces:

Code: ASM  [Select][+][-]
  1. H:\Dev\Tests\00_PointerAbsolute\PointerAbsolute.lpr:27  v1 := pa1^.First.FTheValue;
  2. 00000001000015D0 8B09                     mov ecx,[rcx]
  3. H:\Dev\Tests\00_PointerAbsolute\PointerAbsolute.lpr:28  v2 := pa2^.First.FTheValue;
  4. 00000001000015D2 8B12                     mov edx,[rdx]
  5. H:\Dev\Tests\00_PointerAbsolute\PointerAbsolute.lpr:30  if v1 < v2 then exit(-1);
  6. 00000001000015D4 39CA                     cmp edx,ecx
  7. 00000001000015D6 7E08                     jle +$08    # $00000001000015E0 PAIRKEYCOMPARE1+16 PointerAbsolute.lpr:31
  8. 00000001000015D8 B8FFFFFFFF               mov eax,$FFFFFFFF
  9. 00000001000015DD C3                       ret
  10.  
  11. 00000001000015DE 6690                     nop
  12.  
  13. ; note that edx and ecx are not reloaded (they don't need to)
  14.  
  15. H:\Dev\Tests\00_PointerAbsolute\PointerAbsolute.lpr:31  if v1 = v2 then exit(-0);
  16. 00000001000015E0 39CA                     cmp edx,ecx
  17. 00000001000015E2 7504                     jnz +$04    # $00000001000015E8 PAIRKEYCOMPARE1+24 PointerAbsolute.lpr:33
  18. 00000001000015E4 31C0                     xor eax,eax
  19. 00000001000015E6 C3                       ret
  20. 00000001000015E7 90                       nop
  21. H:\Dev\Tests\00_PointerAbsolute\PointerAbsolute.lpr:33  result := 1;
  22. 00000001000015E8 B801000000               mov eax,$00000001
  23. H:\Dev\Tests\00_PointerAbsolute\PointerAbsolute.lpr:34  end;
  24. 00000001000015ED C3                       ret
  25.  
  26. 00000001000015EE 0000                     add [rax],al
  27.  
  28. H:\Dev\Tests\00_PointerAbsolute\PointerAbsolute.lpr:44  if pa1^.First.FTheValue < pa2^.First.FTheValue then exit(-1);
  29. 00000001000015F0 8B01                     mov eax,[rcx]
  30. 00000001000015F2 3B02                     cmp eax,[rdx]
  31. 00000001000015F4 7D06                     jnl +$06    # $00000001000015FC PAIRKEYCOMPARE2+12 PointerAbsolute.lpr:45
  32. 00000001000015F6 B8FFFFFFFF               mov eax,$FFFFFFFF
  33. 00000001000015FB C3                       ret
  34. H:\Dev\Tests\00_PointerAbsolute\PointerAbsolute.lpr:45  if pa1^.First.FTheValue = pa2^.First.FTheValue then exit(-0);
  35.  
  36. ; it should use eax again instead of loading the value in ecx
  37.  
  38. 00000001000015FC 8B09                     mov ecx,[rcx]
  39. 00000001000015FE 3B0A                     cmp ecx,[rdx]
  40. 0000000100001600 7506                     jnz +$06    # $0000000100001608 PAIRKEYCOMPARE2+24 PointerAbsolute.lpr:47
  41. 0000000100001602 31C0                     xor eax,eax
  42. 0000000100001604 C3                       ret
  43. 0000000100001605 0F1F00                   nop dword ptr [rax]
  44. H:\Dev\Tests\00_PointerAbsolute\PointerAbsolute.lpr:47  result := 1;
  45. 0000000100001608 B801000000               mov eax,$00000001
  46. H:\Dev\Tests\00_PointerAbsolute\PointerAbsolute.lpr:48  end;
  47. 000000010000160D C3                       ret
  48. 000000010000160E 0000                     add [rax],al
  49. H:\Dev\Tests\00_PointerAbsolute\PointerAbsolute.lpr:53  begin
  50. 0000000100001610 488D6424D8               lea rsp,[rsp-$28]
  51. 0000000100001615 E8B6320000               call +$000032B6    # $00000001000048D0 FPC_INITIALIZEUNITS
  52. H:\Dev\Tests\00_PointerAbsolute\PointerAbsolute.lpr:54  PairKeyCompare1(@v1, @v2);
  53. 000000010000161A 488D15FF090100           lea rdx,[rip+$000109FF]    # $0000000100012020
  54. 0000000100001621 488D0DE8090100           lea rcx,[rip+$000109E8]    # $0000000100012010
  55. 0000000100001628 E8A3FFFFFF               call -$0000005D    # $00000001000015D0 PAIRKEYCOMPARE1 PointerAbsolute.lpr:27
  56. H:\Dev\Tests\00_PointerAbsolute\PointerAbsolute.lpr:55  PairKeyCompare2(@v1, @v2);
  57. 000000010000162D 488D15EC090100           lea rdx,[rip+$000109EC]    # $0000000100012020
  58. 0000000100001634 488D0DD5090100           lea rcx,[rip+$000109D5]    # $0000000100012010
  59. 000000010000163B E8B0FFFFFF               call -$00000050    # $00000001000015F0 PAIRKEYCOMPARE2 PointerAbsolute.lpr:44
  60. H:\Dev\Tests\00_PointerAbsolute\PointerAbsolute.lpr:57  readln;
  61. 0000000100001640 E88B6C0000               call +$00006C8B    # $00000001000082D0 fpc_get_input
  62. 0000000100001645 4889C1                   mov rcx,rax
  63. 0000000100001648 E873710000               call +$00007173    # $00000001000087C0 FPC_READLN_END
  64. 000000010000164D E8DE310000               call +$000031DE    # $0000000100004830 FPC_IOCHECK
  65. H:\Dev\Tests\00_PointerAbsolute\PointerAbsolute.lpr:58  end.
  66. 0000000100001652 E889360000               call +$00003689    # $0000000100004CE0 FPC_DO_EXIT
  67. 0000000100001657 90                       nop
  68. 0000000100001658 488D642428               lea rsp,[rsp+$28]
  69. 000000010000165D C3                       ret
  70.  
The code generated using a copy is faster (and better) than the code generated without using a copy.

TinyPortal © 2005-2018