[gameprogrammer] Re: Scripting engines: Upvalues and function refs

[David Olofson <david@olofson.net>]

On Thursday 08 April 2004 18.54, Bob Pendleton wrote:
> On Thu, 2004-04-08 at 06:08, David Olofson wrote:
> > On Tuesday 06 April 2004 18.24, Bob Pendleton wrote:
> > [...]
> >
> > > Yep. Having a GC makes life so much easier for both the
> > > language developer and the programmer! But, using a GC based
> > > language for a task with RT constraints is difficult.
> >
> > I'm leaning towards a hybrid refcount/GC solution eventually. It
> > seems like a properly working refcounting system tends to be
> > slower and more complicated than a proper GC, but I have this
> > feeling that there are shortcuts to be made with a language and
> > compiler designed with this stuff in mind.
>
> Yeah, that is my conclusion also. I've written systems with a GC
> and with reference counting and reference counting is harder to get
> right. I was looking at the same problem you are actually, a
> language for scripting games.
>
> A reference counting system does need a GC to find cyclic
> structures that a reference counting system leaves around. If you
> provide a rich set of data types. like queues, sets, and so on you
> can get rid of a lot of the cases where a programmer is likely to
> create cyclic structures. But, not all of them.

Meanwhile, I'm trying to keep the language pretty minimal, with just a 
few powerful datatypes... There's a conflict there that's hard to 
avoid.


> One technique I played with was using an incremental GC. In an
> interpretor you can run the GC while waiting for input. You can
> also run it "between" instructions in a VM. You can run the VM for
> N instructions and then run the incremental GC for X microseconds,
> and so on.

Incremental GC seems to be the new fashion in multimedia related (ie 
real time) scripting languages. One of the main reasons why I didn't 
just go with Lua is that it relies on GC, but doesn't (yet) have an 
incremental GC implementation.


> If you have a handle based memory allocator you can also merge free
> blocks during idle time and "between" instructions, and reduce
> memory fragmentation.
>
> > Either way, note that bounded execution time is more important
> > than speed, so most of the conclusions drawn in traditional
> > papers on this matter are more or less irrelevant. For RT work,
> > half the average speed is better than occasional extreme or
> > unbounded peaks. I can get a faster CPU if I have to, but not an
> > infinitely fast CPU.
>
> Exactly the same conclusion I came to. Better to have predictable
> behavior and lower performance than to have maximum performance and
> unpredictable behavior.
>
> I have noticed that traditional papers on memory management do not
> address the memory usage patterns in multimedia programs at all.

Maybe this is a catch 22 situation? People that are serious about RT 
generally stay away from scripting languages, and soft RT and non RT 
people just don't care enough to worry about the problem. So, there 
are no scripting solutions that really work in RT environments, and 
as a result, there are no users (ie potential contributors, if we 
think in Free/Open Source terms) of RT scripting systems.

Right, I know there actually *are* RT scripting systems in various 
more or less hidden places - but they all seem to be proprietary, 
closely tied to some synth engine or similar, or both. That means 
they're of little use to me, and I guess, of little use to most 
people that just need a basic RT scripting system.

BTW, my code is LGPL, in case it turns out useful. Code to be released 
as soon as I have anything remotely useful.


[...]
> > > You have to capture the reference into a named variable which
> > > will be different for each reference. Not much chance of
> > > confusion.
> >
> > No, not really... You just have to know what you're capturing
> > (<funcref, context> or <funcref, reference to context>), since
> > that's not obvious from the syntax.
>
> Ok, you lost me there. How would you ever have a context and not a
> reference to a context?

Uhm... I wasn't thinking straight. I actually meant "reference to 
context" vs "reference to private copy of context".


[...function call with illegal context...]
> > > Design the language so that the default value of a reference is
> > > something you can check to see if it is invalid and so that
> > > once assigned a valid value the value can not become invalid.
> >
> > Not quite sure how to do that in this case... The CCALL (call via
> > constant; ie "hardwired" call) instruction takes an operand that
> > tells the VM how many levels to back up the stack to find the
> > lexical parent function's register frame. The upvalue access
> > instructions work in a similar fashion.
>
> There are some techniques for doing that that are much easier to
> use. One is to just push pointers to outer stack frames on the
> stack before pushing the function arguments on the stack. So
> references to outer stack frames are just made indirect through the
> appropriate value on the stack.

That's actually what I'm doing... Each call frame has a fixed field 
that points to the "parent" stack frame, if any.


> You don't need to climb the stack,
> you just indirect through the appropriate frame pointer. This works
> with a linked list stack like your too.

Well, the way my implementation works, the return path forms one 
linked list, and the "upvalue scope path" forms another. (Not always 
the same, since child functions may call each other and stuff, 
requiring "shortcuts" in the upvalue path.)

As to the "stack" itself, it's basically just heap memory that's 
managed by the VM's CALL/RETURN logic. The return path is what makes 
it a linked list. The very simplistic allocation logic is what makes 
it a stack. (The latter will have to change to handle microthreads 
and similar things, that effectively turn the stack into a tree.)


[...]
> > Actually, I'm thinking about plain LUTs, to completely avoid
> > searching.
>
> To me a LUT is simply a look up table. The term doesn't imply a
> lack of searching.

Good point... I was thinking in DSP and general low level terms, where 
the term "LUT" normally means "table that is used to replace 
expensive calculations with direct indexing operations."


> > The idea is that any "typeless" field name should have a
> > globally unique index, so you can look it up by index in any
> > object that has a field by that name. Problem is that each object
> > will need an object LUT that at least spans the indices of the
> > names used, so it only works (efficiently) for small programs.
>
> Yeah, that is why local tables is a good solution. Even if you have
> to search the search is short. But, you can have local tables and
> give local variables unique indexes in the local context.

Well, local *variables* won't be a problem, as mine work just like in 
C; they're allocated on the stack and bound at compile time. Typed 
references won't be a problem either, as they'll use compile time 
binding as well.

All I need is to turn "typeless names" into something that allows 
quick run-time binding to members of objects - or just plain index by 
name (implemented using hash tables where appropriate), if that's the 
only sensible way of doing it.


> Or, if you like the global table, then you can bind local values in
> the global table. On entry to a function you have a list of indexes
> whose current value is pushed on the stack. Then you can use those
> names for you local variables. On exit you just pop the old values
> back into the global table. This is a well know technique for doing
> dynamic scoping efficiently.

Not quite sure I'm following... Calculate the local->global/parent 
mapping/binding when the function is called, so that the actual code 
will then deal with the right values?

Any keywords or references to look for? (I haven't been messing with 
compilers all that much, and I have no formal education on the 
subject, as you might have guessed.)


[...]
> > > > The problem is that this gets ugly if/when objects way down
> > > > the line have fields with names that are already in the table
> > > > - and spread all over it... Making it a hash table seems like
> > > > the obvious answer, but I'm open to suggestions. (Speed is
> > > > important, but bounded look-up time is absolutely critical.)
> > >
> > > Have a table/per object instead of a global table. When you see
> > > o.get just look up get in the table belonging to "o". If o
> > > doesn't point to a class object then it doesn't have a table
> > > and o.get is illegal.
> >
> > Yeah, but then you can't look up by index, right? (The compiler
> > can't tell what index "get" will have in any particular object's
> > list, except in the special case where the type is known at
> > compile time.)
>
> You can't have your cake and eat it too.

Oh. Too bad... ;-)


> If you have dynamic typing
> then you have to pay for dynamic typing.

Yeah... That's why I'll add static typing as well. (Optional type 
specifier when declaring variables, arguments and stuff.) I'm worried 
about performance as well as compile time error checking.

Speaking of which;

	A) No type specifier ==> default type. (Say, integer.)

	B) No type specifier ==> object becomes dynamically typed.

	C) Type specifiers are not optional. Say "dynamic" if
	   that's what you want.

What's your vote?


> If you want static typing
> you have to live with static typing. Mixing them means that
> sometimes you can use indexes and sometime you have to search. So,
> if you have LUTs sometime you can index into them (when the
> compiler knows the type) and sometimes you have to search them
> (when the compiler does not know the type).

Yes... Well, look-ups can be done in bounded time, so there's no major 
issue here. I just want to make sure I'm not missing some obvious 
shortcuts. (Though I guess most things can be fixed later anyway. The 
language isn't set in stone, and I'm going to keep the implementation 
clean and simple until the thing is stable enough for optimization.)


> > > That keeps all the tables local to their objects, no global
> > > interactions to worry about. Also, since the tables are small
> > > you can get good performance with a sequential search of the
> > > tables so that you don't have to use space for a hash table.
> > > OTOH, hash tables can be pretty small so use a hash table per
> > > class.
> >
> > Right... It's not *that* expensive, and there are no nasty
> > surprizes, really; objects with many fields have a higher worst
> > case look-up time, but it's still bounded for any given piece of
> > code.
> >
> > But O(1) is always better, of course. ;-)
>
> Not necessarily. ;-) Sometimes the flexibility that comes from
> using an O(N/2) algorithm is worth the cost. Especially when N is
> usually small.

Yeah... And N is basically defined by the script coder anyway, so it's 
no big deal. Accessing object members through dynamically typed 
variables means the number of elements may affect performance. Keep 
member counts low, or use statically typed references whenever you 
can, if performance is critical.

An optional compiler warning when generating dynamically typed code 
might be handy, just so you don't do it by accident...


> Of course, a good hash table has performance that is
> O(1) in most practical cases.

Yeah, I have some code lying around that guarantees O(1) nearly all 
the time, and O(2) or something in some very rare cases. (You may 
sometimes get two strings with the same hash code.)

However, I suspect that a plain search is faster than any hash tables 
for small tables. Any ballpark figures for that? Or perhaps rather; 
should I bother throwing in any hash table code at all, until it's 
tuning time? :-)


//David Olofson - Programmer, Composer, Open Source Advocate

.- Audiality -----------------------------------------------.
|  Free/Open Source audio engine for games and multimedia.  |
| MIDI, modular synthesis, real time effects, scripting,... |
`-----------------------------------> http://audiality.org -'
   --- http://olofson.net --- http://www.reologica.se ---