Re: [fpc-pascal] How to inline CompareFunc to Sort method in generic abstract class

[Adrian Veith via fpc-pascal]

Hi,

with standard generics in pascal there is currently no solution, but you 
can do it with a "poor man's template". They work with .inc files which 
contain the generic part of your code and they are then included in your 
specialization unit. Something like this for a generic sort - I use 
Delphi syntax !:


file mySuperSort.inc:

procedure Run;

var n, i: Integer; swapped: Boolean begin // this is the generic array 
like object you want to sort n  :=  Length(this);

  repeat
swapped  :=  false
for  i:=0 to n-1 do begin // greater is you generic compare
  if  greater(this[i], this[i+1]) then begin
swap(i,  i+1);
swapped  :=  true;
  end;
end;
n  :=  n- 1;
until not swapped;
end;

Now include it at the place where you need it. In most of the cases the 
easiest way is to create a small adapter record/object


type
  TMySortAdapter = record
this: TMyDataArray;
descending: Boolean;
procedure swap(var a, b: TMyDataType); inline;
function greater(a, b: TMyDataType); inline;
procedure sort(data: TMyDataArray; ADescending:Boolean);
  end;

procedure TMySortAdapter.swap(var a, b: TMyDataType);
var t: TMyDataType;
begin
  t:= a;
  a:= b;
  b:= t;
end;

function TMySortAdapter.greater(a, b: TMyDataType);
begin
  if not descending then
Result:= a > b // whatever you need for you compare
  else
Result:= b > a
end;

procedure TMySortAdapter.sort(data: TMyDataArray; ADescending:Boolean);
{$I mySuperSort.inc}
begin
  this:= data;
  descending:= ADescending;
  run;
end;

That's the idea behind "poor man templates". Code completely untested

Not exactly the answer you were looking for, but it works.

Adrian.

Am 14.11.22 um 19:26 schrieb Vojtěch Čihák via fpc-pascal:

Hi,
  
I wrote a generic abstract class - a list based on dynamic array (i.e. array of T;) and this class can be specialized elsewhere with any type (records or classes).

Part of the class is sorting. There are more ways how to deliver *compare 
function* to sorting method. I can pass it as a parameter or I can define it 
as: function Compare(A, B: T): Integer; virtual; abstract;. But this way the 
function cannot be inlined.
  
Question: Is there a way how to *inline* compare function to sorting method in this general purpose generic abstract class?
  
Thanks.
  
PS: The gain is 6-7%.

___
fpc-pascal maillist  -fpc-pascal@lists.freepascal.org
https://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-pascal___
fpc-pascal maillist  -  fpc-pascal@lists.freepascal.org
https://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-pascal

Re: [fpc-pascal] How to inline CompareFunc to Sort method in generic abstract class

[Flávio Etrusco via fpc-pascal]

Em sáb., 19 de nov. de 2022 18:27, Sven Barth via fpc-pascal <
fpc-pascal@lists.freepascal.org> escreveu:

>  (...)
>
>// this kind of constraint that uses T does not work yet
>generic TList> = class
>  procedure Sort;
>end;
>
> (...)
>

No? Sad, I use this all the time in Java.

Best regards,
Flávio


>
___
fpc-pascal maillist  -  fpc-pascal@lists.freepascal.org
https://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-pascal

Re: [fpc-pascal] How to inline CompareFunc to Sort method in generic abstract class

[Flávio Etrusco via fpc-pascal]

Hi,

Thanks for the clarifications (although in some aspects I'm more confused
now LOL).

If you really want the performance gains (and if you're convinced of these
gains, of course) maybe you could implement inlined functions for each key
native datatype taking an offset for the field.

And if you have computed or complex keys, creating an indirection list
would probably have speed gains.

--
Best regards,
Flavio

Em sáb., 19 de nov. de 2022 00:26, Vojtěch Čihák via fpc-pascal <
fpc-pascal@lists.freepascal.org> escreveu:

> Hi,
>
>
>
> I specialized my generic abstract class in a different unit with this type:
>
>
>
> TRec = record
>
> A: Integer;
>
> B: Integer;
>
>   end;
>
>
>
> (A is for sorting, B is for testing of stability, i.e. for MergeSort,
> TimSort)
>
>
>
> and compare function, declared with inline; directive:
>
>
>
> function MyComptFunc(const ARec, BRec: TRec): Integer;
>
> var i, aCnt: Integer;
>
> begin
>
>   aCnt:=CFComplex;
>
>   for i:=0 to aCnt do
>
> Result:=(BRec.A-ARec.A);
>
>   inc(CFCnt);
>
>   //InterlockedIncrement(CFCnt);
>
> end;
>
>
>
> The reason for this complex compare function is that it also measure
> number of comparisons and it can simulate more expensive comparisons (like
> sorting strings).
>
>
>
> For a while, I added this unit to the second "uses" section
> (implementation) of the other unit, which is impractical, but I had
>
> temporary access to the compare function. I tested again with ShellSort,
> sorting 2'000'000 values takes:
>
> 1380ms inlined
>
> 1515ms not inlined, ~9% slower
>
> 1430ms when compare func. is a parameter ~4% slower
>
>
>
> I pass variables by value. But you are right, when I shave the function
> like this:
>
>
>
> function MyComptFunc(const ARec, BRec: TRec): Integer;
>
> begin
>
>   Result:=(BRec.A-ARec.A);
>
> end;
>
>
>
> the results are:
>
> 750ms inlined
>
> 950ms not inlined, ~21% slower
>
> 835ms when compare func. is a parameter ~10% slower
>
>
>
> so the gain of inlining is higher for sorting primitive types.
> V.
>
> __
> > Od: "Flávio Etrusco via fpc-pascal" 
> > Komu: "FPC-Pascal users discussions" 
> > Datum: 18.11.2022 20:45
> > Předmět: Re: [fpc-pascal] How to inline CompareFunc to Sort method in
> generic abstract class
> >
>
>
> Em seg., 14 de nov. de 2022 15:26, Vojtěch Čihák via fpc-pascal <
> fpc-pascal@lists.freepascal.org> escreveu:,
> What do you mean by "be inlined"? The 'inline' directive instructs the
> compiler (or is it the linker? ) to try copying the whole function
> inline, also avoiding the call (stack) setup; you can't do this for this
> for a general purpose method.
> I'm curious how you got that 6% figure, it seems rather large. Is this
> comparing the parameter vs virtual method approach or comparing a fully
> inline (no indirect call of any kind) sort function to some other option?
> Are you passing the variables by reference?
> Best regards,
> Flávio
>
>
> --
>
> ___
> fpc-pascal maillist  -  fpc-pascal@lists.freepascal.org
> https://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-pascal
> ___
> fpc-pascal maillist  -  fpc-pascal@lists.freepascal.org
> https://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-pascal
>
___
fpc-pascal maillist  -  fpc-pascal@lists.freepascal.org
https://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-pascal

Re: [fpc-pascal] How to inline CompareFunc to Sort method in generic abstract class

[Sven Barth via fpc-pascal]

Am 20.11.2022 um 02:02 schrieb Hairy Pixels:



On Nov 20, 2022, at 4:26 AM, Sven Barth via fpc-pascal 
 wrote:

// this kind of constraint that uses T does not work yet
   generic TList> = class
 procedure Sort;
   end;

Does this mean the generic param “Comparer” has a constraint which is "specialize 
TComparer”? I’ve not ever considered this before but I think it solvers the 
problem where I suggested you could use something like traits.


Yes, those are type constraints. As long as you don't use types that 
were introduced in the same parameter list then it already works. E.g.:


=== code begin ===

program Project1;
{$mode objfpc}{$H+}

type
  generic TGen = class
  end;

  generic TTest> = class
  end;

  TGenLongInt = specialize TGen;
  TTestLongInt = specialize TTest;

begin

end.

=== code end ===

Though I wouldn't really compare that with traits.


  What is the challenge involved in implemented that so that it hasn’t been 
done yet? Just curious. :)


Mainly that a temporary symtable needs to be inserted before starting to 
parse the generic parameter types that is then passed along in the 
parser until the parameters are added to the final symbol table of the 
type or routine where the generic parameters reside.



And related since it comes to mind now, what is the reason generics inside of 
generics (like a generic method inside a generic class) are not supported and 
what challenges are involved?


The main problem is that the recording of the tokens and the use of the 
recorded tokens are managed correctly. E.g. should a generic method 
inside a generic class have it's tokens recorded when they're already 
recorded as part of the type and will be recorded again as a separate 
method when the class is specialized?


Regards,
Sven
___
fpc-pascal maillist  -  fpc-pascal@lists.freepascal.org
https://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-pascal

Re: [fpc-pascal] How to inline CompareFunc to Sort method in generic abstract class

[Hairy Pixels via fpc-pascal]

> On Nov 20, 2022, at 4:26 AM, Sven Barth via fpc-pascal 
>  wrote:
> 
> // this kind of constraint that uses T does not work yet
>   generic TList> = class
> procedure Sort;
>   end;

Does this mean the generic param “Comparer” has a constraint which is 
"specialize TComparer”? I’ve not ever considered this before but I think it 
solvers the problem where I suggested you could use something like traits. What 
is the challenge involved in implemented that so that it hasn’t been done yet? 
Just curious. :)

And related since it comes to mind now, what is the reason generics inside of 
generics (like a generic method inside a generic class) are not supported and 
what challenges are involved? 

Seems like generics are maybe lacking some ability of recursion or something…

Regards,
Ryan Joseph

___
fpc-pascal maillist  -  fpc-pascal@lists.freepascal.org
https://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-pascal

Re: [fpc-pascal] How to inline CompareFunc to Sort method in generic abstract class

[Sven Barth via fpc-pascal]

Am 14.11.2022 um 19:26 schrieb Vojtěch Čihák via fpc-pascal:

Hi,
  
I wrote a generic abstract class - a list based on dynamic array (i.e. array of T;) and this class can be specialized elsewhere with any type (records or classes).

Part of the class is sorting. There are more ways how to deliver *compare 
function* to sorting method. I can pass it as a parameter or I can define it 
as: function Compare(A, B: T): Integer; virtual; abstract;. But this way the 
function cannot be inlined.
  
Question: Is there a way how to *inline* compare function to sorting method in this general purpose generic abstract class?


Currently there is not. But once FPC supports reusing types in other 
specializations inside the generic parameter list you /should/ be able 
to do the following:


=== code begin ===

program tinline;

{$mode objfpc}

type
  generic TComparer = class
    class function Compare(aLeft, aRight: T): Integer;
  end;

  // this kind of constraint that uses T does not work yet
  generic TList> = class
    procedure Sort;
  end;

  TLongIntComparer = class(specialize TComparer)
    class function Compare(aLeft, aRight: T): Integer; inline;
  end;

class function TComparer.Compare(aLeft, aRight: T): Integer;
begin
  Result := 0;
end;

procedure TList.Sort;
begin
  { sort algorithm that calls Comparer.Sort which /should/ be inlined }
end;

class function TLongInt.Compare(aLeft, aRight: T): Integer;
begin
  if aLeft < aRight then
    Result := -1
  else if aLeft > aRight then
    Result := 1
  else
    Result := 0;
end;

var
  l: specialize TList;
begin
  l : =specialize TList.Create;
  l.Sort;
end.

=== code end ===

I can't test this currently whether it would really work due to the 
missing functionality, but it's at least possible.


Regards,
Sven
___
fpc-pascal maillist  -  fpc-pascal@lists.freepascal.org
https://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-pascal

Re: [fpc-pascal] How to inline CompareFunc to Sort method in generic abstract class

[Sven Barth via fpc-pascal]

Am 18.11.2022 um 20:44 schrieb Flávio Etrusco via fpc-pascal:



Em seg., 14 de nov. de 2022 15:26, Vojtěch Čihák via fpc-pascal 
 escreveu:


Hi,

I wrote a generic abstract class - a list based on dynamic array
(i.e. array of T;) and this class can be specialized elsewhere
with any type (records or classes).
Part of the class is sorting. There are more ways how to deliver
*compare function* to sorting method. I can pass it as a parameter
or I can define it as: function Compare(A, B: T): Integer;
virtual; abstract;. But this way the function cannot be inlined.

Question: Is there a way how to *inline* compare function to
sorting method in this general purpose generic abstract class?

Thanks.

PS: The gain is 6-7%.


Hi,

What do you mean by "be inlined"? The 'inline' directive instructs the 
compiler (or is it the linker? ) to try copying the whole function 
inline, also avoiding the call (stack) setup; you can't do this for 
this for a general purpose method.


Inlining is done by the compiler, not the linker. Also inlining does 
work for methods (at least in general; there are exceptions to this, 
e.g. if the method is virtual or uses "inherited"). What it can't be 
done with is method pointers (or function pointers).


Regards,
Sven___
fpc-pascal maillist  -  fpc-pascal@lists.freepascal.org
https://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-pascal

Re: [fpc-pascal] How to inline CompareFunc to Sort method in generic abstract class

[Vojtěch Čihák via fpc-pascal]

Hi,
 
I specialized my generic abstract class in a different unit with this type:
 
TRec = record
    A: Integer;
    B: Integer;
  end;
 
(A is for sorting, B is for testing of stability, i.e. for MergeSort, TimSort)
 
and compare function, declared with inline; directive:
 
function MyComptFunc(const ARec, BRec: TRec): Integer;
var i, aCnt: Integer;
begin
  aCnt:=CFComplex;
  for i:=0 to aCnt do
    Result:=(BRec.A-ARec.A);
  inc(CFCnt);
  //InterlockedIncrement(CFCnt);
end;              
 
The reason for this complex compare function is that it also measure number of 
comparisons and it can simulate more expensive comparisons (like sorting 
strings).
 
For a while, I added this unit to the second "uses" section (implementation) of 
the other unit, which is impractical, but I had
temporary access to the compare function. I tested again with ShellSort, 
sorting 2'000'000 values takes:
1380ms inlined
1515ms not inlined, ~9% slower
1430ms when compare func. is a parameter ~4% slower
 
I pass variables by value. But you are right, when I shave the function like 
this:
 
function MyComptFunc(const ARec, BRec: TRec): Integer;
begin
  Result:=(BRec.A-ARec.A);
end;
 
the results are:
750ms inlined
950ms not inlined, ~21% slower
835ms when compare func. is a parameter ~10% slower
 
so the gain of inlining is higher for sorting primitive types.
V.__

Od: "Flávio Etrusco via fpc-pascal" 
Komu: "FPC-Pascal users discussions" 
Datum: 18.11.2022 20:45
Předmět: Re: [fpc-pascal] How to inline CompareFunc to Sort method in generic 
abstract class




Em seg., 14 de nov. de 2022 15:26, Vojtěch Čihák via fpc-pascal > escreveu:,What do you mean by "be inlined"? The 
'inline' directive instructs the compiler (or is it the linker? ) to try copying the whole function 
inline, also avoiding the call (stack) setup; you can't do this for this for a general purpose 
method.I'm curious how you got that 6% figure, it seems rather large. Is this comparing the parameter 
vs virtual method approach or comparing a fully inline (no indirect call of any kind) sort function 
to some other option? Are you passing the variables by reference?Best regards,Flávio

--

___
fpc-pascal maillist  -  fpc-pascal@lists.freepascal.org
https://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-pascal 


___
fpc-pascal maillist  -  fpc-pascal@lists.freepascal.org
https://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-pascal

Re: [fpc-pascal] How to inline CompareFunc to Sort method in generic abstract class

[Flávio Etrusco via fpc-pascal]

Em seg., 14 de nov. de 2022 15:26, Vojtěch Čihák via fpc-pascal <
fpc-pascal@lists.freepascal.org> escreveu:

> Hi,
>
> I wrote a generic abstract class - a list based on dynamic array (i.e.
> array of T;) and this class can be specialized elsewhere with any type
> (records or classes).
> Part of the class is sorting. There are more ways how to deliver *compare
> function* to sorting method. I can pass it as a parameter or I can define
> it as: function Compare(A, B: T): Integer; virtual; abstract;. But this way
> the function cannot be inlined.
>
> Question: Is there a way how to *inline* compare function to sorting
> method in this general purpose generic abstract class?
>
> Thanks.
>
> PS: The gain is 6-7%.
>

Hi,

What do you mean by "be inlined"? The 'inline' directive instructs the
compiler (or is it the linker? ) to try copying the whole function
inline, also avoiding the call (stack) setup; you can't do this for this
for a general purpose method.
I'm curious how you got that 6% figure, it seems rather large. Is this
comparing the parameter vs virtual method approach or comparing a fully
inline (no indirect call of any kind) sort function to some other option?
Are you passing the variables by reference?

Best regards,
Flávio
___
fpc-pascal maillist  -  fpc-pascal@lists.freepascal.org
https://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-pascal

Re: [fpc-pascal] How to inline CompareFunc to Sort method in generic abstract class

[Hairy Pixels via fpc-pascal]

There’s no way since FPC can’t inline function pointers (I asked already a 
while ago).

It depends on what’s in your list but you can often override comparison 
operators (like =, < and >) or restructure your classes so there is a base last 
and then 2+ subclasses that have the top level sorting methods.

Another idea is to use something like traits and pass in a sorter to the list 
class on construction which does the sorting and has inlined comparison 
functions.

> On Nov 15, 2022, at 1:26 AM, Vojtěch Čihák via fpc-pascal 
>  wrote:
> 
> Hi,
>  
> I wrote a generic abstract class - a list based on dynamic array (i.e. array 
> of T;) and this class can be specialized elsewhere with any type (records or 
> classes).
> Part of the class is sorting. There are more ways how to deliver *compare 
> function* to sorting method. I can pass it as a parameter or I can define it 
> as: function Compare(A, B: T): Integer; virtual; abstract;. But this way the 
> function cannot be inlined.
>  
> Question: Is there a way how to *inline* compare function to sorting method 
> in this general purpose generic abstract class?
>  
> Thanks.
>  
> PS: The gain is 6-7%.  
> ___
> fpc-pascal maillist  -  fpc-pascal@lists.freepascal.org
> https://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-pascal

Regards,
Ryan Joseph

___
fpc-pascal maillist  -  fpc-pascal@lists.freepascal.org
https://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-pascal

[fpc-pascal] How to inline CompareFunc to Sort method in generic abstract class

[Vojtěch Čihák via fpc-pascal]

Hi,
 
I wrote a generic abstract class - a list based on dynamic array (i.e. array of 
T;) and this class can be specialized elsewhere with any type (records or 
classes).
Part of the class is sorting. There are more ways how to deliver *compare 
function* to sorting method. I can pass it as a parameter or I can define it 
as: function Compare(A, B: T): Integer; virtual; abstract;. But this way the 
function cannot be inlined.
 
Question: Is there a way how to *inline* compare function to sorting method in 
this general purpose generic abstract class?
 
Thanks.
 
PS: The gain is 6-7%.  
___
fpc-pascal maillist  -  fpc-pascal@lists.freepascal.org
https://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-pascal