Recent

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

avk

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

avk

  • Sr. Member
  • ****
  • Posts: 265
    • my self-education project
Re: Yet another generics collection
« Reply #31 on: January 05, 2020, 07:37:50 am »
Happy 2020!

I added a translation of Orson Peters' PDQSort algorithm.

avk

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

julkas

  • Hero Member
  • *****
  • Posts: 576
  • KISS principle / Lazarus 2.0.6 / FPC 3.0.4
Re: Yet another generics collection
« Reply #33 on: January 31, 2020, 06:15:34 pm »
@avk your attachments are invisible for guests.
procedure mulu64(a, b: QWORD; out clo, chi: QWORD); assembler;
asm
  mov rax, a
  mov rdx, b
  mul rdx
  mov [clo], rax
  mov [chi], rdx
end;

Thaddy

  • Hero Member
  • *****
  • Posts: 10095
Re: Yet another generics collection
« Reply #34 on: January 31, 2020, 06:29:51 pm »
@avk your attachments are invisible for guests.
That is normal.
I am more like donkey than shrek

avk

  • Sr. Member
  • ****
  • Posts: 265
    • my self-education project
Re: Yet another generics collection
« Reply #35 on: February 01, 2020, 07:01:36 am »
@avk your attachments are invisible for guests.
Doesn’t it depend on the forum settings?

julkas

  • Hero Member
  • *****
  • Posts: 576
  • KISS principle / Lazarus 2.0.6 / FPC 3.0.4
Re: Yet another generics collection
« Reply #36 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?
« Last Edit: February 01, 2020, 04:00:28 pm by julkas »
procedure mulu64(a, b: QWORD; out clo, chi: QWORD); assembler;
asm
  mov rax, a
  mov rdx, b
  mul rdx
  mov [clo], rax
  mov [chi], rdx
end;

Thaddy

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

Thaddy

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

avk

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

avk

  • Sr. Member
  • ****
  • Posts: 265
    • my self-education project
Re: Yet another generics collection
« Reply #40 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):
  • TFPDataHashTable and TFPHashList from contnrs
  • Slightly modified THashMap from fcl-stl(with xxHash32)
  • TDictionary from rtl-generics
  • TDictionary from Delphi.Generics.Collections(compiled with Delphi 10.3 CE)
  • TGenHashMap from yamer's gcontnrs
  • TGHashMapLP, TGLiteHashMapLP and TGChainHashMap from LGenerics
The benchmark was compiled with FPC 3.3.1 r44056(x86_64-win64) and runs on win7.

avk

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

Thaddy

  • Hero Member
  • *****
  • Posts: 10095
Re: Yet another generics collection
« Reply #42 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.
« Last Edit: May 05, 2020, 10:05:13 pm by Thaddy »
I am more like donkey than shrek

fcu

  • Jr. Member
  • **
  • Posts: 63
Re: Yet another generics collection
« Reply #43 on: May 06, 2020, 12:13:53 am »
3mb of code wow !! , my projects never exceed 100kb   
i liked this library very much , also fpc generic.collection becomes microscopic compared with this giant and great library
really thanks for making this public
keep up the good work   

 

TinyPortal © 2005-2018