PDA

View Full Version : Generic collections



Mirage
27-06-2014, 02:50 PM
We'll need some collection classes and algorithms which will be used everywhere in engine.
Requirements:

implementation of at least List, Map (dictionary) and sorting
work with different types, including primitive ones (non classes)
high performance
type safe
without code duplication

Class/interface based approaches are not comply with requirement #2 and #3.
Pointer-based implementations conflicts with requirement #4.
I know two remaining solutions:
1. Generics.
+ intended to solve this problem exactly
- not supported by Delphi 7 and FPC 2.6.2
2. include-based template approach
+ max performance and flexibility
+ support of D7 and FPC 2.6.2
- only one instantiation of each template per unit
- hard to read and support template code (does not apply to code using the templates)

I've implementation of the second approach:
https://github.com/casteng/base/tree/dev/template
You can see what it looks like.

We can drop support of D7 and FPC 2.6.2 and go with generics.
What do you think guys?

pitfiend
28-06-2014, 03:52 AM
Unacceptable. One of the main reasons we are doing this, is because we want to support every version since D7 and all fpc. Another reason is that generics make your app increase in size every time you use another instance of the same library for another purpose. What I was thinking, is to implement some kind of double linked list or btree using pointers (maybe both), advantage we can put anything inside, it's faster than anything, small footprint.

gasdeveloper
28-06-2014, 07:01 AM
Personally I like generics. I find them easy to use and a perfect fit for this situation. As for for the support of D7 and FPC 2.6.2 I understand the support for D7 but FPC is free, anyone can get a newer version. This shouldn't be a factor when deciding how to implement. Just my 2 cents.

Mirage
28-06-2014, 07:33 AM
pitfiend, pointer-based approach is not type safe (remember why we using Pascal?) and has poor data locality, and therefore performance.
So we need to implement collections for each type. Good news that size increase is negligible in case of a few collections and algorithms.

gasdeveloper, the problem with generics is compatibility between Delphi and FPC syntax. I don't know exactly which FPC version is ok for this. Generics with FPC syntax are supported from FPC 2.2.

dj_sharp
28-06-2014, 09:00 AM
I vote for include-based template approach

pitfiend
28-06-2014, 04:42 PM
pitfiend, pointer-based approach is not type safe (remember why we using Pascal?) and has poor data locality, and therefore performance.
So we need to implement collections for each type. Good news that size increase is negligible in case of a few collections and algorithms.

Can't agree on that. One of the most important language features is going to be left just because we use Pascal? A well designed structure and helpers could solve any of our needs. I also think that we must build real objects and not classes, they are faster, have inheritance and also very small footprint. And yes, I am an old school developer.

code_glitch
28-06-2014, 07:27 PM
Would it not be possible to get some polls of who is using which FPC versions and decide then? Personally, I think that if we're making a new engine for the future, it'd be a contradiction to not use some newer features for the sake of backwards compatibility. A couple years down the line, I don't think it'll be very likely we'll alienate people from the engine on account of them not being able to get their hands on a copy of delphi newer than 7 or fpc 2.6.2 (I think it was?).

At a glance it looks like it complicates things and almost causes us to work around a feature just to provide support for what is already considered old software (delphi 7 has been around as long as I can remember) which is already pseudo-irrelevant and will only become more so as times goes on.

SilverWarior
28-06-2014, 08:49 PM
I'm also gainst the use of generics:
1. As it was sad before using generics greatly increases the size of executable.
2. Generics offer much lower performance. I maself rather go and gwite several thousands lines of code more than have mush poorer peroformance.
3. Debuging of code that uses generics is much harder.
4. Delphi compliler is known to sometimes simply fail in compiting generics code. This was reported long ago and still hasn't been fixed entirely.

pitfiend
28-06-2014, 09:02 PM
My position is against using anything that can impact negatively on performance. Using generics is a bad idea, the support on delphi is not very stable neither optimal and fpc is a mess. If we want to make an engine solid, stable and optimal we need things that provide that, also we are not building this for the casual programer and we'll try to make as much documentation as we can provide. BTW, tlist component, a critical component for nearby any kind of list is build with pointers.

AthenaOfDelphi
29-06-2014, 07:42 AM
I've found generics to be useful and reliable in Delphi. I can't comment on performance, but I have no reason to suspect it's poor given the generic part of this is handled at compile time.

So, how about we do what we would probably all do if we encountered this question in our day jobs... lets establish some facts. The key questions here seem to be:-

Do generics have an adverse affect on the size of the compiled binaries?
Are generics stable in both Delphi and FPC? - This might be tricky to prove one way or the other
What are the differences between Delphi and FPC generics?

Personally, I have no problem using them, but it's not just my choice, so does someone (or a collection of people) want to take on a task and get some answers? Then when we have a realistic view of the current state of affairs we can make an educated decision. This of course won't answer the question about whether we drop the idea of supporting D7 which is still very popular I believe. But, the technical side may make the decision easier... if the differences between FPC and Delphi are too great for example, regardless of the other factors, generics would be a non-starter if they are going to need lots of conditionals and such, but then depending on just how different they are we may be able to get around it by creating compiler specific versions of the classes we're talking about.

So, plan of action... let's establish the answers to the key questions and then make a decision based on hard facts.

dj_sharp
29-06-2014, 08:39 AM
Free Pascal has several Pascal syntax modes: FPC, TurboPascal, Object Free Pascal, Delphi and Mac Pascal (whatever it is). Maybe something else I forgot to mention. Objective-C maybe. In Object Free Pascal mode generics are incompatible with Delphi because apparently Free Pascal developers invented their own syntax for generics; however in Delphi syntax mode Free Pascal generics syntax conforms to Delphi generics syntax (more or less). While Free Pascal might not support latest additions to generics introduced in Delphi, it should be able to compile simplier cases; so in general it should be possible to compile same source code with generics both in FreePascal and Delphi.
Most likely, Free Pascal does not support generic constraints: this TIntfListGenericType<T: IInterfaceList> thing

pitfiend
29-06-2014, 10:36 PM
Earlier here in PGD, there was a topic around generics http://www.pascalgamedevelopment.com/showthread.php?6592-Difference-between-FPC-Generics-and-Delphi-Generics and Murmandamus wrote something interesting about http://www.pascalgamedevelopment.com/showthread.php?6592-Difference-between-FPC-Generics-and-Delphi-Generics&p=52445&viewfull=1#post52445 maybe in the time since the post, FPC generics are more compatible, I don't know.

dj_sharp
30-06-2014, 08:10 PM
they are supposed to be compatible in Delphi mode ( {$mode Delphi} )

I still vote for templates with include files though

laggyluk
01-07-2014, 01:33 PM
maybe use whichever is faster in engine internals and leave choice on using generics to engine 'end' users?
imo modern engine should run on many platforms out of the box and expose scripting language as main way of coding the game.
ability to mess with the source code is a big advantage but not everyone would need or want that