Lazarus

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

Title: LGenerics: 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   
Title: Re: Yet another generics collection
Post by: sash on August 10, 2020, 01:43:18 pm
Hello.

Is it possible to use it without installing as a package?
Because otherwise, it's hard to maintain in automated builds.
Title: Re: Yet another generics collection
Post by: avk on August 10, 2020, 02:48:10 pm
There shouldn't seem to be any problems, but to be honest, I haven't tried.
Title: Re: Yet another generics collection
Post by: sash on August 10, 2020, 03:48:38 pm
There shouldn't seem to be any problems, but to be honest, I haven't tried.

Thanks for reply.

I figured out, it works, but only if I add
  (in addition to LGenerics/lgenerics/ in Other unit files(-Fu))
  LGenerics/lgenerics/include to Include files(-Fi),
otherwise compiler cannot find {$I EnumsH.inc}.

I'd suggest improvement in form of replacing such includes as {$i include/xyz.inc}, so -Fi LGenerics/lgenerics/include will not be necessary (as actually being a part of *.pas units).

Another one, how do you construct graphs, can I use builtin hashing helpers for this?
Code: Pascal  [Select][+][-]
  1. uses
  2.    LGSimpleGraph, LGHelpers;
  3. type
  4.   TMyGraph = specialize TGSimpleGraph<TMyVertexClass, TMyEdgeClass, TWhat?>;
  5.  

Thanks again.
Title: Re: Yet another generics collection
Post by: avk on August 10, 2020, 04:48:06 pm
Thanks for the suggestion.

To use the built-in helper for a class, it is enough to declare the graph as
Code: Pascal  [Select][+][-]
  1. uses
  2.    LGSimpleGraph, LGHelpers;
  3. type
  4.   TMyGraph = specialize TGSimpleGraph<TMyVertexClass, TMyEdgeClass, TMyVertexClass>;
  5.  

Note that the built-in helper uses the TObject.Equals and TObject.GetHashCode methods under the hood.
Title: Re: Yet another generics collection
Post by: AlexTP on August 10, 2020, 05:13:06 pm
Added wiki page
https://wiki.freepascal.org/LGenerics
Title: Re: Yet another generics collection
Post by: avk on August 10, 2020, 07:43:36 pm
Thank you very much, that's very kind.
Title: Re: Yet another generics collection
Post by: sash on August 24, 2020, 09:05:45 pm
Again about graphs.
Is there a suggested way of (un)serialization?

Title: Re: Yet another generics collection
Post by: avk on August 25, 2020, 03:33:27 am
Only the simplest SaveToStream/LoadFromStream.
Title: Re: Yet another generics collection
Post by: mr-highball on August 25, 2020, 04:15:03 am
Saw your library back when it was first posted and have to say, you've got some good stuff in here. Just wanted to say it's been starred and to keep up the good work 👍👍
Title: Re: Yet another generics collection
Post by: avk on August 25, 2020, 11:50:54 am
Thank you very much.
Title: Re: Yet another generics collection
Post by: sash on August 26, 2020, 02:41:11 pm
Only the simplest SaveToStream/LoadFromStream.

Well, for Vetices there are Items, but I can't figure out how can I exactly iterate through Edges as linear list.
Can you provide an example?
Title: Re: Yet another generics collection
Post by: avk on August 26, 2020, 04:38:03 pm
It seems I misunderstood your question?

There is the Edges method, which returns enumerable, which enumerates all edges of the graph.
On an undirected graph each edge will meet twice, which may be inconvenient.
Therefore the undirected graph also has the DistinctEdges method.

This code
Code: Pascal  [Select][+][-]
  1. program print_edges;
  2. {$mode delphi}
  3. uses
  4.   SysUtils, LGUtils, LGSimpleGraph;
  5.  
  6. type
  7.   TRef = TGAutoRef<TStrChart>;
  8.  
  9. var
  10.   Ref: TRef;
  11.   g: TStrChart;
  12.   s: string;
  13.   e: TStrChart.TEdge;
  14. begin
  15.   g := Ref;
  16.   g.AddEdge('one', 'two');
  17.   g.AddEdge('one', 'three');
  18.   g.AddEdge('two', 'four');
  19.   g.AddEdge('two', 'five');
  20.   g.AddEdge('three', 'six');
  21.   g.AddEdge('three', 'seven');
  22.   g.AddEdge('six', 'eight');
  23.   g.AddEdge('seven', 'eight');
  24.   g.AddEdge('eight', 'one');
  25. { or
  26.   g.AddEdges(
  27.     ['one', 'two', 'one', 'three', 'two', 'four', 'two', 'five', 'three', 'six',
  28.      'three', 'seven', 'six', 'eight', 'seven', 'eight', 'eight', 'one']); }
  29.  
  30.   WriteLn('Vertices:');
  31.   for s in g.Vertices do
  32.     WriteLn(s);
  33.  
  34.   WriteLn;
  35.  
  36.   WriteLn('Edges:');
  37.   for e in g.DistinctEdges do
  38.     WriteLn(g[e.Source], ' -- ', g[e.Destination]);
  39. end.
  40.  
will print
Code: Text  [Select][+][-]
  1. Vertices:
  2. one
  3. two
  4. three
  5. four
  6. five
  7. six
  8. seven
  9. eight
  10.  
  11. Edges:
  12. one -- two
  13. one -- three
  14. one -- eight
  15. two -- four
  16. two -- five
  17. three -- six
  18. three -- seven
  19. six -- eight
  20. seven -- eight
  21.  
Title: Re: Yet another generics collection
Post by: sash on August 26, 2020, 06:31:53 pm
Yes, my case is undirected graphs (with my own TVertex and TEdge classes), and I need to save/load whole dataset to text/xml (both structure and objects).
Also I need to visualize it in form of "circles connected by lines", so I guess DistinctEdges is what I need.

Currently, I'm using another graph library (C-code linked to my Pascal project), but found your one, and evaluating it. It's very complex, not yet get used to it.

Also, does DistinctEdges return cached value, or does it recalculate list on the fly (from adjacency matrix?)?
Title: Re: Yet another generics collection
Post by: avk on August 26, 2020, 07:42:46 pm
Also, does DistinctEdges return cached value, or does it recalculate list on the fly (from adjacency matrix?)?
The iterator simply traverses the vertex adjacency lists.

BTW, there is a way(rather primitive) to draw a graph.
This code will save the graph from the previous example in Graphviz' dot format:
Code: Pascal  [Select][+][-]
  1. program save2dot;
  2. {$mode delphi}
  3. uses
  4.   SysUtils, LGUtils, LGSimpleGraph;
  5. var
  6.   Ref: TGAutoRef<TStrChart>;
  7.   g: TStrChart;
  8.   DotWriter: TGAutoRef<TStrChartDotWriter>;
  9. begin
  10.   g := Ref;
  11.   g.Title := 'Chart';
  12.   g.AddEdges(['one', 'two', 'one', 'three', 'two', 'four', 'two', 'five', 'three', 'six',
  13.               'three', 'seven', 'six', 'eight', 'seven', 'eight', 'eight', 'one']);
  14.  
  15.   with DotWriter.Instance do
  16.     begin
  17.       ShowTitle := True;
  18.       SizeX := 4;
  19.       SizeY := 4;
  20.       SaveToFile(g, 'Chart.dot')
  21.     end;
  22. end.
  23.  
If you feed the resulting file to Graphviz, you will get a picture similar to the one in the attachment.
Title: Re: Yet another generics collection
Post by: sash on August 26, 2020, 11:34:17 pm
Well, I know about Graphviz, but I must use canvas to draw and edit graph layout...

And what about memory management?
Should I take care about freeing my custom vertex and edge class instances?
Title: Re: Yet another generics collection
Post by: avk on August 27, 2020, 06:55:18 am
If instances of vertices and edges are not stored anywhere except the graph, then certainly yes.
Provided that you do not remove the vertices and edges of the graph while manipulating with it, this can be done in the destructor. Otherwise, you also need to override the protected methods DoRemoveVertex and DoRemoveEdge
Title: Re: Yet another generics collection
Post by: sash on August 27, 2020, 05:17:45 pm
Provided that you do not remove the vertices and edges of the graph while manipulating with it, this can be done in the destructor.
Well ... I do remove elements... so I wrote
Code: Pascal  [Select][+][-]
  1. function TMyGraph.DoRemoveEdge(aSrc, aDst : SizeInt) : Boolean;
  2. var
  3.   edg : TMyGraphEdge;
  4. begin
  5.   Result := false;
  6.   if GetEdgeDataI(aSrc, aDst, edg) then begin
  7.     Result := inherited DoRemoveEdge(aSrc, aDst);
  8.     if Result then
  9.       edg.Free;
  10.   end;
  11. end;
  12.  
Is it ok? Will it work on MyGraph.Clear() ?
Title: Re: Yet another generics collection
Post by: avk on August 27, 2020, 06:02:44 pm
OMG, I completely forgot about Clear.
It also needs to be overridden.

Provided that you do not remove the vertices and edges of the graph while manipulating with it, this can be done in the destructor.
Well ... I do remove elements... so I wrote
Code: Pascal  [Select][+][-]
  1. function TMyGraph.DoRemoveEdge(aSrc, aDst : SizeInt) : Boolean;
  2. var
  3.   edg : TMyGraphEdge;
  4. begin
  5.   Result := false;
  6.   if GetEdgeDataI(aSrc, aDst, edg) then begin
  7.     Result := inherited DoRemoveEdge(aSrc, aDst);
  8.     if Result then
  9.       edg.Free;
  10.   end;
  11. end;
  12.  

I would prefer like this:
Code: Pascal  [Select][+][-]
  1. function TMyGraph.DoRemoveEdge(aSrc, aDst : SizeInt) : Boolean;
  2. var
  3.   edg : TMyGraphEdge;
  4. begin
  5.   if GetEdgeDataI(aSrc, aDst, edg) and (inherited DoRemoveEdge(aSrc, aDst)) then begin
  6.     edg.Free;
  7.     exit(True);
  8.   end;
  9.   Result := False;  
  10. end;
  11.  
Title: Re: Yet another generics collection
Post by: avk on August 27, 2020, 07:08:46 pm
Perhaps something like this:
Code: Pascal  [Select][+][-]
  1. ...
  2. type
  3.  
  4.   TMyVertex = class
  5.   end;
  6.  
  7.   TMyEdge = class
  8.   end;
  9.  
  10.   TMyGraph = class(specialize TGSimpleGraph<TMyVertex, TMyEdge, TMyVertex>)
  11.   protected
  12.     procedure DoRemoveVertex(aIndex: SizeInt); override;
  13.     function  DoRemoveEdge(aSrc, aDst: SizeInt): Boolean; override;
  14.   public
  15.     destructor Destroy; override;
  16.     procedure Clear; override;
  17.   end;
  18.  
  19. implementation
  20. {$B-}{$COPERATORS ON}{$POINTERMATH ON}
  21. ...
  22. { TMyGraph }
  23.  
  24. procedure TMyGraph.DoRemoveVertex(aIndex: SizeInt);
  25. var
  26.   p: PAdjItem;
  27. begin
  28.   for p in AdjLists[aIndex]^ do
  29.     p^.Data.Free;
  30.   Items[aIndex].Free;
  31.   inherited DoRemoveVertex(aIndex);
  32. end;
  33.  
  34. function TMyGraph.DoRemoveEdge(aSrc, aDst: SizeInt): Boolean;
  35. var
  36.   e: TMyEdge;
  37. begin
  38.   if GetEdgeDataI(aSrc, aDst, e) and (inherited DoRemoveEdge(aSrc, aDst)) then
  39.     begin
  40.       e.Free;
  41.       exit(True);
  42.     end;
  43.     Result := False;
  44. end;
  45.  
  46. destructor TMyGraph.Destroy;
  47. begin
  48.   Clear;
  49.   inherited;
  50. end;
  51.  
  52. procedure TMyGraph.Clear;
  53. var
  54.   e: TEdge;
  55.   I: SizeInt;
  56. begin
  57.   for e in DistinctEdges do
  58.     e.Data.Free;
  59.   for I := 0 to Pred(VertexCount) do
  60.     Items[I].Free;
  61.   inherited;
  62. end;
  63.  
Title: Re: Yet another generics collection
Post by: avk on August 28, 2020, 04:41:32 pm
@sash, eventually I added TGSimpleObjGraph. It would be interesting to know your opinion.
Title: Re: Yet another generics collection
Post by: sash on August 29, 2020, 01:33:38 pm
@sash, eventually I added TGSimpleObjGraph. It would be interesting to know your opinion.

Thank you very much.
Updated to TGSimpleObjGraph.

Much more convenient. Seems like It works as it should. I didn't test allocations yet, but certainly will.
I'm glad you implemented OwnsXXX properties, don't know about edges, but my use-case assumes some vertices belongs to multiple graphs, so it's very handy.

Again (some more questions :))
- what happens with orphaned edges (when both connected vertices deleted)?
- can I replace an existing instance of vertex like
Code: Pascal  [Select][+][-]
  1. graph.Items[i].Free;
  2. graph.Items[i] := TAnotherVertex.Create;
?

Title: Re: Yet another generics collection
Post by: avk on August 30, 2020, 01:07:00 pm
- what happens with orphaned edges (when both connected vertices deleted)?
- can I replace an existing instance of vertex like

1. Removal of any vertex of the graph implies the removal of all incident edges.
2. It would be safer like this:
Code: Pascal  [Select][+][-]
  1.   OldValue := graph.Items[i];
  2.   graph.Items[i] := TAnotherVertex.Create;
  3.   OldValue.Free;
  4.  
But the latest revision of the library will do this automatically(provided that the graph owns the vertices).
Title: Re: Yet another generics collection
Post by: sash on August 30, 2020, 05:19:19 pm
But the latest revision of the library will do this automatically(provided that the graph owns the vertices).
Do what? Free old contained object on assignment of new one?
Title: Re: Yet another generics collection
Post by: avk on August 30, 2020, 05:53:38 pm
Yeah, exactly.
Title: Re: Yet another generics collection
Post by: avk on October 19, 2020, 10:45:33 am
Added a radix sort algorithm, so I ran the sorting benchmark again.
A negative value indicates that the algorithm failed the test(exhibits quadratic behavior).
The benchmark was compiled with FPC 3.3.1-r46955 and ran on a win7-64bit machine.
Title: Re: Yet another generics collection
Post by: avk on December 30, 2020, 06:57:56 am
Added implementation of the JSON parser/generator.
It seems it passes all tests from JSONTestSuite (https://github.com/nst/JSONTestSuite).

As for performance, below are the results of a (quick and dirty) benchmark involving Delphi.JSON framework, JsonTools and FpJson.
The benchmark tries to measure the parsing performance(in Kb/s), sources can be found in the "LGenerics/example/json/parse_bench" folder.
It was compiled with FPC-3.3.1-r47862-win64 (-O3), Delphi code was compiled with Delphi 10.3.3 CE (win64, release).

Happy New Year!
Title: Re: Yet another generics collection
Post by: lainz on January 04, 2021, 11:25:43 pm
Wow, I need to try that Json, looks promising and in the graph faster than Json Tools.

I have some questions, because that caused me some headaches. This two bugs are present in your Json library?

https://github.com/sysrpl/JsonTools/issues/12

https://github.com/sysrpl/JsonTools/issues/11

Thanks, if that works, maybe we switch (again) of JSON Library.
Title: Re: Yet another generics collection
Post by: avk on January 05, 2021, 09:10:28 am
Thank you.
Well my locale also uses a comma as the decimal separator.
At least this code
Code: Pascal  [Select][+][-]
  1. ...
  2. var
  3.   o: TJsonNode;
  4. begin
  5.   o := TJsonNode.NewJson('{"test": "one \"\"two\"\" three", "float value": 0.52875}');
  6.   Memo1.Append(o['test']);
  7.   Memo1.Append(Double(o['float value']).ToString);
  8.   Memo1.Append(o.FormatJson);
  9.   o.Free;
  10. end;
  11.  
prints
Code: Text  [Select][+][-]
  1. one ""two"" three
  2. 0,52875
  3. {
  4.     "test": "one \"\"two\"\" three",
  5.     "float value": 0.52875
  6. }
  7.  
Title: Re: Yet another generics collection
Post by: lainz on January 05, 2021, 01:14:01 pm
Thanks!  :)
Title: Re: Yet another generics collection
Post by: avk on January 05, 2021, 01:56:34 pm
You are welcome.
Title: Re: Yet another generics collection
Post by: lainz on January 05, 2021, 02:09:34 pm
Hi I have some questions on the LGJson usage

Code: Pascal  [Select][+][-]
  1. for j:=0 to tempData.Count-1 do
  2.            begin
  3.              // copy
  4.              tempObj := arr.AsArray.AddNode(jvkObject);
  5.              tempObj.AsJson := tempData.Items[j].AsJson;
  6.            end;
  7.            if not bPaginar then
  8.             b := False;
  9.            FreeAndNil(tempData);

tempData, tempObj and arr are al TJsonNode.

What I'm doing is making a copy of tempData into arr.

Basically I get an array from internet (tempData) and must join all the objects I get into (arr). I get several times tempData, and I free that in each iteration. (FreeAndNil(tempData)).

That way of copying the object is fine? Or there is a better way?

Edit: Anyways it works, and in our application works almost the same that JsonTools, I get the same time syncing the same data.

Edit2: Our bottleneck is in another castle!
Title: Re: Yet another generics collection
Post by: avk on January 05, 2021, 05:25:13 pm
It's a good question anyway. I do my best to avoid adding nodes directly, as this is error-prone. However, double parsing isn't a very attractive solution either.
I just hastily added a new ArrayAppend method, maybe that's what you need?
Title: Re: Yet another generics collection
Post by: lainz on January 05, 2021, 09:12:42 pm
Yes that works.

Anyways I get a slower time this time with the change. But I'm not measuring it well, so I can't say, I'm measuring a whole process that depends on internet, so speed can vary and is not only by the json library, but the server speed, internet speed and other things.
Title: Re: Yet another generics collection
Post by: avk on January 18, 2021, 03:10:59 pm
Added pull-style JSON stream reader.

It provides, at the user's choice

As for performance, query
Code: Pascal  [Select][+][-]
  1.   Reader.FindPath('/features/100001')
  2.  
on this (https://github.com/zemirco/sf-city-lots-json/blob/master/citylots.json) JSON(~190MB) takes about 0.7 s. on my machine.
Title: Re: Yet another generics collection
Post by: avk on February 22, 2021, 06:59:47 am
Added implementation of two string matching algorithms (unit lgStrHelpers), both are inheritors of the Boyer-Moore algorithm with minor improvements or simplifications.
The TBmSearch entity implements a Boyer-Moore incarnation called Fast-Search, and TBmhrSearch implements the Boyer-Moore-Horspool-Raita algorithm(sometimes just Raita). TBmSearchCI is a case-insensitive version of TBmSearch.

A simple comparative benchmark on various inputs; BuildinBM denotes FindMatchesBoyerMooreCaseSensitive from StrUtils.

Random string(200000000 bytes) over a five-character alphabet, search for 10 patterns(running time in ms, lower is better).
Code: Text  [Select][+][-]
  1.  pattern len       TBmSearch    TBmhrSearch  BuildinBM
  2.      5               3157          3500        4017
  3.     10               2235          2487        2814
  4.     20               2078          2687        2627
  5.     50               1455          2078        1812
  6.    100               1437          2502        1767
  7.    200               1375          2422        1749
  8.  

Natural language text(English, "The Forsyte Saga", 2079763 bytes), search for 1000 patterns(running time in ms, lower is better).
Code: Text  [Select][+][-]
  1.  pattern len       TBmSearch    TBmhrSearch  BuildinBM
  2.      5               1969          2266        2799
  3.     10               1125          1297        1593
  4.     20                704           811         984
  5.     50                470           516         609
  6.    100                376           405         468
  7.    200                312           327         374
  8.  

Search for a single pattern in a list(200000 items) of moderate-length strings(5000-15000 bytes)(running time in ms, lower is better).
Code: Text  [Select][+][-]
  1.  pattern len       TBmSearch    TBmhrSearch  BuildinBM
  2.      5               2653          3311        3343
  3.     10               1016          1171        1530
  4.     20                842           875        1169
  5.     50                358           375         558
  6.    100                374           419         672
  7.    200                296           314         640
  8.  

Case insensitive search, Pascal sources(83996301 bytes), search for 25 patterns, BuildinBM_CI here denotes FindMatchesBoyerMooreCaseInSensitive(running time in ms, lower is better).
Code: Text  [Select][+][-]
  1.  pattern len       TBmSearchCI    BuildinBM_CI
  2.      5               2565            3250
  3.     10               1488            1744
  4.     20                889            1042
  5.     50                618             709
  6.    100                444             517
  7.    200                390             442
  8.  
Title: Re: Yet another generics collection
Post by: 440bx on February 22, 2021, 07:36:35 am
The TBmSearch entity implements a Boyer-Moore incarnation called Fast-Search, and TBmhrSearch implements the Boyer-Moore-Horspool-Raita algorithm(sometimes just Raita). TBmSearchCI is a case-insensitive version of TBmSearch.
Nicely done!.
Title: Re: Yet another generics collection
Post by: avk on February 22, 2021, 07:52:21 am
Thank you.
Title: Re: Yet another generics collection
Post by: Okoba on February 22, 2021, 02:05:57 pm
Well done avk.
Title: Re: Yet another generics collection
Post by: avk on August 02, 2021, 11:50:55 am
Has rerun the JSON parsing benchmark(in attachment) due to the recent update of JsonTools, this time without Delphi.
Also below are the results of running parser tests (https://github.com/nst/JSONTestSuite) for compliance with the current JSON standard. Only tests from the "SHOULD_BE_ACCEPTED" and "SHOULD_BE_REJECTED" sections were run.
Code: Text  [Select][+][-]
  1. lgJson:
  2.   total:  283
  3.   failed: 0
  4.  
  5. JsonTools:
  6.   total:  283
  7.   failed: 22
  8.  
  9. FpJson:
  10.   crash
  11.  
Title: Re: Yet another generics collection
Post by: avk on October 15, 2021, 01:22:56 pm
lgJson now uses the Eisel-Lemire approximation algorithm for string-to-double conversion, and the Ryū algorithm for the reverse conversion.
The former is used exclusively as an internal function, but the Ryū implementation(Double2Str) has been made public and, accordingly, its performance can be compared with other double-to-string converters.
The selected subjects are divided into two groups: the first does not make an explicit memory allocation, and the second does.
The first group includes DoubleToShort from Mormot2, the built-in FloatToText, Double2Str(procedure) from lgJson and the built-in Str(shortstring).
The second includes DoubleToStr from Mormot2, the built-in FloatToStr, RyuDoubleToString from PasDblStrUtils, Double2Str(function) from lgJson and the built-in Str(string).
The benchmark generates an array of 10000000 random doubles and measures the time(ms) it takes to process the entire array(5 attempts, the best time is taken as the result).

Results:
Code: Text  [Select][+][-]
  1. 1              x86_64  x86
  2. ---------------------------
  3.   DoubleToShort 1216  2106
  4.   Str           1918  4399
  5.   FloatToText   4321  7191
  6.   Double2Str     858  2761
  7. ---------------------------
  8.  
  9. 2                  x86_64  x86
  10. -------------------------------
  11.   DoubleToStr       2480  3432
  12.   Str               2652  5163
  13.   FloatToStr        3588  6349
  14.   RyuDoubleToString 2589  7269
  15.   Double2Str        1482  3322
  16. -------------------------------
  17.  

It seems that parsing in lgJson has become noticeably faster, so it makes sense to run the parser benchmark again.

The list of samples has changed a bit and a parser from InternetTools (XQJsonParser) has been added. InternetTools was compiled with USE_PASDBLSTRUTILS define. The rest of the test subjects remained the same. The results on a win-64 machine can be seen in the attached bar chart.

Edit.
Sorry, incorrect data for the second group was provided. Fixed now.
Title: Re: Yet another generics collection
Post by: Okoba on October 17, 2021, 11:40:57 am
Great as always, avk. It is very nice that you did implement them in Pascal, it is worth mentioning them in the LGenerics readme, and maybe tell the source ones to add yours in their readme too.
Did you compare your implementation with the source ones? It seems like an interesting thing to find out the output code for two compilers.
May I ask why you did not public the Eisel-Lemire procedure?
It seems Ryu has a String to Double method too, do you have plans to test it too?
Title: Re: Yet another generics collection
Post by: avk on October 17, 2021, 03:25:43 pm
Thank you.
Actually, ports of these algorithms to Pascal have already existed, at least here (https://github.com/BeRo1985/pasdblstrutils)(don't know how long ago), so my port is definitely not the first. Perhaps it really makes sense to mention them in the readme, despite the fact that they are tied to JSON.

...
Did you compare your implementation with the source ones? It seems like an interesting thing to find out the output code for two compilers.
...
Yes, you're right, that would be interesting, maybe a little later...

...
May I ask why you did not public the Eisel-Lemire procedure?
...
To be honest, I didn't expect it to be interesting to anyone else. It is used to convert a string that has already been checked by the main parser, therefore it uses a weakened algorithm for parsing. Nothing, of course, prevents from making a normal parser for it, I will try and report the results.

...
It seems Ryu has a String to Double method too, do you have plans to test it too?
No, I don't plan to, but it seems that PasDblStrUtils has an implementation of it.
Title: Re: Yet another generics collection
Post by: avk on October 22, 2021, 02:01:10 pm
lgJson now has a public TryStr2Double() function that uses the Eisel-Lemire algorithm.
Below are the results of a quick and dirty benchmark involving Val(), ConvertStringToDouble() from PasDblStrUtils and fast_double_parser::parse_number().
Two input files were used, the first contains random uniformly distributed(well, almost, there are no nans and infinities) numbers, and the second contains numbers extracted from citylots.json. Each file was looped four times in five attempts, the best time (ms) was taken as the result.
fast_double_parser was compiled with gcc 8.1.0 with options -O3 -s -static -m64.
Code: Text  [Select][+][-]
  1. uniform.txt
  2. read 5000000 lines
  3. total size 109829099 bytes
  4.  
  5.                       x86_64      x86
  6. ------------------------------------------------
  7. Val                    3310      6692
  8. ConvertStringToDouble  1350      2886
  9. TryStr2Double           936      2152
  10. parse_number            760       nt*
  11.  
  12.  
  13.  
  14. citylots.txt
  15. read 5250126 lines
  16. total size 99166601 bytes
  17.  
  18.                       x86_64      x86
  19. ------------------------------------------------
  20. Val                    2558      5818
  21. ConvertStringToDouble  1060      2512
  22. TryStr2Double           639      1825
  23. parse_number            360       nt*
  24.                                      
  25.  
* not tested.

Also compiled the original Ryū version and added its results to the table:
Code: Text  [Select][+][-]
  1. 1              x86_64  x86
  2. ---------------------------
  3.   DoubleToShort 1216  2106
  4.   Str           1918  4399
  5.   FloatToText   4321  7191
  6.   Double2Str     858  2761
  7.   d2s_buffered   514   nt*
  8. ---------------------------
  9.  
  10. 2                  x86_64  x86
  11. -------------------------------
  12.   DoubleToStr       2480  3432
  13.   Str               2652  5163
  14.   FloatToStr        3588  6349
  15.   RyuDoubleToString 2589  7269
  16.   Double2Str        1482  3322
  17.   d2s               1253   nt*
  18. -------------------------------
  19.  
Title: Re: Yet another generics collection
Post by: AlexTP on October 22, 2021, 03:03:18 pm
As I see, you created the new StrToFloat function, which is very fast. Maybe incorporate it into FPC then?
Title: Re: Yet another generics collection
Post by: avk on October 22, 2021, 03:50:33 pm
I know that some devs read this forum, maybe it will interest them.
Title: Re: Yet another generics collection
Post by: avk on March 09, 2022, 11:00:40 am
Hi!
Some news from LGenerics:
recently, a number of functions have been added that implement some algorithms on strings and sequences, regarding metrics and fuzzy matching, the list is annotated in the README of the project. The example/fuzz_bench folder contains several benchmarks for these functions.

It was curious to compare the performance of the SimRatioLevEx() function(which is inspired by FuzzyWuzzy) with some incarnations of the FuzzyWuzzy(listed here (https://pypi.org/project/fuzzywuzzy/)) on my benchmark datasets. Disclamer: SimRatioLevEx() does not reproduce FuzzyWuzzy, but it does some things in a similar way, in particular, SimRatioLevEx() in smTokenSetEx mode and token_set_ratio() do roughly the same job.

It seems the C++ version only supports single-byte strings, so only compared to the single-byte version of SimRatioLevEx():
Code: Text  [Select][+][-]
  1.    Dataset            SimRatioLevEx() token_set_ratio()
  2.  
  3. Short/big_dist             1154              6440
  4. Short/small_dist            967              3020
  5. Medium/big_dist             811              3450
  6. Medium/small_dist           702              1470
  7. Long/big_dist              1966             15000
  8. Long/small_dist            1061              2250
  9.  
The numbers indicate the run time in milliseconds; the C++ version was compiled with gcc-8.1.0 with options -O3 -m64; the Pascal version was compiled with FPC-3.3.1-9941-g8e6e9bbf33, -O3. The benchmark was run on a win-64 machine.

The Go version, on the contrary, always works with Unicode strings:
Code: Text  [Select][+][-]
  1.    Dataset          SimRatioLevExUtf8() TokenSetRatio()
  2.  
  3. Short/big_dist             2143             18705
  4. Short/small_dist           1593              2224
  5. Medium/big_dist            1266             15062
  6. Medium/small_dist           853              1742
  7. Long/big_dist              3853             79851
  8. Long/small_dist            1269              3126
  9.  

go version: go1.10.4 linux/amd64; FPC-3.3.1-10683-g2a19e152b7 -O3. The benchmark was run on a virtual Linux machine.

Happy coding!
Title: Re: Yet another generics collection
Post by: Okoba on March 09, 2022, 11:20:00 am
Great job avk!
Just tested it and works fine.
Title: Re: Yet another generics collection
Post by: AlexTP on March 09, 2022, 11:28:07 am
Posted the new info to https://wiki.freepascal.org/LGenerics#Perfomance
Title: Re: LGenerics: yet another generics collection
Post by: avk on March 12, 2022, 06:54:37 pm
Thanks, I also added a bit more about sortings and algorithms on graphs.
Title: Re: LGenerics: yet another generics collection
Post by: AlexTP on March 12, 2022, 07:52:21 pm
Wiki pic says:
"Cycles per element (lower is better)".
What is cycle?
Why not 'milliseconds'?
Title: Re: LGenerics: yet another generics collection
Post by: avk on March 13, 2022, 06:04:31 am
The processor (core) cycle (clock cycle) is the interval between two pulses of the clock generator, the number of cycles per unit of operation can be considered a measure of performance.
The point is that the fastest algorithms process some test samples of the specified size in less than 1ms. I do not know how to measure such time intervals in Windows, whereas thanks to the presence of rdtscp instruction the number of cycles is easy to know.
Title: Re: LGenerics: yet another generics collection
Post by: 440bx on March 13, 2022, 09:27:52 am
@avk,

I have to say... the more I look at your LGenerics collection of functions, the more I like it.  You really did a great job.
Title: Re: LGenerics: yet another generics collection
Post by: avk on April 14, 2022, 08:33:21 am
Hi!
Recent news from LGenerics: added functionality (TJsonPatch class) to implement JSON Patch(RFC 6902);

JSON Patch is a JSON document format (media type is application/json-patch+json) for expressing a sequence of operations applied to a target JSON document;
it is always an array of objects, each representing a single operation, supported set of operations: ADD, REMOVE, REPLACE, MOVE, COPY, and TEST;
For example, for this document
Code: Text  [Select][+][-]
  1. {
  2.     "foo": [1, 3],
  3.     "boo": ["bar", "baz"]
  4. }
  5.  

applying this patch
Code: Text  [Select][+][-]
  1. [
  2.     {"op": "add", "path": "/foo/1", "value": "fizz"},
  3.     {"op": "replace", "path": "/boo/1", "value": "qux"},
  4.     {"op": "add", "path": "/ozz", "value": "zoo"}
  5. ]
  6.  

will have the following result:
Code: Text  [Select][+][-]
  1. {
  2.     "foo": [1, "fizz", 3],
  3.     "boo": ["bar", "qux"],
  4.     "ozz": "zoo"
  5. }
  6.  

The TJsonPatch class also contains a POC implementation of the Diff utility, which generates a patch by comparing source and target documents.
For example, for this source
Code: Text  [Select][+][-]
  1. {
  2.     "a": 1,
  3.     "b": null,
  4.     "c": ["test", "plop"]
  5. }
  6.  

and for this target
Code: Text  [Select][+][-]
  1. {
  2.     "a": 6,
  3.     "c": ["test", "flop"],
  4.     "d": "baz"
  5. }
  6.  

it will generate a patch like this:
Code: Text  [Select][+][-]
  1. [
  2.     {"op": "replace", "path": "/a", "value": 6},
  3.     {"op": "remove", "path": "/b"},
  4.     {"op": "replace", "path": "/c/1", "value": "flop"},
  5.     {"op": "add", "path": "/d", "value": "baz"}
  6. ]
  7.  

Happy coding!
Title: Re: LGenerics: yet another generics collection
Post by: AlexTP on April 14, 2022, 08:56:50 am
I wrote it to the wiki now,
https://wiki.lazarus.freepascal.org/LGenerics#About_JSON_Patch
Title: Re: LGenerics: yet another generics collection
Post by: marcov on April 14, 2022, 09:31:14 am
Wiki pic says:
"Cycles per element (lower is better)".
What is cycle?
Why not 'milliseconds'?

Because milliseconds varies between two processors of the same kind but with different frequencies. Cycles is a measure independent of the clock rate.
Title: Re: LGenerics: yet another generics collection
Post by: avk on April 14, 2022, 02:47:44 pm
@AlexTP, thanks. I edited the wiki page a bit, maybe you should fix the link.
Title: Re: LGenerics: yet another generics collection
Post by: avk on December 08, 2022, 03:40:54 pm
Hi!
There is some news in LGenerics: added(in the first approximation) unit for handling CSV documents(lgCsvUtils), which seems noticeably faster than CSVDocument. The list of classes is quite usual: the CSV document itself, the reader and the writer.

Of the additional features - the ability to selectively load document fields(a set of fields is specified by using a boolean mask), which can speed up loading.
And as an experiment, it is also possible to load large documents in multi-threaded mode.The current implementation, however, is not entirely safe because it is based on an assumption that may not hold true.

Anyway, experimenting with the "stop_times.txt" file mentioned in this discussion (https://forum.lazarus.freepascal.org/index.php/topic,61035.0.html) on my old dual-core Windows machine gives these numbers("masked" means masking the first four fields):
Code: Text  [Select][+][-]
  1. TCsvDocument, load from file: 14181 ms
  2. TCsvDocument, save to file:   66441 ms
  3. TCsvDoc, load from file:       1201 ms
  4. TCsvDoc, save to file:          468 ms
  5. TCsvDoc, load from file(MT):    671 ms
  6. TCsvDoc, load file(masked):     842 ms
  7. TCsvDoc, load file(masked,MT):  452 ms
  8.  

Any comments and suggestions are highly welcomed.   
Title: Re: LGenerics: yet another generics collection
Post by: avk on December 24, 2022, 07:24:09 am
Hi!
I would like to inform you that a unit has been added to LGenerics for exporting Pascal data structures to JSON format. The following types are currently supported (called PDOs for short):
For example, this code(taken from LGenerics/example/json/pdo_export)
Code: Pascal  [Select][+][-]
  1. program pdo2json;
  2.  
  3. {$MODE OBJFPC}{$H+}{$MODESWITCH ADVANCEDRECORDS}
  4. {$OPTIMIZATION NOORDERFIELDS}
  5.  
  6. uses
  7.   SysUtils, Variants, lgUtils, lgJson, lgPdo;
  8.  
  9. type
  10.   TPerson = record
  11.     Id,
  12.     Age: Integer;
  13.     FirstName,
  14.     LastName,
  15.     Phone: string;
  16.     class procedure WriteJson(r: Pointer; aWriter: TJsonStrWriter); static;
  17.     constructor Make(aId, aAge: Integer; const aName, aLast, aPhone: string);
  18.   end;
  19.  
  20.   TIntArray = array of Integer;
  21.  
  22.   TMember = record
  23.     MemberId: Integer;
  24.     Meta: Variant;
  25.     Person: TPerson;
  26.     RegisterDate: string;
  27.     Friends: TIntArray;
  28.     Groups: TStringArray;
  29.     constructor Make(
  30.       const p: TPerson; aId: Integer; const aMeta: Variant; const d: string; const f: TIntArray;
  31.       const g: TStringArray);
  32.   end;
  33.   TMemberList = array of TMember;
  34.  
  35.   TCommunity = record
  36.     Name,
  37.     Slogan: string;
  38.     GroupList: TStringArray;
  39.     MemberList: TMemberList;
  40.     constructor Make(const aName, aSlogan: string; const gl: TStringArray; const ml: TMemberList);
  41.   end;
  42.   TCommunityList = array of TCommunity;
  43.  
  44. class procedure TPerson.WriteJson(r: Pointer; aWriter: TJsonStrWriter);
  45. type
  46.   PPerson = ^TPerson;
  47. const
  48.   cId    = 'id';
  49.   cAge   = 'age';
  50.   cName  = 'firstName';
  51.   cLast  = 'lastName';
  52.   cPhone = 'phone';
  53. begin
  54.   with PPerson(r)^ do
  55.     aWriter
  56.       .BeginObject
  57.         .Add(cId, Id)
  58.         .Add(cAge, Age)
  59.         .Add(cName, FirstName)
  60.         .Add(cLast, LastName)
  61.         .Add(cPhone, Phone)
  62.       .EndObject;
  63. end;
  64.  
  65. constructor TPerson.Make(aId, aAge: Integer; const aName, aLast, aPhone: string);
  66. begin
  67.   Id := aId;
  68.   Age := aAge;
  69.   FirstName := aName;
  70.   LastName := aLast;
  71.   Phone := aPhone;
  72. end;
  73.  
  74. constructor TMember.Make(const p: TPerson; aId: Integer; const aMeta: Variant; const d: string;
  75.   const f: TIntArray; const g: TStringArray);
  76. begin
  77.   MemberId := aId;
  78.   Meta := aMeta;
  79.   Person := p;
  80.   RegisterDate := d;
  81.   Friends := f;
  82.   Groups := g;
  83. end;
  84.  
  85. constructor TCommunity.Make(const aName, aSlogan: string; const gl: TStringArray; const ml: TMemberList);
  86. begin
  87.   Name := aName;
  88.   Slogan := aSlogan;
  89.   GroupList := gl;
  90.   MemberList := ml;
  91. end;
  92.  
  93. var
  94.   ComList: array of TCommunity = nil;
  95.  
  96. procedure MakeList;
  97. begin
  98.   ComList := [
  99.     TCommunity.Make(
  100.       'Earthlings', 'The further, the more',
  101.       ['bead game', 'kitchen', 'fishing', 'beer', 'skates', 'cutting and sewing', 'choral singing'],
  102.       [
  103.         TMember.Make(
  104.           TPerson.Make(
  105.             42, 21, 'Walter', 'Reynolds', '(204) 537-5981'
  106.           ),
  107.           1, null, '2018-11-13', [7, 17], ['bead game', 'beer', 'skates', 'cutting and sewing']
  108.         ),
  109.         TMember.Make(
  110.           TPerson.Make(
  111.             11, 32, 'Leigh', 'Garza', '(686) 795-8242'
  112.           ),
  113.           7, VarArrayOf([42, pi]), '2020-01-10', [1, 17, 21], ['kitchen', 'fishing', 'cutting and sewing']
  114.         ),
  115.         TMember.Make(
  116.           TPerson.Make(
  117.             5, 19, 'Damon', 'Shelton', '1-404-576-3173'
  118.           ),
  119.           17, VarArrayOf(['none', 'some', null]), '2020-07-29', [1, 11, 21], ['bead game', 'kitchen', 'fishing']
  120.         ),
  121.         TMember.Make(
  122.           TPerson.Make(
  123.             3, 27, 'Nora', 'Potts', '(824) 554-0791'
  124.           ),
  125.           11, VarArrayOf(['meta', 1001]), '2019-03-21', [7, 17, 21], ['beer', 'skates', 'cutting and sewing']
  126.         ),
  127.         TMember.Make(
  128.           TPerson.Make(
  129.             24, 44, 'Shad', 'Campbell', '(874) 556-376'
  130.           ),
  131.           21, 42, '2021-05-20', [1, 7, 17, 11], ['fishing', 'beer', 'cutting and sewing']
  132.         )
  133.       ]
  134.     ),
  135.     TCommunity.Make(
  136.       'Rabbit breeders', 'Who is not with us is not with us',
  137.       ['dinosaur hunting', 'knitting', 'chess', 'car race', 'dancing'],
  138.       [
  139.         TMember.Make(
  140.             TPerson.Make(
  141.               5, 23, 'Mikayla', 'Ray', '1-565-598-5632'
  142.             ),
  143.             22, VarArrayOf(['first', null, 42]), '2018-02-23', [17, 71, 45], ['dinosaur hunting', 'knitting']
  144.         ),
  145.         TMember.Make(
  146.           TPerson.Make(
  147.             37, 35, 'Tyler', 'Moody', '(345) 727-5455'
  148.           ),
  149.           17, 1001, '2021-11-13', [45, 10, 33], ['chess', 'car race', 'dancing']
  150.         ),
  151.         TMember.Make(
  152.           TPerson.Make(
  153.             17, 54, 'Plato', 'Henson', '1-385-896-8851'
  154.           ),
  155.           71, VarArrayOf(['get','put',null]), '2020-12-11', [22, 17], ['knitting', 'chess', 'car race']
  156.         ),
  157.         TMember.Make(
  158.           TPerson.Make(
  159.             23, 19, 'Merrill', 'Joseph', '(634) 768-7274'
  160.           ),
  161.           45, null, '2022-01-15', [17, 71, 10], ['dinosaur hunting', 'chess', 'dancing']
  162.         ),
  163.         TMember.Make(
  164.           TPerson.Make(
  165.             12, 29, 'Jessica', 'Meyers', '(706) 844-0017'
  166.           ),
  167.           10, VarArrayOf(['stop','none']), '2017-04-30', [17, 71, 45], ['knitting', 'chess', 'car race', 'dancing']
  168.         ),
  169.         TMember.Make(
  170.           TPerson.Make(
  171.             7, 33, 'Boris', 'Norton', '(211) 688-1153'
  172.           ),
  173.           33, VarArrayOf([null, null]), '2019-08-07', [22, 17, 71], ['dinosaur hunting', 'knitting', 'chess', 'car race', 'dancing']
  174.         )
  175.       ]
  176.     )
  177.   ];
  178. end;
  179.  
  180. var
  181.   n: specialize TGAutoRef<TJsonNode>;
  182.   s: string;
  183. begin
  184.   RegisterRecordJsonProc(TypeInfo(TPerson), @TPerson.WriteJson);
  185.   RegisterRecordFields(TypeInfo(TMember), ['memberId', 'meta', 'person', 'registerDate', 'friends', 'groups']);
  186.   RegisterRecordFields(TypeInfo(TCommunity), ['name', 'slogan', 'groupList', 'memberList']);
  187.  
  188.   MakeList;
  189.  
  190.   s := specialize PdoToJson<TCommunityList>(ComList);
  191.  
  192.   if not n.Instance.Parse(s) then
  193.     WriteLn('Oops, something went wrong :(')
  194.   else
  195.     WriteLn(n.Instance.FormatJson([jfoEgyptBrace]));
  196. end.
  197.  

will produce nice JSON like this:
Code: Text  [Select][+][-]
  1. [
  2.     {
  3.         "name": "Earthlings",
  4.         "slogan": "The further, the more",
  5.         "groupList": [
  6.             "bead game",
  7.             "kitchen",
  8.             "fishing",
  9.             "beer",
  10.             "skates",
  11.             "cutting and sewing",
  12.             "choral singing"
  13.         ],
  14.         "memberList": [
  15.             {
  16.                 "memberId": 1,
  17.                 "meta": null,
  18.                 "person": {
  19.                     "id": 42,
  20.                     "age": 21,
  21.                     "firstName": "Walter",
  22.                     "lastName": "Reynolds",
  23.                     "phone": "(204) 537-5981"
  24.                 },
  25.                 "registerDate": "2018-11-13",
  26.                 "friends": [
  27.                     7,
  28.                     17
  29.                 ],
  30.                 "groups": [
  31.                     "bead game",
  32.                     "beer",
  33.                     "skates",
  34.                     "cutting and sewing"
  35.                 ]
  36.             }, {
  37.                 "memberId": 7,
  38.                 "meta": [
  39.                     42,
  40.                     3.141592653589793
  41.                 ],
  42.                 "person": {
  43.                     "id": 11,
  44.                     "age": 32,
  45.                     "firstName": "Leigh",
  46.                     "lastName": "Garza",
  47.                     "phone": "(686) 795-8242"
  48.                 },
  49.                 "registerDate": "2020-01-10",
  50.                 "friends": [
  51.                     1,
  52.                     17,
  53.                     21
  54.                 ],
  55.                 "groups": [
  56.                     "kitchen",
  57.                     "fishing",
  58.                     "cutting and sewing"
  59.                 ]
  60.             }, {
  61.                 "memberId": 17,
  62.                 "meta": [
  63.                     "none",
  64.                     "some",
  65.                     null
  66.                 ],
  67.                 "person": {
  68.                     "id": 5,
  69.                     "age": 19,
  70.                     "firstName": "Damon",
  71.                     "lastName": "Shelton",
  72.                     "phone": "1-404-576-3173"
  73.                 },
  74.                 "registerDate": "2020-07-29",
  75.                 "friends": [
  76.                     1,
  77.                     11,
  78.                     21
  79.                 ],
  80.                 "groups": [
  81.                     "bead game",
  82.                     "kitchen",
  83.                     "fishing"
  84.                 ]
  85.             }, {
  86.                 "memberId": 11,
  87.                 "meta": [
  88.                     "meta",
  89.                     1001
  90.                 ],
  91.                 "person": {
  92.                     "id": 3,
  93.                     "age": 27,
  94.                     "firstName": "Nora",
  95.                     "lastName": "Potts",
  96.                     "phone": "(824) 554-0791"
  97.                 },
  98.                 "registerDate": "2019-03-21",
  99.                 "friends": [
  100.                     7,
  101.                     17,
  102.                     21
  103.                 ],
  104.                 "groups": [
  105.                     "beer",
  106.                     "skates",
  107.                     "cutting and sewing"
  108.                 ]
  109.             }, {
  110.                 "memberId": 21,
  111.                 "meta": 42,
  112.                 "person": {
  113.                     "id": 24,
  114.                     "age": 44,
  115.                     "firstName": "Shad",
  116.                     "lastName": "Campbell",
  117.                     "phone": "(874) 556-376"
  118.                 },
  119.                 "registerDate": "2021-05-20",
  120.                 "friends": [
  121.                     1,
  122.                     7,
  123.                     17,
  124.                     11
  125.                 ],
  126.                 "groups": [
  127.                     "fishing",
  128.                     "beer",
  129.                     "cutting and sewing"
  130.                 ]
  131.             }
  132.         ]
  133.     }, {
  134.         "name": "Rabbit breeders",
  135.         "slogan": "Who is not with us is not with us",
  136.         "groupList": [
  137.             "dinosaur hunting",
  138.             "knitting",
  139.             "chess",
  140.             "car race",
  141.             "dancing"
  142.         ],
  143.         "memberList": [
  144.             {
  145.                 "memberId": 22,
  146.                 "meta": [
  147.                     "first",
  148.                     null,
  149.                     42
  150.                 ],
  151.                 "person": {
  152.                     "id": 5,
  153.                     "age": 23,
  154.                     "firstName": "Mikayla",
  155.                     "lastName": "Ray",
  156.                     "phone": "1-565-598-5632"
  157.                 },
  158.                 "registerDate": "2018-02-23",
  159.                 "friends": [
  160.                     17,
  161.                     71,
  162.                     45
  163.                 ],
  164.                 "groups": [
  165.                     "dinosaur hunting",
  166.                     "knitting"
  167.                 ]
  168.             }, {
  169.                 "memberId": 17,
  170.                 "meta": 1001,
  171.                 "person": {
  172.                     "id": 37,
  173.                     "age": 35,
  174.                     "firstName": "Tyler",
  175.                     "lastName": "Moody",
  176.                     "phone": "(345) 727-5455"
  177.                 },
  178.                 "registerDate": "2021-11-13",
  179.                 "friends": [
  180.                     45,
  181.                     10,
  182.                     33
  183.                 ],
  184.                 "groups": [
  185.                     "chess",
  186.                     "car race",
  187.                     "dancing"
  188.                 ]
  189.             }, {
  190.                 "memberId": 71,
  191.                 "meta": [
  192.                     "get",
  193.                     "put",
  194.                     null
  195.                 ],
  196.                 "person": {
  197.                     "id": 17,
  198.                     "age": 54,
  199.                     "firstName": "Plato",
  200.                     "lastName": "Henson",
  201.                     "phone": "1-385-896-8851"
  202.                 },
  203.                 "registerDate": "2020-12-11",
  204.                 "friends": [
  205.                     22,
  206.                     17
  207.                 ],
  208.                 "groups": [
  209.                     "knitting",
  210.                     "chess",
  211.                     "car race"
  212.                 ]
  213.             }, {
  214.                 "memberId": 45,
  215.                 "meta": null,
  216.                 "person": {
  217.                     "id": 23,
  218.                     "age": 19,
  219.                     "firstName": "Merrill",
  220.                     "lastName": "Joseph",
  221.                     "phone": "(634) 768-7274"
  222.                 },
  223.                 "registerDate": "2022-01-15",
  224.                 "friends": [
  225.                     17,
  226.                     71,
  227.                     10
  228.                 ],
  229.                 "groups": [
  230.                     "dinosaur hunting",
  231.                     "chess",
  232.                     "dancing"
  233.                 ]
  234.             }, {
  235.                 "memberId": 10,
  236.                 "meta": [
  237.                     "stop",
  238.                     "none"
  239.                 ],
  240.                 "person": {
  241.                     "id": 12,
  242.                     "age": 29,
  243.                     "firstName": "Jessica",
  244.                     "lastName": "Meyers",
  245.                     "phone": "(706) 844-0017"
  246.                 },
  247.                 "registerDate": "2017-04-30",
  248.                 "friends": [
  249.                     17,
  250.                     71,
  251.                     45
  252.                 ],
  253.                 "groups": [
  254.                     "knitting",
  255.                     "chess",
  256.                     "car race",
  257.                     "dancing"
  258.                 ]
  259.             }, {
  260.                 "memberId": 33,
  261.                 "meta": [
  262.                     null,
  263.                     null
  264.                 ],
  265.                 "person": {
  266.                     "id": 7,
  267.                     "age": 33,
  268.                     "firstName": "Boris",
  269.                     "lastName": "Norton",
  270.                     "phone": "(211) 688-1153"
  271.                 },
  272.                 "registerDate": "2019-08-07",
  273.                 "friends": [
  274.                     22,
  275.                     17,
  276.                     71
  277.                 ],
  278.                 "groups": [
  279.                     "dinosaur hunting",
  280.                     "knitting",
  281.                     "chess",
  282.                     "car race",
  283.                     "dancing"
  284.                 ]
  285.             }
  286.         ]
  287.     }
  288. ]
  289.  

The performance should be noticeably better than in FpJsonRtti, but I would like to come back to that a little later.

Merry Christmas!
Title: Re: LGenerics: yet another generics collection
Post by: 440bx on December 24, 2022, 07:56:58 am
Merry Christmas!
Thank you and Merry Christmas to you and everyone else as well.

Aside from that, I was compiling the "enumerable" example from your latest lgenerics and got the following errors:

Code: Text  [Select][+][-]
  1. Hint: (11030) Start of reading config file D:\Laz64trunk\fpc\bin\x86_64-win64\fpc.cfg
  2. Hint: (11031) End of reading config file D:\Laz64trunk\fpc\bin\x86_64-win64\fpc.cfg
  3. Free Pascal Compiler version 3.3.1-12125-g7da8c774be [2022/11/21] for x86_64
  4. Copyright (c) 1993-2022 by Florian Klaempfl and others
  5. (1002) Target OS: Win64 for x64
  6. (3104) Compiling lgenerics.pas
  7. (1008) 19 lines compiled, 4.8 sec
  8. (1022) 2 hint(s) issued
  9. Hint: (11030) Start of reading config file D:\Laz64trunk\fpc\bin\x86_64-win64\fpc.cfg
  10. Hint: (11031) End of reading config file D:\Laz64trunk\fpc\bin\x86_64-win64\fpc.cfg
  11. Free Pascal Compiler version 3.3.1-12125-g7da8c774be [2022/11/21] for x86_64
  12. Copyright (c) 1993-2022 by Florian Klaempfl and others
  13. (1002) Target OS: Win64 for x64
  14. (3104) Compiling simple_db.lpr
  15. (3104) Compiling main.pas
  16. C:\Users\Private\Downloads\LGenerics-master\example\enumerable\main.pas(93,26) Hint: (5024) Parameter "Sender" not used
  17. C:\Users\Private\Downloads\LGenerics-master\example\enumerable\main.pas(94,27) Hint: (5024) Parameter "Sender" not used
  18. C:\Users\Private\Downloads\LGenerics-master\example\enumerable\main.pas(95,30) Hint: (5024) Parameter "Sender" not used
  19. C:\Users\Private\Downloads\LGenerics-master\example\enumerable\main.pas(96,33) Hint: (5024) Parameter "Sender" not used
  20. C:\Users\Private\Downloads\LGenerics-master\example\enumerable\main.pas(97,28) Hint: (5024) Parameter "Sender" not used
  21. C:\Users\Private\Downloads\LGenerics-master\example\enumerable\main.pas(98,34) Hint: (5024) Parameter "Sender" not used
  22. C:\Users\Private\Downloads\LGenerics-master\example\enumerable\main.pas(99,39) Hint: (5024) Parameter "Sender" not used
  23. C:\Users\Private\Downloads\LGenerics-master\example\enumerable\main.pas(100,37) Hint: (5024) Parameter "Sender" not used
  24. C:\Users\Private\Downloads\LGenerics-master\example\enumerable\main.pas(101,27) Hint: (5024) Parameter "Sender" not used
  25. C:\Users\Private\Downloads\LGenerics-master\example\enumerable\main.pas(102,36) Hint: (5024) Parameter "Sender" not used
  26. C:\Users\Private\Downloads\LGenerics-master\example\enumerable\main.pas(103,40) Hint: (5024) Parameter "Sender" not used
  27. C:\Users\Private\Downloads\LGenerics-master\example\enumerable\main.pas(320,38) Error: (5038) Identifier idents no member "OrElseDefault"
  28. C:\Users\Private\Downloads\LGenerics-master\example\enumerable\main.pas(323,37) Error: (5038) Identifier idents no member "OrElseDefault"
  29. C:\Users\Private\Downloads\LGenerics-master\example\enumerable\main.pas(326,42) Error: (5038) Identifier idents no member "OrElseDefault"
  30. C:\Users\Private\Downloads\LGenerics-master\example\enumerable\main.pas(329,42) Error: (5038) Identifier idents no member "OrElseDefault"
  31. C:\Users\Private\Downloads\LGenerics-master\example\enumerable\main.pas(348,72) Error: (5038) Identifier idents no member "OrElseDefault"
  32. C:\Users\Private\Downloads\LGenerics-master\example\enumerable\main.pas(351,71) Error: (5038) Identifier idents no member "OrElseDefault"
  33. C:\Users\Private\Downloads\LGenerics-master\example\enumerable\main.pas(354,76) Error: (5038) Identifier idents no member "OrElseDefault"
  34. C:\Users\Private\Downloads\LGenerics-master\example\enumerable\main.pas(357,76) Error: (5038) Identifier idents no member "OrElseDefault"
  35. C:\Users\Private\Downloads\LGenerics-master\example\enumerable\main.pas(406,65) Error: (5038) Identifier idents no member "OrElseDefault"
  36. C:\Users\Private\Downloads\LGenerics-master\example\enumerable\main.pas(409,65) Error: (5038) Identifier idents no member "OrElseDefault"
  37. C:\Users\Private\Downloads\LGenerics-master\example\enumerable\main.pas(442,35) Error: (5038) Identifier idents no member "OrElseDefault"
  38. C:\Users\Private\Downloads\LGenerics-master\example\enumerable\main.pas(480) Fatal: (10026) There were 11 errors compiling module, stopping
  39. Fatal: (1018) Compilation aborted
  40. Error: D:\Laz64trunk\fpc\bin\x86_64-win64\ppcx64.exe returned an error exitcode
  41.  
The compiler is unhappy about "OrElseDefault". 

Suggestions/guidance as to how I could solve the problem would be most welcome :)

Thank you.
Title: Re: LGenerics: yet another generics collection
Post by: AlexTP on December 24, 2022, 08:11:45 am
Posted the info to wiki, https://wiki.freepascal.org/LGenerics#Exporting_structures_to_JSON_format
Title: Re: LGenerics: yet another generics collection
Post by: avk on December 24, 2022, 08:35:36 am
@440bx, thank you very much for discovering this sad fact. Some time ago I excluded the TGOptional.OrElseDefault() method and forgot to fix it in this example. Now fixed.

@AlexTP, thanks, but it seems a bit too long. I believe the example could have been removed.
Title: Re: LGenerics: yet another generics collection
Post by: 440bx on December 24, 2022, 09:16:50 am
@440bx, thank you very much for discovering this sad fact. Some time ago I excluded the TGOptional.OrElseDefault() method and forgot to fix it in this example. Now fixed.
My pleasure to be of some help. 
Title: Re: LGenerics: yet another generics collection
Post by: zbyna on December 24, 2022, 05:34:09 pm
Hi!
I would like to inform you that a unit has been added to LGenerics for exporting Pascal data structures to JSON format.
...

The performance should be noticeably better than in FpJsonRtti, but I would like to come back to that a little later.

Merry Christmas!

Thanks for great present. Merry Christmas!

Support for https://msgpack.org/ (https://msgpack.org/) would be great too.
Title: Re: LGenerics: yet another generics collection
Post by: avk on December 25, 2022, 06:13:18 am
Support for MessagePack was planned, but this is unlikely to happen anytime soon.

As promised earlier, let's try to roughly estimate the performance of export to JSON.
Datasets used: a collection of simple items(with three string properties and one integer property) and an array of records whose fields contain values that coincide with the values of the collection's item properties(i.e. the resulting JSONs should be the same). The number of elements in the datasets was chosen so that the size of the resulting JSON approximately corresponded to the values (20KB, 100KB, 1MB, 10MB, 50MB).
TJSONStreamer.CollectionToJSON() was taken as a reference implementation(FpJsonStreamer for short), other members:
  - PdoToJson() with a collection as parameter(PdoCollection);
  - PdoToJson() with array as parameter and field name list registration(PdoRecordFieldMap);
  - PdoToJson() with array as parameter and custom callback registration(PdoRecordCallback);
Each member exports the data several times(number of attempts is pre-defined), the best time is taken as the result.
Full benchmark code(Windows only, uses QueryPerformanceCounter):
Code: Pascal  [Select][+][-]
  1. program test;
  2.  
  3. {$MODE OBJFPC}{$H+}{$MODESWITCH ADVANCEDRECORDS}
  4. {$OPTIMIZATION NOORDERFIELDS}
  5.  
  6. uses
  7.   Windows, Classes, SysUtils, lgPdo, FpJsonRtti, lgJson;
  8.  
  9. const
  10.   AlphaLen = 64;
  11.   Alphabet: array[0..AlphaLen-1] of Char = '1234567890ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz_ ';
  12.  
  13. function RandomString(aLength: SizeInt): string;
  14. var
  15.   I: SizeInt;
  16.   p: PChar;
  17. begin
  18.   Result := '';
  19.   SetLength(Result, aLength);
  20.   p := PChar(Result);
  21.   for I := 0 to Pred(aLength) do
  22.     p[I] := Alphabet[Random(AlphaLen)];
  23. end;
  24.  
  25. type
  26.   TMyObj = class(TCollectionItem)
  27.   private
  28.     FId: Int64;
  29.     FName,
  30.     FValue,
  31.     FInfo: string;
  32.   published
  33.     property id: Int64 read FId write FId;
  34.     property name: string read FName write FName;
  35.     property value: string read FValue write FValue;
  36.     property info: string read FInfo write FInfo;
  37.   end;
  38.  
  39.   TMyRec = record
  40.     Id: Int64;
  41.     Name,
  42.     Value,
  43.     Info: string;
  44.     class procedure JsonWrite(r: Pointer; aWriter: TJsonStrWriter); static;
  45.   end;
  46.  
  47. class procedure TMyRec.JsonWrite(r: Pointer; aWriter: TJsonStrWriter);
  48. type
  49.   PMyRec = ^TMyRec;
  50. const
  51.   fnId    = 'id';
  52.   fnName  = 'name';
  53.   fnValue = 'value';
  54.   fnInfo  = 'info';
  55. begin
  56.   with PMyRec(r)^ do
  57.     aWriter
  58.       .BeginObject
  59.         .Add(fnId, Id)
  60.         .Add(fnName, Name)
  61.         .Add(fnValue, Value)
  62.         .Add(fnInfo, Info)
  63.       .EndObject;
  64. end;
  65.  
  66. const
  67.   MinLen = 5;
  68.   Range  = 16;
  69.  
  70. var
  71.   TestColl: TCollection = nil;
  72.   RecList: array of TMyRec;
  73.  
  74. procedure UpdateData(aElCount: Integer);
  75. var
  76.   I, OldSize: Integer;
  77. const
  78.   IdRange = 9007199254740991;
  79. begin
  80.   if TestColl = nil then
  81.     TestColl := TCollection.Create(TMyObj);
  82.   OldSize := TestColl.Count;
  83.   SetLength(RecList, aElCount);
  84.   for I := OldSize to Pred(aElCount) do
  85.     with TMyObj(TestColl.Add) do begin
  86.       Id   := Random(IdRange);
  87.       Name := RandomString(MinLen + Random(Range));
  88.       Value := RandomString(MinLen + Random(Range));
  89.       Info := RandomString(MinLen + Random(Range));
  90.       RecList[I].Id := Id;
  91.       RecList[I].Name := Name;
  92.       RecList[I].Value := Value;
  93.       RecList[I].Info := Info;
  94.     end;
  95. end;
  96.  
  97. function JsonStreamer: string;
  98. begin
  99.   with TJSONStreamer.Create(nil) do
  100.     try
  101.       Result := CollectionToJSON(TestColl);
  102.     finally
  103.       Free;
  104.     end;
  105. end;
  106.  
  107. function PdoCollection: string;
  108. begin
  109.   Result := PdoToJson(TypeInfo(TestColl), TestColl);
  110. end;
  111.  
  112. function PdoMap: string;
  113. begin
  114.   Result := PdoToJson(TypeInfo(RecList), RecList);
  115. end;
  116.  
  117. function PdoProc: string;
  118. begin
  119.   Result := PdoToJson(TypeInfo(RecList), RecList);
  120. end;
  121.  
  122. procedure RegisterFields;
  123. begin
  124.   RegisterRecordFields(TypeInfo(TMyRec), ['id','name','value','info']);
  125. end;
  126.  
  127. procedure RegisterCallback;
  128. begin
  129.   RegisterRecordJsonProc(TypeInfo(TMyRec), @TMyRec.JsonWrite);
  130. end;
  131.  
  132. procedure UnRegister;
  133. begin
  134.   UnRegisterPdo(TypeInfo(TMyRec));
  135. end;
  136.  
  137. type
  138.   TJsonFun = function: string;
  139.  
  140.   TMember = record
  141.     Fun: TJsonFun;
  142.     Name: string;
  143.     BeforeRun,
  144.     AfterRun: TProcedure;
  145.   end;
  146.  
  147.   TRound = record
  148.     ElCount,
  149.     TryCount: Integer;
  150.     JsonSize: string;
  151.   end;
  152.  
  153. const
  154.   MemberList: array of TMember = (
  155.     (Fun: @JsonStreamer;  Name: 'FpJsonStreamer......'; BeforeRun: nil; AfterRun: nil),
  156.     (Fun: @PdoCollection; Name: 'PdoCollection.......'; BeforeRun: nil; AfterRun: nil),
  157.     (Fun: @PdoMap;        Name: 'PdoRecordFieldMap...'; BeforeRun: @RegisterFields; AfterRun: @UnRegister),
  158.     (Fun: @PdoProc;       Name: 'PdoRecordCallback...'; BeforeRun: @RegisterCallback; AfterRun: @UnRegister));
  159.  
  160.   Rounds: array of TRound = (
  161.     (ElCount: 220;    TryCount: 100; JsonSize: '20 KB'),
  162.     (ElCount: 1091;   TryCount:  50; JsonSize: '100 KB'),
  163.     (ElCount: 10830;  TryCount:  10; JsonSize: '1 MB'),
  164.     (ElCount: 108400; TryCount:   5; JsonSize: '10 MB'),
  165.     (ElCount: 542000; TryCount:   1; JsonSize: '50 MB')
  166.   );
  167.  
  168. procedure Run;
  169. var
  170.   CurrRound: TRound;
  171.   Member: TMember;
  172.   I: Integer;
  173.   Start, Fin, Freq, Best: Int64;
  174.   Elapsed, Rate: Double;
  175.   s: string = '';
  176. const
  177.   Million = 1000000;
  178. begin
  179.   if not QueryPerformanceFrequency(Freq) or (Freq = 0) then
  180.     begin
  181.       WriteLn('Oops, something went wrong with QueryPerformanceFrequency()');
  182.       WriteLn('Error: ', GetLastOsError);
  183.       exit;
  184.     end;
  185.   for CurrRound in Rounds do begin
  186.     UpdateData(CurrRound.ElCount);
  187.     WriteLn('-------<JSON size ', CurrRound.JsonSize, '>-------');
  188.     for Member in MemberList do begin
  189.       if Member.BeforeRun <> nil then
  190.         Member.BeforeRun();
  191.       Best := High(Int64);
  192.       for I := 1 to CurrRound.TryCount do begin
  193.         QueryPerformanceCounter(Start);
  194.         s := Member.Fun();
  195.         QueryPerformanceCounter(Fin);
  196.         if Fin - Start < Best then
  197.           Best := Fin - Start;
  198.       end;
  199.       if Member.AfterRun <> nil then
  200.         Member.AfterRun();
  201.       Elapsed := Double(Best)/Freq;
  202.       WriteLn('  ', Member.Name, Double2Str(Double(Round(Elapsed*Million))/1000), ' ms.');
  203.       Rate := (Double(Length(s))/Million)/Elapsed;
  204.       WriteLn('  Rating:             ', Double2Str(Double(Round(Rate*100))/100), ' MB/s.');
  205.     end;
  206.   end;
  207. end;
  208.  
  209. begin
  210.   Run;
  211.   TestColl.Free;
  212. end.
  213.  

Results on my machine:
Code: Text  [Select][+][-]
  1. -------<JSON size 20 KB>-------
  2.   FpJsonStreamer......1.139 ms.
  3.   Rating:             20.41 MB/s.
  4.   PdoCollection.......0.135 ms.
  5.   Rating:             149.47 MB/s.
  6.   PdoRecordFieldMap...0.095 ms.
  7.   Rating:             212.01 MB/s.
  8.   PdoRecordCallback...0.06 ms.
  9.   Rating:             336.12 MB/s.
  10. -------<JSON size 100 KB>-------
  11.   FpJsonStreamer......6.171 ms.
  12.   Rating:             18.76 MB/s.
  13.   PdoCollection.......0.675 ms.
  14.   Rating:             148.94 MB/s.
  15.   PdoRecordFieldMap...0.475 ms.
  16.   Rating:             211.85 MB/s.
  17.   PdoRecordCallback...0.304 ms.
  18.   Rating:             331.03 MB/s.
  19. -------<JSON size 1 MB>-------
  20.   FpJsonStreamer......88.315 ms.
  21.   Rating:             13.04 MB/s.
  22.   PdoCollection.......7.062 ms.
  23.   Rating:             141.6 MB/s.
  24.   PdoRecordFieldMap...5.018 ms.
  25.   Rating:             199.27 MB/s.
  26.   PdoRecordCallback...3.317 ms.
  27.   Rating:             301.47 MB/s.
  28. -------<JSON size 10 MB>-------
  29.   FpJsonStreamer......3736.737 ms.
  30.   Rating:             3.08 MB/s.
  31.   PdoCollection.......76.899 ms.
  32.   Rating:             130.16 MB/s.
  33.   PdoRecordFieldMap...56.989 ms.
  34.   Rating:             175.63 MB/s.
  35.   PdoRecordCallback...40.309 ms.
  36.   Rating:             248.3 MB/s.
  37. -------<JSON size 50 MB>-------
  38.   FpJsonStreamer......86500.116 ms.
  39.   Rating:             0.67 MB/s.
  40.   PdoCollection.......379.533 ms.
  41.   Rating:             131.94 MB/s.
  42.   PdoRecordFieldMap...278.097 ms.
  43.   Rating:             180.07 MB/s.
  44.   PdoRecordCallback...192.341 ms.
  45.   Rating:             260.35 MB/s.
  46.  

It seems to work pretty fast.
Title: Re: LGenerics: yet another generics collection
Post by: AlexTP on December 25, 2022, 12:18:19 pm
Posted this to wiki, https://wiki.freepascal.org/LGenerics#Perfomance_of_export_to_JSON
Title: Re: LGenerics: yet another generics collection
Post by: avk on December 25, 2022, 01:02:21 pm
Honestly, it would be much more interesting to see these numbers on other devices.
Title: Re: LGenerics: yet another generics collection
Post by: avk on December 25, 2022, 05:01:38 pm
I guess we can end this pointless thread.
TinyPortal © 2005-2018