Re: Switch/Case statements revisited

[Mike Pall <mikelu-0711@...>]

David Given wrote:
> Mike Pall wrote:
> > Jump tables are for AOT compilers. JIT compilers have better ways
> > to optimize this, like profile-directed tree-dispatch. And it
> > shouldn't matter which control-flow constructs in the source
> > language generated the dispatch.
> 
> I haven't met those before (most of my compiler experience is with AOT stuff),
> but I'd have though that would work very nearly as well as an explicit jump
> table in the case where you have a contiguous set of integer indices, and
> better in practically every other case.

One has to take into account the dynamic execution frequencies of
the different cases (hard for AOT, easy for JIT). Often enough a
single case has a 90% hit rate. Only complex CPU designs can
predict indirect branches and then only a single target. A series
of direct branches can use multiple BTB entries. This has better
performance except under rare circumstances (high N, low variance).

> As well as making life easier for the
> compiler and users. Does LuaJIT do this? Is there any real point trying to
> optimise if...elseif...elseif...end sequences?

For Lua it's far more important to optimize calls, since all of
them are dynamically dispatched (not just those resulting from a
dispatch table). E.g. LuaJIT 1.x does this for library calls
(indirect call -> guard + inline).

For LuaJIT 2.x calls are reduced to guards and then treated
exactly the same as those resulting from if's. The trace compiler
takes care of picking the most common path(s). The IR for a
dispatch table and a series of if's should be the same after CSE
of dependent guards (i.e. equally efficient). But I'm not at that
stage, yet.

--Mike