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.