Lazarus

Announcements => Third party => Topic started by: avk on February 04, 2019, 06:18:43 am

Title: Yet another generics collection
Post by: avk on February 04, 2019, 06:18:43 am
As a result of experiments with FPC generics:
https://github.com/avk959/LGenerics (https://github.com/avk959/LGenerics)
Tested on Windows and Linux.
Title: Re: Yet another generics collection
Post by: Alextp on February 04, 2019, 07:22:41 am
Collection of generic algorithms and data structures entirely written in/for FPC and Lazarus. Started as a self-education project, it now seems quite comfortable and fast. In order to use it (FPC 3.1.1 and higher and Lazarus 1.9.0 and higher):

-    open and compile package LGenerics/packages/LGenerics.lpk.
-    add LGenerics package to project dependencies.

Implemented primitives:

-    stack(unit LGStack)
-    queue(unit LGQueue)
-    deque(unit LGDeque)
-    vector(unit LGVector)
-    vector of bits(unit LGVector)
 -   priority queue based on binary heap(unit LGPriorityQueue)
 -   priority queue with key update and melding based on pairing heap(unit LGPriorityQueue)
 -   sorted list(unit LGList)
 -   hashed list - array based list with the ability to fast search by key(unit LGList)
 -   hashset(unit LGHashSet)
 -   sorted set(unit LGTreeSet)
 -   hash multiset(unit LGHashMultiSet)
 -   sorted multiset(unit LGTreeMultiSet)
 -   hashmap(unit LGHashMap)
 -   sorted map(unit LGTreeMap)
 -   hash multimap(unit LGMultiMap)
 -   tree multimap(unit LGMultiMap)
 -   list miltimap(unit LGMultiMap)
 -   bijective map(unit LGBiMap)
 -   sparse 2D table(unit LGTable2D)
 -   disjoint set(unit LGHashSet)
 -   sparse labeled undirected graph(unit LGSimpleGraph)
 -   sparse labeled directed graph(unit LGSimpleDigraph)
Title: Re: Yet another generics collection
Post by: Blaazen on February 04, 2019, 09:15:25 am
Nice. Don't forget to add link to wiki: http://wiki.lazarus.freepascal.org/Components_and_Code_examples (http://wiki.lazarus.freepascal.org/Components_and_Code_examples)
Title: Re: Yet another generics collection
Post by: heejit on February 04, 2019, 10:31:17 am
If possible add into OPM  and a wiki with examples
Title: Re: Yet another generics collection
Post by: Thaddy on February 04, 2019, 10:43:56 am
@avg
It has a big issue: I assume for speed there is an over-use of {$H-} which not everybody likes, because it limits its applicability.
Compliments, with the restriction that it is nice code, but with niche application because of its reliance on short strings.
I am not even sure the many $H+ and $H- switches over the units are always correct.... or that every string  in $H- mode has the guaranteed correct size..
I would not accept that in production code.

Don't let that discourage you, but document the limitation. O:-)
Title: Re: Yet another generics collection
Post by: marcov on February 04, 2019, 10:47:58 am
Sortedlist uses single array. That is a scaling risk when you get into the 100k range.
Title: Re: Yet another generics collection
Post by: Thaddy on February 04, 2019, 10:52:33 am
Sortedlist uses single array. That is a scaling risk when you get into the 100k range.
Yes. Should be heap allocated. The range can be even earlier depending on stack. Use a pointer type.
(but again at the cost of speed)
Title: Re: Yet another generics collection
Post by: marcov on February 04, 2019, 11:12:01 am
Sortedlist uses single array. That is a scaling risk when you get into the 100k range.
Yes. Should be heap allocated. The range can be even earlier depending on stack. Use a pointer type.
(but again at the cost of speed)

A dynamic array is already heap allocated. I was referring to the slowdown ordered insertion of items into a single array (average O(n) operation).

The thread about the benchmark that PascalDragon refers had some info on it. I added lightcontainers to that benchmark, but it was post added and is not on by default. This simply does (dynamic) array of (dynamic) array.

Note also that the benchmark only are about lookup, array based ordered lists are of course slower than hashes than lookup, but usually more conservative with memory, allow in-order iteration and allow to find the items close to a certain item. Still the benchmark is quite nice.

p.s. oops, PascalDragon mentioned in a related but different thread here (https://forum.lazarus.freepascal.org/index.php/topic,44048.0/topicseen.html)
Title: Re: Yet another generics collection
Post by: avk on February 04, 2019, 11:42:07 am
Nice...
Thank you.
Sortedlist uses single array. That is a scaling risk when you get into the 100k range.
Yes of course.
@Thaddy, could you clarify your point:
It has a big issue: I assume for speed there is an over-use of {$H-} which not everybody likes, because it limits its applicability.
Title: Re: Yet another generics collection
Post by: Leledumbo on February 04, 2019, 12:24:37 pm
@Thaddy, could you clarify your point:
It has a big issue: I assume for speed there is an over-use of {$H-} which not everybody likes, because it limits its applicability.
I believe what he meant was: shortstrings are stack allocated, has much simpler structure and requires no manager, therefore it has speed advantage over ansistrings and other string types that doesn't have the 255 8-bit character limitation. This might be a good show in benchmark, but in reality, people might require more than 255 characters. The silent truncation behavior of most (or all?) of its related function doesn't help for sure.
Title: Re: Yet another generics collection
Post by: Thaddy on February 04, 2019, 01:00:19 pm
@Thaddy, could you clarify your point:
See Leledumbo's answer who beat me to it  ;D.
But there are more effects that can cause trouble along the way:
It is better to protect the string changes with $push and $pop too, because currently some versions of FPC (e.g. 3.0.4) keep the string changes in units over unit boundaries (which is a reported bug, it should adhere to the program settings if another unit does not define a string type)
That's why things like:
Code: Pascal  [Select][+][-]
  1. interface
  2. {$MODE OBJFPC}{$H+}    // <----- OK
  3. {$INLINE ON}{$WARN 6058 off : }
  4. {$MODESWITCH NESTEDPROCVARS}
  5. {$MODESWITCH ADVANCEDRECORDS}
  6.  
  7. interface
  8.  
  9. uses
  10.  
  11.   SysUtils,
  12.   LGUtils,
  13.   {%H-}LGHelpers,    /// < ---- this can cause a lot of trouble afterwards.....
  14.   LGAbstractContainer,
  15.   LGHashTable,
  16.   LGStrConst;

Can bring the user into trouble.
And once the bug is fixed it won't work outside a unit
You should:
- Set the string type on a per unit basis or not at all.
- At least restore the string type.

As it stands it is a shortcut that works by accident and not by language specification and documentation.
Title: Re: Yet another generics collection
Post by: Thaddy on February 04, 2019, 01:08:48 pm
@Avk
Oh, I see: you write {%H-} and not {$H-}...
In that case, that's a Lazarus IDE macro and not an FPC define?
That's also not a good idea in a library...
Title: Re: Yet another generics collection
Post by: avk on February 04, 2019, 01:16:42 pm
Yes, that's a Lazarus IDE directive.
Why is this not a good idea in the library?
Title: Re: Yet another generics collection
Post by: Thaddy on February 04, 2019, 02:04:21 pm
The library should be transparent.
Your library does not rely on visual code.
E.g: I do not usually use the Lazarus ide but Geany.
You won't find any Lazarus macro's in any FPC library code.
That's also the reason I misinterpreted it at first glance.
Title: Re: Yet another generics collection
Post by: marcov on February 04, 2019, 02:22:31 pm
The library should be transparent.

Your library does not rely on visual code.

E.g: I do not usually use the Lazarus ide but Geany.

So? What is the problem there? How do the lazarus macros make that impossible

Quote
You won't find any Lazarus macro's in any FPC library code.
That's also the reason I misinterpreted it at first glance.

Incorrect. See e.g. packages/src/avl_tree
Title: Re: Yet another generics collection
Post by: avk on February 04, 2019, 02:24:40 pm
@Thaddy, thank you, I have to think about it.
The fact is that FPC generates a lot of unnecessary hints among which you can not see the important.
Title: Re: Yet another generics collection
Post by: Thaddy on February 04, 2019, 05:14:21 pm
I wrote a wiki article on how to handle that properly. http://wiki.freepascal.org/Turn_warnings_and_hints_on_or_off
Maybe that helps
Title: Re: Yet another generics collection
Post by: Akira1364 on February 04, 2019, 09:04:26 pm
Cool library! Whole lot of "something wasn't inlined" hints though. Just in case you aren't aware, that is almost always caused by a function being marked inline but being called by another function with an implementation that comes later in the file than it. It just won't ever work in that case.
Title: Re: Yet another generics collection
Post by: valdir.marcos on February 05, 2019, 02:11:34 am
Collection of generic algorithms and data structures entirely written in/for FPC and Lazarus. Started as a self-education project, it now seems quite comfortable and fast. In order to use it (FPC 3.1.1 and higher and Lazarus 1.9.0 and higher):

Also the types in Generics.Collections support records without any operator overload.
One advantage of the FGL ones: they are small, so they're more suitable for embedded projects where memory size might be an issue.
And for those that are interested: here (http://www.benibela.de/fpc-map-benchmark_en.html) we have a performance comparison of various FPC containers (no, not by me).
Just curious.

If there are already official Generics implementations for Objfpc syntax since version 2.2. and Delphi compatible syntax since version 2.6.0.
http://wiki.freepascal.org/Generics

Why are there still so many alternative implementations for Generics?

Shouldn't all this effort be redirected to evolve official Generics implementation?
Title: Re: Yet another generics collection
Post by: Akira1364 on February 05, 2019, 03:40:00 am
Shouldn't all this effort be redirected to evolve official Generics implementation?

I think a more important thing to look at first would be to start actively encouraging people to use generics overall in new code, and stop pointing them at things like Contnrs as though they're still "the best you'll get." They're not. Typecasting void pointers back and forth is dumb when it can be avoided.

There's a reason nobody uses non-generic TList or anything from Contnrs when working with new Delphi versions. I don't get why FPC is so different in this regard when it has all the same functionality (better functionality in some ways) available.
Title: Re: Yet another generics collection
Post by: Blaazen on February 05, 2019, 02:48:30 pm
@ Akira1364

Something similar asked Graeme on ML a few years ago. For example, I still use TCollection and TCollectionItem for visual components because they work well and have built-in design-time editors. Otherwise I use FGL (at most TFPGObjectList)  for reasons you pointed.
One of reasons may be that CodeTools still does not fully support generics, i.e. when you hit Ctrl+Space you don't get proper choice.
Title: Re: Yet another generics collection
Post by: Akira1364 on February 05, 2019, 03:10:34 pm
For example, I still use TCollection and TCollectionItem for visual components because they work well and have built-in design-time editors.

One of reasons may be that CodeTools still does not fully support generics, i.e. when you hit Ctrl+Space you don't get proper choice.

TCollection and TCollectionItem are a bit different I'd say due to the specific "persistent" RTTI-based functionality they provide. There's definitely good reasons to use those, since no relevant generic equivalent currently exists.

For the CodeTools stuff, it's true that the support for generics still isn't perfect. I don't think I'd ever write my code specifically to workaround IDE issues, though.
Title: Re: Yet another generics collection
Post by: avk on February 06, 2019, 12:01:06 pm
Whole lot of "something wasn't inlined" hints though.
I cleaned the inlines a bit, so the compiler noise about this should be smaller.
Title: Re: Yet another generics collection
Post by: marcov on February 06, 2019, 05:25:02 pm
Why are there still so many alternative implementations for Generics?

The Delphi compatible generics library is not yet delivered in a release.
Title: Re: Yet another generics collection
Post by: avk on February 07, 2019, 08:29:55 am
The Delphi compatible generics library is not yet delivered in a release.
Just in case, LGenerics is incompatible with Delphi.
Title: Re: Yet another generics collection
Post by: avk on February 23, 2019, 11:13:33 am
recent changes in LGenerics:
 - added implementation of concurrent fine-grained hashmap(first attempt)
 - added some thread pool implementations
 - improved implementation of futures
Title: Re: Yet another generics collection
Post by: Thaddy on February 23, 2019, 11:29:09 am
I like the thread pool features. Will test.
Title: Re: Yet another generics collection
Post by: avk on February 24, 2019, 08:36:51 am
... Will test.
Thank you, it would be highly interesting to know if it works on the arm device.
Title: Re: Yet another generics collection
Post by: avk on December 22, 2019, 05:23:25 am
Hi everyone,
a separate branch "stable_0_52"(I hope) has been created for the current version of the LGenerics package and it seems to be compatible with fpc 3.2.

It has been added since the last announcement
new primitives:
 - some variants of "smart pointers"
 - dynarray with COW semantics
 - 128-bit integers
 - general rooted tree
 - red-black tree
 - some variants of the treap
 - static segment tree
 - helpers for getting an extended IEnumerable interface
   for any entity that provides an enumerator

algorithms on graphs:
 - minimum vertex cover
 - chordality testing
 - dominators in flowgraps
 - FMR planarity testing algorithm

Merry Christmas and happy coding! 
Title: Re: Yet another generics collection
Post by: julkas on December 22, 2019, 11:35:00 am
@avk Great +5.
1. Plans for random algorithms on graph (Karger, ...) ?
2. Delphi compatibility?
Add docs.

Thanks.
Title: Re: Yet another generics collection
Post by: avk on December 30, 2019, 07:30:02 am
@julkas, thank you.

Especially with regard to randomized algorithms, I have not yet thought, now there is a desire to expand the set of supported types of graphs. But if you are interested in finding the minimum cut, the library has a deterministic algorithm.
As for Delphi compatibility: if Delphi will support helper inheritance and record management operators, why not? :)

The library is still in its infancy, a lot has to be changed, so as long as I don't see the point in writing documentation, it will have to be rewritten. So far, I've been trying to comment on classes and methods in detail.
Title: Re: Yet another generics collection
Post by: avk on January 05, 2020, 07:37:50 am
Happy 2020!

I added a translation of Orson Peters' PDQSort algorithm.
Title: Re: Yet another generics collection
Post by: avk on January 31, 2020, 12:13:18 pm
Slightly improved sorting algorithms performance.
Below are results of some comparison benchmarks, first plot is about pascal sortings:
A negative value indicates that the algorithm failed the test(exhibits quadratic behavior).
win7-64bit, fpc-3.3.1-r44056, Delphi 10.3 CE;

The second one shows comparison with c++ sortings on a virtual Linux machine(gcc 7.3.0).
Title: Re: Yet another generics collection
Post by: julkas on January 31, 2020, 06:15:34 pm
@avk your attachments are invisible for guests.
Title: Re: Yet another generics collection
Post by: Thaddy on January 31, 2020, 06:29:51 pm
@avk your attachments are invisible for guests.
That is normal.
Title: Re: Yet another generics collection
Post by: avk on February 01, 2020, 07:01:36 am
@avk your attachments are invisible for guests.
Doesn’t it depend on the forum settings?
Title: Re: Yet another generics collection
Post by: julkas on February 01, 2020, 03:43:47 pm
Slightly improved sorting algorithms performance.
Below are results of some comparison benchmarks, first plot is about pascal sortings:
  • Delphi denotes Delphi.Generics.Collections.TList<Integer>.Sort
  • Fgl  - fgl.TFpgList<Integer>.Sort
  • GCol - rtl-generics.Generics.Collections.TList<Integer>.Sort
  • Fcl  - fcl-stl.TOrderedArrayUtils.Sort(TVector<Integer>)
  • Lg   - LGenerics.TGVectorHelper.Sort(TGVector<Integer>)
A negative value indicates that the algorithm failed the test(exhibits quadratic behavior).
win7-64bit, fpc-3.3.1-r44056, Delphi 10.3 CE;

The second one shows comparison with c++ sortings on a virtual Linux machine(gcc 7.3.0).
Can you give more info about your benchmark env (VM, CPU, RAM, optimization switches, C++ source code)?
What about 10**7, 10**8?
Title: Re: Yet another generics collection
Post by: Thaddy on February 01, 2020, 04:22:55 pm
Doesn’t it depend on the forum settings?
Yes. Being able to view (or upload) is dependent on forum membership.
Title: Re: Yet another generics collection
Post by: Thaddy on February 01, 2020, 04:25:40 pm
What about 10**7, 10**8?
What about 10**555 ?
That's a silly question.  I do not think C++ can even handle that with standard libraries....We are talking quadratic expansion here.
Given the code and sufficient memory and time 10**7 should be no problem.
Title: Re: Yet another generics collection
Post by: avk on February 01, 2020, 05:28:59 pm
Can you give more info about your benchmark env (VM, CPU, RAM, optimization switches, C++ source code)?
Oh sure. This is Ubuntu MATE 18.04 with 2 GB RAM on VirtualBox 5.2.26. The host system and processor are listed above.
Attachment contains sources and a small Readme. If you want, you can add 10^7 and more there. 
Title: Re: Yet another generics collection
Post by: avk on February 16, 2020, 12:38:03 pm
The performance of the containers seems to have improved slightly.
Below are some results of "quick and dirty" comparison benchmark for some hashmaps(string keys) from Pascal' hashmap zoo.
Participants(with default settings):
The benchmark was compiled with FPC 3.3.1 r44056(x86_64-win64) and runs on win7.
Title: Re: Yet another generics collection
Post by: avk on May 05, 2020, 04:17:10 pm
Added support for sets of arbitrary size (well, at least up to High(Cardinal) div 33).
Quick and dirty comparison of performance with the built-in set looks like this:
Code: Text  [Select][+][-]
  1. built-in set - size:              32
  2. generic set  - size:              32
  3. built-in set - include:           670 ms
  4. generic set  - include:           410 ms
  5. built-in set - contains:          520 ms
  6. generic set  - contains:          200 ms
  7. built-in set - intersection:      300 ms
  8. generic set  - intersection:      20 ms
  9. built-in set - iteration(sparse): 720 ms
  10. generic set  - iteration(sparse): 130 ms
  11. built-in set - iteration(dense):  670 ms
  12. generic set  - iteration(dense):  660 ms  
  13.  
Title: Re: Yet another generics collection
Post by: Thaddy on May 05, 2020, 07:58:41 pm
Nice! I abandon my efforts... for the huge sets. I am using your library more and more.
Compliments! This is not "Yet another" but also firmly founded in theory, which I especcially like. And you have a really clean coding style, which I also like very much. Therefor the code is quite self-documenting.
Title: Re: Yet another generics collection
Post by: fcu on May 06, 2020, 12:13:53 am
3mb of code wow !! , my projects never exceed 100kb   
i liked this library very much , also fpc generic.collection becomes microscopic compared with this giant and great library
really thanks for making this public
keep up the good work   
TinyPortal © 2005-2018