wf-gdk-wfcode Mailing List for World Foundry GDK

SourceForge Headquarters 225 Broadway Suite 1600 San Diego, CA 92101 +1 (858) 422-6466

On Wed, 2003-01-22 at 09:22, nl...@nl... wrote:
> How do you test performance of real compiled language vs byte code
> interpreted language, and how can you determine if cache issues are
> indeed responsible for better performance of byte code interpreters?

When I did it is was on the Playstation, which was an environment I had
control over (no OS to speak of), so benchmarking was pretty easy. We
ported some logic from C++ to aicomp and it ran faster.

> I'd really like a byte-code-interpreter that is faster than compiled code=
,
> but I have trouble believing that this can actually be the case (and
> would want to be able to verify why it is faster if it is the case).

A compiled script is a form of compression, one atom (whatever size you
use for scripting codes, I have done a system with 8 bit codes, and
another with 16 bit codes) is smaller than the code the interpreter runs
as a result of that atom. So assuming op codes are used more than once
in the script program, overall there will be fewer data transfers from
memory (the native code to implement the opcode gets loading into cache
once, then each subsequent use only loads a few atoms worth of data).

A concrete example: I wrote a scripting language which implemented a 2D
graphics library which used 16 bit opcodes & operands. One of the
instructions was "Draw a line". It took 5 parameters: x1,y1,x2,y2,color.
So each draw line command consumed 12 bytes of memory. Contrast this to
a function call in C/C++, which would consist of stack frame creation,
then 5 push opcodes (one for each parameter), then the call itself. It
would look something like this (I think the x86 has a push immediate, if
not this would be even bigger):
=09
	push	color		; 3 bytes each
	push	y2			=09
	push	x2
	push	y1
	push	x1
	call	DrawLine	; 3 or 5 bytes (short or long call
	add	framesize,sp	; 3 bytes
=09
(my x86 is rusty, I don't remember exactly how to specify the size of
the constant being pushed, something like WORD in there somewhere)

So, assuming the best case that each op-code is 1 byte, the above is 21
or 23 bytes long. As you can see, the code version is almost twice as
big (and this is a best case, the actual output from the compiler could
be bigger). The reason for this is that for each parameter not only the
data must be specified, but what to do with it as well. Note that what
to do with it is repetitious (put it on the stack), which is wasteful
(and compressible).=20

What does any of this have to do with the cache? The purpose of the
cache is to reduce the # of main memory fetches that occur, because main
memory is much slower than the processor.
The above cooperates with the cache due to 2 things:
1. Reuse. Once the portion of the script interpreter for drawing a line
is in memory it doesn't need to get fetched again,
2. The total # of memory fetches is reduced, since reading 12 bytes of
script data is less than 21 bytes of native machine code.

The above is the smallest case savings, where both the script
interpreter and the native code call a function to do the actual work of
drawing a line. It is better to have as much of the drawing function
inlined as possible, avoids the overhead of the function call and give
better cache coherency.=20

Of course this example is a bit contrived, one would hope that the
programmer wouldn't hard code line coordinates in code like this
(although I have seen much code which did exactly this). If the goal is
only to draw a bunch of lines then a C loop through a coordinate data
array would be even faster than the script interpreter approach. Where
the script becomes the right choice is in the middle ground, between
wanting to only do one thing (like draw lines), and needing to do
absolutely anything (in which case the native language is best). An
example middle ground would be 2D drawing primitives, or AI logic.

All of this is based on tests I did on the Sony Playstation, which has
the most pathetic cache system I have ever seen (4K code cache, 4K of
broken data cache where the program has to explicitly use it), a modern
PC is clearly a different beast, but I think some of the same truths
will apply.

Another thing to consider: inlining is the enemy of the cache, because
it puts the same code in many different places, so the cache can't
notice the redundancy. Therefore inliing should only be done when the
resulting code is smaller than the function call would be.

In general smaller code will tend to run faster as it fits into the
cache more often, so in some cases setting optimizations to favor size
over speed might actually execute faster.

> How do you test or effectively monitor cache performance? Furthermore
> isn't relying on a cache-advantage a shaky proposition, since
> then your performance depends on the memory access pattern of your code,
> which is generally not something that you explicitly control?

I don't really know how to measure the cache specifically, but one can
benchmark the whole program and get an idea where the time is going.

BTW, there are multiple ways to measure a program's performance, what
seems to be most popular is to run a profiler, which interrupts the
program thousands of times a second and notes the PC, so captures a
histogram of where the program spends its time. This sort of profiling
is valuable, but it can't reveal anything about cache issues since a
cache hit is not something which is embodied in PC addresses (it also
includes level loading in the profile, which skews the results). The
sort of profiling I prefer is to add code to your program which times
sub-sections, which gives a complete picture of the performance of each.
When doing console games I accomplished this by having each sub-section
set the screen background to a different color, so down the screen there
would be color bands indicating what was executing (this only works if
the game runs at 60Hz, or you only enable color setting for a portion of
the execution less than 1/60th of a second, otherwise the colors overlap
and are difficult to read (although it can be done with a vcr by
pausing)). This was pretty nice because one could run the game, move
around and see portions of gameplay affect performance.=20
I haven't done this sort of profiling on the PC, I imagine I would just
read the high resolution clock and write values to a file.=20
=20
> I've been looking at Small (http://www.compuphase.com/small.htm), which
> seems quite good. It has a virtual machine interpreting byte code at
> run-time, is a small language, fixed/float support, coroutine support,
> interfaces to C, has just-in-time compilation to native code for Windows,
> and a GCC-optimized VM for Linux (but still slower than JIT).

Be sure to add that link to the scripting language wiki page).

> I still need to do performance tests though.

WF needs a performance test library, if I ever have the time I might
develop one.

--=20
Kevin Seghetti: E-Mail: kt...@te..., HTTP: www.tenetti.org
GPG public key: http://tenetti.org/phpwiki/index.php/KevinSeghettiGPGKey
Check out www.worldfoundry.org for my GPL'ed 3D video game engine

2000	Jan	Feb (2)	Mar (4)	Apr	May	Jun (2)	Jul	Aug	Sep	Oct	Nov	Dec
2001	Jan	Feb	Mar	Apr	May	Jun	Jul	Aug	Sep	Oct	Nov	Dec (1)
2002	Jan	Feb	Mar	Apr	May	Jun	Jul	Aug	Sep	Oct (23)	Nov (4)	Dec (25)
2003	Jan (7)	Feb	Mar	Apr	May	Jun	Jul	Aug	Sep	Oct	Nov	Dec