View Issue Details

IDProjectCategoryView StatusLast Update
0027206FPCCompilerpublic2019-02-12 12:45
ReporterMaciej IzakAssigned ToSven Barth 
PrioritynormalSeverityminorReproducibilityalways
Status resolvedResolutionfixed 
Product Version2.7.1Product Build27327 
Target VersionFixed in Version3.1.1 
Summary0027206: [Patch] Christmas gift by FreeSparta : Generics.Collections
DescriptionHo ho ho, Merry Christmas :)

I've decided to close the "FreeSparta" project and I decided to give Generics.Collections library as an open source project.

Best regards,
Maciej Izak

Important:

TFastHashMap from Generics.Collections is faster than any other generic container for fpc :) (is based on "De-amortized Cuckoo Hashing" http://arxiv.org/abs/0903.0391). For big data count is even faster than TFPStringHashTable.

Suggestion:

1. someone can extend generics.memoryexpanders for TCustomList/TList (for control memory growth by constraints)
2. nice to have for dictionary hashing: http://blog.synopse.info/post/2014/05/25/New-crc32c%28%29-function-using-optimized-asm-and-SSE-4.2-instruction

Library (with RTL patch) is compatible with Rev 27327. To run this library in new version of compiler we need to fix:

REGRESSION: 26483 and 26481

and will be nice to fix

CRITICAL: 24848(!!!), 24872(!), 25607(!), 26030, 25917, 25918, 25620, 24283, 24254, 24287 (Related to? 24872)
IMPORTANT: 23862(!), 24097, 24285, 24286 (Similar to? 24285), 24098, 24609 (RTL inconsistency), 24534, 25606, 25614, 26177, 26195
OTHER: 26484, 24073, 24463, 25593, 25596, 25597, 25602, 26181 (or MYBAD?)
CLOSED BUT IMO STILL TO FIX: 25601(!), 25594

Additionaly attached patch implements important low level Delphi functions (useful for, Generics, RTTI and any scripting engine):

http://docwiki.embarcadero.com/Libraries/XE2/en/System.InitializeArray
procedure InitializeArray(p: Pointer; typeInfo: Pointer; elemCount: NativeUInt);
http://docwiki.embarcadero.com/Libraries/XE2/en/System.CopyArray
procedure CopyArray(Dest, Source, TypeInfo: Pointer; Count: NativeInt);
http://docwiki.embarcadero.com/Libraries/XE2/en/System.FinalizeArray
procedure FinalizeArray(P: Pointer; TypeInfo: Pointer; Count: NativeUInt);
http://docwiki.embarcadero.com/Libraries/XE2/en/System.DynArrayClear
procedure DynArrayClear(var A: Pointer; TypeInfo: Pointer);
http://docwiki.embarcadero.com/Libraries/XE2/en/System.DynArraySetLength
procedure DynArraySetLength(var a: Pointer; typeInfo: Pointer; dimCnt: NativeInt; lengthVec: PNativeInt);

http://docwiki.embarcadero.com/Libraries/XE2/en/System.DynArrayIndex
function DynArrayIndex(P: Pointer; const Indices: array of NativeInt; TypInfo: Pointer): Pointer; overload;
function DynArrayIndex(P: Pointer; const Indices: array of Integer; TypInfo: Pointer): Pointer; overload;

http://docwiki.embarcadero.com/Libraries/XE2/en/System.DynArrayDim
function DynArrayDim(typeInfo: Pointer): Integer;
http://docwiki.embarcadero.com/Libraries/XE2/en/System.DynArraySize
function DynArraySize(A: Pointer): NativeInt;

http://docwiki.embarcadero.com/Libraries/XE2/en/System.IsDynArrayRectangular
function IsDynArrayRectangular(const DynArray: Pointer; typeInfo: Pointer): Boolean;
http://docwiki.embarcadero.com/Libraries/XE2/en/System.DynArrayBounds
function DynArrayBounds(const DynArray: Pointer; typeInfo: Pointer): TBoundArray;
TagsNo tags attached.
Fixed in Revision34229
FPCOldBugId
FPCTarget
Attached Files

Relationships

related to 0026030 new FPC Class type expected, but got "<erroneous type>" error in non generic descendant class 
related to 0025917 resolvedSven Barth FPC "Fatal: No memory left" for generic code 
related to 0024848 resolvedSven Barth FPC Class constructor undefined symbol in generic class 
related to 0024872 resolvedSven Barth FPC Global Generic template references static symtable for generic record 
related to 0025607 closedJonas Maebe FPC Can't determine which overloaded function to call for override constructor 
related to 0025918 new FPC "Constraint override" in inner class (identifier idents no member) 
related to 0025620 new FPC Fatal: Compilation aborted, for second compilation with generic class 
related to 0024283 new FPC Generics syntax error, ">" expected but "<" found 
related to 0020503 acknowledged FPC Generics does not support parameterized method 
related to 0024287 resolvedSven Barth FPC Generics type name conflict (Identifier not found) 
related to 0024097 acknowledgedSven Barth FPC Generics forward declaration of class and "Identifier not found" 
related to 0023862 resolvedFlorian FPC Inline and "Procedure too complex, it requires too many registers" 
related to 0026483 resolvedSven Barth FPC Generics regression, wrong section visibility in module level - identifier idents no member "F" 
related to 0026481 resolvedSven Barth FPC Generics regression, fatal error for class var. 
related to 0024285 new FPC Generics class type expected, but got "<erroneous type>" 
related to 0024286 new FPC Generics illegal expression (specialization inside class) 
related to 0024098 new FPC Generics explicit cast and boolean expression 
related to 0024609 new FPC tkUChar in TypInfo 
related to 0024534 confirmed FPC Generics variable identifier expected error for const pointer to static method. 
related to 0025606 resolvedSven Barth FPC Illegal qualifier for type initialization by const in type/record helper 
related to 0025614 new FPC Generics "Error: Identifier not found" shown in wrong place 
related to 0026177 resolvedMichael Van Canneyt FPC Wrong data for pointer method and "External SIGSEGV" (type helper) 
related to 0026195 new FPC Missing error for wrong generic method implementation (constraints) 
related to 0026484 new FPC Generics Internal error 2014052305 
related to 0024073 resolvedMaciej Izak FPC Wrong behavior of generic "record parameter" 
related to 0024463 resolvedSven Barth FPC Generics fatal error for local var in method. 
related to 0025593 new FPC Directive WARNINGS ON/OFF don't work correctly 
related to 0025596 resolvedSven Barth FPC Keyword "with" don't work with default property in generic class 
related to 0025597 resolvedSven Barth FPC Forbidden word - field name "hash" with "with" keyword and generics usage. 
related to 0025602 resolvedFlorian FPC Unclear compiler error for generic array initialization. 
related to 0026181 new FPC Can't determine which overloaded function to call for generic version of code 
related to 0027320 resolvedSven Barth FPC Regression. "Fatal: compilation aborted" for generic static class function 
related to 0027393 resolvedMattias Gaertner Patches [Patch] Support for dotted named units like Generics.Collections 
related to 0027565 resolvedFlorian FPC Generics Internal error 2010021405 for Unix 64 bits (Generics.Collections) 
related to 0025613 confirmedMattias Gaertner Lazarus Code completion broken/block for generic specialization type inside generic type 
related to 0025615 confirmedMattias Gaertner Lazarus "Complete Code" don't work correctly for method that return generic type (delphi mode) 
related to 0025617 confirmedMattias Gaertner Lazarus "Complete Code" don't work correctly for method that contain parameter with generic type (delphi mode) 
related to 0025618 assignedMattias Gaertner Lazarus "Complete Code" unnecessarily generates inherited 
related to 0025619 resolvedMattias Gaertner Lazarus "Complete Code" broken/blocked for property with generic type (delphi mode) 
related to 0025612 new Lazarus Code navigation. Small problem in *.inc files 
related to 0025595 confirmedMattias Gaertner Lazarus Code completion don't work for generic constructors (delphi mode) 

Activities

Maciej Izak

2014-12-23 22:55

reporter  

sparta_fpc_src_mod.7z (91,470 bytes)

Maciej Izak

2014-12-23 22:56

reporter  

GenericsCompatibilityMatrix.pdf (707,149 bytes)

Marco van de Voort

2014-12-27 22:27

manager  

rttichanges.path (5,794 bytes)

Marco van de Voort

2014-12-27 22:28

manager   ~0079987

I extracted the RTL files from the archive, synced them to the current version, and then diffed. File attached

Fiji

2014-12-29 13:57

reporter   ~0080005

Doubt these bugs will ever be fixed. It seems the FPC CORE team doesn't like generics at all.

Florian

2014-12-29 18:52

administrator   ~0080010

> Doubt these bugs will ever be fixed. It seems the FPC CORE team doesn't like generics at all.

Then it is your turn apparently.

Marco van de Voort

2015-01-01 01:29

manager   ~0080061

Last edited: 2015-01-01 01:32

View 2 revisions

I committed the RTTI changes after noticing the first hunk is because Maciej based himself on old sources (a commit from Nikolay changed that)

(please use universal diff patches as much as possible)

Maciej Izak

2015-01-07 19:02

reporter   ~0080190

Last edited: 2015-01-07 19:03

View 2 revisions

@Sven: Missing bug reports : 0026483 and 0026481 in the Relationships list (from REGRESSION list). You skipped the most important bugs - with bugs from REGRESSION list you can't run this library. :)

Regards,
Maciej Izak

Sven Barth

2015-01-07 21:39

manager   ~0080196

Ah yes, I indeed missed those... -.-
Would you please take a look at 0025597 while you're at it? :)

Regards,
Sven

Maciej Izak

2015-01-08 18:35

reporter   ~0080222

Yeah 0025597 works fine ^^. The next eliminated bug! :D

Maciej Izak

2015-01-16 23:07

reporter   ~0080450

Last edited: 2015-01-16 23:09

View 2 revisions

New relationship 0027320. After fixng 0027320 - VICTORY :).

Btw. nice work for 0026481, 0026483 and 0025917

Maciej Izak

2015-01-24 13:46

reporter  

generics_collections_final.zip (124,884 bytes)

Maciej Izak

2015-01-24 13:46

reporter   ~0080560

Last edited: 2015-01-24 13:54

View 4 revisions

FINALLY ! *____*

Good news : Attached generics_collections_final.zip works fine with FPC trunk rev. 29537 :DDD - library and all examples!!!

Thanks especially for Sven and FPC Team :)

Regards,
Maciej Izak

Thaddy de Koning

2015-02-11 14:37

reporter   ~0080954

Last edited: 2015-02-11 14:38

View 2 revisions

@Maciej Izak: Yes, time to fix the bugs in the demo's ;):

e.g. 64 bit gotcha's:
C:\fpc\generics_collections_final\fpcsrc\packages\rtl-generics\examples\TArraySi
ngle>ppcx64 -Mdelphi -Fu..\..\src;c:\fpc\trunk\packages\rtl-objpas\src\inc;c:\fp
c\trunk\packages\rtl-objpas\src\win -Fic:\fpc\trunk\packages\rtl-objpas\src\inc
-CX -XX -Xs -Os -O4 TArrayProjectSingle.lpr
TArrayProjectSingle.lpr(86,57) Error: Call by var for arg no. 3 has to match exa
ctly: Got "LongInt" expected "Int64"
TArrayProjectSingle.lpr(94,57) Error: Call by var for arg no. 3 has to match exa
ctly: Got "LongInt" expected "Int64"
TArrayProjectSingle.lpr(102,57) Error: Call by var for arg no. 3 has to match ex
actly: Got "LongInt" expected "Int64"
TArrayProjectSingle.lpr(112) Fatal: There were 3 errors compiling module, stoppi
ng
Fatal: Compilation aborted

Maciej Izak

2015-03-18 13:06

reporter   ~0082067

Last edited: 2015-03-18 13:07

View 2 revisions

@Thaddy de Koning

Fixed. You can find current version in github repo.

https://github.com/dathox/generics.collections

Works fine with FPC rev. 30239 and newer.

Regards,
Maciej Izak

Sven Barth

2015-05-08 17:20

manager   ~0083524

So, I've finally found the time to look at the code more deeply. I have the following points to remark:
- please don't use "{$warning off}...{$warning on}", but instead use "{$push}{$warning off}...{$pop}" as this way warnings that were disabled on the command line stay disabled
- where does that DelphiHashLittle in Generics.Hashes come from?
- is there a reason why the check for ENDIAN_LITTLE is disabled in there?
- in reference to the previous question: did you test on big endian systems? (PowerPC, MIPS or M68k)
- I'm not entirely happy with your usage of "manual interfaces" in Generics.Defaults; I know why you do it, but I'm not happy with it... I'll put it up for discussion with the other core developers
- would you please write tests (fpcunit based) so that we can ensure that the classes keep working correctly?

Regards,
Sven

Maciej Izak

2015-06-01 23:02

reporter   ~0084166

Hi Sven,

sorry for delay.

> please don't use "{$warning off}...{$warning on}", but instead use "{$push}{$warning off}...{$pop}" as this way warnings that were disabled on the command line stay disabled

ok, I will upload new version to github soon

> where does that DelphiHashLittle in Generics.Hashes come from?

My hash solution is based on http://www.burtleburtle.net/bob/c/lookup3.c - DelphiHashLittle is compatible with Delphi function "BobJenkinsHash" (from Delphi module - System.Generics.Defaults). Algorithm used in Delphi is slightly different from the original "Jenkins hash function". Delphi version contins in first step additional shl operation:

a := $DEADBEEF + UInt32(ALength shl 2) + AInitVal;

original version:

a := $DEADBEEF + UInt32(ALength) + AInitVal;

The methods have been written from "scratch" in FPC (converted from lookup3.c).

> is there a reason why the check for ENDIAN_LITTLE is disabled in there?

I have no idea how BorCodeRo can implement their version of "BobJenkinsHash" for big endian systems, so I decide just to disabled ENDIAN_LITTLE. Maybe this is a mistake.

> in reference to the previous question: did you test on big endian systems? (PowerPC, MIPS or M68k)

I do not have such a possibility.

> I'm not entirely happy with your usage of "manual interfaces" in Generics.Defaults; I know why you do it, but I'm not happy with it... I'll put it up for discussion with the other core developers

:(

> would you please write tests (fpcunit based) so that we can ensure that the classes keep working correctly?

I'm working on additional example for LCL (to show memory layout for different hashing methods) + some performance chart.

Best regards,
Maciej Izak

Sven Barth

2016-07-29 17:17

manager   ~0093889

I know it took me an eternity, but I've finally added your contribution to FPC. I'm still reluctant regarding the manual interfaces, but I've done some performance tests and I can't argue with those...

I've done two changes to the code you provided on the linked GitHub repository:
- I've removed the use of the Contnrs unit from Generics.Defaults as it wasn't used; this way I could add your units as "rtl-generics" instead of "fcl-generics" (Contnrs is part of "fcl-base")
- I've changed the names of the example projects to lowercase

For any new changes please open a new bug report and thank you very much for this contribution. :)

Regards,
Sven

Marco van de Voort

2016-07-30 00:41

manager   ~0093899

(contnrs as Delphi unit could be moved to rtl-objpas if necessary).

I'm happy that this is done. Any info for (post 3.0.2 of course) fixes merging?

Maciej Izak

2016-07-30 18:17

reporter   ~0093907

@Sven @Marco:

I can't comment on "resolved Issue" so "reopened" only for comment purpose :P. Thanks Sven! My proposition is to move discussion on "Generics collections" topic on fpc-devel in related thread started by Dimitrios Chr. Ioannidis

best regards
& please resolve again ;)

Sven Barth

2016-08-04 22:07

manager   ~0094019

@Marco: the contnrs unit was not needed, so I could simply remove its usage :)

Resolved again

Issue History

Date Modified Username Field Change
2014-12-23 22:55 Maciej Izak New Issue
2014-12-23 22:55 Maciej Izak File Added: sparta_fpc_src_mod.7z
2014-12-23 22:56 Maciej Izak File Added: GenericsCompatibilityMatrix.pdf
2014-12-27 22:27 Marco van de Voort File Added: rttichanges.path
2014-12-27 22:28 Marco van de Voort Note Added: 0079987
2014-12-29 13:57 Fiji Note Added: 0080005
2014-12-29 18:52 Florian Note Added: 0080010
2015-01-01 01:29 Marco van de Voort Note Added: 0080061
2015-01-01 01:32 Marco van de Voort Note Edited: 0080061 View Revisions
2015-01-06 13:52 Sven Barth Relationship added child of 0024848
2015-01-06 13:54 Sven Barth Relationship added child of 0024872
2015-01-06 13:55 Sven Barth Relationship added child of 0025607
2015-01-06 13:56 Sven Barth Relationship added related to 0026030
2015-01-06 13:56 Sven Barth Relationship added related to 0025917
2015-01-06 13:56 Sven Barth Relationship deleted child of 0024848
2015-01-06 13:56 Sven Barth Relationship added related to 0024848
2015-01-06 13:57 Sven Barth Relationship deleted child of 0024872
2015-01-06 13:57 Sven Barth Relationship added related to 0024872
2015-01-06 13:57 Sven Barth Relationship deleted child of 0025607
2015-01-06 13:57 Sven Barth Relationship added related to 0025607
2015-01-06 13:58 Sven Barth Relationship added related to 0025918
2015-01-06 14:02 Sven Barth Relationship added related to 0025620
2015-01-06 14:02 Sven Barth Relationship added related to 0024283
2015-01-06 14:04 Sven Barth Relationship added related to 0020503
2015-01-06 14:05 Sven Barth Relationship added related to 0024287
2015-01-06 14:07 Sven Barth Relationship added related to 0023863
2015-01-06 14:08 Sven Barth Relationship added related to 0024097
2015-01-06 14:09 Sven Barth Relationship added related to 0024285
2015-01-06 14:09 Sven Barth Relationship added related to 0024286
2015-01-06 14:10 Sven Barth Relationship added related to 0024098
2015-01-06 14:11 Sven Barth Relationship added related to 0024609
2015-01-06 14:11 Sven Barth Relationship added related to 0024534
2015-01-06 14:12 Sven Barth Relationship added related to 0025606
2015-01-06 14:14 Sven Barth Relationship added related to 0025614
2015-01-06 14:15 Sven Barth Relationship added related to 0026177
2015-01-06 14:16 Sven Barth Relationship added related to 0026195
2015-01-06 14:30 Sven Barth Relationship added related to 0026484
2015-01-06 14:31 Sven Barth Relationship added related to 0024073
2015-01-06 14:32 Sven Barth Relationship added related to 0024463
2015-01-06 14:32 Sven Barth Relationship added related to 0025593
2015-01-06 14:34 Sven Barth Relationship added related to 0025596
2015-01-06 14:35 Sven Barth Relationship added related to 0025597
2015-01-06 14:36 Sven Barth Relationship added related to 0025602
2015-01-06 14:42 Sven Barth Relationship added related to 0026181
2015-01-06 21:56 Sven Barth Relationship deleted related to 0023863
2015-01-06 21:56 Sven Barth Relationship added related to 0023862
2015-01-07 19:02 Maciej Izak Note Added: 0080190
2015-01-07 19:03 Maciej Izak Note Edited: 0080190 View Revisions
2015-01-07 21:37 Sven Barth Relationship added related to 0026483
2015-01-07 21:37 Sven Barth Relationship added related to 0026481
2015-01-07 21:39 Sven Barth Note Added: 0080196
2015-01-08 18:35 Maciej Izak Note Added: 0080222
2015-01-16 23:07 Maciej Izak Note Added: 0080450
2015-01-16 23:09 Maciej Izak Note Edited: 0080450 View Revisions
2015-01-17 12:45 Sven Barth Relationship added related to 0027320
2015-01-24 13:46 Maciej Izak File Added: generics_collections_final.zip
2015-01-24 13:46 Maciej Izak Note Added: 0080560
2015-01-24 13:47 Maciej Izak Note Edited: 0080560 View Revisions
2015-01-24 13:49 Maciej Izak Note Edited: 0080560 View Revisions
2015-01-24 13:54 Maciej Izak Note Edited: 0080560 View Revisions
2015-02-01 13:10 Juha Manninen Relationship added related to 0027393
2015-02-11 14:37 Thaddy de Koning Note Added: 0080954
2015-02-11 14:38 Thaddy de Koning Note Edited: 0080954 View Revisions
2015-03-14 11:47 Marco van de Voort Relationship added related to 0027565
2015-03-18 12:35 Juha Manninen Relationship added related to 0025613
2015-03-18 12:35 Juha Manninen Relationship added related to 0025615
2015-03-18 12:36 Juha Manninen Relationship added related to 0025617
2015-03-18 12:36 Juha Manninen Relationship added related to 0025618
2015-03-18 12:36 Juha Manninen Relationship added related to 0025619
2015-03-18 12:38 Juha Manninen Relationship added related to 0025612
2015-03-18 12:38 Juha Manninen Relationship added related to 0025595
2015-03-18 13:06 Maciej Izak Note Added: 0082067
2015-03-18 13:07 Maciej Izak Note Edited: 0082067 View Revisions
2015-05-08 17:20 Sven Barth Note Added: 0083524
2015-05-08 17:20 Sven Barth Assigned To => Sven Barth
2015-05-08 17:20 Sven Barth Status new => feedback
2015-06-01 23:02 Maciej Izak Note Added: 0084166
2015-06-01 23:02 Maciej Izak Status feedback => assigned
2016-07-29 17:17 Sven Barth Fixed in Revision => 34229
2016-07-29 17:17 Sven Barth Note Added: 0093889
2016-07-29 17:17 Sven Barth Status assigned => resolved
2016-07-29 17:17 Sven Barth Fixed in Version => 3.1.1
2016-07-29 17:17 Sven Barth Resolution open => fixed
2016-07-30 00:41 Marco van de Voort Note Added: 0093899
2016-07-30 18:17 Maciej Izak Note Added: 0093907
2016-07-30 18:17 Maciej Izak Status resolved => feedback
2016-07-30 18:17 Maciej Izak Resolution fixed => reopened
2016-08-04 22:07 Sven Barth Note Added: 0094019
2016-08-04 22:07 Sven Barth Status feedback => resolved
2016-08-04 22:07 Sven Barth Resolution reopened => fixed