Monday, November 12, 2007

Stupid Enumerator Tricks - And now for something completely different

Sometimes I get admittedly kooky, crazy ideas.  While playing with Tasks, ParallelFor, and Thread Pooling, a rather interesting thought popped into my head.  I've been pouring over the very interesting ideas and techniques outlined in this article on MSDN that is referring to the Parallel FX library that is in the works for the .NET framework.  One thing I've been looking at is how to make something like this applicable to natively compiled code in Delphi for Win32.  While I understand that .NET has a lot of great features and that a managed runtime environment has some interesting advantages, right now I'm all about researching how to take native Win32 code and Delphi to a new level.

What does this all have to do with Enumerators and Stupid tricks.  Well... it turns out that in Win32, the for..in language construct is the only case where the compiler will actually properly manage the lifetime of a class.  If you're curious to what I mean, make sure you look into this excellent rundown on how to write them.  It you look at some of the code in the referenced MSDN article (ignoring, for now the use of anonymous methods) there is this bit of code:

static void For( int from, int to, Action<int> body )
{
int index = from;
ReplicableTask rtask = new ReplicableTask( delegate {
int i;
while ((i = Interlocked.Increment(ref index)-1) < to) {
body(i);
}
});
rtask.Wait();
}

Since .NET is a nice garbage collected environment, there is no need to explicitly worry about freeing the "rtask" variable.  It will be collected for you.  However in the cold-cruel world of natively compiled code, you are afforded no such luxury*... sort of.  Ignoring that whole anonymous method thing, but using the nested procedure trick I mentioned here, here's a potential implementation in Delphi for Win32:



procedure ParallelFor(AFrom, ATo: Integer; AEvent: TIteratorEvent);
var
RTask: TReplicableTask;
Index: Integer;

procedure ExecuteEvent;
var
I: Integer;
begin
I := InterlockedIncrement(Index) - 1;
while I < ATo do
begin
AEvent(I);
I := InterlockedIncrement(Index) - 1;
end;
end;

begin
Index := AFrom;
RTask := TReplicableTask.Create(@ExecuteEvent);
try
RTask.Wait;
finally
RTask.Free;
end;
end;

But what if we could eliminate writing that whole try...finally thing?  Here's where it gets a little out there and on the edge :).  What if, instead we write this:



procedure ParallelFor(AFrom, ATo: Integer; AEvent: TIteratorEvent);
var
RTask: TReplicableTask;
Index: Integer;

procedure ExecuteEvent;
var
I: Integer;
begin
I := InterlockedIncrement(Index) - 1;
while I < ATo do
begin
AEvent(I);
I := InterlockedIncrement(Index) - 1;
end;
end;

begin
Index := AFrom;
for RTask in TReplicableTask.Create(@ExecuteEvent)do
RTask.Wait;
end;

So how does this work?  If you read up on enumerators on Primoz' and Hallvard's blogs, you'll know that as long as the TReplicableTask object has a method called "GetEnumerator" that returns an enumerator with the Current property of type TReplicableTask.  It will also automatically embed a try..finally block into the code and properly destroy the enumerator object for you.  Like I mentioned above, this is the only place where the compiler does this for you.  So if we added a GetEnumerator method to TReplicableTask that looked something like this:



type
TReplicableTask = class;
TTaskDestructor = class
private
FTask: TReplicableTask;
FMoved: Integer;
public
constructor Create(ATask: TReplicableTask);
destructor Destroy; override;
function GetCurrent: TAutoObject; inline;
function MoveNext: Boolean; inline;
property Current: TAutoObject read GetCurrent;
end;

TReplicableTask = class
public
...
function GetEnumerator: TObjectDestructor;
...
end;

{ TTaskDestructor }
constructor TTaskDestructor.Create(ATask: TReplicable);
begin
inherited Create;
FTask := ATask;
FMoved := -1;
end;

destructor TTaskDestructor.Destroy;
begin
FTask.Free;
inherited;
end;

function TTaskDestructor.GetCurrent: TAutoObject;
begin
Result := FTask;
end;

function TTaskDestructor.MoveNext: Boolean;
begin
Result := InterlockedIncrement(FMoved) > 0;
end;

function TReplicableTask.GetEnumerator: TTaskDestructor;
begin
Result := TTaskDestructor.Create(Self);
end;


So there you go...  An enumerator that is not really an enumerator, but actually a poor-man's implementation of an auto-destroyed object.  Yep, a Stupid Enumerator Trick of the highest order :).  So... what if we really did have anonymous methods in some future version of the compiler?  What would the above code look like then?  This is pure speculation, but I'd imagine it might look something like this:



procedure ParallelFor(AFrom, ATo: Integer; AEvent: TIteratorEvent);
var
RTask: TReplicableTask;
Index: Integer;
begin
Index := AFrom;
for RTask in TReplicableTask.Create(
procedure
var
I: Integer;
begin
I := InterlockedIncrement(Index) - 1;
while I < ATo do
begin
AEvent(I);
I := InterlockedIncrement(Index) - 1;
end;
end
) do
RTask.Wait;
end;


And, just to remind you... I'm talking natively compiled code here :).  Let the rampant speculation begin....


 


*Some would argue that this is a "good thing," but that is a can-of-worms I will refuse to open at this point :)