As part of the new language syntax inherited from Delphi.NET, native Delphi now (since Delphi 2005) supports for-in loops (known as foreach in C#). The new syntax is easy to read, and it reduces the clutter of maintaining a loop index variable, checking boundary conditions (typically 0 and Count-1) and indexing into the array or list.
While Delphi has special built-in support for for-in for (got it? ;) arrays, strings, and set types, the RTL and VCL also implements support for for-in by implementing an enumerator pattern. You can do the same with your own collection classes. There are a number of ways to implement such enumerators. We will look at a couple of variants, studying the code that the compiler generates for them. We will mainly focus on getting as efficient code as possible.
The Enumerator Pattern
Primoz Gabrijelcic has already posted several excellent blog posts about how to write enumerators in Delphi - please read them first if you haven't already.
Basically, when writing support for the for-in loop in one of your own classes or records (you can have records with methods these days, you know) you need to provide a single function called GetEnumerator. This function needs to return an instance of a class or a record that needs to have a public MoveNext function and a public Current property.
Here is a complete example that closely mimics the way TList implements its enumerator.
type
TMyObject = class(TObject)
procedure Foo;
end;
TMyList = class;
TMyListEnumerator = class
private
FIndex: Integer;
FMyList: TMyList;
public
constructor Create(AMyList: TMyList);
function MoveNext: Boolean;
function GetCurrent: TMyObject;
property Current: TMyObject read GetCurrent;
end;
TMyList = class(TList)
public
procedure Add(AMyObject: TMyObject);
function GetEnumerator: TMyListEnumerator;
end;
implementation
procedure TMyObject.Foo;
begin
end;
procedure TMyList.Add(AMyObject: TMyObject);
begin
inherited Add(AMyObject);
end;
function TMyList.GetEnumerator: TMyListEnumerator;
begin
Result := TMyListEnumerator.Create(Self);
end;
constructor TMyListEnumerator.Create(AMyList: TMyList);
begin
inherited Create;
FIndex := -1;
FMyList := AMyList;
end;
function TMyListEnumerator.GetCurrent: TMyObject;
begin
Result := FMyList.List[FIndex];
end;
function TMyListEnumerator.MoveNext: Boolean;
begin
Result := FIndex < FMyList.Count - 1;
if Result then
Inc(FIndex);
end;
With this code in place we can now create instances of TMyList and run the shiny new for-in loops on them.
procedure Test;
var
MyList: TMyList;
MyObject: TMyObject;
begin
MyList := TMyList.Create;
for MyObject in MyList do
MyObject.Foo;
end;
The Generated Code
This is all pretty straight-forward code, but let's look one level deeper and look at the assembly code that the compiler generates from this code. This is as easy as setting a break-point on the for-in loop, hitting run (F5) and then press Ctrl+Alt+C to open the CPU window. The code we see looks like this (from Delphi 2007).
for MyObject in MyList do
call TMyList.GetEnumerator
mov [ebp-$04],eax
xor eax,eax
push ebp
push $0040ff8c
push dword ptr fs:[eax]
mov fs:[eax],esp
jmp $0040ff62
mov eax,[ebp-$04]
call TMyListEnumerator.GetCurrent
mov ebx,eax
MyObject.Foo;
mov eax,ebx
call TMyObject.Foo
for MyObject in MyList do
mov eax,[ebp-$04]
call TMyListEnumerator.MoveNext
test al,al
jnz $0040ff51
xor eax,eax
pop edx
pop ecx
pop ecx
mov fs:[eax],edx
push $0040ff93
MyObject.Foo;
cmp dword ptr [ebp-$04],$00
jz $0040ff8b
mov dl,$01
mov eax,[ebp-$04]
call TObject.Destroy
ret
jmp @HandleFinally
jmp $0040ff7b
Wow! That sure was a lot of machine code from two innocent looking lines of Pascal!
Without digging into the semantics of each assembly instruction, we can quickly see that there are calls to four methods (GetEnumerator, GetCurrent, Foo and MoveNext) and one destructor (TObject.Destroy). There are also some magic gyrations involving FS: [xx] segment overrrides and a jump instruction to HandleFinally - this is the hallmark of a try-finally implementation.
If we try and expand the for-in loop into Pascal code, it would look something like this.
procedure TestImpl;
var
MyList: TMyList;
MyObject: TMyObject;
MyListEnumerator: TMyListEnumerator;
begin
MyList := TMyList.Create;
MyListEnumerator := MyList.GetEnumerator;
try
while MyListEnumerator.MoveNext do
begin
MyObject := MyListEnumerator.Current;
MyObject.Foo;
end;
finally
if Assigned(MyListEnumerator) then
MyListEnumerator.Destroy;
end;
end;
Is all of this overhead really necessary? Not really. While all of the enumerators in the Delphi RTL and VCL (and even in Primoz' sample code) are implemented as classes (forcing the the compiler to implicitly free the enumerator instance after the loop), there is no rule that says that all enumerators must be implemented by classes.
Enumerator Records
No, light-weight records with methods can implement enumerators, too - and they are allocated directly on the stack and has no need for calling a destructor. So changing the enumerator from a class to a record will make the code smaller and faster. Most enumerators can be favorably be implemented as records. In fact, all the existing enumerators in the Delphi RTL and VCL could be easily re-implemented as records - producing smaller and faster code for all for-in loops that use them. I can see only two reasons to use classes for enumerators; if the class needs to free something in an overridden destructor, or if the class needs to inherit functionality from another class. In all other cases, enumerators should be implemented as records.
Another observation is that the implementations for GetCurrent and MoveNext (and even GetEnumerator) are typically very short and thus perfect candidates for inlining. The two first methods will be called once for every item iterated over in the collection, so it makes sense to inline them at the call site.
So, lets change the sample code above with these two optimizations. To better see the effect on the generated code, we'll do one change at the time. First we replace the class with a record - yielding the following simple changes in the code.
type
TMyListEnumerator = record
private
FIndex: Integer;
FMyList: TMyList;
public
constructor Create(AMyList: TMyList);
function MoveNext: Boolean;
function GetCurrent: TMyObject;
property Current: TMyObject read GetCurrent;
end;
constructor TMyListEnumerator.Create(AMyList: TMyList);
begin
FIndex := -1;
FMyList := AMyList;
end;
The only changes we did was to change "class" to "record" and comment out the call to the inherited constructor (as records do not inherit anything - and cannot have parameterless constructors). Without the need to free the enumerator instance, the code the compiler generates for the for-in loop is now much simpler.
for MyObject in MyList do
mov edx,esp
mov eax,ebx
call TMyList.GetEnumerator
jmp $0041010d
mov eax,esp
call TMyListEnumerator.GetCurrent
mov ebx,eax
MyObject.Foo;
mov eax,ebx
call TMyObject.Foo
for MyObject in MyList do
mov eax,esp
call TMyListEnumerator.MoveNext
test al,al
jnz $004100fd
We can still see the three method calls to GetEnumerator, GetCurrent, Foo and MoveNext, but the heavy try-finally code and the Destroy call are gone. If we try to write this in Pascal again, it would be something like this.
procedure TestImpl;
var
MyList: TMyList;
MyObject: TMyObject;
MyListEnumerator: TMyListEnumerator;
begin
MyList := TMyList.Create;
MyListEnumerator := MyList.GetEnumerator;
while MyListEnumerator.MoveNext do
begin
MyObject := MyListEnumerator.Current;
MyObject.Foo;
end;
end;
That is much better, don't you think!? ;)
Inlining the Loop Calls
While the class-to-record optimization gave some nice code size savings, for long running loops it doesn't really affect the overall running time, because it only affects what happens before and after the loop.
The next step is to turn on inlining the the small and simple enumerator functions. This is as easy as adding the inline directive to the declaration of the methods, like this.
TMyListEnumerator = record
private
FIndex: Integer;
FMyList: TMyList;
public
constructor Create(AMyList: TMyList);
function MoveNext: Boolean; inline;
function GetCurrent: TMyObject; inline;
property Current: TMyObject read GetCurrent;
end;
Here we have just added "inline;" to the MoveNext and GetCurrent methods. Recompiling, running and hitting the break-point again, we can inspect the assembly code once again.
for MyObject in MyList do
mov edx,esi
mov eax,ebx
call TMyList.GetEnumerator
jmp $00410222
mov eax,[esi+$04]
mov eax,[eax+$04]
mov edx,[esi]
mov ebx,[eax+edx*4]
MyObject.Foo;
mov eax,ebx
call TMyObject.Foo
for MyObject in MyList do
mov eax,esi
call TMyListEnumerator.MoveNext
test al,al
jnz $00410210
Notice that the GetCurrent call is now gone - instead the assembly instructions for its implementation have been merged into our loop. This is good as excessive branching inside a loop brings down performance. But notice that the MoveNext call is still there. For some reason the compiler is not heeding our inline directive for the MoveNext function.
While Expressions Not Inlined
As discussed in my DN4DP piece on Delphi inlining, the inline directive is just a hint that the compiler should try to inline the call if possible - there are a number of documented and undocumented cases where it will not be inlined. It looks like we have stumbled onto one of the undocumented cases here - the MoveNext function of an enumerator will not currently (D2007) be inlined in the code that the compiler generates for a for-in loop.
I've done some more testing and digging, and it seems like no functions are inlined if they appear inside a while loop control expression. Given some mock-up test code:
procedure Foo;
begin
end;
function Inlined(var I: integer): boolean; inline;
begin
Dec(I);
Result := I <> 0;
end;
We can now used this inlined function in a while loop.
procedure Test1;
var
I: integer;
begin
I := 100;
while Inlined(I) do
Foo;
end;
If the inlining worked we should see no call to the Inlined function in the generated assembly code.
I := 100;
mov [esp],$00000064
jmp $0040fdc7
Foo;
call Foo
while Inlined(I) do
mov eax,esp
call Inlined
test al,al
jnz $0040fdc2
Alas, there is clearly a "call Inlined" in there :-(.
Transforming a While Loop
Let's experiment a little. Testing shows that the Inlined routine is properly inlined for a simple if-test. It is possible to rewrite a while loop with an expression into a while-true loop with an if-statement on the negated expression and a Break. We can rewrite the non-inlining while loop in Test1 with a semantically equivalent loop.
procedure Test2;
var
I: integer;
begin
I := 100;
while True do
begin
if not Inlined(I) then
Break;
Foo;
end;
end;
Looking at the generated code again (we're really getting the hang of this, right?;)), we can see that the inlining does work just fine in this loop.
I := 100;
mov [esp],$00000064
if not Inlined(I) then
dec dword ptr [esp]
cmp dword ptr [esp],$00
setnz bl
test bl,bl
jz $0040fdf2
TestInlining.dpr.57: Foo;
call Foo
while True do
jmp $0040fddd
This shows that the compiler is able to inline loop control like this - it just needs a little assistance ;).
Quality Central Reports
CodeGear could fix this in two ways;
- Fix the compiler so that while-loop expressions can be inlined (this is the best solution). This should then automatically also inline the MoveNext call that the compiler generates for for-in loops.
- If this is hard or impossible for some reason, at least the for-in loop could be changed to generate a while-true loop with if not MoveNext then Break; logic. Thus would ensure that for-in loops can become more efficient than today.
While they are at it, they could also:
- Refactor all existing RTL and VCL enumerators from class to record
- Inline all GetCurrent and MoveNext functions in all enumerators
Yes, I know should probably log these issues in Quality Central. And I will - eventually ;).
Update: I have now taken the time to report these issues and suggestions in Quality Central. Note: I think the first QC report ended up as a Beta report and may thus not be publically viewable - but it seems CodeGear have noticed anyway ;).
QC#53623 - Function calls inside while expressions are not inlined
QC#53737 - For-in codegen: Enumerator MoveNext calls are not inlined
QC#53738 - Change all RTL and VCL enumerators from class to record
QC#53739 - Inline GetCurrent and MoveNext in all RTL and VCL enumerators
