On 29.10.2011 15:16, Manu wrote:
On 29 October 2011 10:55, Dmitry Olshansky <[email protected]
<mailto:[email protected]>> wrote:

    On 29.10.2011 3:15, Manu wrote:


            This is instruction dispatch, the trick in the branch prediction
            that operates on per branch basis, thus single switch-jump
        based VM
            dispatch will mispredict jumps most of the time. I seen
        claims of up
            to 99% on average.
            If you place a whole switch at the end of every instruction
        code I'm
            not sure compiler will find it's way out of this mess, or even
            optimize it. I tried that with DMD, the problem is it have
        no idea
            how to use the *same* jump *table* for all of identical
        switches.


        I don't quite follow what you mean here... so forgive me if I'm
        way off,
        or if you're actually agreeing with me :)
        Yes, this piece of code is effectively identical to the switch
        that may
        fall at the top of an execute loop (assuming the switch compiles
        a jump
        table), but there are some subtle differences...
        As said before, there's no outer loop, which saves some code and a
        branch,


    It doesn't save code - you replace unconditional jump to start of
    switch, with an extra load from table + indirect jump per VM opcode.


True, it may appear there is more code, but the pipeline is far more
overlapped, it can load the jump target earlier, also there is still
less work whichever way you slice it.

Yes, I was just arguing that code size is *strictly speaking* larger. Yet it's faster, but saving on extra uncoditional jump is not the only reason.


    but more importantly, on architectures that have branch target

        registers, the compiler can schedule the load to the branch target
        earlier (while the rest of the 'opcode' is being executed),
        which will
        give the processor more time to preload the instruction stream
        from the
        branch destination, which will reduce the impact of the branch
        misprediction.


    I was thinking x86 here, but there are other processors that do not
    have branch target register. And depending on the pipeline length
    prediction it should be done earlier then loading of destination
    address.


I'm not sure what you mean here about pipeline length prediction...

Ouch.
It should have been: depending on the pipeline length, prediction should have started earlier then loading destination address.

 but
with respect to x86, and other performance orientated architectures, I
don't see how this could disadvantage the processor in any way. While an
out-of-order processor like x86 may be able to look ahead, resolve an
unconditional jump back to the top of a switch, and begin resolving the
next target ahead of time, having the dispatch inline just means there
is no unconditional jump, a couple less instructions to process.


No objections here, it is faster.


        I'm not sure what you're trying to say about the branch
        prediction, but
        this isn't a 'branch' (nor is a switch that produces a jump
        table), it's
        a jump, and it will never predict since it doesn't have a binary
        target.


    I'm not sure about terminology, but branch === jump, and both can be
    conditional. By switch-jump I mean tabulated indirect jump, that is
    target is loaded from table.
    It's an indirect jump and as such can go wherever it wants to. And
    yes it's still predicted, mostly on basis of "it will go to the same
    address as last time". Actually, branch benediction mechanisms I
    heard of don't know if some jump is conditional at all (that would
    complicate it), the end result is just a block of "branch/jump at
    address X is predicted to go to address Y".


I would say branch != jump; a branch is conditional (I think the term
'branch' implies conditionality), and is a candidate for prediction.
Branch opcodes are more often than not to absolute targets too. A jump
is unconditional, the branch prediction hardware has no effect on jump
opcodes, and naturally it may be an absolute jump (performs more or less
like a noop), or an indirect one, which is the worst case.

Indirect jumps are still being predicted, that's what I've been arguing. Anyway, it's a well known stuff called threaded code, and I'm sure there are better sources then my mumbling about optimizing it:
http://www.complang.tuwien.ac.at/anton/lvas/sem06w/revucky.pdf

 cpu's will
typically try and optimise this by prefetching the code at the earliest
moment it can know the target. The mechanics of which are quite
different for out-of-order processors, and architectures like PPC, which
have a specific register indirect jump targets.
An x86 or some other OoO processor may look ahead far enough to find the
target in advance, but I'm not sure about that. Simplier architectures
will not be able to do that (intel atom/ppc/arm/mips).


        Many architectures attempt to alleviate this sort of unknown target
        penalty by introducing a branch target register, which once
        loaded, will
        immediately start fetching opcodes from the target.. the key for the
        processor is to load the target address into that register as
        early as
        possible to hide the instruction fetch latency. Code written in the
        style I illustrate will give the best possible outcome to that end.


    Nice to know, which ones by the way?


PowerPC being the most important one (only one that's relevant these
days), ie, all games consoles. But also some popular microcontrollers.
But I'm fairly sure most popular architectures will do the same thing
where the jump target comes from a general register (ARM). The sooner
the target is known, the better.


I don't see any real disadvantage to this syntax. It's optional, has no
side effects, and allows you to express something that can't be
expressed any other way.
I imagined it would be easy to implement, and it's definitely useful in
certain circumstances, a handy tool to have, particularly when working
on embedded platforms where compiler backends/optimisers are always weak
and immature, and these sorts of performance considerations are more
important (ie, games consoles, microcontrollers).


--
Dmitry Olshansky

Reply via email to