[fpc-devel] RFC: Improvements for TDictionary and other hash containers

[Martin Frb]

On 27/03/2025 12:28, Martin Frb wrote:
> There are 2 features, I am missing.

I did a couple of experiments... Those are not finished code. They only 
showcase the ideas, and only for the one OpenAddressingLp case

https://gitlab.com/martin_frb/fpc-src/-/compare/main...rtl-gen-opt?from_project_id=28644964

Would like to get opinions, if this can be included.

1) "Rehash"
This has a minor speed up effect.
It depends on the resize stepping (usually very few resizes), and cost 
of recomputing the known hashes.

2 / 3)  TryAdd / AddOrSetValue
This has a noticeable impact on performance, if running those in a loop.

- The hash does not change by a resize/rehash, so don't recompute it
- if there is no rehash then the bucketindex is known, and does not need 
to be found a 2nd time

It needs clean up, currently its 3 times the same code.
- If the new "DoAdd" are called, then all inherited classes must be 
fixed up, as they get bypassed otherwise.
- I didn't want to forward several small steps to virtual (none 
inline-able) methods, hence the copied code. But there may be a better way

4)  GetOrAddMutable
Just an extension, like AddOrSetValue.
Having it as one call, avoids recalculating the hash/index.

5) TryGetEqualKey

That is a bit special.

I have a case where
- I store object instances. (custom IEqualityComparer getting hash of 
instance content)
- I then later have another instance that may be equal (by content) to 
an existing instance (but new memory alloc)
- I want to find the original

Currently I need to
TDictionary<TMyClass, TMyClass>

Storing the identical instance pointer as key and value.

Obviously that doubles memory usage (twice the amount of pointers).