Hi everyone,

I may be missing the obvious here, but I've noticed that there are some notable absences in the Free Generics Library.  While there's a standard list and a map and the like, there aren't any of the special lists like a stack and a queue and the like.  It proved slightly problematic while in a mentoring session with another programmer whom I was introducing to Free Pascal, because our sample project required a stack.  The standard TStack uses pointers, which is not exactly portable.

If not present, can I request the addition of TFPGStack and TFPGQueue to the Free Generics Library? They should be simple descendants of of TFPGList unless I'm missing something painfully obvious.  Or am I missing something even more obvious in that they are defined elsewhere?

Gareth aka. Kit

---
This email has been checked for viruses by Avast antivirus software. https://www.avast.com/antivirus

PM J. Gareth Moreton wrote

I may be missing the obvious here, but I've noticed that there are some notable absences in the Free Generics Library.

All of that stuff is available in "rtl-generics" (currently trunk-only, but AFAIK works on 3.0.4 if you copy the source over.)

There's also a really good (even more features that rtl-generics) library called "LGenerics", shared not too long ago on the Lazarus forums, which can be found here:

https://github.com/avk959/LGenerics

I feel so silly now. Thank you.

Gareth aka. Kit

On Tue 04/06/19 22:14 , Ben Grasset
sent:

On Tue, Jun 4, 2019 at 4:40 PM J. Gareth

Moreton wrote

I may be missing the obvious here, but

I've noticed that there are some

notable absences in the Free Generics

Library.

All of that stuff is available in "rtl-

generics" (currently trunk-only, but

AFAIK works on 3.0.4 if you copy the

source over.)

There's also a really good (even more

features that rtl-generics) library

called "LGenerics", shared not too long

ago on the Lazarus forums, which

can be found here: https://github.com/avk959/LGenerics [1]

J. Gareth Moreton schrieb am Di., 4. Juni 2019,
22:40:

Just to add a bit to the other answer: FPC has three generic libraries: fgl, fcl-stl and rtl-generics.
fgl is the oldest and also served as a testbed for the generics. It cycles together with the compiler and is comparatively lightweight (at least to the other two), but has some requirements when using records as parameters and the performance isn't as good as that if rtl-generics. fcl-stl had been a contribution by a third party developer for a C++-STL-like generics library.
rtl-generics was also contributed by a third party developer for Delphi compatibility, is rather performant, but also rather heavy weight.

You can also see a speed comparison here:
http://www.benibela.de/fpc-map-benchmark_en.html

In the end (if you don't need specific functionality like a stack ;) ), it's a "pick your own poison" problem :P

Regards,
Sven

Hah, oh that sounds fun!

I would develop something more lightweight and efficient, but that would just make a 4th poison to choose from.

Gareth aka. Kit

---
This email has been checked for viruses by Avast antivirus software. https://www.avast.com/antivirus

Still, saying all that, maybe there's room for improvement in rtl-generics in the form of refactoring, like I've found in the compiler itself in a few places.  When you say 'heavyweight', do you mean it's a little slow sometimes or just very bulky when it comes to code size? (Taking a brief look at rtl-generics, there are a lot of classes!)

Gareth aka. Kit

---
This email has been checked for viruses by Avast antivirus software. https://www.avast.com/antivirus

J. Gareth Moreton schrieb am Mi., 5. Juni 2019,
11:54:

As Ben mentioned there is also LGenerics which is a third party library, so there already is a fourth poison, so yours would be a fifth :P

Regards,
Sven

J. Gareth Moreton schrieb am Mi., 5. Juni 2019,
14:27:

The latter. That's the price to pay for the flexibility to work with any type.

As said the performance is often better than the other collections (see the comparison site I linked).

Regards,
Sven

rtl-generics is meant to be Delphi compatible, so be careful. Also, Maciej did his best to make it as fast as possible. I doubt you can improve his code.

If you want to make improvements, I think fcl-stl and fgl units are more amenable to that.

Michael.

Sounds fair.  I would be trying for a refactoring approach, in that the API and outward behaviour is identical to before (i.e. a black box), but the inner workings are better.  I noticed that one potential source of improvement is changing the Quicksort algorithm, used in most of the sorting, for Introsort.

To explain Introsort, it is Quicksort most of the time, but switches to Heapsort if the depth level gets degenerate (usually set to "2 log n", where n is the list size - this tends to only happen if the list is carefully crafted to defeat Quicksort), and switches to Insertion Sort when a sublist gets to about 16 entries in size, since while Insertion Sort is O(n²), it has much lower overhead than Quicksort at this size and is hence faster.  Unlike the implementation in C++'s std::sort, I've noticed that it's better to do the insertion sort right there and then because the sublist will more likely still be in the cache; doing it as an end step like std::sort I found is slower in Object Pascal, possibly due to all the cache misses.  I don't know if this is specific to Object Pascal though.  Something to make a benchmark for though.

Gareth aka. Kit

P.S. Because Quicksort, Heapsort and Insertion Sort are all comparison sort algorithms, Introsort is also a comparison algorithm overall, so it is still compatible with classes that have a custom compare routine.

---
This email has been checked for viruses by Avast antivirus software. https://www.avast.com/antivirus

J. Gareth Moreton schrieb am Mi., 5. Juni 2019,
14:52:

You could try to adjust the FGL unit to use the pluggable sorting system introduced here:
https://svn.freepascal.org/cgi-bin/viewvc.cgi?view=revision&revision=41167

It's currently only used for the non generic TList and TFPList.

You could then add a IntroSort implementation.

Regards,
Sven

Sounds fun.  I'm currently working on a personal project to put into my online Github in order to show off to prospective employers, so it might be a while before I get around to that.

On another note, I'm also still waiting on Pierre to approve my XML node dump, since he and I have been doing a kind of iterative improvement with each patch we make.  It's been about a week now though since he's responded.  I do hope that gets implemented soon because using that to help implement pure functions will be very useful.  I have thought about another place where pure functions in particular have an advantage when coupled with a smart compiler - for example:

*for *X := 0 *to *Min(BUFFER_SIZE, DataLeft) *- 1 do*
*begin*
   { Do some work that doesn't modify DataLeft }
*end*;

Say that Min is given the *pure *directive, BUFFER_SIZE is a *const *and DataLeft is a property or some non-local variable.  Since no volatile intrinsic is used to safeguard multi-threading issues, and DataLeft isn't modified by the for-loop, DataLeft can be promoted to the stack or a register. Even though its exact value is not known, DataLeft is determined to be constant within the confines of the for-loop, hence since both arguments in "Min(BUFFER_SIZE, DataLeft)" are constants, the result must also be constant, since it's a pure function, therefore the function only has to be called once and its result be stored on the stack, recalled during each iteration of the for-loop.  At least that's the theory.  Of course, you can just store the result yourself in a local variable and use that as part of the for-loop, but it's just a thought where pure functions could be used that doesn't involve computing their aka. Kit

---
This email has been checked for viruses by Avast antivirus software. https://www.avast.com/antivirus

J. Gareth Moreton schrieb am Mi., 5. Juni 2019,
18:06:

With properties or global variables you can't guarantee that DataLeft is constant as the for loop might call some routine that more or less indirectly might change what DataLeft returns.
That said: the end-expression of a for-loop is specified to be evaluated only once anyway (in contrast to C-like languages).

Regards,
Sven

Ah, fair enough.  I didn't think to study the for-loop that closely yet since I haven't really found a need to check its code.  Sometimes I feel silly blurting out my ideas like this, but at least you stopped me from doing a fool's errand.  Thanks.

Gareth aka. Kit

---
This email has been checked for viruses by Avast antivirus software. https://www.avast.com/antivirus

Still, the theory's there just in case... if the arguments are constant (but unknown) and the pure function is called multiple times, then it can be optimised to only be called once.

Gareth aka. Kit

---
This email has been checked for viruses by Avast antivirus software. https://www.avast.com/antivirus

On Wed, Jun 5, 2019 at 11:11 AM Sven Barth via fpc-devel <

Wouldn't that system itself need to be generic and not just use void pointers first? Or is that part of what you meant?

IMO something FGL would benefit from also is the removal of the probably-not-the-best-design inheritance from non-generic TFPSList to everything else, which prevents inlining in a large number of places (the compiler notes indicating such are visible basically any time you use anything from FGL.)

You are right George.  I'm not entirely sure what the standards are with everything, but it would be nice to have something public and concrete.  Things that already exist cannot have their API changed - they can be refactored, but as a black box it might be completely identical.  Things like changing a sorting algorithm is no problem (so long as it's still a comparison sort).

Gareth aka. Kit

---
This email has been checked for viruses by Avast antivirus software. https://www.avast.com/antivirus

An object based container library would also be helpful.

With classes stored on the heap you always need additional memory access. Just one, but that is already bad in performance critical loops

Best, Benito

Op 2019-06-06 om 16:57 schreef Ben Grasset:

Yes, but that would be incompatible. However maybe some simple object based types next to it would furfill the remaining purpose of the unit ( cases where you need some simple generic container in places that haven't access to the ones in packages (fcl-stl, rtl-generics)).

But I would keep it simple and straightforward, and save the complex stuff for the more complicated libraries.

Marco van de Voort schrieb am Sa., 8. Juni
2019, 13:43:

Yes, that would be a good compromise.

Regards,
Sven