# Re: [stack] new toy benchmark

## Martin Young — 2000-09-19 12:36:47

    Sorry about the lack of attribution: the text appeared as an attachment and I

    can't quote those properly...

     > 	* fundamental data structure is now a doubly linked box chain

     Why doubly linked?  Which operations need a "previous" reference?

     >	* program = stack = continuation

     Is this a mistype?  Surely "program+stack=continuation"?  If not, could you

    explain this at greater length?

    How do you represent the program and the continuations?  Logically a Joy

    program is a strict tree, the current execution position is a node in that tree

    and the continuation is the untraversed portion of the whole.  If you are not

    recursing on the native Oberon stack, and you only have one Joy stack, where

    are you storing the continations?

    The only way I can see to do this would be to build the whole tree before

    execution and represent the program as a reference into that tree.  I don't

    think you're doing this however as you've already said you allow words to be

    redefined at runtime using a hashed dictionary.

    Please enlighten us.

    Fyi, my implementation has a second stack (the dip stack) where continuations

    (and other bits and pieces) are stored and are visable to and manipulatable by

    the program itself.  All the combinators are derived from a single "while"

    style construct which itself achives itteration by manipulating the current

    continuations.

     >	* it is now trivial to start and stop threads. a thread is a list which

    	>  remembers where it is executing.

     Yes, this has occured to me too.  What I haven't worked out yet it how to

    synchronise such threads and to allow data to be communicated between them.

     Any thoughts?

     >	* speed: one would expect toy to be slower now and it is. The

    >	  standard benchmark [ 1 [ 1 plus ] 10000000 times] now takes

    >	  almost 16 seconds -- before it was around 4.5 seconds. toy is now

    >	  about 3.5 times slower and twice as slow as official Joy.

     This is impressive.  It's a little better than 10x faster than Monkey.

    I implemented the Sieve Of Erastothanes (sp?) in Monkey last night as I believe

    it would be a more representitive benchmark but I couldn't get the thing to

    work with Joy.  Do you have any longer test programs?

    How do you implement "times" without recursion in the interpreter?

     > It is to be hoped that, this accomplished, such a bootable image would meet

    > with not only a courteous but a frankly warm reception from the estimable

    > recipients of this mailing list.

     Okay, I'll bite.

    Obviously I can't speak for the estimable recipients of this mailing list.  I

    am speaking purely for myself when I say that I'll be more impressed when I can

    look at the code.

    --

    Martin Young  working for  STMicroelectronics at     `(o)_(o)' The fat wise /

    1000 Aztec West, Almondsbury, Bristol, BS32 4SQ.      (  V  ) owl eats only >

    +44 1454 462 523    `v'      Martin.Young@...      `.___,' clean mice.  /

                       _(_)_                             -="==="=============='

## wtanksley@bigfoot.com — 2000-09-19 15:42:42

    From: Martin Young [mailto:martin.young@...]

     >>	* program = stack = continuation

    >Is this a mistype?  Surely "program+stack=continuation"?  If

    >not, could you explain this at greater length?

     A continuation is the same as a program; there's no need to bind a stack

    with it (and in fact, binding a stack makes it useless for most of the

    purposes of continuation).

    A program can be represented by a list with destructive access to one end,

    which in turn is a stack.

     >How do you represent the program and the continuations?

    >Logically a Joy

    >program is a strict tree, the current execution position is a

    >node in that tree

    >and the continuation is the untraversed portion of the whole.

     Not true -- a Joy program is a strict *list*.  Joy data can be tree

    structured (as with quotations), list structured, and graph structured; but

    manipulating a graph doesn't make your program a graph.  If you were going

    to call your Joy program a tree simply because it contains literal

    quotations, you'd also have to call it a graph because it uses names.

     >If you are not

    >recursing on the native Oberon stack, and you only have one

    >Joy stack, where are you storing the continations?

     If he actually isn't using the Oberon stack, he'd have to store the return

    addresses (which are equivalent to continuations) on the heap.

     >The only way I can see to do this would be to build the whole

    >tree before

    >execution and represent the program as a reference into that

    >tree.  I don't

    >think you're doing this however as you've already said you

    >allow words to be

    >redefined at runtime using a hashed dictionary.

     I don't understand why this should matter.  You just compile each word as

    you meet its definition, and execute words as you come across their names.

     >Fyi, my implementation has a second stack (the dip stack)

    >where continuations

    >(and other bits and pieces) are stored and are visable to and

    >manipulatable by

    >the program itself.  All the combinators are derived from a

    >single "while"

    >style construct which itself achives itteration by

    >manipulating the current continuations.

     Ah, somewhat Forthlike.  The return stack in Forth is vital.

     >>	* it is now trivial to start and stop threads. a thread

    >>       is a list which

    >>       remembers where it is executing.

    >Yes, this has occured to me too.  What I haven't worked out

    >yet it how to

    >synchronise such threads and to allow data to be communicated

    >between them. Any thoughts?

     A very good question.  Obviously the stack itself can't be used directly for

    such things; I can think of a couple of solutions, but they all start with

    the need for semaphores or task variables (that is, spaces in memory which

    can only be accessed by one task, but which can be set to 'open' for any

    access, or deeded over to a specific task).  So why beat around the bush --

    implement semaphores.

     >Martin Young  working for  STMicroelectronics at     `(o)_(o)'

     -Billy

## Louis Madon — 2000-09-19 22:45:09

    Martin Young wrote:

     > >      * speed: one would expect toy to be slower now and it is. The

    > >        standard benchmark [ 1 [ 1 plus ] 10000000 times] now takes

    > >        almost 16 seconds -- before it was around 4.5 seconds. toy is

    > now

    > >        about 3.5 times slower and twice as slow as official Joy.

    >

    > This is impressive.  It's a little better than 10x faster than Monkey.

    >

    > I implemented the Sieve Of Erastothanes (sp?) in Monkey last night as I believe

    > it would be a more representitive benchmark but I couldn't get the thing to

    > work with Joy.

     One thing I've noticed with the Joy interpreter is that it doesn't check

    for stack overflow and so sometimes a perfectly good program will core

    dump. If you're Sieve of Eratosthenes is generating alot of intermediate

    data (eg. by deep recursion) this might be the cause.  One way to check,

    is to try and increase the maximum size of the stack: in globals.h

    change MEMORYMAX to something like 2 million and recompile (its

    originally at 20000).

    --

    Louis.

## Martin Young — 2000-09-20 09:46:55

    On Sep 19,  8:42am, wtanksley@... wrote:

     > From: Martin Young [mailto:martin.young@...]

    >

    > >>	* program = stack = continuation

    > >Is this a mistype?  Surely "program+stack=continuation"?  If

    > >not, could you explain this at greater length?

    >

    > A continuation is the same as a program; there's no need to bind a stack

    > with it (and in fact, binding a stack makes it useless for most of the

    > purposes of continuation).

    > A program can be represented by a list with destructive access to one end,

    > which in turn is a stack.

     I parsed the original statement as "the program is equivilent to the stack

    which is equivilent to the continuations", i.e. not that they can be

    represented by the same data structures, but that are the same thing.

    Given deterministic execution I can see that one could derive the stack and the

    continuations from the program, but surely during execution one needs a

    separate stack?

    What would you say are most of the purposes of continuations?  For implementing

    exceptions and threads you do need to bind a stack with the continuations for

    them to be useful.

     > >How do you represent the program and the continuations?

    > >Logically a Joy

    > >program is a strict tree, the current execution position is a

    > >node in that tree

    > >and the continuation is the untraversed portion of the whole.

    >

    > Not true -- a Joy program is a strict *list*.

     If one represents a Joy program as a binary tree, each node represents a word

    where the left branch is that word's definition and the right branch is the

    rest of the current program.  The interpreter traverses the tree left branch

    first, depth first.  Because the order of traversal is fixed the nodes could

    indeed be flattened out into a list.

    Personally I prefer to think of Joy programs as trees because this preserves

    more of the program structure.

     > >If you are not

    > >recursing on the native Oberon stack, and you only have one

    > >Joy stack, where are you storing the continations?

    >

    > If he actually isn't using the Oberon stack, he'd have to store the return

    > addresses (which are equivalent to continuations) on the heap.

     Well, yes, obviously: they have to be stored somewhere and if it's not the

    stack it must be the heap.  Okay, I suppose they could be written to a file or

    something but they's pretty unlikely.

    Let me rephrase the question: how are the continuations built up?  They must be

    structured somehow.  Are they built as a linked list in the heap?  Are they

    mixed, somehow, into the Toy stack?  What I'm trying to get at here is this: at

    the end of a word's definition how does Toy get back to executing the previous

    word?

     > >The only way I can see to do this would be to build the whole

    > >tree before execution [snip]

    > I don't understand why this should matter.  You just compile each word as

    > you meet its definition, and execute words as you come across their names.

     <thinks about it>  Okay, you could do this.

    Still, I'd like Soren to tell us what he actually does.

     > A very good question.  Obviously the stack itself can't be used directly for

    > such things; I can think of a couple of solutions, but they all start with

    > the need for semaphores or task variables (that is, spaces in memory which

    > can only be accessed by one task, but which can be set to 'open' for any

    > access, or deeded over to a specific task).  So why beat around the bush --

    > implement semaphores.

     I'm not sure I like explicit semaphores.  I'd rather have have synchronisation

    implicit in the language structure, more like Occam (and to a lesser extent

    canonical monitors) than pthreads.  OTOH I haven't thought seriously about

    this.

    --

    Martin Young  working for  STMicroelectronics at     `(o)_(o)' The fat wise /

    1000 Aztec West, Almondsbury, Bristol, BS32 4SQ.      (  V  ) owl eats only >

    +44 1454 462 523    `v'      Martin.Young@...      `.___,' clean mice.  /

                       _(_)_                             -="==="=============='

## wtanksley@bigfoot.com — 2000-09-20 17:00:24

    From: Martin Young [mailto:martin.young@...]

     >On Sep 19,  8:42am, wtanksley@... wrote:

    >> From: Martin Young [mailto:martin.young@...]

    >> >>	* program = stack = continuation

    >> >Is this a mistype?  Surely "program+stack=continuation"?  If

    >> >not, could you explain this at greater length?

    >> A continuation is the same as a program; there's no need to

    >> bind a stack

    >> with it (and in fact, binding a stack makes it useless for

    >> most of the

    >> purposes of continuation).

    >> A program can be represented by a list with destructive

    >> access to one end, which in turn is a stack.

    >I parsed the original statement as "the program is equivilent

    >to the stack

    >which is equivilent to the continuations", i.e. not that they can be

    >represented by the same data structures, but that are the same thing.

     Ah!  I see the problem.  Well, I can see how his statement wouldn't make any

    sense if you interpreted it that way -- so I recommend interpreting it in a

    way which makes sense :-).  So don't try to read "program" as "THE program";

    instead, just read it as "any program".  And so on for "stack" and

    "continuation".  He's describing an implementation detail.

     >What would you say are most of the purposes of continuations?

    >For implementing

    >exceptions and threads you do need to bind a stack with the

    >continuations for them to be useful.

     No, you don't.  A continuation in a stack-based language doesn't need a

    stack.  Now, a _thread_ does need a stack, as does an exception.  But that

    just means that both a thread and an exception are *more* than a

    continuation.  That doesn't make the continuations useless -- it just means

    that they're not threads or exceptions.

     >> >How do you represent the program and the continuations?

    >> >Logically a Joy

    >> >program is a strict tree, the current execution position is a

    >> >node in that tree

    >> >and the continuation is the untraversed portion of the whole.

    >> Not true -- a Joy program is a strict *list*.

    >If one represents a Joy program as a binary tree, each node

    >represents a word

    >where the left branch is that word's definition and the right

    >branch is the

    >rest of the current program.  The interpreter traverses the

    >tree left branch

    >first, depth first.  Because the order of traversal is fixed

    >the nodes could

    >indeed be flattened out into a list.

     That's a suprising idea to me.  What advantages does it bring for you?  It

    seems to result in nothing but enormous complication.  You do realise that

    what you describe isn't a tree, but rather a graph, right?  After all, if

    you have two uses of a word you automatically form a double link (directed

    acyclic graph), and if you have any recursion or mutual recursion you form a

    cycle.

    Graphs are *hard* to deal with.  Trees are simpler.  Lists are simplest of

    all.  Why do all that work simply to shun simplicity?

     >Personally I prefer to think of Joy programs as trees because

    >this preserves more of the program structure.

     I don't understand this, because the program structure *is* a list.  Or at

    least my little mind is having a hard time seeing it as anything else.

     >> >If you are not

    >> >recursing on the native Oberon stack, and you only have one

    >> >Joy stack, where are you storing the continations?

    >> If he actually isn't using the Oberon stack, he'd have to

    >> store the return

    >> addresses (which are equivalent to continuations) on the heap.

    >Let me rephrase the question: how are the continuations built

    >up?  They must be

    >structured somehow.  Are they built as a linked list in the

    >heap?  Are they

    >mixed, somehow, into the Toy stack?  What I'm trying to get at

    >here is this: at

    >the end of a word's definition how does Toy get back to

    >executing the previous word?

     I'll let him answer -- it's his implementation.  Personally :-), I would use

    a stack, and allow words to access it freely to store "return XTs" into data

    structures of their own invention.  (XT == eXecution Token.)  The reason for

    this is that the implicit structure of the language is a stack: you return

    to your caller.  If you want to return to someone else, siply place their

    address on top of your caller's address, and return.  If you never want to

    return to your caller, drop his address off the return stack (and possibly

    continue dropping addresses, if you'd like).

    I've seen very sophisticated backtracking implemented using this, and it

    looked completely natural.

     >> A very good question.  Obviously the stack itself can't be

    >> used directly for

    >> such things; I can think of a couple of solutions, but they

    >> all start with

    >> the need for semaphores or task variables (that is, spaces

    >> in memory which

    >> can only be accessed by one task, but which can be set to

    >> 'open' for any

    >> access, or deeded over to a specific task).  So why beat

    >> around the bush -- implement semaphores.

    >I'm not sure I like explicit semaphores.  I'd rather have have

    >synchronisation

    >implicit in the language structure, more like Occam (and to a

    >lesser extent

    >canonical monitors) than pthreads.  OTOH I haven't thought

    >seriously about this.

     I've put some thought into this, and I see a couple of useful designs -- but

    in every case, you start with a sempahore.  By Forth logic, this means that

    you give your programmer semaphores, as well as a couple of libraries built

    on top of them.

    One possible way to handle synchronous execution is to use 'dynamic

    evaluation tokens': these are stack items which are actually just tokens.

    As soon as you attempt to evaluate them, your process will 'wait' until

    they're ready.  Of course, they're implemented by means of semaphores.

     >Martin Young  working for  STMicroelectronics at     `(o)_(o)'

     -Billy