FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister 
 ProfileProfile   Log in to check your private messagesLog in to check your private messages   Log inLog in 

Memory management, suspendVM and coroutines

 
Post new topic   Reply to topic     Forum Index -> MiniD
View previous topic :: View next topic  
Author Message
vektorboson



Joined: 14 Sep 2006
Posts: 44

PostPosted: Tue Nov 20, 2007 8:50 am    Post subject: Memory management, suspendVM and coroutines Reply with quote

I'll explain shortly what I need for my game engine (for now I'm using Squirrel):

1. the game should be able to run for hours without the scripting engine causing a garbage collection (unless some scripter codes some bull)

2. scripts could be run every single frame, but mostly operating on small data (integers, 3d-vectors, game object references), little on arrays and strings

3. I need multiple scripting contexts (or 'threads'/coroutines), having local variables each and optionally sharing 'global variables'.

4. Every script (thread/coroutine) should be able to be suspended (with a sleep-function) and optionally depending on number of executed opcodes.

---
(1) and (2) would become a problem: Let's assume my game is running at 30 FPS for 1 hour with one script creating 240 bytes of temporaries per frame.
Then I'd get 25.920.000 = 26MB after 1 hour, just for only one script. But I want to run multiple scripts and I want it to run for 2-4 hours, so the value could become much much higher.
Assuming that MiniD let's unused temporaries be collected, I'd get a GC run pretty soon (or memory allocation error). So reference counting + custom allocator would be quite nice.

(3)
I have a sleep-function that calls Squirrel's suspendVM. The VM is then put into a PriorityQueue and when the VMs wait time decreased to 0, wakeup is called on the VM.
I also have a function called asyncExec that creates a new VM with Squirrel's newthread and is put into the Queue, so the other script may continue.

What I don't want, is to use a "master script" that controls and resumes the coroutines, and calls the engine's update function. (This somehow feels awkward to me).

------
I'm not trying to persuade you to change MiniD to the way I want it, but I'd like to know whether it is possible and how hard to adjust MiniD to my requirements. I'd do it myself if you say it isn't to hard.

As for reference counting: I'd be OK with manually doing ref() and deref(), as I'd be storing only references to VMs/coroutines and closures. (I guess that doing this for the whole MiniD would be lots of work...)

From the looks I really like MiniD, but the lack of a suspendVM and the GC have prevented me using it. And I truely want to use a scripting language that is written and integrated with D (Monster seems to be inactive?).
Back to top
View user's profile Send private message
JarrettBillingsley



Joined: 20 Jun 2006
Posts: 457
Location: Pennsylvania!

PostPosted: Tue Nov 20, 2007 12:11 pm    Post subject: Reply with quote

Quote:
3. I need multiple scripting contexts (or 'threads'/coroutines), having local variables each and optionally sharing 'global variables'.


Can't say much for the other three in this list, but this is already supported in MiniD. You have an MDContext, which is analogous to an OS process -- it contains global state, and there are any number of "threads" (MDStates) which run inside of it and share their globals. Each MDState is a coroutine with its own call stack and locals stack. You could theoretically create multiple contexts, and have each one run in a separate native thread, and it'd be threadsafe (I have done next to nothing to ensure thread safety, though, not being entirely experienced with anything outside of single-threaded coding myself; there would probably be issues somewhere.).

As for refcounting: adding refcounting probably wouldn't be terribly hard, just .. tedious. Every time you assign one MDValue to another (something that happens a lot in the interpreter), you'd have to make sure to increment the ref count, but only if it's a ref type, and decrement the ref count of the previous value. There's no way to overload the copy operator in D so it can't be automated. You could replace all MDValue-MDValue assignments with something like "v1.assign(v2)" where assign was a method of MDValue that took a ref MDValue as its param; then you could do the appropriate refcounting, and as long as the method was kept short it would probably be inlined by the compiler.

Lastly, suspension. You could probably accomplish this easily by using Tango's Fibers. Hopefully it wouldn't interact badly with native coroutines (but if you didn't have a need for those, it wouldn't be a problem). The harder way would be to modify the interpreter fairly extensively to allow it to pause, save all its state, including pending call epilogues and such, and return from the main execution function. That would probably involve a lot more modification.
Back to top
View user's profile Send private message
vektorboson



Joined: 14 Sep 2006
Posts: 44

PostPosted: Tue Nov 20, 2007 12:55 pm    Post subject: Reply with quote

Hi Jarrett,

thanks for your answer;

As I understand, for my problem I should create one MDContext and for this context I can create an arbitrary number of MDState classes?
This would be my "threads", which may be executed independent of each other. And all those states would share a global variable space, but have each their own local variable space?
(And different contexts don't share global variables?)

As for VM suspension: I looked into the code, especially for the case Op.Yield in MDState.execute; it looks as if yield already could take over the role of sleep() as it returns from execute. Would this 'Pseudocode' do as I imagine?

Code:

PriorityQueue!(MDState, TimeType) queue;

while( queue.ready(time) )
{
  auto state = queue.pop();
  state.call(); // resume or start

  // here check for yield
  if( state.mState == State.Suspended )
  {
    auto duration = popFloat();
    queue.push( state, time + duration );
  }
}


What about yielding in MiniD-functions? Would the following MiniD-code return to my scripting control-loop? Or does it return to 'after Foo()' with Foo() unfinished and the script 'dead'?

Code:

function Foo()
{
  print("Foo()");
  yield( 10.0 );
  print("Foo() after 10 seconds");
}

Foo();
// after Foo()


As for Tango's Fibers; I would have to create a fiber for every MDState, if I want MiniD's threads to execute independent of each other? (This sounds like too much overhead!)

---

As for memory consumption, I'll ask a bit different; let's assume the following script:
Code:

for( i = 1 to 10 )
{
  c = a + b;
}


The loop is executed 10 times, and thus 10 temporaries for (a+b) are created.
Now, do I have 9 MDValues that have to be garbage collected?
Or just the "contents" of those 9 MDValues need to be garbage collected?

Thanks in advance!
Back to top
View user's profile Send private message
JarrettBillingsley



Joined: 20 Jun 2006
Posts: 457
Location: Pennsylvania!

PostPosted: Tue Nov 20, 2007 2:31 pm    Post subject: Reply with quote

Quote:
As I understand, for my problem I should create one MDContext and for this context I can create an arbitrary number of MDState classes?
This would be my "threads", which may be executed independent of each other. And all those states would share a global variable space, but have each their own local variable space?
(And different contexts don't share global variables?)


Correct on all counts.

Quote:
I looked into the code, especially for the case Op.Yield in MDState.execute; it looks as if yield already could take over the role of sleep() as it returns from execute. Would this 'Pseudocode' do as I imagine?


That looks about right. You would have to resume the states in the queue using another state, by calling them as if they were functions, but yes, that should work.

Quote:
What about yielding in MiniD-functions? Would the following MiniD-code return to my scripting control-loop? Or does it return to 'after Foo()' with Foo() unfinished and the script 'dead'?


You can yield at any arbitrary call depth as long as there are no native functions on the call stack, which will always yield to the thread which resumed this one. When this thread is subsequently resumed, it will continue execution exactly where it left off. That is to say, calling your script using your scheduler might result in the following output:

Code:
Foo()
In scheduler, thread requested to yield for 10.0 seconds.
Foo() after 10 seconds


Quote:
I would have to create a fiber for every MDState, if I want MiniD's threads to execute independent of each other? (This sounds like too much overhead!)


The more I think about it, you probably wouldn't have to, actually. Since you can't yield across native call boundaries anyway (that is, if your call stack looks like "script -> native -> script", where "->" means "called", you wouldn't be able to yield here.), you could just yield from scripts back into the scheduler.

In fact, have a look at the samples/thread.md example for an example of using coroutines to emulate multiple scheduled threads which block on "system calls". The Thread class in there supports a simple message queue and the ability to make a thread wait for some amount of time. The scheduler is a simple round-robin scheduler, but of course you could have a more sophisticated one.

Quote:
The loop is executed 10 times, and thus 10 temporaries for (a+b) are created.
Now, do I have 9 MDValues that have to be garbage collected?
Or just the "contents" of those 9 MDValues need to be garbage collected?


None of the above Smile No temporary is created with (a + b); the MiniD VM uses a Lua/Squirrel-like pseudoregister architecture, so that addition and assignment are turned into a single three-op instruction, like "add c, a, b".

Second, Locals are never dynamically allocated, they are simple indexes into the local stack which usually is allocated and resized a couple times, and then stays that size forever.

Lastly, 'null', bool, int, float, and char values are value types and are never allocated on the heap, unlike in Python.

Thus your code likely performs at most one heap allocation, to make the local stack big enough to hold this function activation's local stack, so there's no garbage to collect. And of course, when this script finishes and its top-level function returns, the local stack is kept the same size so that subsequent function calls in the same state can reuse that stack space. This is, in fact, the exact same way Lua and Squirrel work (MiniD is very similar to both languages in its VM implementation).
Back to top
View user's profile Send private message
vektorboson



Joined: 14 Sep 2006
Posts: 44

PostPosted: Tue Nov 20, 2007 3:01 pm    Post subject: Reply with quote

Great! Big thanks Jarrett, I'm giving MiniD a try now!
Back to top
View user's profile Send private message
JarrettBillingsley



Joined: 20 Jun 2006
Posts: 457
Location: Pennsylvania!

PostPosted: Tue Nov 20, 2007 3:04 pm    Post subject: Reply with quote

Very Happy
Back to top
View user's profile Send private message
vektorboson



Joined: 14 Sep 2006
Posts: 44

PostPosted: Wed Nov 21, 2007 6:09 am    Post subject: Reply with quote

Great, works like a charm; also my glue code between the VM and my engine has shrunk by a good amount!

There was also a problem; in the documentation for MDState.call() it says

Code:

  // 2. Push the context.  You must always have a context.
  s.push(someContext);


That was irritating, as I tried s.push( s.context ), which gave me an error...
The context is meant to be a namespace:

Code:

  // 2. Push a namespace. You, must always have a namespace
  // This could be someNamespace = s.context.globals.ns
  s.push(someNamespace);
Back to top
View user's profile Send private message
vektorboson



Joined: 14 Sep 2006
Posts: 44

PostPosted: Wed Nov 21, 2007 12:57 pm    Post subject: Reply with quote

Another question:

In MDState.reset() (at line ~4638)
Code:

if(mCoroFiber)
  mCoroFiber.reset();


shouldn't this be

Code:

if(mCoroFiber !is null)
  mCoroFiber.reset();


Since "if(mCoroFiber)" calls the class' invariant?

Could you add a reset-function, that takes a closure for this state?

Code:

public final void reset( MDClosure coroFunc )
{
  if(mState != State.Dead)
    throwRuntimeException("Can only reset a dead coroutine, not a {} coroutine", stateString());

  if(mCoroFiber)
    mCoroFiber.reset();

  mCoroFunc = coroFunc;

  mState = State.Initial;
}


(Probably there needs to be check for coroFunc.isNative(), like in the contructor?)

What I'm trying, is to reuse 'dead' MDStates, so I don't have to construct new ones every time I want to execute a script.

Could there also be a 'exit'-function/opcode that yields from the coroutine but changes the state to 'dead'?
Back to top
View user's profile Send private message
JarrettBillingsley



Joined: 20 Jun 2006
Posts: 457
Location: Pennsylvania!

PostPosted: Wed Nov 21, 2007 8:11 pm    Post subject: Reply with quote

Quote:
in the documentation for MDState.call() it says ... That was irritating, as I tried s.push( s.context ), which gave me an error...
The context is meant to be a namespace:


Ugh, you're right, that's not very clear. It's not actually required to be a namespace either. It's passed as the 'this' pointer to the function. I kind of use "the this pointer" and "the context pointer" interchangeably and I probably shouldn't do that, especially when "context" has a different meaning in the native API Smile

Quote:
Since "if(mCoroFiber)" calls the class' invariant?


Nope, it doesn't. See, this is what happens when you special-case stuff, Walter! Class invariants are called when you do "assert(mCoroFiber)". It's only in assert statements that this happens. Everywhere else, when you use a class reference as a condition, it checks if it's null. *sigh* it's dumb, I know.

Quote:
Could you add a reset-function, that takes a closure for this state?


Good idea.

Quote:
Could there also be a 'exit'-function/opcode that yields from the coroutine but changes the state to 'dead'?


Hm, I hadn't thought about that. Out of curiosity, what would you need this for?
Back to top
View user's profile Send private message
vektorboson



Joined: 14 Sep 2006
Posts: 44

PostPosted: Thu Nov 22, 2007 6:19 am    Post subject: Reply with quote

JarrettBillingsley wrote:

Nope, it doesn't. See, this is what happens when you special-case stuff, Walter! Class invariants are called when you do "assert(mCoroFiber)". It's only in assert statements that this happens.


Arrgh! You're right; I was bitten a few times by the assert-invariant, that I started to use (instance !is null) everywhere!

Quote:

Quote:
Could there also be a 'exit'-function/opcode that yields from the coroutine but changes the state to 'dead'?


Hm, I hadn't thought about that. Out of curiosity, what would you need this for?


It's for being able to stop a script everywhere, were you can yield. Just think of it like some kind of lightweight exception: If some prerequisite is not met, than exit this script, but do not throw an error (since reporting errors take 75% of my game's screen space and distract from gameplay).
It makes scripting more error-tolerant and easier to use (but probably encourages sloppy coding...).

Just a sample:
Code:

 ...
  if( ! Obj.alive() )
    exit();
  ...


Here for example it doesn't make sense to proceed with executing the script, especially in a function that returns something. You don't need to check the function for a error-return-value. I hope this makes it somehow clear.

(Think of it as C's stdlib exit-function)
Back to top
View user's profile Send private message
JarrettBillingsley



Joined: 20 Jun 2006
Posts: 457
Location: Pennsylvania!

PostPosted: Thu Nov 22, 2007 12:19 pm    Post subject: Reply with quote

Alright, I can see how that's useful. One question I have is, would you expect any 'finally' blocks to be executed when this exit occurs?
Back to top
View user's profile Send private message
vektorboson



Joined: 14 Sep 2006
Posts: 44

PostPosted: Thu Nov 22, 2007 12:37 pm    Post subject: Reply with quote

JarrettBillingsley wrote:
Alright, I can see how that's useful. One question I have is, would you expect any 'finally' blocks to be executed when this exit occurs?


As for me, I'd expect exit() to stop execution immediately => no more code execution and thus no execution of 'finally'-blocks.
If people wanted finally, they would use exceptions anyway, right?
Back to top
View user's profile Send private message
JarrettBillingsley



Joined: 20 Jun 2006
Posts: 457
Location: Pennsylvania!

PostPosted: Thu Nov 22, 2007 1:50 pm    Post subject: Reply with quote

Yes, I suppose that's true Smile
Back to top
View user's profile Send private message
vektorboson



Joined: 14 Sep 2006
Posts: 44

PostPosted: Fri Nov 23, 2007 10:54 am    Post subject: Reply with quote

Btw. What is the best way to propose features/improvements to MiniD? Do you use trac's ticket system, or is it better to post here in the forum?
Back to top
View user's profile Send private message
JarrettBillingsley



Joined: 20 Jun 2006
Posts: 457
Location: Pennsylvania!

PostPosted: Fri Nov 23, 2007 1:28 pm    Post subject: Reply with quote

Either way, but I guess the ticket system is a little more formal and organized, so use that if you can.
Back to top
View user's profile Send private message
Display posts from previous:   
Post new topic   Reply to topic     Forum Index -> MiniD All times are GMT - 6 Hours
Page 1 of 1

 
Jump to:  
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum


Powered by phpBB © 2001, 2005 phpBB Group