[Vm-dev] RoarVM: The Manycore SqueakVM

[Igor Stasenko]

On 6 November 2010 20:30, Levente Uzonyi <leves at elte.hu> wrote:
>
> 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.
>
>

I suppose its related to fact, that with small number of cases (like up to 16)
its not worth using indirect jump, because with branch prediction you
can achieve same or even better performance.
That's why i think, modern compilers do not using jump tables.
Having more than 16 number of cases, is an edge case. Not saying about 256.


Btw, I was also thinking that compilers generating jump tables for
case statements.

> 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.
>>
>



-- 
Best regards,
Igor Stasenko AKA sig.