There are 2 features, I am missing.

And I can't see a way to add them via subclassing, as the internal FItems array is private, and neither TItem, nor TPair can be gotten by the integer index into that array.

1) AddOrGetPointerToEmpty
This would actually just be to try and see if it gives any benefit in performance.

There is    TryAdd()
But, the caller must already have a new value, that it can pass for that key.

However, if the dictionary already has a value for that key, then the
existing value may be enough,
So the caller ends up
    NewVal := CreaterNewValSpendingTime;
   if not Dictionary.TryAdd(TheKey, NewVal) then
     NewVal.Destroy;

Alternatively the caller can do
  If not Dictionary.ContainsKey(TheKey) then ...

But the latter then means, that "TheKey" need to be hashed twice, if a new value needs to be added (Even though the hash could already be known).

If there was a function
   GetItemPointer(AKey: TKey; out APtr: PValue): boolean;

which returns True, if Akey was found and therefore APtr points to existing Data, while otherwise APtr points to the empty slot, where the data can be copied to.

2) Key and Data to be the same.

Lets say I have lots of data, to which I have pointers (e.g. instances of some object).
Now when I have such a pointer, I want to know if I had a previous pointer to the same data. (even if the new pointer points to a copy of the data at a new location).

I could do TDictionary<TMyClass, TMClass>
I need to have my own IEqualityComparer, so I don't compare the pointers, but the data in the object. (That I can do).

But now I need to do
  MyDict.Add(val, val);
Which means the same value is stored as pointer and data => doubling mem requirements.

What I would need is
- set TData to "record end" (zero size)
- be able to retrieve the existing key, for another key that returns equal to the stored key

So instead of
   MyVal := Dict.Items[AKey];
I need
   ExsitingKey := Dict.Keys[ANewKey];

Obviously since the key is the data, my IEqualityComparer can do proper comparison, so even if the hash clashes, the pointed to data can be compared.

Op 27-3-2025 om 12:28 schreef Martin Frb via fpc-devel:

Without a key, you can't find the bucket or whatever where to allocate, so this is not possible for all dictionaries IMHO. IOW, it violates the contract with implementation details.

But in this feature, you always have the key.

You just don't have the data yet. You only create the data, if it does not yet exist.

Its pretty much a
  TryAdd.

But instead of having data, it adds "Default(TData)", and returns a pointer to the mem.
Or, if the key existed, it returns a pointer to the existing data.

Of course the pointer is only valid, until the next operation on the dict (or hash container).

It's just to save calculating the hash of the key twice.

It doesn't have to be a pointer.

It can be some opaque value, that can be used as "index like" lookup. E.g. in most cases, the actual bucket index (only valid till next rehash, but that is the same for a pointer).

Then there can be a
  SetData(TheOpaqueIndex, Data)

This would mean it can deal with refcount for ansi string, if any dealing is required.

Or if preferred, it does not return at all, but internally stores the bucket location.
Then it Could be
  if not Dict.TryGetValue(Akey, AReturnedValue) then     Dict.AddValueForLastTriedKey(ANewVal);

Then it can even invalidate the location, if it rehashes. But it increases adds a new field, as the last keys bucket location needs to be stored....

It does not violate the contract imho.

In a TDictionary<K,V> it would return a pointer to V which is valid because it either retrieved an existing entry or added a new one with default(v).

I implemented this a while ago in Spring4D roughly following the API that was introduced in .NET some time ago.

I called it GetValueOrAddDefault and recently renamed it to GetValueRefOrAddDefault. It has three overloads:

    function GetValueRefOrAddDefault(const key: TKey): Ref<TValue>.PT; overload;
    function GetValueRefOrAddDefault(const key: TKey; const defaultValue: TValue): Ref<TValue>.PT; overload;
    function GetValueRefOrAddDefault(const key: TKey; const defaultValue: TValue; out exists: Boolean): Ref<TValue>.PT; overload;

Ref<TValue>.PT is ^TValue - I had to write it that way because this method is part of my IDictionary<TKey,TValue> interface and pointers to generic type parameters in Delphi are just ugh...

Yes the pointer is just valid as long as no other modifications happen to the dictionary but regardless the implementation (I have a hashtable and a rb tree based one) you always can return the location where the value is stored.

You just need to keep in mind though that any notify events on the dictionary will not receive any value that was changed in such a way - but that's a rather corner case when using such an optimization.

For your second feature request it just needs a method added to THashSet<T> that retrieves the stored item based on the passed key.

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).

Actually needs bool result, to indicate if it was gotten or added.

Any comments? Or any idea when someone (someone relevant for decisions) may have time to comment?

Are the ideas (if/once implemented in a manner required) generally acceptable?

If, yes, and if given any requirements how to implement, I would make them a PR. But, if that is either going to be rejected or forever pending, then I'll consider making a copy for Lazarus (where the requirements exists).

Just want to know if there is any interest?   Or if I just gonna do my own copy (somewhere in LazUtils)

If its too busy right now, then just an ack, and a "maybe in 4/6/8/10? weeks"... would be nice.

Thanks

Martin Frb wrote

Just want to know if there is any interest?   Or if I just gonna do my own copy (somewhere in LazUtils)

The 1-4 are interesting so MR is welcome, the 5 I don't understand what you want to achieve, I would assume a custom comparer is simply the answer ?

Michael.

ok, I will work on that.

the 5 I don't understand what you want to achieve, I would assume a custom comparer is simply the answer ?

The custom comparer (and hasher) I already have. But its not enough.

The concrete use case is the SynEdit Highlighter.

For each text-line it assembles an object that represents the state of the parser after the line (for the next line to start with). This contains Flags on the parser state, fold info, and similar.

Each line has a pointer to its state.
Additionally all states end up in a pool (in this case a TDictionary). The pool is used for de-duplication.
If an object for the state already exists then the existing object is used (and the object that was created during working on the line is discarded).

With the current TDictionary I have (TRange is the object for the line state)
specialize TDictionary <TRange, TRange>

So I can then look up a range (the dictionary uses the content of the object, the internal pointer is not part of the comparison). But it stores the object by storing the internal pointer to it (it does not copy the instance memory)

The same object (same instance) is key and data at the same time. But, when I have the the current lines new range object, then I do MyDict.TryGetValue(TempRange, WantedExistingRange) .

That all works very well, but for each range the dictionary stores 2 copies of the pointer to that object (twice the same pointer).
- One as key (even though the actual key is the data pointed too)
- One as Data (pointing to the same data).

Instead I like to do
  type
    TMyEmpty = record end; // empty
    specialize TDictionary <TRange, TMyEmpty>

Then only the key is stored.

But then I need a way to retrieve the existing key, for a new key that I have.

That sounds stupid, but remember that the key is passed as the internal pointer to the object.
So 2 different pointers can point to 2 mem-locations with data that is equal (and is the same key).

I want the "key" pointer to the original memory, with the same content as pointed to my new key.

I admit its a very special case for a dictionary, but probably still useful. It is done with lists all the time, that data is added "if indexof(data) < 0" and otherwise existing data is used.

If its not added to the public interface, then maybe some protected accessor can be created, based on which a subclass can implement it?

We look forward to the MR...

If I had bet on the use case, I would have won my bet ;-)

But why don't you simply use a TList<TRange> with your custom comparer ? You can then use List.BinarySearch() and retrieve the existing TRange at once?

Your solution seems quite hackish to me.
So if you really need it in TDictionary, make it protected as you indicated...

Michael.

Because there may be several 10000 entries (ok extreme case, I get 40000 entries, after scanning several 100 files).

And entries are added over time.
When adding a new entry, the list must be sorted again. That is the slow part.

The old code used an AVL tree.
That is fine.
But uses more memory, that the TDictionary (even with the double pointer storage).

AVL tree, needs Left/rigt/balance, and because the range is not inheriting

When the mailer decides to sent....

there is a separate node instance.

Of course the dictionary varies depending on the amount of empty slots.

If keys could be accessed by index (the internal slot), the TDictionary.IndexOfKey
and
TDictionary.Keys[idx]

would do

Hm. I assumed a 'Sorted' property as in TStringList, which should insert on the correct spot if you do an add, but apparently the generic TList does not have this :-(

Michael.

That seems like a more 'conventional' solution to me.

I'll leave it up to you how to enhance TDictionary using either solution...

Michael.

Sorry, I was unclear. Yes Sorted = true.

And "Sorted again" => not from scratch, rather "kept sorted", but keeping inserting elements into the middle of a list that size => costly.

Sorted list / bin search => lowest memory, but slower    (so depending on capacity it can be as much as a dictionary... / and too low capacity makes it slower)
AVL tree => more memory (maybe can be reduced, by rewriting some of it...), fast
TDictionary => currently fastest, and lowest mem consumption (and hopefully even less mem)

Quick question

When re-using known hash in rehash
https://gitlab.com/martin_frb/fpc-src/-/commit/9b398efb33897b3b5e98678033ddaafd1bcea883

Rehash is (mostly?) used for resize.
But an inherited class could change the hash algorithm and call it.

So there need to be a way to force new hashes.

1) Split into rehash and resize
Contra: Code duplication

2) New param
   AForceHashCalculation: Boolean = True

Default to current behaviour.

2) Use existing "AForce"

Slight change of existing code calling it with AForce=False, but new size, and new hash algorithm.

AForce is currently set to true by
procedure
TOpenAddressingTombstones<OPEN_ADDRESSING_CONSTRAINTS>.ClearTombstones;

-----------
2nd question

Most subclasses use the same code in  FindBucketIndex(AItems....)

1) Move to TOpenAddressing
Contra: extra code for subclasses not using it
Contra: if new subclasses do not override either FindBucketIndex or FindBucketIndexForHash then it creates a circle.
  (Old subclasses must have it already overriden

2) New subclass inbetween TOpenAddressingSingleHash ? Name?

3) Leave as in the commit?
Contra: Duplicate code

Since the method is virtual the options are more limited.

- New params wont work
- A new method must still call the old method, in case it is overriden.

So I introduced a wrapper, setting a flag in a private field. https://gitlab.com/martin_frb/fpc-src/-/commit/bf07831d7eaef3b06a63ac3ed72fae1fd19562ae

Reasonable?

Index may be misleading as it points to buckets, and they aren't continuous.

FindBucketIndex is already protected. So I can call that from a subclass.

If I can add protected methods

Function GetKeyFromBucket: TKey;
Function GetDataFromBucket: TValue;

Or
Function GetItemFromBucket(idx: sizeint): TItem; // contains hash,key and value
Function GetItemPtrFromBucket(idx: sizeint): PItem; // no need to copy the content

The last one could be named GetMutableItemFromBucket. Of course it has the issue that the slots for hash and key MUST NOT be written.

So maybe the former 2 methods (getKeyFromBucket and GetValueFromBucket / maybe GetMutableValueFromBucket).