Walking the key-value container

The recent discussion in comments to my latest articles (Fun with enumerators - Walking the (integer) list, On bad examples and smelly code) caused a shift in my perspective. I was always treating my TGpIntegerObjectList and TGpInt64ObjectList as lists with some baggage attached, but in practice I'm almost never using them that way. Most of the time I treat them as a background storage for key-value pairs.

What's the difference? Most of the time, I don't care about item indices. When I use my lists as containers, I never need to know where in the list some (Key, Value) pair is stored. OK, almost never. When I'm deleting from the list, I sometimes use the index, just for the performance purposes. And when I access the Value part, I have to find the index with IndexOf and then use it to reference the Objects property. There are probably other cases too - but that's something that you just have to take into account if you want to use a list as a storage media.

From time to time I'm extending lists in my GpLists unit with small wrappers that help me not to use list indices in some specific situation. Today, I used the new Walk enumerator in some code and asked myself: "Why does it have to return list index? Why couldn't it return a (Key, Value) pair?"

Good question. Why couldn't it? It turns out that it could.

A little enumerator that could

Let's set up some assumptions first. Assume that I have this pointless list.

il := TGpIntegerObjectList.Create;
il.AddObject(1, TGpString.Create('one'));
il.AddObject(2, TGpString.Create('two'));
il.AddObject(3, TGpString.Create('three'));

Further assume that I want to walk over it and display both number and text for each item. I can do this with a standard loop.

for idx := 0 to il.Count - 1 do
  Log('%d: %s', [il[idx], TGpString(il.Objects[idx]).Value]);

Or with my index-returning walker.

for idx in il.Walk do
  Log('%d: %s', [il[idx], TGpString(il.Objects[idx]).Value]);

But what I'd really like to do is.

for kv in il.WalkKV do
  Log('%d: %s', [kv.Key, TGpString(kv.Value).Value]);

Or even better.

for kv in il.WalkKV do
  Log('%d: %s', [kv.Key, kv.StrValue]);

In other words, I want to return not a single item, but a pair of items from the enumerator. Of course, Delphi expressions can only return a single result and not a tuple so we have to provide a wrapper for enumerated (Key, Value) pairs. We have to pack them in a record, class or interface.

Getting all self-destructive

My first idea was to return an interface to a key-value object from the enumerator.

  IGpKeyValue = interface
    function GetKey: int64;
    function GetValue: TObject;
    property Key: int64 read GetKey;
    property Value: TObject read GetValue;
  end; { IGpKeyValue }

  TGpKeyValue = class(TInterfacedObject, IGpKeyValue)
  private
    kvKey: int64;
    kvValue: TObject;
  protected
    function  GetKey: int64;
    function  GetValue: TObject;
  public
    constructor Create(key: int64; value: TObject);
    property Key: int64 read GetKey;
    property Value: TObject read GetValue;
  end; { TGpKeyValue }

  TGpIntegerObjectListWalkKVEnumerator = class
    //...
    function  GetCurrent: IGpKeyValue;
    property Current: IGpKeyValue read GetCurrent;
  end; { TGpIntegerObjectListWalkKVEnumerator }

function TGpIntegerObjectListWalkKVEnumerator.GetCurrent: IGpKeyValue;
var
  idx: integer;
begin
  idx := wkeListEnumerator.GetCurrent;
  Result := TGpKeyValue.Create(wkeListEnumerator.List[idx],
    TGpIntegerObjectList(wkeListEnumerator.List).Objects[idx]);
end; { TGpIntegerObjectListWalkKVEnumerator.GetCurrent }

That surely works fine, but guess what - it's incredibly slow. I wouldn't expect anything else - after all an object is allocated for every enumerated value, plus all that complications with interface reference counting...

I did some testing, of course. Thousand iterations over a list with 10.000 elements. Results are quite interesting. 5 milliseconds for a standard for loop. 50 milliseconds for my Walk enumerator. 5 seconds for interface-based WalkKV. Ouch! Let's return to the drawing board...

One allocation is enough

My next idea was to return not an interface, but an object. When you return an object, you actually return a pointer to the object data, which is quite fast. It would not help much if I would recreate this object every time the GetCurrent is called, but luckily there is no real reason to do that. I can create the object when enumerator is created and destroy it when enumerator is destroyed.

  TGpKeyValue = class
  private
    kvKey  : int64;
    kvValue: TObject;
  public
    property Key: int64 read kvKey write kvKey;
    property Value: TObject read kvValue write kvValue;
  end; { TGpKeyValue }

  TGpIntegerObjectListWalkKVEnumerator = class
  private
    wkeCurrentKV: TGpKeyValue;
    wkeListEnumerator: TGpIntegerListWalkEnumerator;
  public
    constructor Create(aList: TGpIntegerObjectList; idxFrom, idxTo: integer);
    destructor  Destroy; override;
    //...
    function  GetCurrent: TGpKeyValue;
    property Current: TGpKeyValue read GetCurrent;
  end; { TGpIntegerObjectListWalkKVEnumerator }

constructor TGpIntegerObjectListWalkKVEnumerator.Create(aList: TGpIntegerObjectList;
  idxFrom, idxTo: integer);
begin
  inherited Create;
  wkeListEnumerator := TGpIntegerListWalkEnumerator.Create(aList, idxFrom, idxTo);
  wkeCurrentKV := TGpKeyValue.Create;
end; { TGpIntegerObjectListWalkKVEnumerator.Create }

destructor TGpIntegerObjectListWalkKVEnumerator.Destroy;
begin
  FreeAndNil(wkeCurrentKV);
  FreeAndNil(wkeListEnumerator);
  inherited;
end; { TGpIntegerObjectListWalkKVEnumerator.Destroy }

function TGpIntegerObjectListWalkKVEnumerator.GetCurrent: TGpKeyValue;
var
  idx: integer;
begin
  idx := wkeListEnumerator.GetCurrent;
  wkeCurrentKV.Key := wkeListEnumerator.List[idx];
  wkeCurrentKV.Value := TGpIntegerObjectList(wkeListEnumerator.List).Objects[idx];
  Result := wkeCurrentKV;
end; { TGpIntegerObjectListWalkKVEnumerator.GetCurrent }

BTW, you can see another trick in this implementation - enumeration by delegation. I'm reusing my Walk enumerator to do the actual walking.

That works much faster than the interface-based version - 300 ms for my test case. It's still six times slower than the Walk enumerator, though, and it is not really obvious why the difference is so big. Leave that be, for a moment.

The third approach would be to use a record to store the current (Key, Value) pair. Then there is no allocation/deallocation at all, but resulting code is not faster. Record-based enumerator needs about 500 ms to run the test case.

This slowdown occurs because record is not returned as a pointer, but as a full copy. In the class-based scenario, GetCurrent returns a pointer to the TGpKeyValue object and that pointer is passed in a register. In the record version, GetCurrent returns not a pointer to the record, but the record itself - it copies full record to the stack so the caller can use this copy - and that is waaaay slower.

The speed difference

Let's return to that major speed difference between Walk and WalkKV. I looked at the code, but couldn't find any good reason. Then I turned to the CPU view and it was evident. The problem lied not in the enumerator, but in my poorly designed benchmarking code :(

You see, I was timing multiple repetitions of these three loops:

for idx := 1 to 10000 do 
  ;

for idx in il.Walk do
  ;

for kv in il.WalkKV do
  ;

Three empty loops, so I'm timing just the enumeration, yes? No!

First loop just runs from 1 to 10000. Trivial job and compiler will generate great code.

Second loop does the same, but with more overhead.

Third loop does much more than that. It also accesses il[] and il.Objects[] (inside the GetCurrent).

In reality, code inside the for statement in the first two cases would have to access il[] and il.Objects[] by itself. The code inside the third for statement has no need for that - it gets data neatly prepared in kv.Key and kv.Value.

I changed the loops to:

for idx := 0 to il.Count - 1 do begin
  il[idx];
  obj := il.Objects[idx];
end;

for idx in il.Walk do begin
  il[idx];
  obj := il.Objects[idx];
end;

for kv in il.WalkKV do begin
  kv.Key;
  obj := kv.Value;
end;

I'm just accessing and throwing the Items[]/Key information away and then I copy the Objects[]/Value information into the local variable. All loops are now running comparable jobs.

Results are now significantly different. Simple for loop needs 300 ms to run the test, Walk version needs 310 ms (really small difference) and WalkKV version needs 470 ms. It is still slower, but by less than the factor of two. If there would be a real code inside the for loop, the difference would be unnoticeable.

Morale? You should benchmark, but you should also check that you're benchmarking the right thing!

Syntactic sugar

The generic version of WalkKV only supports this kind of code:

for kv in il.WalkKV do
  Log('%d: %s', [kv.Key, TGpString(kv.Value).Value]);

But there's a really neat trick to change this into

for kv in il.WalkKV do
  Log('%d: %s', [kv.Key, kv.StrValue]);

without modifying the WalkKV itself. Can you guess it? Class helpers, of course.

You just have to declare a simple helper in the WalkKV consumer (no need to change the WalkKV itself) and you can use the StrValue instead of TGpString(kv.Value).Value.

  TGpKeyStrValue = class helper for TGpKeyValue
  public
    function StrValue: string; inline;
  end; { TGpKeyStrValue } 

function TGpKeyStrValue.StrValue: string;
begin
  Result := TGpString(Self.Value).Value;
end;

Conclusion: class helpers are great. Key-value walker is useful. Enumerator-induced performance loss is negligible. Enumerators are fun.

---

I've tagged this and all previous enumerator-related articles with the enumerators label so you can now access them all at once via this simple link.