[Vm-dev] RoarVM: The Manycore SqueakVM

[Levente Uzonyi]

On Sat, 6 Nov 2010, Igor Stasenko wrote:

>
> 2010/11/6 Levente Uzonyi <leves at elte.hu>:
>>
>> The actual performance difference may be greater depending on the used bytecodes (tinyBenchmarks uses only a few) and the compiler's capabilities. Btw I wonder why gcc can't compile switch statements like this to jump tables by itself without gnuification.
>>
> Maybe because C sucks? :)
> But if seriously, if you look into numerous cases where switch
> statement used, only few of them would have an ordered set of cases,
> and from them, only few will have a power of two number of cases.
> So, its not worth the effort.

When I learned C, my teacher said that the switch statement was designed 
to be compiled to jump tables in most cases. I was a bit disappointed when 
I realized that most compilers don't even try to do it.

I guess you're wrong about the jump table implementation. Here's a simple 
example:

switch (i) {
 	case 0: ...;
 	case 1: ...;
 	case 2: ...;
 	default: ...;
}

It doesn't have power of two size, but it still can be implemented 
as a jump table. You just need an "array", that has 3 slots with the 
pointers of the instructions of the cases. The mapping from keys to 
indices is simply identity. You just check the bounds and jump to the 
"default" address if the key is not in the range of the array (between 0 
and 2 in this case). If there are "holes" in the table, say:

switch (i) {
 	case 0: ...;
 	case 1: ...;
 	case 3: ...;
 	default :...;
}

then the slot at index 2 will contain the address of the "default" case.

If the keys have a different offset, or are multiplied by a number, then 
the key to index mapping is a bit more complicated:

switch (i) {
 	case 28: ...;
 	case 20: ...;
 	case 16: ...;
 	default
}

The mapping is index >> 2 - 4. Also note that the cases are not ordered, 
but that doesn't matter. The array has the pointers to case 16, 20, 24 and 
28.

I think these cases should be detected by the compiler. Also compilers 
could generate perfect hash tables for all other cases to achieve similar 
performance.


Levente

>
> Another way would be to use function table, but then compiler should
> be able to inline all functions from that table, which is also
> non-trivial from compiler perspective, since its indirect.
>
>>
>> Levente
>>
>>>
>>>>
>>>> Levente
>>>>
>>>> snip
>>>>
>>>
>>>
>>>
>>> --
>>> Best regards,
>>> Igor Stasenko AKA sig.
>>
>>
>
>
>
> -- 
> Best regards,
> Igor Stasenko AKA sig.
>