HighDots Forums  

GOTO in Javascript

Javascript JavaScript language (comp.lang.javascript)


Discuss GOTO in Javascript in the Javascript forum.

Reply
 
Thread Tools Display Modes
  #1  
Old   
David Given
 
Posts: n/a

Default GOTO in Javascript - 07-07-2008 , 05:58 PM






I have a situation where I need to use GOTO in a Javascript program.

No, I can't use break or continue. Yes, I really do know what I'm doing.
What I've got is a huge mass of automatically generated code that
contains thousands of clauses like this:

label1:
...do something...
if (condition)
goto label3;
else
goto label9;

This situation is exactly what GOTO is the ideal tool for. Except that
Javascript doesn't have GOTO.

One alternative is to use tail calls, so that each block would turn into
a function like this:

function label1()
{
...do something...
if (condition)
return label3();
else
return label9();
}

Unfortunately, Javascript doesn't support tail calls either --- each
function call adds another entry to the stack which means I only get a
few thousand calls before everything grinds to a halt.

The only other thing I can think of is to use a switch statement like this:

while (true)
{
switch (label)
{
case 1:
...do something...
if (condition)
label = 3;
else
label = 9;
break;
}
}

However this is going to do horrible things to my performance due to
having to keep reading and writing the label variable; also, I'm very
dubious has to how well Javascript switch statements perform with very
big numbers of entries (thousands, remember).

Can anyone suggest anything else I could try?

--
┌─── dg*cowlark.com ───── http://www.cowlark.com ─────
│ "I have always wished for my computer to be as easy to use as my
│ telephone; my wish has come true because I can no longer figure out
│ how to use my telephone." --- Bjarne Stroustrup



Reply With Quote
  #2  
Old   
Joost Diepenmaat
 
Posts: n/a

Default Re: GOTO in Javascript - 07-07-2008 , 06:15 PM






David Given <dg (AT) cowlark (DOT) com> writes:

Quote:
I have a situation where I need to use GOTO in a Javascript program.
[ ... ]

Quote:
Unfortunately, Javascript doesn't support tail calls either --- each
function call adds another entry to the stack which means I only get a
few thousand calls before everything grinds to a halt.
So, you're calling recursively? If not, there are plenty fairly simple
solutions.

Quote:
The only other thing I can think of is to use a switch statement like this:

while (true)
{
switch (label)
{
case 1:
...do something...
if (condition)
label = 3;
else
label = 9;
break;
}
}
Actually, this doesn't look too bad at all.

Quote:
However this is going to do horrible things to my performance due to
having to keep reading and writing the label variable; also, I'm very
dubious has to how well Javascript switch statements perform with very
big numbers of entries (thousands, remember).
You're only writing the label variable once per iteration, and
probably not reading it much more than once either. I haven't tried
it, but I would be completely astonished if a simple variable
assignment + read is going to make any appreciable slowdown.

Due to the way switch/case is defined in JS (it's defined in terms of
!==), I would guess it would perform fairly well regardless of the
number of cases. AFAICS it would be comparable to:

var label;
var myswitch = {
something: function() {
// stuff;
label = "somethingelse";
},
somethingelse: function() {
// stuff;
label = "something";
}
};
while (true) {
myswitch[label]();
}

Which can be pretty well optimized in theory at least (you can cache
the hash code for strings, and numbers can provide their own).

Quote:
Can anyone suggest anything else I could try?
I suggest you run a few benchmarks first and profile some stuff before
you discount your current strategy. Also: firebug has a fairly useful
profiler, so check that out too; maybe the performance issues you're
seeing aren't really due to the switch statement.

--
Joost Diepenmaat | blog: http://joost.zeekat.nl/ | work: http://zeekat.nl/


Reply With Quote
  #3  
Old   
Thomas 'PointedEars' Lahn
 
Posts: n/a

Default Re: GOTO in Javascript - 07-07-2008 , 06:33 PM



David Given wrote:
Quote:
I have a situation where I need to use GOTO in a Javascript program.

No, I can't use break or continue. Yes, I really do know what I'm doing.
^^^^^^^^^^^^^^^^
There is a "not" missing.

Quote:
What I've got is a huge mass of automatically generated code that
^^^^^^^^^^^^^^^^^^^^^^^^^^^^
contains thousands of clauses like this:

label1:
...do something...
if (condition)
goto label3;
else
goto label9;
See?

Quote:
This situation is exactly what GOTO is the ideal tool for. Except that
Javascript doesn't have GOTO.
BASIC's GOTO nonsense stopped being implemented in higher-level programming
language which provide better ways to implement program logic. You are
well-advised to learn them.


PointedEars
--
Prototype.js was written by people who don't know javascript for people
who don't know javascript. People who don't know javascript are not
the best source of advice on designing systems that use javascript.
-- Richard Cornford, cljs, <f806at$ail$1$8300dec7 (AT) news (DOT) demon.co.uk>


Reply With Quote
  #4  
Old   
David Given
 
Posts: n/a

Default Re: GOTO in Javascript - 07-07-2008 , 06:52 PM



Joost Diepenmaat wrote:
[...]
Quote:
You're only writing the label variable once per iteration, and
probably not reading it much more than once either. I haven't tried
it, but I would be completely astonished if a simple variable
assignment + read is going to make any appreciable slowdown.

Due to the way switch/case is defined in JS (it's defined in terms of
!==), I would guess it would perform fairly well regardless of the
number of cases.
Do Javascript switches on simple integers turn into jump tables? I'd
really rather not have to to do a dictionary lookup on each state
change. In particular, given that most Javascript interpreters implement
variables as entries in a scope-specific dictionary, this means we're
theoretically getting *three* dictionary lookups per state change. I
realise that modern interpreters will optimise at least some of this,
but given the operation I'm trying to do is so utterly basic I still
resent having to waste cycles.

What I've got, you see, is a huge collection of states generated with
code; control flow transfers from state to state arbitrarily and
extremely frequently. Wasted cycles on state changes will directly
impact performance in a very big way. Despite the goto-is-evil nonsense
that you hear so much of (mostly from people who don't know what they're
talking about), it really is the best tool for the job here...

[...]
Quote:
I suggest you run a few benchmarks first and profile some stuff before
you discount your current strategy. Also: firebug has a fairly useful
profiler, so check that out too; maybe the performance issues you're
seeing aren't really due to the switch statement.
I'll admit that I haven't actually tried running code yet --- this is
still speculative before I start work on the code generator (which is
currently designed to emit code for a language that actually does have a
GOTO).

--
┌─── dg*cowlark.com ───── http://www.cowlark.com ─────
│ "I have always wished for my computer to be as easy to use as my
│ telephone; my wish has come true because I can no longer figure out
│ how to use my telephone." --- Bjarne Stroustrup


Reply With Quote
  #5  
Old   
Thomas 'PointedEars' Lahn
 
Posts: n/a

Default Re: GOTO in Javascript - 07-07-2008 , 07:05 PM



David Given wrote:
Quote:
Joost Diepenmaat wrote:
[...]
You're only writing the label variable once per iteration, and
probably not reading it much more than once either. I haven't tried
it, but I would be completely astonished if a simple variable
assignment + read is going to make any appreciable slowdown.

Due to the way switch/case is defined in JS (it's defined in terms of
!==), I would guess it would perform fairly well regardless of the
number of cases.

Do Javascript switches on simple integers turn into jump tables?
I beg your pardon?

Quote:
I'd really rather not have to to do a dictionary lookup on each state
change. In particular, given that most Javascript interpreters implement
variables as entries in a scope-specific dictionary, this means we're
theoretically getting *three* dictionary lookups per state change.
No, it does not. Expressions are evaluated first.

Quote:
I realise that modern interpreters will optimise at least some of this,
but given the operation I'm trying to do is so utterly basic I still
resent having to waste cycles.
ISTM you don't know what you are talking about. To begin with, you are
repeating the usual half-wit nonsense about a single programming language
where there are in fact several different implementations of ECMAScript,
of which only one you could really know all this about.

Quote:
What I've got, you see, is a huge collection of states generated with
code; control flow transfers from state to state arbitrarily and
extremely frequently. Wasted cycles on state changes will directly
impact performance in a very big way. Despite the goto-is-evil nonsense
that you hear so much of (mostly from people who don't know what they're
talking about), it really is the best tool for the job here...
Yeah, well, see above.


PointedEars
--
Anyone who slaps a 'this page is best viewed with Browser X' label on
a Web page appears to be yearning for the bad old days, before the Web,
when you had very little chance of reading a document written on another
computer, another word processor, or another network. -- Tim Berners-Lee


Reply With Quote
  #6  
Old   
Joost Diepenmaat
 
Posts: n/a

Default Re: GOTO in Javascript - 07-07-2008 , 07:16 PM



David Given <dg (AT) cowlark (DOT) com> writes:

Quote:
Do Javascript switches on simple integers turn into jump tables? I'd
really rather not have to to do a dictionary lookup on each state
change.
The difference between a jump table and a dictionary lookup isn't (or
shouldn't be) all that large, especially given that everything else in
JS is pretty slow anyway.

Quote:
In particular, given that most Javascript interpreters implement
variables as entries in a scope-specific dictionary, this means we're
theoretically getting *three* dictionary lookups per state change.
Not if the state variable is in the top-most scope. Which it will be
in this case. Scopes chains are (probably) simple stacks.

All this depends on the implementation of course.

Quote:
I realise that modern interpreters will optimise at least some of
this, but given the operation I'm trying to do is so utterly basic I
still resent having to waste cycles.
How much it matters is completely dependent on how much work you're
doing in between state changes. If the work being done is trivial,
then you may have to rethink your strategy.

Quote:
What I've got, you see, is a huge collection of states generated with
code; control flow transfers from state to state arbitrarily and
extremely frequently. Wasted cycles on state changes will directly
impact performance in a very big way. Despite the goto-is-evil nonsense
that you hear so much of (mostly from people who don't know what they're
talking about), it really is the best tool for the job here...
But maybe javascript isn't. :-) Or maybe try to reduce the number of
state changes, IOW *increase* the number of states - while you're
generating code anyway.

Quote:
[...]
I suggest you run a few benchmarks first and profile some stuff before
you discount your current strategy. Also: firebug has a fairly useful
profiler, so check that out too; maybe the performance issues you're
seeing aren't really due to the switch statement.

I'll admit that I haven't actually tried running code yet --- this is
still speculative before I start work on the code generator (which is
currently designed to emit code for a language that actually does have a
GOTO).
Well, since you're automatically generating code, it shouldn't be too
hard to test a few different constructs at least.

--
Joost Diepenmaat | blog: http://joost.zeekat.nl/ | work: http://zeekat.nl/


Reply With Quote
  #7  
Old   
David Given
 
Posts: n/a

Default Re: GOTO in Javascript - 07-07-2008 , 07:28 PM



Joost Diepenmaat wrote:
[...]
Quote:
In particular, given that most Javascript interpreters implement
variables as entries in a scope-specific dictionary, this means we're
theoretically getting *three* dictionary lookups per state change.

Not if the state variable is in the top-most scope. Which it will be
in this case. Scopes chains are (probably) simple stacks.
Ah, good, that'll save a fair bit of time. (The entire state machine
will live in a single large function --- although I will have multiple
state machines in different functions, they're all independent).

Quote:
All this depends on the implementation of course.
Indeed.

[...]
Quote:
How much it matters is completely dependent on how much work you're
doing in between state changes. If the work being done is trivial,
then you may have to rethink your strategy.
Unfortunately the work *is* like to be trivial. Alas, what work is done
and what states that are being emitted depend very much on the input
material to the code generator, which I don't have any control over.

[...]
Quote:
Well, since you're automatically generating code, it shouldn't be too
hard to test a few different constructs at least.
Indeed. I'll give the switch method a try and see how that works out. As
you say, Javascript is fundamentally slow anyway...

--
┌─── dg*cowlark.com ───── http://www.cowlark.com ─────
│ "I have always wished for my computer to be as easy to use as my
│ telephone; my wish has come true because I can no longer figure out
│ how to use my telephone." --- Bjarne Stroustrup


Reply With Quote
  #8  
Old   
Thomas 'PointedEars' Lahn
 
Posts: n/a

Default Re: GOTO in Javascript - 07-07-2008 , 07:30 PM



Thomas 'PointedEars' Lahn wrote:
Quote:
David Given wrote:
I realise that modern interpreters will optimise at least some of this,
but given the operation I'm trying to do is so utterly basic I still
resent having to waste cycles.

ISTM you don't know what you are talking about. To begin with, you are
repeating the usual half-wit nonsense about a single programming language
where there are in fact several different implementations of ECMAScript,
of which only one you could really know all this about.
Rather three, KJS has always been and Apple JavaScriptCore went open source,
too. (Did I forget another one?)


PointedEars
--
realism: HTML 4.01 Strict
evangelism: XHTML 1.0 Strict
madness: XHTML 1.1 as application/xhtml+xml
-- Bjoern Hoehrmann


Reply With Quote
  #9  
Old   
Tom de Neef
 
Posts: n/a

Default Re: GOTO in Javascript - 07-08-2008 , 03:41 AM



"David Given" <dg (AT) cowlark (DOT) com> schreef in bericht
news:48729189$0$78075$5a6aecb4 (AT) news (DOT) aaisp.net.uk...
Quote:
I have a situation where I need to use GOTO in a Javascript program.

No, I can't use break or continue. Yes, I really do know what I'm doing.
What I've got is a huge mass of automatically generated code that
contains thousands of clauses like this:

label1:
...do something...
if (condition)
goto label3;
else
goto label9;

Could you implement these code parts as functions and assign them to array
elements?
eg:

var codeparts = []
codeparts[1] = function ()
{ ...do something...
if (condition) return 3 else return 9
}

codeparts[2] = function ()
{ ...do something...
if (condition) return 7 else return 11
}

etc..

var state = 1
while (state) { state = codeparts[state] }

Tom




Reply With Quote
  #10  
Old   
RoLo
 
Posts: n/a

Default Re: GOTO in Javascript - 07-08-2008 , 09:19 AM






On Jul 7, 5:58 pm, David Given <d... (AT) cowlark (DOT) com> wrote:
Quote:
I have a situation where I need to use GOTO in a Javascript program.

No, I can't use break or continue. Yes, I really do know what I'm doing.
What I've got is a huge mass of automatically generated code that
contains thousands of clauses like this:

label1:
...do something...
if (condition)
goto label3;
else
goto label9;

This situation is exactly what GOTO is the ideal tool for. Except that
Javascript doesn't have GOTO.

One alternative is to use tail calls, so that each block would turn into
a function like this:

function label1()
{
...do something...
if (condition)
return label3();
else
return label9();

}

Unfortunately, Javascript doesn't support tail calls either --- each
function call adds another entry to the stack which means I only get a
few thousand calls before everything grinds to a halt.

The only other thing I can think of is to use a switch statement like this:

while (true)
{
switch (label)
{
case 1:
...do something...
if (condition)
label = 3;
else
label = 9;
break;
}

}

However this is going to do horrible things to my performance due to
having to keep reading and writing the label variable; also, I'm very
dubious has to how well Javascript switch statements perform with very
big numbers of entries (thousands, remember).

Can anyone suggest anything else I could try?

--
$B(#(!(!(!(B $B#d#g!w#c#o#w#l#a#r#k!%#c#o#m(B $B(!(!(!(!(!(Bhttp://www.cowlark.com$B(!(!(!(!(!(B
$B("(B "I have always wished for my computer to be as easy to use as my
$B("(B telephone; my wish has come true because I can no longer figure out
$B("(B how to use my telephone." --- Bjarne Stroustrup
templates in javascript.


Reply With Quote
Reply




Thread Tools
Display Modes

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

vB code is On
Smilies are On
[IMG] code is On
HTML code is Off



Powered by vBulletin Version 3.5.4
Copyright ©2000 - 2014, Jelsoft Enterprises Ltd.