After playing around with writing an IL interpreter in C# (for fun, not profit - see here), I got the idea to write an IL to C++ compiler that will take a .Net *.exe and do the following:

  • Do a static analysis of the code to determine which methods and types are actually in the code path, and ignore everything else. Done
  • Create substitute types for all the commonly used types like Int8, Int16, Int32 etc, object, string, DateTime, TimeSpan, etc. Since a lot of the "native" types make internal calls, they need to be replaced with "pure" types. Unfortunately I would also need to create equivalents to other commonly used classes, since any methods that call into internal calls would be flagged as an error. Mostly done (although not all of the base type methods and properties have been implemented yet, just some to test the feasibility of the approach).
  • Ensure the type system is fully managed. This means that the actual type of an "object" (or void*) can be determined at runtime. I can take this all the way to what reflection can do right now in .Net, it just depends on how much metadata I care to store in the exe. For instance, right now I don't store a type's namespace, its name or its member layouts etc, but it would be trivial to add it if I find I need it. Done.
  • Implement generics. Done.
  • Implement boxing/unboxing. Not done yet but should not be too difficult.
  • Implement PInvoke. Not implemented yet but this should be relatively trivial since we are already in C++ land.
  • Compile a C++ header file, declaring each used type and method. Done
  • Compile a C++ source file with method implementations. Of course this involves the actual compiling from IL instructions to C++ code but from my previous experience with the IL interpreter I think this would be relatively easy although time consuming. Not done yet.

Advantages of this approach:

  • You can take the C++ files and compile them for a microcontroller using any supported C++ compiler.
  • This should run at almost "native" speed. Currently the .Net framework runs about 100 to 1000 times slower on a microcontroller than the equivalent native code.
  • You can use the "full" .Net as opposed to just the .Net Micro Framework, although most of the framework classes' methods would not be available due to them making internal calls (this is a per-method limitation, so some methods might work just fine).
  • The exe generated by this should be very small, since only the methods and types that are actually used in the call graph are compiled. For instance, if you never use the method DateTime.Now, that code will never make it into the final exe. This has a big advantage to even the Micro Framework, which still requires all of the .Net runtime to be present on the microcontroller.

I don't have a problem writing the part of the GC that walks the object graph marking all referenced objects and then deleting unreferenced ones. Since I have full control over the C++ class generation, I intend to implement something like this:

class VirtualObject
{
public:
    Bool m_mark;

    virtual void Mark()
    {
        m_mark = True;
    }
};

class VirtualMyClass : VirtualObject
{
public:
    VirtualObject m_variableA;
    SomeOtherObject m_variableB;

    virtual void Mark()
    {
        if (m_mark)
            return;   // prevent infinite loops if two objects reference each other directly or indirectly

        VirtualObject::Mark();

        if (m_variableA)
            m_variableA->Mark();

        if (m_variableB)
            m_variableB->Mark();
    }
};

The above code would be trivial to create. There would be a "virtual stack" where all "ref types" will be created and referenced to. Now all the GC has to do is to look at all the static variables and the "virtual stack", and call Mark() on all variables derived from VirtualObject that are not null. Then walk all of the currently allocated VirtualObject types and delete the ones that do not have the mark flag set, and clear the mark flag on the ones that do have it set (for the next pass).

OK, that was way more than I intended to write, but it helps to get the full picture of what I'm doing. Now to the questions I have...

So marking and deleting objects are taken care of. But what about compacting the remaining objects? I'm wondering how one would go about implementing VirtualObjects that are "movable". I have some ideas by they seem way too complex, and it involves having multiple levels of indirection. This doesn't seem ideal either because even if you have an array of objects and use an index as a "handle" for each, if you then allocate 1,000,000 objects, but only end up keeping a reference to the last one, you are stuck with a lookup array that has 999,999 items that are null but just the last one is not null. You can't compact the array since something is referencing to the item at index 999,999.

So what is the correct way to implement a system where object are fully "movable"? Even JITted code would still need to implement this. How do the smart guys do it?