There was in interesting discussion on the Ocaml mailing list today about implementing a byte code interpreter using a continuation passing style.

The best implementation of that program is available as an OCaml Journal article with a detailed description of its design and implementation. The next F# Journal article will be along similar lines.

I was wondering if this would be relevant to HDFS logic simulations in F#. Basically the issue I face is when constructing a simulation one generally ends up with lots of very tiny "tasks". A task is simply a funtion of type unit->unit and a complete simulation consists of an ordered list of these tasks which gets executed with "List.iter (fun x -> x()) tasks". In some cases the task can be quite complex (say evaluation of of a 128x128 bit multiply), but in most cases it'll be something very simple like ((a.[0]+b.[0]) &&& mask). My gut feeling (which could well be totally off) is that in most simulations as much time is being in the overhead of iterating through the task list and calling the function as actually performing the operation itself.

The benefit of transformation to CPS is the ability to hoist computations from the inner loop and replace them with indirections. The way you explain your problem, it sounds as though you've already hoisted everything that can be hoisted. In which case, you'll just pay the price from F#'s slow tail calls when invoking one continuation from the next and CPS will probably end up making your program slower.

Is there some way in which a CPS style would alleviate this overhead? I can see that tail recusion can be used, but I would expect List.iter to already do that (though perhaps with a small amount of pointer artihmetic). How about the function call overhead?

CPS is less likely to help in F# but it sounds as though it would not help in your case anyway.

I must admit I am looking for a magic bullet here as I realize the "proper" solution to this would be to generate and compile byte code directly.

Yes. Fortunately, this is much easier with F# thanks to .NET's built-in IL generation or LINQ. There are sections on these topics in F# for Scientists, BTW.

I am also trying to encourage the F# team to add better support for metaprogramming. After all, the F# compiler itself is a great IL code generator... :-)

List.iter is tail recursive.

Array.iter would be faster.

RE: How about the function call overhead?

Creating a closure corresponds to creating an object descending from a FastFunc* class. Calling it will be a (virtual) method call. Reflector will show what is happening.

You can profile for allocation and speed with the CLRProfiler and Visual Studio sampling.

I also wondered about "ordered list".

Given your insert/consume pattern, could another datastructure give improvements?

One option is System.Collections.Generic.LinkedList.