ChessKISS and memory

This engine is a memory hunter, trying to reduce the memory I've created two new entries in the .ini which are the maximum amount of memory that the transposition tables can use expressed in megabytes:


[cache]
EvaluationHashSize=16
TranspositionTableSize=256

(also it is needed for the winboard protocol, but I haven't implemented yet)

Before I was using a simple TDictionary<int64, TInfo> (key/value)

Now I use an intermediate class called TCache which internally uses a TDictionary AND a TLinkedList, but why?

Because we must delete entries once we have reach the maximum amount of memory allowed, how we do it?, just adding the key to the LinkedList and deleting always the first item (first item is always the oldest one)

procedure TCache<TKey, TValue>.Add(aKey: TKey; aValue: TValue);
begin
  FItems.Add(aKey, aValue);
  AddPointer(aKey, aValue);
end;

procedure TCache<Key, Value>.AddPointer(const aKey: Key; const aValue: Value);
begin
  FPointers.Enqueue(aKey);
  Inc(FCurrentSize, Length(aValue));

  case FType of
    ctPerEntries:
      begin
        if Count > FMaxSize then
          DeleteOldest;
      end;

    ctPerSize:
      begin
        while FCurrentSize > FMaxSize do
          DeleteOldest;
      end;
  end;
end;

function TCache<Key, Value>.Length(const aValue: Value): integer;
var
  v: TValue;

begin
  v := TValue.From<Value>(aValue);
  if v.Kind in [tkLString, tkWString, tkUString] then
    Exit(System.Length(v.AsString) * SizeOf(char))
  else
    Exit(v.DataSize);
end;
procedure TCache<TKey, TValue>.DeleteOldest;
begin
  Remove(FPointers[0]);
end;

procedure TCache<TKey, TValue>.Remove(aKey: TKey);
var
  i: integer;

begin
  FItems.Remove(aKey);
  FPointers.Delete(aKey);
end;

Why a LinkedList, because is the best collection once you want to remove the initital item, is just a matter of freeze the node and update the head node, for example with list or arrays the WHOLE list has to be moved to the left.

LinkedList:

procedure TLinkedList<T>.Delete(aItem: T);
var
  current, prior, next: TNodeList;

begin
  current := InternalFind(aItem);
  if current = nil then
    raise Exception.Create('Item not found');

  prior := current.Prior;
  next := current.Next;

  TryFreeObject(current.Item);

  //Update head
  if FHead = current then
  begin
    if next <> nil then
      FHead := next
    else
      FHead := nil;
  end;

  //Update tail
  if FTail = current then
  begin
    if prior <> nil then
      FTail := prior
    else
      FTail := nil;
  end;

  //Update sides
  if prior <> nil then
    prior.Next := next;

  if next <> nil then
    next.Prior := prior;

  current.Free;
  Dec(FCount);
end;

A fast delete..., now a typical array approach:

procedure TArrayEx<T>.Delete(aIndex: integer);
var
  i: integer;

begin
  if aIndex < FCount - 1 then
  begin
    for i := aIndex to FCount - 1 do
      FArray[i] := FArray[i + 1];
    FArray[FCount] := Default(T);
  end;

  Dec(FCount);
end;
The more elements the worst...
So now we do:
constructor TTranspositionTable.Create;
begin
  //In MB!
  FData := TCache<int64, TInfo>.Create(ctPerSize, 
TSettings.Instance.Transposition TableSize * 1024 * 1024);
FHits := 0;
  FMisses := 0;
end;
And voila! (of course the own LinkedList also consumes memory...)
But the engine still consumes too much memory, I've to find out why and where...