fetch opcode-struct from hash-table
(the hash-fail rate is apparently very low);

note: I have plenty of past experience with both ASM and JIT, but at the
moment am leaning against this, and in favor of using pure C-based
interpretation for now.

dunno if anyone knows some major way around this.

dunno if anyone knows some major way around this.

"BGB / cr88192" <cr88192 at (no spam) hotmail.com> writes:
note: I have plenty of past experience with both ASM and JIT, but at the
moment am leaning against this, and in favor of using pure C-based
interpretation for now.

dunno if anyone knows some major way around this.

Modify the C compiler so that it generates optimized code for your
specific case (ie. hide your specific assembly in the C compiler).

--
__Pascal Bourguignon__

Hi cr,

How does the performance of your bytecode interpreter compare to that of
your actual hardware?

I wrote a tiny microbenchmark called ULPS
(http://inglorion.net/comparisons/ulps/) to compare the speed of
programming language implementations. Basically, all it does is decrement
an integer variable until it reaches zero, and report how many iterations
per second were done.

Using my TurboVM bytecode interpreter (which uses switch dispatch), I get
about a factor 20 to 30 fewer iterations per second as an equivalent
program
written in C and compiled with gcc -s -O3 (the exact factor depends on the
CPU). How does your bytecode interpreter compare to your actual hardware?

dunno if anyone knows some major way around this.

At some point, there is nothing you can do to make instruction dispatch
faster. At that point, the only thing you can do to reduce the overhead is
to make instructions do more work. I believe that is what Parrot
(http://www.parrot.org/) does.

Regards,

Bob

--
I eat my peas with honey;
I've done it all my life.
It makes the peas taste funny,
But it keeps them on my knife.

In alt.lang.asm BGB / cr88192 <cr88192 at (no spam) hotmail.com> wrote in part:
fetch opcode-struct from hash-table
(the hash-fail rate is apparently very low);

There's your improvement opportunity -- substitute a simpler
hash with larger failure rate and/or larger jump table.

-- Robert

"Pascal J. Bourguignon" <pjb at (no spam) informatimago.com> wrote in message
news:877huaihe4.fsf at (no spam) galatea.local...
"BGB / cr88192" <cr88192 at (no spam) hotmail.com> writes:
note: I have plenty of past experience with both ASM and JIT, but at the
moment am leaning against this, and in favor of using pure C-based
interpretation for now.

dunno if anyone knows some major way around this.

Modify the C compiler so that it generates optimized code for your
specific case (ie. hide your specific assembly in the C compiler).


I am using MSVC on x64 for this...

I can't even do stupid inline assembly, as MS removed this feature for
x64...

now, I could use my own compiler, but alas then I would have to debug its
output...

or even GCC's Win64 support, but last time I tried to use it, it produced
code so bad (buggy and ill formed) as to scare me away. granted, it has been
a fairly long time now (~ 1 year already?...), so maybe they have improved
it some, I don't know...

this is an observation I have made in the past, and I think I will state
here as if it were some kind of rule:
when a profiler says that the largest amount of time used in an interpreter
is the main opcode dispatch switch (rather than some function called by it,
or some logic contained within said switch, ... especially if this switch
does nothing more than call functions...), then they are rapidly approaching
the performance limits they can hope to gain from said interpreter.

which is kind of lame in this case, as this interpreter is, technically, not
all that fast...

but, then again, there may still be a little tweaking left, as said switch
has not gained 1st place (it is 2nd), and holds approx 12% of the total
running time.

1st place, at 15%, is the hash-table for fetching instructions (and, sadly,
is not really optimizable unless I discover some way to 'optimize' basic
arithmetic expressions, which FWIW is about as productive as trying to
optimize a switch...).

this means: 27% of time:
hash EIP (currently: "((EIP*65521)>>16)&65535");
fetch opcode-struct from hash-table (the hash-fail rate is apparently very
low);
switch on opcode info (branches to functions containing further dispatch and
logic code).

(well, all this, as well as a few arithmetic ops, such as adding the opcode
size to EIP, ...).

previously I had an opcode decoder which was not super fast (approx 60% of
runtime if sequential decoding is used), but the hash seems to have largely
eliminated it (since most of the time, pre-decoded opcodes are used from the
hash).


so, alas, it is an x86 interpreter performing at approx 386 (or maybe
486)-like speeds on my computer (~6 MIPS...).
could be faster, except that MSVC on x64 has no real idea what it is doing
WRT optimizations.

then again, it is around 12x faster than when I started trying to optimize
it (~0.5 MIPS...).


note: I have plenty of past experience with both ASM and JIT, but at the
moment am leaning against this, and in favor of using pure C-based
interpretation for now.


dunno if anyone knows some major way around this.

IOW: if there is anything that can be done when the main switch creeps into
a high position, and code starts becomming very fussy about the fine details
WRT performance issues...

past experience is generally not... (that this is a general limit to C-based
interpreters...).


any comments?...

"BGB / cr88192" <cr88192 at (no spam) hotmail.com> writes:

"Pascal J. Bourguignon" <pjb at (no spam) informatimago.com> wrote in message
news:877huaihe4.fsf at (no spam) galatea.local...
"BGB / cr88192" <cr88192 at (no spam) hotmail.com> writes:
note: I have plenty of past experience with both ASM and JIT, but at
the
moment am leaning against this, and in favor of using pure C-based
interpretation for now.

dunno if anyone knows some major way around this.

Modify the C compiler so that it generates optimized code for your
specific case (ie. hide your specific assembly in the C compiler).


I am using MSVC on x64 for this...

So unless you're rich enough to buy the sources of MSVC, forget it.

I can't even do stupid inline assembly, as MS removed this feature for
x64...

May I suggest you to switch to an open source compiler (such as gcc)?
Or just write your own compiler?

now, I could use my own compiler, but alas then I would have to debug its
output...

Hence the suggestion for a debugged compiler such as gcc.

or even GCC's Win64 support, but last time I tried to use it, it produced
code so bad (buggy and ill formed) as to scare me away. granted, it has
been
a fairly long time now (~ 1 year already?...), so maybe they have
improved
it some, I don't know...

This doesn't matter. What matters is that you have the sources, so
you can improve its optimizer.

(But also, read the interview of Fran Allen in "Coders at Work" (Peter
Seibel, Apress), you might prefer another language altogether to be
able to really optimize its compiler).

--
__Pascal Bourguignon__

On Sat, 31 Oct 2009 23:46:13 -0700, "BGB / cr88192"
cr88192 at (no spam) hotmail.com> wrote:

this is an observation I have made in the past, and I think I will state
here as if it were some kind of rule:
when a profiler says that the largest amount of time used in an
interpreter
is the main opcode dispatch switch (rather than some function called by
it,
or some logic contained within said switch, ... especially if this switch
does nothing more than call functions...), then they are rapidly
approaching
the performance limits they can hope to gain from said interpreter.

which is kind of lame in this case, as this interpreter is, technically,
not
all that fast...

but, then again, there may still be a little tweaking left, as said switch
has not gained 1st place (it is 2nd), and holds approx 12% of the total
running time.

1st place, at 15%, is the hash-table for fetching instructions (and,
sadly,
is not really optimizable unless I discover some way to 'optimize' basic
arithmetic expressions, which FWIW is about as productive as trying to
optimize a switch...).

this means: 27% of time:
hash EIP (currently: "((EIP*65521)>>16)&65535");
fetch opcode-struct from hash-table (the hash-fail rate is apparently very
low);
switch on opcode info (branches to functions containing further dispatch
and
logic code).

Offhand the above sounds ugly. I don't know many op codes you
are using but I expect that it most it is a few hundred.

The
hash function you use is relatively expensive. Using a hash
table at all is relatively expensive. A trie might be cheaper or
possibly a perfect hash. Then there is the question of why you
are using a switch at all. If the op-code lookup yields an
index, why aren't you using it as an index into a table that
contains the pointer to the action function and the op-code
struct?

Mind you, there might be very good reasons for doing what you are
doing. I don't have access to your code. Still, it sounds as
though your code is cumbersome.

(well, all this, as well as a few arithmetic ops, such as adding the
opcode
size to EIP, ...).

previously I had an opcode decoder which was not super fast (approx 60% of
runtime if sequential decoding is used), but the hash seems to have
largely
eliminated it (since most of the time, pre-decoded opcodes are used from
the
hash).


so, alas, it is an x86 interpreter performing at approx 386 (or maybe
486)-like speeds on my computer (~6 MIPS...).
could be faster, except that MSVC on x64 has no real idea what it is doing
WRT optimizations.

then again, it is around 12x faster than when I started trying to optimize
it (~0.5 MIPS...).


note: I have plenty of past experience with both ASM and JIT, but at the
moment am leaning against this, and in favor of using pure C-based
interpretation for now.


dunno if anyone knows some major way around this.

IOW: if there is anything that can be done when the main switch creeps
into
a high position, and code starts becomming very fussy about the fine
details
WRT performance issues...

past experience is generally not... (that this is a general limit to
C-based
interpreters...).


any comments?...



Richard Harter, cri at (no spam) tiac.net
http://home.tiac.net/~cri, http://www.varinoma.com
Kafka wasn't an author;
Kafka was a prophet!

"Richard Harter" <cri at (no spam) tiac.net> wrote in message
news:4aedcfb0.958856406 at (no spam) text.giganews.com...
On Sat, 31 Oct 2009 23:46:13 -0700, "BGB / cr88192"
cr88192 at (no spam) hotmail.com> wrote:
[snip]

Offhand the above sounds ugly. I don't know many op codes you
are using but I expect that it most it is a few hundred.

errm...

the x86 ISA has a bit more than this, closer to around 1,800 (core integer
ops, x87, SSE/SSE2/..., and partial AVX). full AVX and SSE5 might push it a
bit over 2000.

note that this is actual opcodes, not nmonics, where x86 likes using a
number of different opcodes with the same nmonic, although in my list there
are still around 800 nmonics...

as for there being only a few hundred opcodes, in nearly any other bytecode
this would probably be the case, but is not so much the case with x86...

the interpreter does not at present handle the full set though...


but, the hash is not used for opcode lookup/decoding, rather it is used for
grabbing already decoded instructions from a cache (which is based on memory
address).

(this is because instruction decoding is fairly expensive, and so is not
done inline, and when instructions are actually decoded, they are converted
from an in-memory opcode, to a struct-based representation, which is what is
fetched here by the hash lookup).

so, it serves a role similar to that of the L1 cache.

The
hash function you use is relatively expensive. Using a hash
table at all is relatively expensive. A trie might be cheaper or
possibly a perfect hash. Then there is the question of why you
are using a switch at all. If the op-code lookup yields an
index, why aren't you using it as an index into a table that
contains the pointer to the action function and the op-code
struct?


the hash table fetches the (already decoded) opcode struct, and the switch
is used to have the interpreter actually so something.

Step:
hash EIP address (actually: EIP+CS.Base);
try fetch decoded opcode:
ExecOpcode.
fail:
set up hash entry;
decode opcode at EIP into hash;
ExecOpcode.

ExecOpcode:
switch(op->type) //not exact, but close enough
case Basic: ExecOpcodeBasic(); break;
case Reg: ExecOpcodeReg(); break;
case RM: ExecOpcodeRM(); break;
case RegRM: ExecOpcodeRegRM(); break;
case RMReg: ExecOpcodeRMReg(); break;
case Imm: ExecOpcodeImm(); break;
case RegImm: ExecOpcodeRegImm(); break;
case RMImm: ExecOpcodeRMImm(); break;
...

...
ExecOpcodeRegRM:
resolve RM, ...
switch(op->opnum)
case ADC: ...
case ADD: ...
case AND: ...
case BSF: ...
case BSR: ...
...

in all, it is a fairly "heavyweight" interpreter, but alas, x86 is also a
fairly heavy ISA...


Mind you, there might be very good reasons for doing what you are
doing. I don't have access to your code. Still, it sounds as
though your code is cumbersome.


kind of, but it could be a whole lot worse...


how would you approach something like x86?...

hopefully not by suggesting a huge switch to dispatch for every possible
opcode byte/prefix/... and then re-enter for following bytes. many opcodes
are long (2/3 bytes for just the 'opcode' part, or 4/5 for many SSE
opcodes), and then there is the Mod/RM field, which itself is an issue to
decode.

(if you don't believe me, go and take a good long hard look at the Intel
docs, and imagine how you would go about writing an interpreter for all this
stuff...).

I started initially trying this, but soon found it unworkable.

I then switched to a more "generic" strategy (essentially grabbing my
pre-existing disassembler and using this as a template for an opcode
decoder, which itself was mostly based on a pattern-matching strategy).

it took a bit of tweaking to get the speed up (following that of reworking
it into a piece of usable interpreter machinery), but it was still fairly
slow vs the interpreter, hence I added the hash (actually, originally I
considered a more involved strategy, but this was much simpler for now, and
can still pull off more-or-less the same effect...).



(well, all this, as well as a few arithmetic ops, such as adding the
opcode
size to EIP, ...).

previously I had an opcode decoder which was not super fast (approx 60% of
runtime if sequential decoding is used), but the hash seems to have
largely
eliminated it (since most of the time, pre-decoded opcodes are used from
the
hash).


so, alas, it is an x86 interpreter performing at approx 386 (or maybe
486)-like speeds on my computer (~6 MIPS...).
could be faster, except that MSVC on x64 has no real idea what it is doing
WRT optimizations.

then again, it is around 12x faster than when I started trying to optimize
it (~0.5 MIPS...).


note: I have plenty of past experience with both ASM and JIT, but at the
moment am leaning against this, and in favor of using pure C-based
interpretation for now.


dunno if anyone knows some major way around this.

IOW: if there is anything that can be done when the main switch creeps
into
a high position, and code starts becomming very fussy about the fine
details
WRT performance issues...

past experience is generally not... (that this is a general limit to
C-based
interpreters...).


any comments?...



Richard Harter, cri at (no spam) tiac.net
http://home.tiac.net/~cri, http://www.varinoma.com
Kafka wasn't an author;
Kafka was a prophet!

but, then again, there may still be a little tweaking left, as said switch
has not gained 1st place (it is 2nd), and holds approx 12% of the total
running time.

1st place, at 15%, is the hash-table for fetching instructions (and,
sadly, is not really optimizable unless I discover some way to 'optimize'
basic arithmetic expressions, which FWIW is about as productive as trying
to optimize a switch...).

this means: 27% of time:
hash EIP (currently: "((EIP*65521)>>16)&65535");
fetch opcode-struct from hash-table (the hash-fail rate is apparently very
low);
switch on opcode info (branches to functions containing further dispatch
and logic code).

(well, all this, as well as a few arithmetic ops, such as adding the
opcode size to EIP, ...).

previously I had an opcode decoder which was not super fast (approx 60% of
runtime if sequential decoding is used), but the hash seems to have
largely eliminated it (since most of the time, pre-decoded opcodes are
used from the hash).

note: I have plenty of past experience with both ASM and JIT, but at the
moment am leaning against this, and in favor of using pure C-based
interpretation for now.

dunno if anyone knows some major way around this.

but, the hash is not used for opcode lookup/decoding, rather it is used for
grabbing already decoded instructions from a cache (which is based on memory
address).