Generics vs templates

classic Classic list List threaded Threaded
19 messages Options
Reply | Threaded
Open this post in threaded view
|

Generics vs templates

Ryan Joseph
I was talking with a c++ developer who explained how templates are implemented in c++ and how use some recursive method which causes them to totally murder compile times. This isn’t the first I’ve heard of the problem though and I recall some game studios who develop engines in c++ saying they are strictly off limits for the same reasons.

Having just started to use generics in FPC myself I was curious if FPC suffers from the same problem of slow compile times?

Regards,
        Ryan Joseph

_______________________________________________
fpc-pascal maillist  -  [hidden email]
http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-pascal
Reply | Threaded
Open this post in threaded view
|

Re: Generics vs templates

Free Pascal - General mailing list
Am 08.01.2018 08:50 schrieb "Ryan Joseph" <[hidden email]>:
I was talking with a c++ developer who explained how templates are implemented in c++ and how use some recursive method which causes them to totally murder compile times. This isn’t the first I’ve heard of the problem though and I recall some game studios who develop engines in c++ saying they are strictly off limits for the same reasons.

Having just started to use generics in FPC myself I was curious if FPC suffers from the same problem of slow compile times?

FPC essentially reparses a generic during specialization so I'd say that they definitely affect compile times. However we're still only doing a single pass of parsing. This while the compilation might be slower it might not be as bad as with a C++ compiler. 

As far as I know no one has done a benchmark for that however. 

Regards, 
Sven 

_______________________________________________
fpc-pascal maillist  -  [hidden email]
http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-pascal
Reply | Threaded
Open this post in threaded view
|

Re: Generics vs templates

Mattias Gaertner
In reply to this post by Ryan Joseph
On Mon, 8 Jan 2018 14:19:42 +0700
Ryan Joseph <[hidden email]> wrote:

> I was talking with a c++ developer who explained how templates are implemented in c++ and how use some recursive method which causes them to totally murder compile times.
> Having just started to use generics in FPC myself I was curious if FPC suffers from the same problem of slow compile times?

C++ templates are Turing complete. FPC generics are not.

https://en.wikipedia.org/wiki/Template_metaprogramming

Mattias
_______________________________________________
fpc-pascal maillist  -  [hidden email]
http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-pascal
Reply | Threaded
Open this post in threaded view
|

Re: Generics vs templates

Ryan Joseph
In reply to this post by Free Pascal - General mailing list


> On Jan 8, 2018, at 5:58 PM, Sven Barth via fpc-pascal <[hidden email]> wrote:
>
> FPC essentially reparses a generic during specialization so I'd say that they definitely affect compile times.

Does c++  not “specialize” in one location like FPC? looking at c++ code I often see things like Vector<x> used in multiple locations instead of declaring a single type (I have no idea why they would do that but it’s very common). Maybe that’s why compile times are so slow?

In one instance I did something similar but hopefully it “unfolds” only once when the unit compiles. Is that true?

type
        generic TStaticArray<T> = class (TObject)
        end;

type
        generic TDynamicArray<T> = class (specialize TStaticArray<T>)
        end;

type
        generic TGenericArray<T> = class (specialize TDynamicArray<T>)
        end;

type
        TIntegerArray = specialize TGenericArray<Integer>;
        TLongIntArray = specialize TGenericArray<LongInt>;
        TStringArray = specialize TGenericArray<String>;
        TSingleArray = specialize TGenericArray<Single>;
        TDoubleArray = specialize TGenericArray<Double>;
        TFloatArray = specialize TGenericArray<TFloat>;
        TPointerArray = specialize TGenericArray<Pointer>;

Regards,
        Ryan Joseph

_______________________________________________
fpc-pascal maillist  -  [hidden email]
http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-pascal
Reply | Threaded
Open this post in threaded view
|

Re: Generics vs templates

Free Pascal - General mailing list
Am 08.01.2018 12:52 schrieb "Ryan Joseph" <[hidden email]>:


> On Jan 8, 2018, at 5:58 PM, Sven Barth via fpc-pascal <[hidden email]> wrote:
>
> FPC essentially reparses a generic during specialization so I'd say that they definitely affect compile times.

Does c++  not “specialize” in one location like FPC? looking at c++ code I often see things like Vector<x> used in multiple locations instead of declaring a single type (I have no idea why they would do that but it’s very common). Maybe that’s why compile times are so slow?

C++ specializes once per compilation unit (and per unique type parameters). FPC does this as well, but in addition it will try to reuse a compatible specialization that's located in the interface section of a used unit. 

Regards, 
Sven

_______________________________________________
fpc-pascal maillist  -  [hidden email]
http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-pascal
Reply | Threaded
Open this post in threaded view
|

Re: Generics vs templates

Graeme Geldenhuys-6
In reply to this post by Free Pascal - General mailing list
On 2018-01-08 10:58, Sven Barth via fpc-pascal wrote:
> FPC essentially reparses a generic during specialization so I'd say that
> they definitely affect compile times. However we're still only doing a
> single pass of parsing. This while the compilation might be slower it might
> not be as bad as with a C++ compiler.
>
> As far as I know no one has done a benchmark for that however.


Speaking of Generics and Benchmarks. Has anybody done some benchmarks on
FPC's Generics vs "old-school" TList and TObjectList. Recently I did a
very simple test with Delphi XE3 using TList<Integer> and a stock TList.
Adding 50,000 and 200,000 integer values to each list, and timing the
creation of the list and population of the list. Then I also timed the
destruction of the list. I was horified to find out how much slower
Delphi's Generics were compared to TList and TObjectList. Destruction
was 250x slower in many cases. Creation and population of the list was
5x-10x slower.

Lets hope FPC fares better. If nobody has done such tests, I can do it
tomorrow at work with the same Delphi test code I created.


Regards,
   Graeme

--
fpGUI Toolkit - a cross-platform GUI toolkit using Free Pascal
http://fpgui.sourceforge.net/

My public PGP key:  http://tinyurl.com/graeme-pgp
_______________________________________________
fpc-pascal maillist  -  [hidden email]
http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-pascal
Reply | Threaded
Open this post in threaded view
|

Re: Generics vs templates

Giuliano Colla
Il 08/01/2018 21:30, Graeme Geldenhuys ha scritto:

> I was horified to find out how much slower Delphi's Generics were
> compared to TList and TObjectList

I don't expect FPC behave much better. Whenever you move something from
compile time to execution time you may gain in flexibility, but you
surely lose in performance. Whenever a generic can be replaced by an if
.. then .. else .., using a generic is just an useless performance killer.
The same holds true for using a TObject, when a record would be enough
or for using an Interface instead of just linking the appropriate
library when this would be possible (see Lazarus vs fpGui!).

Giuliano

_______________________________________________
fpc-pascal maillist  -  [hidden email]
http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-pascal
Reply | Threaded
Open this post in threaded view
|

Re: Generics vs templates

Ryan Joseph
In reply to this post by Graeme Geldenhuys-6


> On Jan 9, 2018, at 3:30 AM, Graeme Geldenhuys <[hidden email]> wrote:
>
> Recently I did a very simple test with Delphi XE3 using TList<Integer> and a stock TList. Adding 50,000 and 200,000 integer values to each list, and timing the creation of the list and population of the list. Then I also timed the destruction of the list. I was horified to find out how much slower Delphi's Generics were compared to TList and TObjectList. Destruction was 250x slower in many cases. Creation and population of the list was 5x-10x slower.

What does this have to do with generics exactly? If I understand correctly generics are “meta-programming” where they essentially just re-insert a generated class based on the template (c++’s naming scheme makes more sense imo) but they don’t actually add any runtime code.

Regards,
        Ryan Joseph

_______________________________________________
fpc-pascal maillist  -  [hidden email]
http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-pascal
Reply | Threaded
Open this post in threaded view
|

Re: Generics vs templates

Free Pascal - General mailing list
Am 09.01.2018 02:59 schrieb "Ryan Joseph" <[hidden email]>:


> On Jan 9, 2018, at 3:30 AM, Graeme Geldenhuys <[hidden email]> wrote:
>
> Recently I did a very simple test with Delphi XE3 using TList<Integer> and a stock TList. Adding 50,000 and 200,000 integer values to each list, and timing the creation of the list and population of the list. Then I also timed the destruction of the list. I was horified to find out how much slower Delphi's Generics were compared to TList and TObjectList. Destruction was 250x slower in many cases. Creation and population of the list was 5x-10x slower.

What does this have to do with generics exactly? If I understand correctly generics are “meta-programming” where they essentially just re-insert a generated class based on the template (c++’s naming scheme makes more sense imo) but they don’t actually add any runtime code.

But you need to program in a way that allows the usage of multiple, different types. That can more often than not lead to worse performance. 

Regards, 
Sven 

_______________________________________________
fpc-pascal maillist  -  [hidden email]
http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-pascal
Reply | Threaded
Open this post in threaded view
|

Re: Generics vs templates

Ryan Joseph


> On Jan 9, 2018, at 2:04 PM, Sven Barth via fpc-pascal <[hidden email]> wrote:
>
> But you need to program in a way that allows the usage of multiple, different types. That can more often than not lead to worse performance.
>

Examples? I had to add some if statements in a couple areas I didn’t want to and a virtual method but beyond that I don’t see what would affect performance.

Regards,
        Ryan Joseph

_______________________________________________
fpc-pascal maillist  -  [hidden email]
http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-pascal
Reply | Threaded
Open this post in threaded view
|

Re: Generics vs templates

Free Pascal - General mailing list
Am 09.01.2018 08:13 schrieb "Ryan Joseph" <[hidden email]>:


> On Jan 9, 2018, at 2:04 PM, Sven Barth via fpc-pascal <[hidden email]> wrote:
>
> But you need to program in a way that allows the usage of multiple, different types. That can more often than not lead to worse performance.
>

Examples? I had to add some if statements in a couple areas I didn’t want to and a virtual method but beyond that I don’t see what would affect performance.

Precisely these virtual methods are one point. They might not add much by themselves, but if they're called for each Add or Remove operation they can add quite a bit.
Why do you think that the TFP(Object)List classes don't have notification support unlike T(Object)List? Even if it only checks whether a notification handler is assigned it's enough for a noticeable difference in performance. 

Regards, 
Sven 

_______________________________________________
fpc-pascal maillist  -  [hidden email]
http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-pascal
Reply | Threaded
Open this post in threaded view
|

Re: Generics vs templates

Michael Schnell
In reply to this post by Free Pascal - General mailing list
On 09.01.2018 08:04, Sven Barth via fpc-pascal wrote:
But you need to program in a way that allows the usage of multiple, different types. That can more often than not lead to worse performance.
Seemingly it is done that way.

I rather often did a kind of "Generics" in ANSI C by using Macros. It's catastrophic for code writing and for debugging but does not impose any performance issues.

I suppose there is a reason why in Pascal Generics are not translated in multiple dedicatedly typed code snippets at compile time.

-Michael

_______________________________________________
fpc-pascal maillist  -  [hidden email]
http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-pascal
Reply | Threaded
Open this post in threaded view
|

Re: Generics vs templates

Maciej Izak
In reply to this post by Graeme Geldenhuys-6
2018-01-08 21:30 GMT+01:00 Graeme Geldenhuys <[hidden email]>:
Speaking of Generics and Benchmarks. Has anybody done some benchmarks on FPC's Generics vs "old-school" TList and TObjectList. Recently I did a very simple test with Delphi XE3 using TList<Integer> and a stock TList. Adding 50,000 and 200,000 integer values to each list, and timing the creation of the list and population of the list. Then I also timed the destruction of the list. I was horified to find out how much slower Delphi's Generics were compared to TList and TObjectList. Destruction was 250x slower in many cases. Creation and population of the list was 5x-10x slower.

Lets hope FPC fares better. If nobody has done such tests, I can do it tomorrow at work with the same Delphi test code I created.

It depends on use case and on library design. For example in the FPC case, generic TList<T> has better performance for larger lists (the capacity uses golden ratio) than regular TList (for Integers). The performance difference in daily usage is rather minor (if any). 

We have available detailed tests for generic and non generics hash maps thanks to Benito van der Zander (FPC has so many different maps! :) ):


The results for rtl-generics should be better soon. I am working on new version of rtl-generics library, so all should works faster (better hashing function + optimizations for managed types - especially improved for incoming smart pointers/objects). 
 
--
Best regards,
Maciej Izak

_______________________________________________
fpc-pascal maillist  -  [hidden email]
http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-pascal
Reply | Threaded
Open this post in threaded view
|

Re: Generics vs templates

Graeme Geldenhuys-6
In reply to this post by Ryan Joseph
On 2018-01-09 01:29, Ryan Joseph wrote:
> What does this have to do with generics exactly?

Everything I guess. ;-) That was the point of my reply.

When using the Generics.Collections unit of Delphi I can define a list
class that can hold Integer data types, by doing the following:

   var
     IntList: TList<Integer>;
   begin
     IntList := TList<Integer>.Create;
     IntList.Add(12345);

How Generics does that (how it is implemented underneath), I don't know
- I never bothered to look. All I'm saying is that in our company the
developers love Generics, but then can't understand why performance
degrades is some areas of our project. Further testing revealed that the
usage of Generics was partly to blame.

I then investigated this, and compared some of those lists, and
implementing the equivalent manually (using TList, TObjectList and
such). For example, the above code example can be accomplish with a
TList only.

   var
     IntList: TList;
   begin
     IntList := TList.Create;
     IntList.Add(Pointer(12345));

Yes, the second code sample might not look so nice (the casting), but it
was just the simplest and quickest example I could knock up to store
integers in a list. Either way, the non-Generics code example was
considerably faster in adding and freeing itself.

This was just one example. TObjectList (or a customised descendant...
eg: TAddressList) was another case where it was way faster than
Generics.Collections.pas unit provided.

Like I said, this was all tested under Delphi XE3. I didn't have time
today to test under FPC, but will try and do so tomorrow.


Regards,
   Graeme

--
fpGUI Toolkit - a cross-platform GUI toolkit using Free Pascal
http://fpgui.sourceforge.net/

My public PGP key:  http://tinyurl.com/graeme-pgp
_______________________________________________
fpc-pascal maillist  -  [hidden email]
http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-pascal
Reply | Threaded
Open this post in threaded view
|

Re: Generics vs templates

Ryan Joseph


> On Jan 10, 2018, at 6:37 AM, Graeme Geldenhuys <[hidden email]> wrote:
>
> When using the Generics.Collections unit of Delphi I can define a list class that can hold Integer data types, by doing the following:
>
>  var
>    IntList: TList<Integer>;
>  begin
>    IntList := TList<Integer>.Create;
>    IntList.Add(12345);

I presume then TList<> and TList class are not implemented the same then because I still don’t know how the generic itself affects runtime performance.

Btw this looks like C# code because C# explicitly does not specialize at compile time but rather runtime so every instance will be using TList<Integer>. Does Delphi do this also? I think FPC requires you MUST specialize at compile time so simply using TList<Integer> won’t compile.

Regards,
        Ryan Joseph

_______________________________________________
fpc-pascal maillist  -  [hidden email]
http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-pascal
Reply | Threaded
Open this post in threaded view
|

Re: Generics vs templates

Marco van de Voort
In reply to this post by Free Pascal - General mailing list
In our previous episode, Sven Barth via fpc-pascal said:
> Precisely these virtual methods are one point. They might not add much by
> themselves, but if they're called for each Add or Remove operation they can
> add quite a bit.
> Why do you think that the TFP(Object)List classes don't have notification
> support unlike T(Object)List? Even if it only checks whether a notification
> handler is assigned it's enough for a noticeable difference in performance.

But Graeme compared Delphi TList to Delphi TList<> so both have notifiers?
_______________________________________________
fpc-pascal maillist  -  [hidden email]
http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-pascal
Reply | Threaded
Open this post in threaded view
|

Re: Generics vs templates

Free Pascal - General mailing list
Am 10.01.2018 07:39 schrieb "Marco van de Voort" <[hidden email]>:
In our previous episode, Sven Barth via fpc-pascal said:
> Precisely these virtual methods are one point. They might not add much by
> themselves, but if they're called for each Add or Remove operation they can
> add quite a bit.
> Why do you think that the TFP(Object)List classes don't have notification
> support unlike T(Object)List? Even if it only checks whether a notification
> handler is assigned it's enough for a noticeable difference in performance.

But Graeme compared Delphi TList to Delphi TList<> so both have notifiers?

That was more about what a difference the existence of notifiers can have to highlight what performance difference generic capable code can have compared to non-generic code. 

Regards, 
Sven 

_______________________________________________
fpc-pascal maillist  -  [hidden email]
http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-pascal
Reply | Threaded
Open this post in threaded view
|

Re: Generics vs templates

Free Pascal - General mailing list
In reply to this post by Ryan Joseph
Am 10.01.2018 05:10 schrieb "Ryan Joseph" <[hidden email]>:


> On Jan 10, 2018, at 6:37 AM, Graeme Geldenhuys <[hidden email]> wrote:
>
> When using the Generics.Collections unit of Delphi I can define a list class that can hold Integer data types, by doing the following:
>
>  var
>    IntList: TList<Integer>;
>  begin
>    IntList := TList<Integer>.Create;
>    IntList.Add(12345);

I presume then TList<> and TList class are not implemented the same then because I still don’t know how the generic itself affects runtime performance.

Btw this looks like C# code because C# explicitly does not specialize at compile time but rather runtime so every instance will be using TList<Integer>. Does Delphi do this also? I think FPC requires you MUST specialize at compile time so simply using TList<Integer> won’t compile.

That are two orthogonal points. FPC and Delphi both allow inline specializations which is what you see above (in the non-Delphi modes of course with the "specialize" keyword). That doesn't change that such specializations are done at compile time. For the compiler it is as if the type "TList<Integer>" exists as a full type wherever it is used. 

Regards, 
Sven 

_______________________________________________
fpc-pascal maillist  -  [hidden email]
http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-pascal
Reply | Threaded
Open this post in threaded view
|

Re: Generics vs templates

Free Pascal - General mailing list
In reply to this post by Michael Schnell
Am 11.01.2018 08:06 schrieb "Michael Schnell" <[hidden email]>:
On 09.01.2018 08:04, Sven Barth via fpc-pascal wrote:
But you need to program in a way that allows the usage of multiple, different types. That can more often than not lead to worse performance.
Seemingly it is done that way.

I rather often did a kind of "Generics" in ANSI C by using Macros. It's catastrophic for code writing and for debugging but does not impose any performance issues.

I suppose there is a reason why in Pascal Generics are not translated in multiple dedicatedly typed code snippets at compile time.

Huh? A generic is reparsed for every type tuple it is specialized with (except of course it already finds an existing previous specialization for these types), but you need to write the generic's code in a way that satisfies the parser for all these types (though FPC is more lenient here than Delphi). 

Regards, 
Sven

_______________________________________________
fpc-pascal maillist  -  [hidden email]
http://lists.freepascal.org/cgi-bin/mailman/listinfo/fpc-pascal