Why do bytecodes work?

199 views
Skip to first unread message

Kristoffer Lawson

unread,
Oct 15, 2002, 7:04:33 PM10/15/02
to
This is a stupid question, I'm sure, but how does bytecode make code faster?
Yes, obviously not having to interpret string code every time and looking
up hash tables will make things faster, but why the conversion to a separate
bytecode? I cannot understand how executing bytecode could possibly be faster
than using a translator that changes code to direct function pointers
and calling them. The latter would naturally have the benefit that all
commands and all extensions would be fast.

I realize the above is perhaps difficult to do with commands as argyments
and stuff, but I tested it for a simple command executor I worked on a
while back and it seemed to work OK and saved me the bother of creating
a bytecode translator.

I'm sure there are very good reasons why this would not work, and I
admit to not having checked the bytecode source much, but I'm curious
because surely bytecodes have to do the same as the called C code
anyway (and have to be translated), so how can this be quicker than
calling the implementing C function directly?

--
/ http://www.fishpool.com/~setok/

miguel sofer

unread,
Oct 15, 2002, 9:19:21 PM10/15/02
to

One effect is the one you are considering: replacing command lookup at
runtime by pointers (cached in a Tcl_Obj). But this effect does not
really need the bytecodes, as you well saw. You more or less get it with
the 'pure list optimisation', i.e., when you do
eval $pureList

But additionally bytecodes avoid a lot of runtime parsing, replace many
(local) variable lookups at runtime by pointers, replace many C-calls by
jumps (bytecoded commands such as set, append, lappend, lindex, lset,
if, for, foreach, while; Tcl_Eval* calls for loop bodies or conditional
scripts), and other such stuff.

The general idea is: perform at compile time as much as possible while
respecting Tcl's late-binding semantics. The current compiler/engine is
still far from "as much as possible", but does quite a bit.

miguel

David Gravereaux

unread,
Oct 16, 2002, 12:45:02 AM10/16/02
to
Hi Miguel,

Sounds like a good place for me to poke in..

Today at work, I got around to testing the tbcload/8.4.0 issue and good news,
Jeff's changes work great. So there's no problem anymore.. Phew!

About [Incr Tcl], though. It's common to mixup "compiling" with "obfuscating"
as part of tclpro's procomp is to render a compiled script unreversable.

D:\>type itclTest.tcl
package require Itcl

itcl::class Foo {
constructor {anArg} {
set Baz $anArg
}
method Bar {} {
return $Baz
}
private variable Baz
}

proc Blah {a b c} {
return [concat $a $b $c]
}

D:\>c:\progra~1\tclpro1.4\win32-ix86\bin\procomp -nologo itclTest.tcl

D:\>c:\progra~1\tclpro1.4\win32-ix86\bin\tclsh83
% source itclTest.tbc
% proc lala {a b c} {return $a$b$c}
% lala 1 2 3
123
% info body lala
return $a$b$c
% info body Blah
# Compiled -- no source code available
error "called a copy of a compiled script"
% Foo #auto qwerty
foo0
% foo0 Bar
qwerty
% foo0 info function
::Foo::isa ::Foo::Bar ::Foo::configure ::Foo::constructor ::Foo::cget
% foo0 info function Bar
public method ::Foo::Bar {} {
return $Baz
}
%


In the above, I can't retrieve what the original 'Blah' procedure was, yet I can
ask Itcl what the parts of its inside are. Makes me wonder how to do the same
"obfuscating" ability... Any ideas?
--
David Gravereaux <davy...@pobox.com>
Tomasoft Engineering, Hayward, CA
[species: human; planet: earth,milkyway,alpha sector]

Donal K. Fellows

unread,
Oct 16, 2002, 10:10:45 AM10/16/02
to
Kristoffer Lawson wrote:
> I cannot understand how executing bytecode could possibly be faster
> than using a translator that changes code to direct function pointers
> and calling them. The latter would naturally have the benefit that all
> commands and all extensions would be fast.

Compiling to the form you describe is quite possibly faster when running, but it
is much harder to do. The key advantage (in terms of maintainability) that a
bytecode has over real machine-code is that the bytecode engine can be written
once, but the code to target a particular machine architecture would have to be
rewritten for every new machine variant. Porting to a new architecture would
become an enormous task, similar to getting GCC running on that new platform!

And many of Tcl's bytecodes are fairly high-level so beating them with direct
code (while maintaining Tcl's semantics) is not straight-forward...

Donal.
--
Donal K. Fellows http://www.cs.man.ac.uk/~fellowsd/ donal....@man.ac.uk
"If RedHat are so purblind that they think computing is about ever fancier
'desktop themes', they are in the interior design business, and as everyone
knows, if you can piss you can paint." -- Steve Blinkhorn

Kevin Kenny

unread,
Oct 16, 2002, 6:16:37 AM10/16/02
to
Kristoffer Lawson wrote:
> This is a stupid question, I'm sure, but how does bytecode make code faster?

You're essentially asking about the merits of a bytecoded interpreter
versus a threaded one.

Essentially, it comes down to the fact that the C code

switch (*pc++) {
case INSTR1:
...
case INSTR2;
...
}

is -- on most platforms -- faster than code like

pc = (*pc++)( ... params ... );

particularly since the parameter list must include at least a stack pointer,
which can otherwise be kept in a local register variable. The overhead
of parameter passing, saving register variables to memory,
making the call, making the return, getting register vars back, cleaning up
the stack, ... is greater than the cost of a couple of jumps.

Also, generally speaking, the code for the individual instructions is
faster in a bytecoded system than in a threaded one,
because most optimizing C compilers do a fair job on inline
code but are horrible at interprocedural optimization.

Remember that while some of the bytecodes (INST_LSET_FLAT comes to mind)
are hideously complex, others (such as INST_LOAD_SCALAR1, which is a lot
more common) are only a couple of machine instructions. For the simple
ones, the overhead of a function call would dominate the cost of
executing the bytecode instruction.

What I'm saying here is not categorically true on all implementations,
and Miguel Sofer in particular is actively trying various alternatives.
It is true, though, that Brian Lewis did a few experiments with a
threaded interpreter before building the bytecoded one in 8.0, and
the results were unpromising.
--
73 de ke9tv/2, Kevin

Kristoffer Lawson

unread,
Oct 16, 2002, 5:19:42 PM10/16/02
to
miguel sofer <mso...@users.sf.net> wrote:
>
> But additionally bytecodes avoid a lot of runtime parsing, replace many
> (local) variable lookups at runtime by pointers, replace many C-calls by
> jumps (bytecoded commands such as set, append, lappend, lindex, lset,
> if, for, foreach, while; Tcl_Eval* calls for loop bodies or conditional
> scripts), and other such stuff.

Well I understand the variable lookups and stuff, but my question was
really referring to commands such as lappend, lindex etc. The same
effect has to be made anyway, so why can the compiler not build a structure
with direct pointers to functions implementing those features? And do
this with absolutely everything so all functions are in a sense "compiled".


--
/ http://www.fishpool.com/~setok/

Kristoffer Lawson

unread,
Oct 16, 2002, 5:28:42 PM10/16/02
to
Kevin Kenny <ken...@acm.org> wrote:
>
> particularly since the parameter list must include at least a stack pointer,
> which can otherwise be kept in a local register variable. The overhead
> of parameter passing, saving register variables to memory,
> making the call, making the return, getting register vars back, cleaning up
> the stack, ... is greater than the cost of a couple of jumps.

OK, thanks for your response. I guess that is a fair explanation, although
I'm not quite sure how well it holds up with modern compilers. F.ex. the
SGI MIPS Pro compiler actually does interprocedural optimisation, even
across object files (naturally this requires extra functionality from the
linker too).

The reason I'm asking is because a bytecode implementation has a lot
of hard-coded logic and can never really be perfect, because each new
feature of the language should be added to the massive switch. The
code for the byte compiler in Tcl is much more difficult to understand
and change than the equivalent functional versions. F.ex. the change
I once proposed for handling lists (and the faster lreplace and linsert)
would have been more complex if the byte compiler would have to be
considered too. The same applies to the idea of having Tcl strings work
as ladders. The task seems a bit daunting when beginning to consider
the effects on the byte compiler.


>
> What I'm saying here is not categorically true on all implementations,
> and Miguel Sofer in particular is actively trying various alternatives.
> It is true, though, that Brian Lewis did a few experiments with a
> threaded interpreter before building the bytecoded one in 8.0, and
> the results were unpromising.

So does the current compilation system also build a structure of
function pointers for commands which are not compiled? If not, this would
be one area for possible improvement (yes, I realize it is far from trivial),
which would lead to just about every extension being faster, as well as
all commands which are not currently converted to bytecode.

--
/ http://www.fishpool.com/~setok/

Kristoffer Lawson

unread,
Oct 16, 2002, 5:38:42 PM10/16/02
to
Donal K. Fellows <donal.k...@man.ac.uk> wrote:
> Kristoffer Lawson wrote:
>> I cannot understand how executing bytecode could possibly be faster
>> than using a translator that changes code to direct function pointers
>> and calling them. The latter would naturally have the benefit that all
>> commands and all extensions would be fast.
>
> Compiling to the form you describe is quite possibly faster when running, but it
> is much harder to do. The key advantage (in terms of maintainability) that a
> bytecode has over real machine-code is that the bytecode engine can be written
> once, but the code to target a particular machine architecture would have to be
> rewritten for every new machine variant. Porting to a new architecture would
> become an enormous task, similar to getting GCC running on that new platform!

Hm, not true, unless you want very specific optimisations. My own
code -> function pointer translator should be totally portable to all
machines supporting ANSI C. Note that I'm not talking about a JIT compiler
but a compiler that builds up a stucture (in my case a simple array was
sufficient) with direct pointers to the implementing functions and
the code is then executed by calling those pointers with the appropriate
arguments. I vaguely remember that with some compilers this can be
even faster than the big switch used in the current Tcl compiler.

This way one can avoid using hash tables, and any commands from any extension
are called in a way which should be almost as fast as calling them directly
in C.

Again, I'm not saying this is easy and it's quite possible Tcl does this
for commands already (I'm sorry, I really haven't checked), but on paper
it looks possible.

--
/ http://www.fishpool.com/~setok/

Chang Li

unread,
Oct 17, 2002, 10:40:38 AM10/17/02
to
How could a bytecod speedup following proc?

proc foo {} {
return "very long string"
}

The "very long string" is acturally compiled into the bytecode.

Chang

"miguel sofer" <mso...@users.sf.net> wrote in message
news:3DACBE99...@users.sf.net...

Kevin Kenny

unread,
Oct 17, 2002, 11:19:06 AM10/17/02
to

Kristoffer Lawson wrote:
> [...] I guess that is a fair explanation, although


> I'm not quite sure how well it holds up with modern compilers. F.ex. the
> SGI MIPS Pro compiler actually does interprocedural optimisation, even
> across object files (naturally this requires extra functionality from the
> linker too).

Alas, few of us are blessed with modern compilers! The vast majority of Tcl
users are using Tcl built with gcc (many platforms), SunPro cc (Solaris),
VC++6 (Windows), or HP's cc. Of these, only HP's compiler has
interprocedural optimization that even begins to approach what can be
done with the inline code.

> So does the current compilation system also build a structure of
> function pointers for commands which are not compiled? If not, this would
> be one area for possible improvement (yes, I realize it is far from trivial),
> which would lead to just about every extension being faster, as well as
> all commands which are not currently converted to bytecode.

It does something close to it. The generated bytecodes push function
parameters onto the evaluation stack left-to-right, then interpret the
Tcl object corresponding to the command. Once the engine has resolved the
command name once (at bytecode execution time), the Tcl_Obj
has the function pointer as one part of its internal representation.
If the same function is invoked again, the name resolution is
avoided. It's not as fast as direct threading, but nearly so.

The drawback is that re-evaluating the same function in a different
namespace context shimmers the function pointer away again. This case can
be improved by reducing the amount of promiscuous literal sharing that the
compiler does. Miguel and I are looking at that issue.

Another issue with a pure-threaded scheme for the interpreter engine is
that you either have to track what threaded codes use what commands, or
else you have to invalidate all your compiled code every time someone
redefines a [proc], because the new procedure could be redefining a
command inside threaded code that you've already compiled. This issue
isn't insurmountable, but the dynamic nature of Tcl makes it a bit
tricky. The scheme used today doesn't need to invalidate the bytecode
nearly as aggressively, because few scripts redefine Tcl's internal
commands.

One last consideration is that whatever we do in an 8.x release has to be
forward compatible with bytecodes generated in 8.0 - at least to the extent
that 'tbcload' needs to be able to do a translation to the new scheme.
Otherwise, scripts compiled with 'procomp' need to be recompiled moving
forward. (8.4.0 has a bug with that, which is one reason for hastening
8.4.1 out the door.)

If you want to experiment in this area, the few of us that work with it
would be glad of the help!

--
73 de ke9tv/2, Kevin KENNY GE Corporate R&D, Niskayuna, New York, USA

Schelte Bron

unread,
Oct 18, 2002, 4:55:32 AM10/18/02
to
On 10/16/02 06:45, David Gravereaux wrote:
> Today at work, I got around to testing the tbcload/8.4.0 issue and good news,
> Jeff's changes work great. So there's no problem anymore.. Phew!
>
Are you implying that TclPro based on tcl 8.4.0 is available somewhere?
I looked at the TclPro web page, but the latest version there is still
based on 8.3.2. Where should I go to get a procomp based on version
8.4.0? If the answer is SourceForge, do I really need to have my own
account there or should it be possible to get all needed sources using
the anonymous account?

Thanks,
Schelte.

Jeffrey Hobbs

unread,
Oct 18, 2002, 11:27:27 AM10/18/02
to
Schelte Bron wrote:
> On 10/16/02 06:45, David Gravereaux wrote:
>
>> Today at work, I got around to testing the tbcload/8.4.0 issue and good news,
>> Jeff's changes work great. So there's no problem anymore.. Phew!

> Are you implying that TclPro based on tcl 8.4.0 is available somewhere?

ActiveState will be making a more 8.4-aware version of the Tcl Dev Kit,
which includes TclPro, available before the end of the month. We will
be releasing updated versions of ActiveTcl in the next week as well which
include the updated tbcload.

The updated Tcl Dev Kit will include both 8.3 and 8.4 based wrapper stubs
for prowrap, as well as both a procomp and a procomp8.4. 2 procomps are
necessary because:
* an 8.3-based procomp cannot compile code with 8.4 features in it (eg:
if {$a eq $b} ...)
* if you compile code with an 8.4-based procomp, you cannot use it in an
8.3 or earlier interpreter, even if it didn't use 8.4 features, because
the internal bytecodes of 8.4 are different (more instructions).
If you have 8.3 or earlier based code and compile it with the 8.3 based
procomp, it will work in 8.4 (with the updated binaries next week).

> 8.4.0? If the answer is SourceForge, do I really need to have my own
> account there or should it be possible to get all needed sources using
> the anonymous account?

You can access any SF project's CVS anonymously. Just look at any
project's CVS page and it has the instructions there.

--
Jeff Hobbs The Tcl Guy
Senior Developer http://www.ActiveState.com/
Tcl Support and Productivity Solutions

Kristoffer Lawson

unread,
Oct 18, 2002, 2:34:39 PM10/18/02
to
Kevin Kenny <ken...@acm.org> wrote:
>
> Alas, few of us are blessed with modern compilers! The vast majority of Tcl
> users are using Tcl built with gcc (many platforms), SunPro cc (Solaris),
> VC++6 (Windows), or HP's cc. Of these, only HP's compiler has
> interprocedural optimization that even begins to approach what can be
> done with the inline code.

Yes, you're probably right. I'm not even sure how well SGI's compiler
handles interprocedural optimisation. I just know it tries.


>
>> So does the current compilation system also build a structure of
>> function pointers for commands which are not compiled? If not, this would
>> be one area for possible improvement (yes, I realize it is far from trivial),
>> which would lead to just about every extension being faster, as well as
>> all commands which are not currently converted to bytecode.
>
> It does something close to it. The generated bytecodes push function
> parameters onto the evaluation stack left-to-right, then interpret the
> Tcl object corresponding to the command. Once the engine has resolved the
> command name once (at bytecode execution time), the Tcl_Obj
> has the function pointer as one part of its internal representation.
> If the same function is invoked again, the name resolution is
> avoided. It's not as fast as direct threading, but nearly so.

This sounds quite good enough, but does it apply to all commands
or just certain commands? I'm asking this because I can't see how the
above solves the issue of command redefinition (of course the whole
dynamic nature of Tcl makes things like this really tricky). You also
mentioned that this is less of a problem because "few scripts redefine
Tcl's internal commands", which leads me to believe this optimisation
currently only applies to core commands?

--
/ http://www.fishpool.com/~setok/

Kevin Kenny

unread,
Oct 18, 2002, 5:12:42 PM10/18/02
to
Kristoffer Lawson wrote:
> This sounds quite good enough, but does it apply to all commands
> or just certain commands? I'm asking this because I can't see how the
> above solves the issue of command redefinition (of course the whole
> dynamic nature of Tcl makes things like this really tricky). You also
> mentioned that this is less of a problem because "few scripts redefine
> Tcl's internal commands", which leads me to believe this optimisation
> currently only applies to core commands?

It's all commands, but redefining *any* command in a given namespace
causes *all* references to commands in that namespace to shimmer away.

That doesn't actually work all that badly if you don't ever redefine
commands in the global namespace after application initialization, because
at least Tcl builtins will be resolved quickly. Likewise for canned
packages that are well-behaved. In general, you pay for the dynamic
nature of Tcl only in namespaces that use it.

As I said, right now it's got a problem with promiscuous literal sharing
if names are duplicated among namespaces. We're working on that.

Schelte Bron

unread,
Oct 21, 2002, 5:57:16 AM10/21/02
to
On 10/18/02 17:27, Jeffrey Hobbs wrote:
> If you have 8.3 or earlier based code and compile it with the 8.3 based
> procomp, it will work in 8.4 (with the updated binaries next week).
>
Thanks Jeff. Sorry that I kept harping on about this.

> You can access any SF project's CVS anonymously. Just look at any
> project's CVS page and it has the instructions there.
>

I can't stand it when I'm unable to do things that should be simple, so
I had another go at building TclPro from the cvs sources. I followed the
instructions described in:
http://www.tcl.tk/software/tclpro/README.build.txt
I ran into a number of problems which could be solved using
http://wiki.tcl.tk/3115.

Then make failed for the included tclsh8.3.2:
~/cvs> cd tclpro/linux
~/cvs/tclpro/linux> ../configure
~/cvs/tclpro/linux> make
[snip]
checking union wait... yes
checking matherr support... yes
checking for strncasecmp... yes
checking for BSDgettimeofday... no
./configure: line 8707: syntax error: unexpected end of file

***ERROR: command returned nonzero exit status
Working Directory:
/home/sbron/cvs/tclpro/linux/build/linux-ix86/tcl_static/unix
Failed Command: bash ./configure
--srcdir=/home/sbron/cvs/tcl8.3.2/unix
--prefix=/home/sbron/cvs/tclpro/linux/out
--exec-prefix=/home/sbron/cvs/tclpro/linux/out/linux-ix86
--with-tcl=/home/sbron/cvs/tclpro/linux/build/linux-ix86/tcl/unix
--disable-shared --enable-gcc --enable-symbols


failed: bash ./configure --srcdir=/home/sbron/cvs/tcl8.3.2/unix
--prefix=/home/sbron/cvs/tclpro/linux/out
--exec-prefix=/home/sbron/cvs/tclpro/linux/out/linux-ix86
--with-tcl=/home/sbron/cvs/tclpro/linux/build/linux-ix86/tcl/unix
--disable-shared --enable-gcc --enable-symbols
make: *** [install] Error 1

There seems to be something wrong with the configure file included with
tcl8.3.2 so I installed the tcl and tk 8.4.0 sources:
~/cvs/tclpro/linux> cd ~/cvs
~/cvs> tar zxvf ../rje/tcl8.4.0-src.tar.gz
~/cvs> tar zxvf ../rje/tk8.4.0-src.tar.gz

Now Itcl fails:
~/cvs> cd tclpro/linux
~/cvs/tclpro/linux> rm -rf *
~/cvs/tclpro/linux> ../configure
~/cvs/tclpro/linux> make
[snip]
checking for Tk configuration... found
/home/sbron/cvs/tclpro/linux/build/linux-ix86/tk_static/unix/tkConfig.sh
checking for existence of
/home/sbron/cvs/tclpro/linux/build/linux-ix86/tk_static/unix/tkConfig.sh...
loading
checking for name if Itcl stub library... configure: error: Can't find
name of Itcl stub library. How did this happen?
configure: error: /bin/sh '/home/sbron/cvs/itcl3.2/itk/configure' failed
for itk

***ERROR: command returned nonzero exit status
Working Directory:
/home/sbron/cvs/tclpro/linux/build/linux-ix86/itcl_static
Failed Command: bash ./configure
--srcdir=/home/sbron/cvs/itcl3.2
--prefix=/home/sbron/cvs/tclpro/linux/out
--exec-prefix=/home/sbron/cvs/tclpro/linux/out/linux-ix86
--with-tcl=/home/sbron/cvs/tclpro/linux/build/linux-ix86/tcl/unix
--with-tcl=../../tcl_static/unix --with-tk=../../tk_static/unix
--disable-shared --enable-gcc --enable-symbols


failed: bash ./configure --srcdir=/home/sbron/cvs/itcl3.2
--prefix=/home/sbron/cvs/tclpro/linux/out
--exec-prefix=/home/sbron/cvs/tclpro/linux/out/linux-ix86
--with-tcl=/home/sbron/cvs/tclpro/linux/build/linux-ix86/tcl/unix
--with-tcl=../../tcl_static/unix --with-tk=../../tk_static/unix
--disable-shared --enable-gcc --enable-symbols
make: *** [install] Error 1

At this point I'm stuck. What am I doing wrong?

Thanks,
Schelte.

lvi...@yahoo.com

unread,
Oct 22, 2002, 7:05:50 AM10/22/02
to

According to Schelte Bron <sb...@wanadoo.nl>:
:I can't stand it when I'm unable to do things that should be simple, so
:I had another go at building TclPro from the cvs sources.

I'm glad to see that you continue to try, despite the frustrations.
I hope that you continue to do so, and that members of the tclpro
project are able to provide you assistance.


:Then make failed for the included tclsh8.3.2:

TclPro project members - is the latest TclPro still dependant on 8.3.2 -
I would have thought that 8.3.4 would have been the minimum requirement
and perhaps even 8.4.0 .

--
Tcl - The glue of a new generation. <URL: http://wiki.tcl.tk/ >
Even if explicitly stated to the contrary, nothing in this posting
should be construed as representing my employer's opinions.
<URL: mailto:lvi...@yahoo.com > <URL: http://www.purl.org/NET/lvirden/ >

Reply all
Reply to author
Forward
0 new messages