Is this possible somehow:

	int op(int r, int i)
	{
		static auto tbl = [&add, &sub, &mul];
		goto tbl[i % 3];

		add:
			r++;
			goto end;
		sub:
			r--;
			goto end;
		mul:
			r*=r;
			goto end;
		end:
		return r;
	}

Happy holidays!
BR
/HF

Heywood Floyd <soul8o8@gmail.com> wrote:

> Is this possible somehow:
>      int op(int r, int i)
>     {
>         static auto tbl = [&add, &sub, &mul];
>         goto tbl[i % 3];
>            add:
>             r++;
>             goto end;
>         sub:
>             r--;
>             goto end;
>         mul:
>             r*=r;
>             goto end;
>         end:
>         return r;
>     }

Absolutely:

enum ops : int {
    add = 0,
    sub = 1,
    mul = 2;
}

int op( int r, int i ) {
    switch( i % 3 ) {
        case add:
            r++;
            break;
        case sub:
            r--;
            break;
        case mul:
            r*=r;
            break;
    }
    return r;
}

-- 
Simen

Heywood Floyd:

> Is this possible somehow:

In this simple case Simen kjaeraas has shown you a solution. But in general D-DMD doesn't support computed gotos yet. I have asked for them some times, in some different ways. I guess they will added as a non-standard D exception, hopefully with the same syntax across different compilers.

Bye,
bearophile

Thanks for the answer!
Ok, hm, how about this then:

	auto opTable = [&op_add, &op_cmp, &op_end]; //etc.

	ubyte[] eval(ubyte[] prog)
	{
		int ip = 0, sp = 0;
		ubyte[4096] stack;

		next:
			goto opTable[prog[ip++] & OP_TABLE_MASK];

		op_add:
			stack[sp] += stack[sp-1];
			goto next;

		op_cmp:
			stack[sp] = stack[sp-1] == stack[sp-2];
			goto next;

		/// and so on...

		op_end:
			return stack;
	}


What I'm looking for here is a way of interpreting code without creating branches in the machine code, unless the interpreted code actually does a branch (ie a conditional jump). Seems to me a switch would introduce branching (?) of some sort.

I mean, even if switch is implemented as a jump table, it would still do some basic bounds checking, or?

I'm also interested in trying to inline the "next"-operation here, ie like

	string op_next(){ return "goto opTable[prog[ip++] & OP_TABLE_MASK];"; }
	//...
	op_add:
		stack[sp] += stack[sp-1];
		mixin(op_next());

..in order to reduce a jump. Of course I'm just playing around with different strategies for creating a fast interepreter. In C, at least, using a jump table instead of a switch is faster, especially in 32-bit mode (according to some very simple experiments, which may or may not hold water in reality™).

Any ideas for how to make a jump-table interpreter in D? Is it doable with inline asm perhaps? If at least not for any other reason than to investigate if it's faster. (Or is it a stupid idea to begin with? Is this overkill? : )

cheers!
BR
/HF


PS. How do you export assembler code from the DMD-compiler?










Simen kjaeraas Wrote:

> Heywood Floyd <soul8o8@gmail.com> wrote:
> 
> > Is this possible somehow:
> >      int op(int r, int i)
> >     {
> >         static auto tbl = [&add, &sub, &mul];
> >         goto tbl[i % 3];
> >            add:
> >             r++;
> >             goto end;
> >         sub:
> >             r--;
> >             goto end;
> >         mul:
> >             r*=r;
> >             goto end;
> >         end:
> >         return r;
> >     }
> 
> Absolutely:
> 
> enum ops : int {
>      add = 0,
>      sub = 1,
>      mul = 2;
> }
> 
> int op( int r, int i ) {
>      switch( i % 3 ) {
>          case add:
>              r++;
>              break;
>          case sub:
>              r--;
>              break;
>          case mul:
>              r*=r;
>              break;
>      }
>      return r;
> }
> 
> -- 
> Simen

Heywood Floyd <soul8o8@gmail.com> wrote:

> Thanks for the answer!
> Ok, hm, how about this then:
> 	auto opTable = [&op_add, &op_cmp, &op_end]; //etc.
> 	ubyte[] eval(ubyte[] prog)
> 	{
> 		int ip = 0, sp = 0;
> 		ubyte[4096] stack;
> 		next:
> 			goto opTable[prog[ip++] & OP_TABLE_MASK];
> 		
> 		op_add:
> 			stack[sp] += stack[sp-1];
> 			goto next;
> 		
> 		op_cmp:
> 			stack[sp] = stack[sp-1] == stack[sp-2];
> 			goto next;
> 	
> 		/// and so on...
> 	
> 		op_end:
> 			return stack;
> 	}


enum opTable : int {
    op_add,
    op_cmp,
    op_end,
    // etc
}

ubyte[] eval(ubyte[] prog) pure {
    int ip = 0, sp = 0;
    ubyte[4096] stack;

    while ( true ) {
        final switch ( cast( opTable )( prog[ip++] & OP_TABLE_MASK ) ) {
            case op_add:
                stack[sp] += stack[sp-1];
                continue;
            case op_cmp:
                // blahblahblah
                continue;
            // ???
            case op_end: // Profit!
                return stack;
        }
    }
}

> What I'm looking for here is a way of interpreting code without creating branches in the machine code, unless the interpreted code actually does a branch (ie a conditional jump). Seems to me a switch would introduce branching (?) of some sort.

Seems to me a goto would introduce a branch, so I'm not sure doing if
your way actually causes less branching.


> I mean, even if switch is implemented as a jump table, it would still do some basic bounds checking, or?

Final switch to the rescue!
http://digitalmars.com/d/2.0/statement.html#FinalSwitchStatement

Essentially, mark the switch as final, and cover every option.
Likely, the optimizer does that for you if you cover every option but
don't mark the switch as final.


> I'm also interested in trying to inline the "next"-operation here, ie like
> 	string op_next(){ return "goto opTable[prog[ip++] & OP_TABLE_MASK];"; }
> 	//...
> 	op_add:
> 		stack[sp] += stack[sp-1];
> 		mixin(op_next());
> ..in order to reduce a jump. Of course I'm just playing around with different strategies for creating a fast interepreter. In C, at least, using a jump table instead of a switch is faster, especially in 32-bit mode (according to some very simple experiments, which may or may not hold water in reality™).

Now this, this would not work with a simple switch, no.


> Any ideas for how to make a jump-table interpreter in D? Is it doable with inline asm perhaps? If at least not for any other reason than to investigate if it's faster. (Or is it a stupid idea to begin with? Is this overkill? : )

It likely is overkill, but I'm no expert in these matters. My forays
into the inline asm idea proved fruitless, but there may yet be ways.


> PS. How do you export assembler code from the DMD-compiler?

Not sure what you mean here. Do you want an assembler-listing as the
output of the compiler? If so, I don't think there's a way except for
obj2asm or similar disassemblers.

-- 
Simen

Simen kjaeraas:

> Essentially, mark the switch as final, and cover every option. Likely, the optimizer does that for you if you cover every option but don't mark the switch as final.

This is true in theory, and I remember Walter liking this optimization. But in practice I don't know if DMD performs this optimization already, so you need to take a look at the produced asm to be sure.

--------------------------------

This is a little test, D2 code:

enum E { e1, e2, e3 }

int foo1(E e) {
    switch (e) {
        case E.e1: return 1;
        case E.e2: return 2;
        case E.e3: return 3;
        default: assert(0);
    }
}

int foo2(E e) {
    switch (e) {
        case E.e1: return 1;
        case E.e2: return 2;
        default: return 3;
    }
}

int foo3(E e) {
    final switch (e) {
        case E.e1: return 1;
        case E.e2: return 2;
        case E.e3: return 3;
    }
}
void main() {}


_D5test4foo1FE5test31EZi
        push EAX
        test EAX,EAX
        je  L11
        cmp EAX,1
        je  L18
        cmp EAX,2
        je  L1F
        jmp short L26
L11:    pop ECX
        mov EAX,1
        ret
L18:    pop ECX
        mov EAX,2
        ret
L1F:    pop ECX
        mov EAX,3
        ret
L26:    hlt

_D5test4foo2FE5test31EZi
        push EAX
        test EAX,EAX
        je  LC
        cmp EAX,1
        je  L13
        jmp short L1A
LC:     pop ECX
        mov EAX,1
        ret
L13:    pop ECX
        mov EAX,2
        ret
L1A:    pop ECX
        mov EAX,3
        ret

_D5test4foo3FE5test31EZi
        push EAX
        test EAX,EAX
        je  L11
        cmp EAX,1
        je  L18
        cmp EAX,2
        je  L1F
        jmp short L26
L11:    pop ECX
        mov EAX,1
        ret
L18:    pop ECX
        mov EAX,2
        ret
L1F:    pop ECX
        mov EAX,3
        ret
L26:    pop EAX
        ret

--------------------------------

Some C code compiled with GCC 4.5.1:

typedef enum { e1, e2, e3 } E;

int foo2(E e) {
    switch (e) {
        case e1: return 1;
        case e2: return 2;
        default: return 3;
    }
}

int foo3(E e) {
    switch (e) {
        case e1: return 1;
        case e2: return 2;
        case e3: return 3;
    }
}

int foo4(E e) {
    static void *array[] = { &&E1, &&E2, &&E3 };

    goto *array[e];

    E1: return 1;
    E2: return 2;
    E3: return 3;
}

int main() {
    return 0;
}


_foo2:
    movl    4(%esp), %edx
    movl    $3, %eax
    cmpl    $1, %edx
    jbe L5
    rep
    ret
    .p2align 4,,7
L5:
    movl    _CSWTCH.1(,%edx,4), %eax
    ret
    .p2align 4,,15

_foo3:
    movl    4(%esp), %edx
    cmpl    $1, %edx
    je  L11
    movl    $1, %eax
    jb  L6
    cmpl    $2, %edx
    je  L13
    .p2align 4,,3
    rep
    ret
    .p2align 4,,7
L11:
    movl    $2, %eax
L6:
    .p2align 4,,3
    rep
    ret
    .p2align 4,,7
L13:
    movb    $3, %al
    ret

_foo4:
	movl	4(%esp), %eax
	jmp	*_array.1639(,%eax,4)
	.p2align 4,,7
L15:
	movl	$1, %eax
	ret
	.p2align 4,,7
L17:
	movl	$2, %eax
	ret
	.p2align 4,,7
L18:
	movl	$3, %eax
	ret

--------------------------------

> My forays into the inline asm idea proved fruitless, but there may yet be ways.

In D+DMD inline asm kills inlining, so you may use inline asm only if you need to do lot of computations. In LDC there are pragma(allow_inline) and asm expressions that some most of this problem.

Going back to the OP problem: in D there are no computed gotos, that are useful if you want to write very fast interpreters and other things. But keep in mind that DMD supports normal gotos from and in inlined asm (LLVM-LDC doesn't supports this well), plus naked asm, this gives you some possibilities.
An option on Linux is to write the interpreter core using GNU C (that has computed gotos) and then link the core to the D code compiled with DMD/GDC.

It's strange how something as basic, old and necessary as a switch, to create a basic but fast interpreter, is so hard to compile well for compilers :-)

Bye,
bearophile

Thank you bearophile and Simen for your replies! Very helpful! I'll keep looking into it...

BR
/HF



bearophile Wrote:

> Simen kjaeraas:
> 
> > Essentially, mark the switch as final, and cover every option. Likely, the optimizer does that for you if you cover every option but don't mark the switch as final.
> 
> This is true in theory, and I remember Walter liking this optimization. But in practice I don't know if DMD performs this optimization already, so you need to take a look at the produced asm to be sure.
> 
> --------------------------------
> 
> This is a little test, D2 code:
> 
> enum E { e1, e2, e3 }
> 
> int foo1(E e) {
>     switch (e) {
>         case E.e1: return 1;
>         case E.e2: return 2;
>         case E.e3: return 3;
>         default: assert(0);
>     }
> }
> 
> int foo2(E e) {
>     switch (e) {
>         case E.e1: return 1;
>         case E.e2: return 2;
>         default: return 3;
>     }
> }
> 
> int foo3(E e) {
>     final switch (e) {
>         case E.e1: return 1;
>         case E.e2: return 2;
>         case E.e3: return 3;
>     }
> }
> void main() {}
> 
> 
> _D5test4foo1FE5test31EZi
>         push EAX
>         test EAX,EAX
>         je  L11
>         cmp EAX,1
>         je  L18
>         cmp EAX,2
>         je  L1F
>         jmp short L26
> L11:    pop ECX
>         mov EAX,1
>         ret
> L18:    pop ECX
>         mov EAX,2
>         ret
> L1F:    pop ECX
>         mov EAX,3
>         ret
> L26:    hlt
> 
> _D5test4foo2FE5test31EZi
>         push EAX
>         test EAX,EAX
>         je  LC
>         cmp EAX,1
>         je  L13
>         jmp short L1A
> LC:     pop ECX
>         mov EAX,1
>         ret
> L13:    pop ECX
>         mov EAX,2
>         ret
> L1A:    pop ECX
>         mov EAX,3
>         ret
> 
> _D5test4foo3FE5test31EZi
>         push EAX
>         test EAX,EAX
>         je  L11
>         cmp EAX,1
>         je  L18
>         cmp EAX,2
>         je  L1F
>         jmp short L26
> L11:    pop ECX
>         mov EAX,1
>         ret
> L18:    pop ECX
>         mov EAX,2
>         ret
> L1F:    pop ECX
>         mov EAX,3
>         ret
> L26:    pop EAX
>         ret
> 
> --------------------------------
> 
> Some C code compiled with GCC 4.5.1:
> 
> typedef enum { e1, e2, e3 } E;
> 
> int foo2(E e) {
>     switch (e) {
>         case e1: return 1;
>         case e2: return 2;
>         default: return 3;
>     }
> }
> 
> int foo3(E e) {
>     switch (e) {
>         case e1: return 1;
>         case e2: return 2;
>         case e3: return 3;
>     }
> }
> 
> int foo4(E e) {
>     static void *array[] = { &&E1, &&E2, &&E3 };
> 
>     goto *array[e];
> 
>     E1: return 1;
>     E2: return 2;
>     E3: return 3;
> }
> 
> int main() {
>     return 0;
> }
> 
> 
> _foo2:
>     movl    4(%esp), %edx
>     movl    $3, %eax
>     cmpl    $1, %edx
>     jbe L5
>     rep
>     ret
>     .p2align 4,,7
> L5:
>     movl    _CSWTCH.1(,%edx,4), %eax
>     ret
>     .p2align 4,,15
> 
> _foo3:
>     movl    4(%esp), %edx
>     cmpl    $1, %edx
>     je  L11
>     movl    $1, %eax
>     jb  L6
>     cmpl    $2, %edx
>     je  L13
>     .p2align 4,,3
>     rep
>     ret
>     .p2align 4,,7
> L11:
>     movl    $2, %eax
> L6:
>     .p2align 4,,3
>     rep
>     ret
>     .p2align 4,,7
> L13:
>     movb    $3, %al
>     ret
> 
> _foo4:
> 	movl	4(%esp), %eax
> 	jmp	*_array.1639(,%eax,4)
> 	.p2align 4,,7
> L15:
> 	movl	$1, %eax
> 	ret
> 	.p2align 4,,7
> L17:
> 	movl	$2, %eax
> 	ret
> 	.p2align 4,,7
> L18:
> 	movl	$3, %eax
> 	ret
> 
> --------------------------------
> 
> > My forays into the inline asm idea proved fruitless, but there may yet be ways.
> 
> In D+DMD inline asm kills inlining, so you may use inline asm only if you need to do lot of computations. In LDC there are pragma(allow_inline) and asm expressions that some most of this problem.
> 
> Going back to the OP problem: in D there are no computed gotos, that are useful if you want to write very fast interpreters and other things. But keep in mind that DMD supports normal gotos from and in inlined asm (LLVM-LDC doesn't supports this well), plus naked asm, this gives you some possibilities.
> An option on Linux is to write the interpreter core using GNU C (that has computed gotos) and then link the core to the D code compiled with DMD/GDC.
> 
> It's strange how something as basic, old and necessary as a switch, to create a basic but fast interpreter, is so hard to compile well for compilers :-)
> 
> Bye,
> bearophile