Recent

Author Topic: Yet another generics collection  (Read 11017 times)

avk

  • Sr. Member
  • ****
  • Posts: 265
    • my self-education project
Yet another generics collection
« on: February 04, 2019, 06:18:43 am »
As a result of experiments with FPC generics:
https://github.com/avk959/LGenerics
Tested on Windows and Linux.

Alextp

  • Hero Member
  • *****
  • Posts: 964
    • UVviewsoft
Re: Yet another generics collection
« Reply #1 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)

Blaazen

  • Hero Member
  • *****
  • Posts: 2782
  • POKE 54296,15
    • Eye-Candy Controls
Re: Yet another generics collection
« Reply #2 on: February 04, 2019, 09:15:25 am »
Lazarus 2.1.0 r61214:62238 FPC 3.3.1 r40507 x86_64-linux-qt Chakra, Qt 4.8.7/5.13.2, Plasma 5.17.3
Lazarus 1.8.2 r57369 FPC 3.0.4 i386-win32-win32/win64 Wine 3.21

Try Eye-Candy Controls: https://sourceforge.net/projects/eccontrols/files/

heejit

  • Full Member
  • ***
  • Posts: 216
Re: Yet another generics collection
« Reply #3 on: February 04, 2019, 10:31:17 am »
If possible add into OPM  and a wiki with examples

Thaddy

  • Hero Member
  • *****
  • Posts: 10112
Re: Yet another generics collection
« Reply #4 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:-)
« Last Edit: February 04, 2019, 10:50:17 am by Thaddy »
I am more like donkey than shrek

marcov

  • Global Moderator
  • Hero Member
  • *****
  • Posts: 8385
  • FPC developer.
Re: Yet another generics collection
« Reply #5 on: February 04, 2019, 10:47:58 am »
Sortedlist uses single array. That is a scaling risk when you get into the 100k range.

Thaddy

  • Hero Member
  • *****
  • Posts: 10112
Re: Yet another generics collection
« Reply #6 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)
« Last Edit: February 04, 2019, 10:55:57 am by Thaddy »
I am more like donkey than shrek

marcov

  • Global Moderator
  • Hero Member
  • *****
  • Posts: 8385
  • FPC developer.
Re: Yet another generics collection
« Reply #7 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
« Last Edit: February 04, 2019, 12:36:01 pm by marcov »

avk

  • Sr. Member
  • ****
  • Posts: 265
    • my self-education project
Re: Yet another generics collection
« Reply #8 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.

Leledumbo

  • Hero Member
  • *****
  • Posts: 8209
  • Programming + Glam Metal + Tae Kwon Do = Me
Re: Yet another generics collection
« Reply #9 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.

Thaddy

  • Hero Member
  • *****
  • Posts: 10112
Re: Yet another generics collection
« Reply #10 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.
« Last Edit: February 04, 2019, 01:05:05 pm by Thaddy »
I am more like donkey than shrek

Thaddy

  • Hero Member
  • *****
  • Posts: 10112
Re: Yet another generics collection
« Reply #11 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...
I am more like donkey than shrek

avk

  • Sr. Member
  • ****
  • Posts: 265
    • my self-education project
Re: Yet another generics collection
« Reply #12 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?

Thaddy

  • Hero Member
  • *****
  • Posts: 10112
Re: Yet another generics collection
« Reply #13 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.
« Last Edit: February 04, 2019, 02:08:17 pm by Thaddy »
I am more like donkey than shrek

marcov

  • Global Moderator
  • Hero Member
  • *****
  • Posts: 8385
  • FPC developer.
Re: Yet another generics collection
« Reply #14 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
« Last Edit: February 04, 2019, 02:31:23 pm by marcov »

 

TinyPortal © 2005-2018