It's a slow Friday afternoon so I figured I'd brain dump some things I've been playing with for Release 14 of Epoch.

As I've mentioned in the past, one of my proof-of-concept programs for R14 is a raytracer. This is for a few reasons:

• Raytracing is just cool (and I have a nostalgic soft spot for it for ancient historical reasons)
  
• Good raytracers can test a language's type system to its limits in the name of compactness
  
• A raytracer can test a language's execution model to its limits in the name of performance

The raytracer project already revealed a lot of bugs and weak spots in the R13 type system implementation, which I've also mentioned before. So it's already been a huge win just on getting things in the language to work correctly and intuitively.

The other thing it did was light a fire under my butt to get Epoch's runtime performance more sane. The VM model I've been developing under is great for prototyping and knocking out features, but when it comes to execution speed, it leaves a lot to be desired. For comparison, a 300x300 pixel render of a single shaded sphere was taking over 8 seconds under the old, pure VM. I got that down to around 2 seconds by optimizing the VM implementation, but that's just not enough.

Back in the day, I worked on a realtime raytracing engine that could have done that scene at 40FPS on a sub-GHz CPU without breaking a sweat. I haven't ported the raytracer to C++ to benchmark the feature set, but my gut feeling is that anything in excess of 30ms for rendering time of that image is far too slow. In a perfect world, I want that sphere to be drawn basically realtime - and I think that may be doable.

In the interests of accomplishing that, I've started moving large swaths of the program into "[native]" functions. [native] is a tag which can be applied to Epoch functions which instructs the VM to run that function (and anything it tries to call) as native code. This is done by translating the VM bytecode into LLVM bitcode and then running the LLVM JITter to produce machine code that does the same things.

A fair amount of that transformation is trivial. Thanks to LLVM's static single assignment model, it's pretty easy to convert Epoch VM instructions to streams of comparable LLVM instructions. Thanks to the optimization passes in LLVM, turning that into insanely fast machine code is a walk in the park.

As a total side note, the "entity" model I built into Epoch ages ago has proven very useful for JITting. Since loops, conditionals, and other "code block" constructs are already abstracted in a convenient way in Epoch (and in the VM bytecode), it's drop-dead simple to convert an Epoch entity into an LLVM basic block. It's also wildly extensible - I could add more types of entities to Epoch and have them automatically support JITting just by dropping in a few lines of code.

So getting some of the raw arithmetic (ray/sphere intersections, vector normalization, dot products, etc.) into native code was a breeze. Where things got sticky was when it came time to start supporting the more interesting features of Epoch.

Sum types and pattern matching were the last two things I managed to get working in the JITter, so I'll ramble a little bit about those.


In Epoch, a sum type is stored basically as a struct that looks like this (in C):

struct SumType
{
unsigned ActualTypeTag;
union
{
// Each base type has an entry here, so e.g. int and float
} Contents;
};

Thankfully, LLVM has first-class support for structure types, so adding the tagging was easy. Where it got painful was the union - LLVM has no union types.

What I wound up doing was kind of hacky, but it works: at JIT time, I look through all known possible types that might be stored in the union. The one with the largest size (in bits) becomes the "type" of the contents field of the LLVM struct. I then simply store things in those bits and occasionally do a type cast to reinterpret the bits as the correct type. So basically, more or less exactly what a C/C++ compiler would do with a union in the first place.

The difference is that Epoch unions are designed so that if you put type A into a sum type, you can never get back out anything but type A. If you replace the contents with something of type B, the type is now "permanently" type B. So it's 100% type safe and can't be used to do things like convoluted reinterpret_cast<> hacks. So the Epoch compiler will never emit an unsafe sequence of instructions that causes data to be misinterpreted via a sum type, which I think is pretty nifty. (Granted, it limits the usefulness of Epoch if you need bit hacks, but I have plans for fixing that via other mechanisms.)


Pattern matching became much more interesting, particularly the part where Epoch supports multiple dispatch via type matching. For example, consider this snippet:

structure Numeric :
integer alpha,
integer beta

structure Textual :
string alpha,
string beta


operate : Numeric n -> integer gamma = n.alpha + n.beta // addition

operate : Textual t -> string gamma = n.alpha ; n.beta // string concatenation

So far so good; this is just function overloading based on type, right?

But wait, there's more!

type Anything : Numeric | Textual

entrypoint :
{
Anything a = Numeric(40, 2)
Anything b = Textual("Hello ", "World")

print(operate(a))
print(operate(b))
}

"Anything" is an algebraic sum type, which can dynamically hold either Numeric or Textual objects. The overloads are checked at run time, providing a form of virtual dispatch; I can give "operate" a Numeric or a Textual - wrapped in an Anything - and it'll automatically call the right code at runtime.

So... virtual functions without classes. So what?

One more snippet:

type Geometry : Sphere | Box | Cylinder | PolygonMesh

collide : Sphere s1, Sphere s2 -> boolean collision = false { ... }

collide : Sphere s, Box b -> boolean collision = false { ... }

collide : Cylinder c, Box b -> boolean collision = false { ... }

// and so on

Suppose I'm writing a physics engine in Epoch. I want to handle every possible combination of object/object collision easily. In C++, I'd have to do some gross thing like double dispatch wrappers or visitor patterns or RTTI or some custom hodgepodge of all of the above.

In Epoch, I write each function once, and I'm done. For any combination of Geometry I pass to collide(), the runtime guarantees that the correct target will be invoked, based on the actual types of the Geometry algebraic sum type that I handed the call.


This works in the Epoch VM using magic functions called dispatchers. They examine the passed-in arguments for a function which has been detected (by the compiler) to perform type decomposition during pattern matching. Based on the types received, the dispatcher then transparently tail-calls into the correct function, or throws an error if no overload can handle the type combo provided.

Where this got sticky in LLVM was handling the tail call into the correct target function. There are two combinations of flow that have to work:

• An Epoch VM function calls a native function and expects type decomposition along the way
  
• A native function calls some other native function and expects type decomposition

In the former case, the type dispatcher has to read from the Epoch VM's stack and heap space to do the type matching. In the latter case, most of the type data actually lives on the native machine stack. So there are technically now three implementations of type matching in Epoch: one for VM->VM calls, one for VM->native calls, and one for native->native calls.

Eww.


All these shenanigans have led me to a conclusion that I've sort of orbited around in the past: the Epoch VM is evil and needs to die.

I want to get away from the VM model eventually, since writing a full-fledged performant VM is a nasty job in and of itself and I don't want to be tied to it. I'd rather integrate the garbage collection model with native code generation (LLVM has some support for this anyways) and take advantage of essentially 100% native code generation for Epoch programs.

This will be a big effort, though, for several reasons:

• Epoch's type system is still only partially implemented in terms of LLVM
  
• Calling external native code is tricky, because of marshaling between garbage-collected "Epoch space" and the rest of the universe
  
• Prototyping new features is much faster in the Epoch VM than in native code, so me being lazy, I naturally resist anything that'll complicate new feature development
  
• Garbage collection will have to be reimplemented on top of LLVM instead of my own hacky version that exists now
  
• Adding things like lexical closures, exceptions, etc. will become a lot trickier without being able to screw with the running program state in the VM

And I'm sure there are other hurdles that escape me at the moment.


Nonetheless, I'm eager to start moving in that direction. It's pretty clear that as an execution model the VM needs to die, and Epoch will never be competitive with other languages so long as it remains chained to a half-cooked VM implementation. R14 will probably support JITting most if not all of the language to native code, and within two or three releases I'd like to fully excise the VM from the codebase.


We'll see how that goes.