TDictionary<K,V> und Kapazität

[ventiseis]

Hallo,

während einer längeren Debugging-Session ist mir etwas aufgefallen. Bekannt ist:

• man kann ein TDictionary<K,V> mit einer bestimmten Kapazität über den Konstruktor erzeugen (siehe TDictionary.Create)
• ein Dictionary hat immer einen gewissen Füllgrad
• die Einträge des Dictionaries werden in ein Array aus Buckets einsortiert
• ist der Füllgrad erreicht, dann muss das Bucket-Array vergrößert werden, ansonsten wird der Lookup im Dictionary ineffizient

In der Implementierung von TDictionary wurde das so umgesetzt:

• die Kapazität ist immer die nächstgrößere Zweierpotenz, aber mindestens 4 Buckets
• der Füllgrad wird berechnet: (Kapazität shr 1) + (Kapazität shr 2)

Das führt aber dazu, dass bei manchen Kapazitätswerten nicht mehr alle Einträge ins Dictionary passen und das Dictionary beim Hinzufügen von Elementen vergrößert werden muss, obwohl man eine ausreichende Kapazität angegeben hat:

Kapazität / Konstruktor	verwendete Kapazität	Max. Füllgrad
4	4	3	Kapazität im Konstruktor nicht ausreichend
20	32	24	Kapazität ausreichend
29	32	24	Kapazität wieder nicht ausreichend

Mein Fazit: falls man Reallokationen vermeiden will, sollte man die Kapazität des Dictionaries größer angeben als die Anzahl der Elemente, weil der Füllgrad bei der Kapazitätsberechnung nicht einbezogen wird.

Ist das auch schon mal jemand aufgefallen? Oder habe ich hier ein Verständnisproblem?

[ventiseis]

Hier ein Testprogram zum Auslesen des Füllgrads für Delphi 10.2:

Delphi-Quellcode:

program Project7;

{$APPTYPE CONSOLE}

{$R *.res}

uses
  System.SysUtils, System.Generics.Collections, System.Rtti;

function GetGrowThreshold(AInstance: TObject): NativeUInt;
var
  LContext: TRttiContext;
  LType: TRttiType;
  LField: TRttiField;
begin
  LContext := TRttiContext.Create();
  LType := LContext.GetType(TDictionary<Integer, Integer>);
  LField := LType.GetField('FGrowThreshold');
  Result := LField.GetValue(AInstance).AsType<Integer>;
end;

var
  I: Integer;
  LDictionary: TDictionary<Integer, Integer>;

const

  C = 20;

begin
  LDictionary:=TDictionary<Integer, Integer>.Create(C);
  try

    for I := 1 to C  do
    begin
      LDictionary.Add(i,i);
      WriteLn(IntToStr(i) + ': ' + GetGrowThreshold(LDictionary).ToString);
    end;
    ReadLn;
  finally
    FreeAndNil(LDictionary);
  end;
end.

[Stevie]

Ja, das stimmt. Die Kapazität, die man angibt stimmt nicht mit der Anzahl der Elementen überein, die man ohne Grow hinzufügen kann.