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%.  

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.

Regards,
Ryan Joseph

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

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

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.______________________________________________________________

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

----------

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

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<T> = class
     class function Compare(aLeft, aRight: T): Integer;
   end;
   // this kind of constraint that uses T does not work yet
   generic TList<T; Comparer: specialize TComparer<T>> = class
     procedure Sort;
   end;
   TLongIntComparer = class(specialize TComparer<LongInt>)
     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<LongInt>;
begin
   l : =specialize TList<LongInt, TLongIntComparer>.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

Does this mean the generic param “Comparer” has a constraint which is "specialize TComparer<T>”? 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

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<T> = class
   end;
   generic TTest<T: specialize TGen<LongInt>> = class
   end;
   TGenLongInt = specialize TGen<LongInt>;
   TTestLongInt = specialize TTest<TGenLongInt>;
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

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.

Em sáb., 19 de nov. de 2022 18:27, Sven Barth via fpc-pascal <

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

Best regards,
Flávio

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.