Experimental interpreter in C

[NicoNex]

Lately I've been working on an experimental interpreter written in C for Tau for performance reasons.
My hope is that with the C interpreter we can squeeze more performance and hopefully beat Python.
To have an idea of what would be the difference in speed between the two interpreters for the moment I'm implementing a subset of Tau enough for running the fibonacci example in this repo and thus compare the two speeds.

To check it out refer to CTau.
Ideas, contributions and suggestions are very welcome :D

[prologic]

What kind of "performance" benefit do you expect go gain? Have you gotten as far yet to see how much you've managed to squeeze out? 🤔 I mean to be honest, Go is pretty damn well near C enough that I find it hard to imagine you'd get much faster 😅

[NicoNex]

I did some profiling and I couldn't find any hot spot to work on, everything seems pretty optimized in the VM.
I researched a bit and I found a very interesting repo called monkey-c-monkey-do which is basically monkey in C and according to the benchmarks that @dannyvankooten published his interpreter is actually faster than python.

As to now I haven't really got to the point where I can benchmark the fibonacci example yet in the C interpreter but I'm pretty close so in the next days I'll update this discussion.

TBH I prefer Go both for clarity and ease of development, so I'm currently researching better ways to achieve more speed, it would be nice to implement a JIT compiler in Tau keeping the Go version.

To profile Tau simply run go run profile.go, optionally you can pass to it another Tau file so that it doesn't use the default fibonacci benchmark code.
Then to see the result run go tool pprof cpu.prof and type web in the console to see the calling graph.

[NicoNex]

So I finally managed to have a working C interpreter and the difference in performance are pretty huge.
So now I'll see if I can efficiently include only the C VM in the Go project (the thing presents some challenges).

Here are the results of the benchmark running the same Fibonacci algorithm of 35 (as in the examples) on Apple M2:
Go Tau: 3.676s
Python: 1.391s
C Tau: 1.304s

I think it's interesting to see how I managed to gain such performance (I did it by looking at Python 3.11 implementation and taking inspiration from the monkey-c-monkey-do project):
https://github.com/NicoNex/ctau/blob/master/src/vm/vm.c#L374

[prologic]

I'd be really keen to understand where you're the most performance boost/gains have come from. Did you change any part of your VM implementation compared to the Go version? AFAIK Go is pretty performant in terms of "raw benchmark performance", so I'm a bit skeptical to be honest that the C version would be 3x faster 😅 Keen to get a better idea of what's really going on 👌

[NicoNex]

Yup I did change how the VM works:
in the Go version the VM consists of a loop which contains a switch case with all the atomic operations of the VM,
in the C version the VM consists of a series of labels and a static jump table with all their addresses, so in order for the VM to work it just has to goto *jump_table[*frame->ip++] at the end of each operation as defined in the DISPATCH() macro.

I think that the difference between the two implementations is best described by the Python team:

Computed GOTOs, or
       the-optimization-commonly-but-improperly-known-as-"threaded code"
using gcc's labels-as-values extension
 (http://gcc.gnu.org/onlinedocs/gcc/Labels-as-Values.html).
   
The traditional bytecode evaluation loop uses a "switch" statement, which
decent compilers will optimize as a single indirect branch instruction
combined with a lookup table of jump addresses. However, since the
indirect jump instruction is shared by all opcodes, the CPU will have a
hard time making the right prediction for where to jump next (actually,
it will be always wrong except in the uncommon case of a sequence of
several identical opcodes).
   
"Threaded code" in contrast, uses an explicit jump table and an explicit
indirect jump instruction at the end of each opcode. Since the jump
instruction is at a different address for each opcode, the CPU will make a
separate prediction for each of these instructions, which is equivalent to
predicting the second opcode of each opcode pair. These predictions have
a much better chance to turn out valid, especially in small bytecode loops.
   
A mispredicted branch on a modern CPU flushes the whole pipeline and
can cost several CPU cycles (depending on the pipeline depth),
and potentially many more instructions (depending on the pipeline width).
A correctly predicted branch, however, is nearly free.
   
At the time of this writing, the "threaded code" version is up to 15-20%
faster than the normal "switch" version, depending on the compiler and the
CPU architecture.

Additionally many smaller gains of performance that all add up are obtained by many other factors, most notably:
the way objects are implemented in the C implementation:

union data {
	int64_t i;
	double f;
	char *str;
	struct object **list;
	struct function *fn;
	struct closure *cl;
};

struct object {
	union data data;
	enum obj_type type;
	size_t len;
	void (*dispose)(struct object *o);
	void (*print)(struct object *o);
};

VS the Go implementation:

type Type int

type Object interface {
	Type() Type
	String() string
}

While this allows for a faster checking of the object type (since you compare uint32_t types) and a free value "extraction" with no expensive casting thanks to the union, it also keeps the object memory footprint pretty small (since that union weighs only 8 bytes):

struct object *o = vm_stack_pop(vm);
if (o->type == obj_integer) {
    int64_t value = o->data.i;
    // do something with value
}

var o = vm.pop()
if obj.AssertTypes(o, obj.IntType) {
    value := o.(obj.Integer)
    // do something with value
}

Also I noticed that the usage of macros for asserting the objects' types at runtime (instead of inline functions) saves around 100ms in the benchmark, and the VM stack operations are macros as well:

#define vm_stack_push(vm, obj) vm->stack[vm->sp++] = obj
#define vm_stack_pop(vm) (vm->stack[--vm->sp])
#define vm_stack_pop_ignore(vm) vm->sp--
#define vm_stack_peek(vm) (vm->stack[vm->sp-1])

#define ASSERT(obj, t) (obj->type == t)
#define ASSERT2(obj, t1, t2) (ASSERT(obj, t1) || ASSERT(obj, t2))
#define M_ASSERT(o1, o2, t) (ASSERT(o1, t) && ASSERT(o2, t))
#define M_ASSERT2(o1, o2, t1, t2) (ASSERT2(o1, t1, t2) && ASSERT2(o2, t1, t2))

Even though it's uglier, it's pretty faster than the Go implementation:

func (vm *VM) push(o obj.Object) error {
	if vm.sp >= StackSize {
		return vm.errorf("stack overflow")
	}

	vm.stack[vm.sp] = o
	vm.sp++
	return nil
}

func (vm *VM) pop() obj.Object {
	vm.sp--
	o := vm.stack[vm.sp]
	return o
}

func (vm *VM) peek() obj.Object {
	return vm.stack[vm.sp-1]
}

func AssertTypes(o Object, types ...Type) bool {
	for _, t := range types {
		if t == o.Type() {
			return true
		}
	}
	return false
}

The object type assertion happens thousands of times per second in the VM so it's pretty important.
Additionally of course enabling compiler optimisations with -fno-gcse and -O3 helps as well.

[prologic]

This is really good stuff. Quite valuable learning here 👌 You should write a blog post on this 👌

[NicoNex]

I finally managed to merge the C VM in the Tau repository so that I don't have to rewrite everything else.
The work can be checked out in the branch fast-vm, and it also contains a custom way to encode the generated bytecode into a []byte that can be either stored in .tauc files or passed to the C VM so that it can generate the bytecode with the C objects.
This new custom encoder produces precompiled files that take up to 60% less space than the previous generated by gob.

Additionally I've been working on some very hardcore optimisations in the C VM that produced astonishing results (these benchmarks have been conducted on an Intel i7 8700K with the same fibonacci recursive algorithm as last time):
Go Tau: 4,608s
Python 3.10: 1,828s
C Tau: 0,819s

This means that C Tau runs 5.75 times faster than the Go implementation and 2.25 times faster than Python 3.10.

[prologic]

Btw... I hope you don't mind, But I'll probably end up forking tau and keep the Go versions going if you don't mind, mostly because I actually quite like it 👌

[NicoNex]

Hi, actually the Go version will stay the main one and the only one at least for the foreseeable future.

The only difference with before is that first I'll disable the evaluator (it will continue existing under the hood for some compiler optimisations), and there will be 2 VMs.

The VM in Go will be used especially for the REPL since it doesn't need to convert Go objects to C objects.
The VM in C (with CGO written in a portable way) will be used when running files and for the moment it must be explicitly enabled with the -f flag, since doesn't support all the GO features yet.

So idk what your needs are but you might not need to fork it if you like the Go version.

[NicoNex]

Basically in the end I figured it was way more convenient to keep the entire project in Go both because I didn't have to develop all the features again and because Go it's way easier and more elegant to use.
So what I did was just adding the C VM to the Go project and thanks to the awesome CGO it worked very smoothly, in fact the latest benchmark I published were obtained by running the Go Tau with just the VM written in C.

[prologic]

Oh I see. Actually that's a nice surprise and an interesting direction to take 👌

[prologic]

Sorry to bring up an old topic 😅 But I actually find this type of problem kind of interesting. I tried to get my forked version of tau up-to-date (minus the C VM) and I think I got it "close enough" 🤣

Spent time time going through this discussion again and took a CPU profile of:

$ time ./tau fib.tau
9227465



real	0m4.667s
user	0m4.248s
sys	0m0.056s

See attached CPU Profile output (SVG):

I think we spend a lot of type in obj.Unwrap(...). Though I'm not completely sure yet why this is so expensive?

Also noted in my own research that Go actually uses a binary search for switch cases greater than 3? Anyway I don't think the switch vs. call table buys you too much as I noted that tengo is actually pretty damn fast! 😱

$ time ./tengo fib.tengo

real	0m2.131s
user	0m2.123s
sys	0m0.031s

Looking through their implementation, they way they handle types is a bit different, otherwise that's the only significant difference I can see.

[NicoNex]

Hi, the reason why you see such low times in your benchmarks with the old tau version is because you're calculating the fibonacci of 35 while for the latest benchmarks I used 40. Probably I generated this confusion because at the beginning I was using 35 while after a while I started only using 40.

Anyway here are the up-to-date benchmarks with both 40 and 35 for reference.

# Fibonacci of 40
$ time ./tau examples/fib.tau
102334155

real	0m10,884s
user	0m10,862s
sys	0m0,003s

# Fibonacci of 35
$ time ./tau examples/fib.tau
9227465

real	0m1,003s
user	0m1,003s
sys	0m0,000s

The thing you mentioned about Go is interesting and I'll look into it for sure.
I was thinking of mantaining a fork of Tau 1.5 and getting it up-to-date mostly to support Windows (Tau is currently compilable on Windows but it's a bit difficult due to LibFFI), it would be so nice if you could help me with that.

[prologic]

Pretty sure I can help with that 👌

[prologic]

Also it is worth noting that compiling your version of tau now doesn't work very well on macOS :/ I spent a bit of time trying to get it to compile but gave up :( This is one of the downsides of C I guess 🤣

[NicoNex]

Please tell me more about this because it should be as easy as running make in the terminal, I'm currently trying to configure GitHub workflow so that it publishes the releases directly on the repo, but I'm not having luck for the Windows one.

[prologic]

I was missing texinfo 🤦‍♂️