Rapid.Generics revamp

[Stefan Glienke 2125]

  On 4/1/2025 at 10:42 PM, Alex7691 said:

One specific scenario where I replaced the std TDictionary with the Rapid.Generics one (a notification bus where a dictionary is used to map the instances) had a performance increase of 10x or more

I am very curious about this particular scenario. Can you tell me the dictionary's key and value types and usage? Is it mostly looking up values or adding/removing items?

[Alex7691 19]

  On 4/7/2025 at 8:34 AM, Rollo62 said:

Have you tested this under VCL, FMX, Win32, Win64, Macos (x86/ARM), iOS, Android, Linux as well?

 

 

Tested using Win32 and Win64 compilers only for now. Android and Linux, it's possible in a near future. Not sure if I'm going to test on any Apple OS, though... Not into MacOS/iOS dev myself.

 

FMX and VCL are UI frameworks and don't have any relevance for the testing.

Edited Tuesday at 09:02 AM by Alex7691

[Alex7691 19]

  On 4/7/2025 at 9:31 AM, Stefan Glienke said:

I am very curious about this particular scenario. Can you tell me the dictionary's key and value types and usage? Is it mostly looking up values or adding/removing items?

Hi Stefan,

 

In our application there is a notification bus which internally has 2 dictionaries. The main one has an object (the "observable") as the key and a list of objects (each object has references to observers and notification methods) as the value. The second dictionary also has an object (the "observer") as the key and and Integer as the value. 

 

The dictionary may contain a large number of objects (dozens of thousands) and at some point in time all the objects need to be freed. So when ObjA (an observable) is being destroyed it will notify all it's observers. Then it will remove itself from the dictionary and all oberservers will also be removed if they are only observing ObjA. This is where the new dictionary performance surprised me. The notification happens faster (because retriving the values from the keys is faster), but more importantly removing them from the dictionary is way faster than the previous version based on std TDictionary.

 

 

Edited Tuesday at 09:04 AM by Alex7691

[Alex7691 19]

  On 4/7/2025 at 12:50 AM, pyscripter said:

@Alex7691Good work.  It is useful to have a drop-in fast generics replacement.

 

A couple of questions:

• Is there an impact on code size?
• I see a lot of code included that it is not directly related to generics.  (e.g. TSyncSpinlock, TSyncLocker, TaggedPointer, TCustomObject. TLiteCustomObject  etc.).  Are they actually essential for the rapid collections?   

Thanks.

Responding to your questions:

 

a) The only metrics I have is the size of the executable. Using Rapid.Generics, I got a slightly smaller executable.

 

b) Most of these classes that you mentioned are not necessary for most containers (the sync objects are needed for the TThreadList<>, TThreadedQueue<>. But if you don't use them, Delphi smart linker won't include them.

Edited Tuesday at 09:04 AM by Alex7691

[Stefan Glienke 2125]

One thing that I dislike about the Rapid implementation is the ton of magic numbers and the fact that the used hash algorithm is documented nowhere - I assume some form of Robert Sedgewick hash (which I could not find a formal description of anywhere on the internet).

That makes it hard to verify its correctness and behavior. 

[HeartWare 5]

How does Rapid.TList<STRING> compare to THashSet<STRING> (only for checking if an entry exists in the list or not)? It'll be called thousands of times (the list itself will be pretty small - 5 or 10 entries)

Edited Tuesday at 09:36 AM by HeartWare
Clarified T = STRING

[Stefan Glienke 2125]

  On 4/8/2025 at 9:19 AM, HeartWare said:

How does Rapid.TList<STRING> compare to THashSet<STRING> (only for checking if an entry exists in the list or not)? It'll be called thousands of times (the list itself will be pretty small - 5 or 10 entries)

List always does linear search, which is O(n), while hashset does it in O(1) - however, considering the significantly higher cost of calculating the hashcode even with a very fast hash function (which the RTL does not use) and the length of the string for a small amount of entries linear search beats a hashtable. In theory, if the entries are not changed that often, one could sort the list and use binary search. But that also requires a fast, optimized, inlined BinarySearch implementation, which the RTL does not have, IIRC.

 

P.S. Rapid.Generics.TList<T>.IndexOf is broken - line 19503 causes an endless loop. The same defect exists in InternalIndexOfRev.

How to repro:

 

procedure IndexOfEndlessLoop;
begin
  var list := Rapid.Generics.TList<string>.Create;
  for var i := 0 to 1 do
    list.Add(TGUID.NewGuid.ToString);
  list.indexOf(list[1]);
end;

 

Edited Tuesday at 11:23 AM by Stefan Glienke

[Rollo62 569]

  On 4/7/2025 at 9:29 AM, David Heffernan said:

How could VCL/FMX be relevant to code at the RTL level?

Excaclty, it should not ...

 

Thats why I asked, if its tested against those and ensured that no hidden UI units are linked or involved.

I think everyone can very well understand the meaning of my question here, even if VCL/FMX mentioned.

There are too many VCL-only libraries out there.

 

But thanks for your clarification.

Edited yesterday at 09:50 AM by Rollo62

[David Heffernan 2409]

  On 4/9/2025 at 9:50 AM, Rollo62 said:

Excaclty, it should not ...

 

Thats why I asked, if its tested against those and ensured that no hidden UI units are linked or involved.

I think everyone can very well understand the meaning of my question here, even if VCL/FMX mentioned.

There are too many VCL-only libraries out there.

 

But thanks for your clarification.

No library developer would test things like this. I mean why stop at FMX/VCL? What about database frameworks. Does it have dependencies on any of them? Does it work in a Windows service? Should there be a test for that? It's simple to see by inspecting the uses clause, so the developer just does not need to do any of that.

[Rollo62 569]

  On 4/9/2025 at 11:35 AM, David Heffernan said:

No library developer would test things like this. I mean why stop at FMX/VCL? What about database frameworks. Does it have dependencies on any of them? Does it work in a Windows service? Should there be a test for that? It's simple to see by inspecting the uses clause, so the developer just does not need to do any of that.

Yes you are right. VCL/FMX unit linkage is comparable to DB and Windows-Service.
Also tests for other platforms are completely superfluous, especially if Win32 ASM code is used in the library, nothing can go wrong here.
I revoke all my silly notes above, they seem to be too stupid.

 

Edited yesterday at 12:07 PM by Rollo62

[Anders Melander 1965]

  On 4/9/2025 at 12:06 PM, Rollo62 said:

Yes you are right. VCL/FMX unit linkage is comparable to DB and Windows-Service.
Also tests for other platforms are completely superfluous, especially if Win32 ASM code is used in the library, nothing can go wrong here.
I revoke all my silly notes above, they seem to be too stupid.

[Rollo62 569]

Mindful misunderstanding of other peoples Intention and expressions is also a Form of Art.

[David Heffernan 2409]

  On 4/9/2025 at 12:06 PM, Rollo62 said:

Also tests for other platforms are completely superfluous

No, platform tests are important and valuable.

 

But framework dependency tests have no power here because you can read a single uses clause and know it's fine in 15s.

[Rollo62 569]

  20 hours ago, David Heffernan said:

... because you can read a single uses clause and know it's fine in 15s. ....

Yes, I agreed to this already 10 thread posts before.
I only asked if anybody already looked into it and/or tested against it.        Any terms within the former sentence may start further massive nitpicking, I know.

Nevermind, it's OK then for me.