Stack vs Event Queue

[Crystarx]

Can someone help me understand the exact difference between the two.?.

From what I understand so far the event queue is where functions are loaded to be executed but what exactly is the stack, I know that if you run out of memory then you get a stack heap error which I am guessing is because there are too many events and functions "stacked" up inside of the script?.

[Qie Niangao]

When a program runs, it uses memory to call functions, both the ones internal to the script and in libraries. Part of the function-calling process is to store the values the function is going to use ("arguments") somewhere the function can find them, and it puts them on a "stack"... and then if that function calls another function, it stacks more values on top, etc. If the stack uses too much memory, bumping into non-stack program memory (the "heap") the program halts.

The event queue is just a (mostly) chronological sequence of all the occurrences (such as touches, collisions, messaging, sensors, timer expiry, etc.) that trigger script processing. There are a fixed number of slots where these are stored. Read more here, including:

Quote

Events do not interrupt each other, but instead are queued FIFO, though the state_entry event can jump the queue. If more that 64 events are waiting, new events are discarded until free slots become available. If the script is paused, such as when an object is taken to inventory, pending events are preserved and handled the next time the object is rezzed. On state change the event queue is cleared and any open listens are removed automatically.

[ETA: Just in case the "stack" and "queue" abstract data structures aren't familiar, that distinction is simple: Stacks are "Last In First Out" or "LIFO", so stacked data is processed in the opposite order of how it got pushed on the stack; queues are "First In First Out" or "FIFO" so the data is processed in the same order it was received.]

Edited January 26, 2020 by Qie Niangao

[Crystarx]

10 minutes ago, Qie Niangao said:

 

That is interesting. Thank you. How does that work in the case of a loop. Lets say we are running a while loop of i < = 1000 to simply increase a variable by 1. Is each loop of the loop added to the event queue or is it run as a single entity if you get me?

[Qie Niangao]

Yeah, I kinda left out the way the stack is used internal to a function or event handler, and that's down in the implementation of the virtual machine's instruction set... but yeah, it pushes values on the stack and pops them off again all the time. The event queue, however, is more about the control of processing from outside the program. Internal program control structures such as loops don't use the event queue. Scripts however certainly do generate events for internal consumption, e.g., llSetTimerEvent() to start an interval timer that enqueues the timer() event to trigger subsequent processing.

Edited January 26, 2020 by Qie Niangao

[Crystarx]

So as an example

list j=[];

while(i<100){ //This is ran internally

      j+=; //This is adding to the stack

    llOwnerSay((string)llGetListLength(j)); //This is adding to the queue

Have I got this right? @Qie Niangao

[Qie Niangao]

As to the stack, we can know that the function calls, llOwnerSay() and llGetListLength() at least push their arguments onto the stack, and no doubt the other statements caused some (very) local stack operations too. I've never worried about those local, instruction-level operations; they'll differ between LSO* and Mono anyway.

None of those statements would add to the event queue. Scripts only indirectly add to the event queue by causing events to happen in the runtime engine. I gave the example of starting an interval timer. Another might be to llMessageLinked() to LINK_THIS with a message that is seen by the script's own link_message() event handler.

(I sense I'm not explaining this well. Maybe somebody else can do better.)

________________
*LSO is what you get when you compile using the LSL option.

[Wulfie Reanimator]

"Stack" is used for run-time memory. When you call a function like llList2String, the function itself takes a bit of memory on the stack and the final list returned by that function also goes onto the stack. If you have too much memory on the stack, the script will crash.

The "event queue" is just a waiting list for events like touch_start, listen, control, sensor, etc. When the script is processing some event and a new event is triggered, the new event goes onto the queue. This queue is handled by the region and does not take up any memory from the script itself. Up to to 64 events are kept by the region, any more than that are discarded.

So when you have an event/function with a loop, the script will just be busy processing that loop and any new events will go into the queue. The iterations don't take up any memory on the stack by themselves, so the stack doesn't change either unless you use other functions that use memory.

list j; // The variable itself is stored on the heap.
        // All of the compiled bytecode is also stored on the heap.
default
{
    state_entry()
    {
        llListen(0, "", "", ""); // The function call uses stack.

        // The memory used by llListen is freed from the stack after it returns.
    }

    // When a chat message is heard, "listen" goes into the queue.
    // If the script isn't busy, it will start processing the next event.
    // The event will use stack memory while being processed.
    listen(integer channel, string name, key id, string message)
    {
        integer i; // Stack

        while (i < 1000) // Uses no memory, but the script stays "busy."
        {                // (1000 uses heap because it's a literal.)
            j += message;   // Stack memory grows.
            ++i; // Technically uses stack, but doesn't really use memory.
        }

        if (message == "clean") // "clean" is a literal.
        {
            j = []; // Stack memory shrinks.
        }
    }
    // All of the stack-memory used by listen (everything besides j)
    // gets freed when the event ends and the script is no longer "busy."
}

You can crash the above script with a stack-heap collision if you never say "clean" near it.

Edit: I guess if we go super nitpicky, "i < 1000" uses memory because the expression returns a value (1 or 0), but I don't exactly know when it gets freed but that's extremely insignificant to any script.

Edited January 27, 2020 by Wulfie Reanimator

[Rider Linden]

Let's talk about what a stack and a queue are and then I'll discuss what they mean in the context of a running program. 

Stacks and Queues are both very similar data structures that are used extensively in software engineering. At a very basic level stacks and queues are just a list of "things".  What those things are varies from use case to use case.  You can add things on to the end("top") of one of these lists and take things off the end. In both stacks and queues things are always added to the end of list. The difference arises in how you take things off. 

In the case of a stack items are taken from the end of the list (Another name for a Stack is a "Last In, First Out" or LIFO List).  A common image would be a stack of plates... You put a plate on the top of the stack after you've washed it, then when you need a plate you take the one on the top (Trying to take the bottom plate in this example usually leads to a very loud crash 😉) 

For a queue items are added to the end of the list and removed from the front.  Queues are also called FIFO Lists for "First In, First Out".  A common example would be a line of people waiting at the grocery checkout.

The common terms for adding a thing to one of these lists is called "pushing" and taking a thing off is called "popping".

 

Now,  In the context of a running program.  When a program calls a function it needs to know where it was called from so that it can return there when the function has finished. Most programming langues, including LSL, use a stack for this purpose.  When the program encounters a function call it will push the address that should execute after the function is done onto the stack, along with all of the parameters that should be passed to the function.  It then jumps to the function and begins running it.  The first thing that function does is pop the parameters from the top of the stack.  When it is finished it will pop the address that it should return too,  push the return value (if any), and then jump to the address it was given.  When the original code gets control back after the jump it pops the return value and continues on its merry way.

LSL programs also process events.  Events are things that happen at arbitrary times within the environment that the program is running, and the program must respond to these events. We can not arbitrarily interrupt the program in real time when an event occurs so instead we push that event and any data about it (who touched the prim, what was the chat message, etc) into a queue.  Every frame the program looks at the queue to see if there are any events waiting.  If there are we pop the next event and its data and call the event handler in the program to do whatever processing is needed by the program (at this point the stack takes over.)  Since events are in a queue we know that they will always be processed in the order that they were pushed(FIFO).

You, also asked for some clarification about how these interact with for instance a while statement.  while is one of a family of instructions that are called "flow control statements"  (others common examples would be for, if/else, and goto.)  Flow control statements do not interact with the stack, they simply execute a jump to the next instruction.

 

Here are some short videos on Stacks and Queues (and watermelons!) that I found.  

 

[Rider Linden]

6 hours ago, Wulfie Reanimator said:

"Stack" is used for run-time memory. When you call a function like llList2String, the function itself takes a bit of memory on the stack and the final list returned by that function also goes onto the stack. If you have too much memory on the stack, the script will crash.

The "event queue" is just a waiting list for events like touch_start, listen, control, sensor, etc. When the script is processing some event and a new event is triggered, the new event goes onto the queue. This queue is handled by the region and does not take up any memory from the script itself. Up to to 64 events are kept by the region, any more than that are discarded.

 

A minor correction.  The Heap is used for run-time memory and global variables.  So in your example

list j; // Lives in the heap

and

j += message; // Will increase heap usage. 

i, is a "local variable" and does live in the stack.

integer i; // Does live in the stack, modifying it (++i) changes the value in the stack but does not alter stack usage.

 

If however you have a local variable of say type list:

list local_list; // Lives in the stack, but its memory usage there is fixed

local_list = local_list + [ "foobar" ];  // This actually grows the Heap

The list itself lives on the stack, but the items contained in the list actually live in the heap. Once a function has set up its local variables on the stack their usage is fixed, any additional memory required needs to be allocated from the heap.

[animats]

Internals question: in Mono, are  the stack and the heap actually in the same address space? The stack and heap are limited to 64K currently, but is it technically possible to increase the stack limit without increasing the heap limit? Stack use has less impact on resources; that memory is returned when the event finishes. Heap use is permanent.

The reason I ask this is because there are a few events (notably link messages) and LSL calls (notably llGetStaticPath) which can unexpectedly return large strings or lists. Scripts can't set a limit on the size of those incoming objects. This can cause a "stack/heap collision" unexpectedly. Protecting scripts against this requires big safety margins backed up by stall timers and script resets.

 

[Rider Linden]

I would need to check, but I believe that the stack and the heap share the same memory address.  Mukashi Mukashi, in langues like C, the heap would grow from up from the bottom of available memory and the stack would grow down from top, when the two overlapped you would get a stack/heap collision. I don't think it would be easy to change stack size without also changing the heap size. 

Heap usage shouldn't be permanent.  If I have a list and I put 20 items into that list, each of those items is using some heap.  If I then clear that list the memory used on the heap should be returned to the program and be available for other uses. (If this is not happening that would be a bug.) 

As to the problem with large bits of data coming in from outside the program (HTTP results, llGetStaticPath, etc) I wonder if there would be a way to let the program access those results as they are stored outside its own memory space. I will have to thing very hard about that since it could very easily have security implications. 

[Wulfie Reanimator]

32 minutes ago, Rider Linden said:

i, is a "local variable" and does live in the stack.

integer i; // Does live in the stack, modifying it (++i) changes the value in the stack but does not alter stack usage.

Here's a fun one; what about i++?

Since post-increment requires the current value of i to be copied, incremented, and assigned to the previous address, it does require the stack unlike ++i.

Unless the compiler does the smart thing when both would work, anyway.

[Rider Linden]

I believe that:

integer i;

i++;

Will not increase stack size (the compiler is smart enough to do the right thing in this case.)

foo(++i);
bar(i++);

For both of the calls above an integer is pushed onto the stack (LSL is a pass by value language.) 

for foo i would be increased by one and that value is pushed.

for bar the value of i would be pushed and then increased by one.

[Fenix Eldritch]

Oh geeze... All this time I've been operating under a bunch of misconceptions. I thought that the heap only contained the complied (static) bytecode and the rest was handled by the stack. Clearly that's not the case - as explained by Rider.

So regarding local variables... (correct me if I misspeak) once declared, they go on to the stack with whatever value they were initialized with. For data types like integer, float, key, etc, they can be updated in place on the stack without needing anything from the heap. I presume the system maintains an internal offset to reference them in the stack directly, yes? But for types like lists (and I suppose strings?), any update to them is handled by the heap... what happens if you initialize a local list with some values an then set it to equal an empty list? Does that mean the stack will get updated in place to be an empty list in addition to releasing whatever extra heap memory it previously used?

Edited January 27, 2020 by Fenix Eldritch

[Mollymews]

@Rider Linden

i would like to know the definitive answer to the list thing as well

this is my understanding:
 

list this = [];  // creates a stack entry. Heap address pointer is ?null?

integer i = 10;  // creates a stack entry. 'i' stack entry value is 10

while (~--i)      // 'i' stack entry value is reduced by 1
{
    this += [i];  // [i] is added to heap. 'this' stack entry heap address pointer is updated
}

this = [];   // 'this' stack entry heap address pointer is set to null.  Heap memory assigned to 'this' is marked for garbage collection

what I don't know exactly is when does garbage collection kick in with a script like this:

default
{
   touch_start(integer n)
   {
      list this;

      integer i = 10;
      while (~--i)
      {
         this += [i];
      }
      this = [];
   }
}

does garbage collection take place when the event exits ?

Edited January 27, 2020 by Mollymews
typo

[Wulfie Reanimator]

~--i

I can't tell if I'm ready to vomit or propose.

  

Edit:

12 minutes ago, Love Zhaoying said:

I hate a classmate in college programming who thought "queue" was pronounced "kwee".

I think you meant "cuwewe."

Edited January 27, 2020 by Wulfie Reanimator

[Mollymews]

~--i

assuming the Linden Mono compiler does it like the standard Mono compiler then this way of coding it generates the least amount of CIL byte code

'i' is pushed onto the stack

-- deducts 1 from the value on the stack

~ does a logical NOT operation on the value on the stack

CIL byte code for each way of coding this
 

// ~i;
ldloc.s 0
not
pop

// i > -1
ldloc.s 1
ldloc.s 0
clt
pop

// i >= 0
ldloc.s 1
ldloc.s 0
cgt
ldc.i4.0
ceq
pop

 

 

[Love Zhaoying]

On 1/26/2020 at 5:17 PM, Qie Niangao said:

ETA: Just in case the "stack" and "queue" abstract data structures aren't familiar,

I hate a classmate in college programming who thought "queue" was pronounced "kwee".

[animats]

3 hours ago, Rider Linden said:

As to the problem with large bits of data coming in from outside the program (HTTP results, llGetStaticPath, etc) I wonder if there would be a way to let the program access those results as they are stored outside its own memory space. I will have to thing very hard about that since it could very easily have security implications. 

I think that link messages and llGetStaticPath are the only ones which can unexpectedly return enough data to blow the stack limit. You can set a limit on body size in llHttpRequest, inbound HTTP has a limit of 2048 bytes, and listens are limited to 1023 bytes.

Those would need settable limits to avoid breaking existing scripts. For everything else, you can keep checking how much memory is left before doing the operation. Which I do, a lot, splitting up operations when tight on memory.

One current workaround is that I have one script in my NPC system that's not too big doing the llGetStaticPath calls. It truncates the list returned, encodes it in JSON, and sends that via link message to the bigger script that needs that data. Moves are made in multiple sections, with repeated calls to llGetStaticPath from along the way. This avoids blowing up the script system when headed for distant goals. This is an adequate workaround for now, although it increases the SL script load.

My NPCs currently have 13 scripts working in coordination to get around the memory limits of LSL. It's all working well now, but it was a tough cram job, made harder by the unpredictability. I can live with the space limits but don't like the possibility that the code may blow up due to external factors.

[ItHadToComeToThis]

@Rider Linden  That is actually very interesting information. Would you consider adding that to the LSL wiki?. I would do it myself only we mere peasants are no longer allowed to edit it. 

[Love Zhaoying]

16 hours ago, Wulfie Reanimator said:

~--i

I can't tell if I'm ready to vomit or propose.

  

Edit:

I think you meant "cuwewe."

It may have been more like "kuhwee".

[Rider Linden]

11 hours ago, ItHadToComeToThis said:

@Rider Linden  That is actually very interesting information. Would you consider adding that to the LSL wiki?. I would do it myself only we mere peasants are no longer allowed to edit it. 

@ItHadToComeToThis,

You might be on to something actually. An LSL Programming blog of some sort.  I might want to start out with just some basic "Programming 101/Basics" stuff but I could get into some of the deeper aspects too.  Let me see what I can get organized. 

[ItHadToComeToThis]

6 hours ago, Rider Linden said:

@ItHadToComeToThis,

You might be on to something actually. An LSL Programming blog of some sort.  I might want to start out with just some basic "Programming 101/Basics" stuff but I could get into some of the deeper aspects too.  Let me see what I can get organized. 

Tbh it would be nice to not only have a blog but to revamp the wiki alongside it. More updated tutorials, better explanations of things, a decent tutorial for beginners in rotations and rotations in general, bit wise, lsl math. Better wiki layout, functions grouped together by category instead of just all on one page. Allow submissions through this forum for a more updated LSL wiki library with nifty functions people might want posted that could be helpful to others.

Side note : We should have a blog page on our web profiles 😅. Imagine being able to follow each other’s blog pages on our own profiles instead of external sites like wordpress

[Rolig Loon]

On 1/28/2020 at 11:29 AM, Rider Linden said:

You might be on to something actually. An LSL Programming blog of some sort.  I might want to start out with just some basic "Programming 101/Basics" stuff but I could get into some of the deeper aspects too.  Let me see what I can get organized. 

Of course, in this forum and its previous incarnations going back to at least 2007 (when I entered SL and first became aware of the forum) we have always had a sticky thread with handy advice and discussion about LSL challenges.  We have five of them at the top of the Scripting forum right now, in fact, and the moderators have been very responsive to our requests when we have asked them to sticky things of general interest.  I think a blog is a great idea, especially if it means that Rider, Kyle, and others in the Linden Lab basement would participate, but I hope we continue to keep useful tutorials and stuff in our sticky threads too.

[VenKellie]

oh god dont use while for looping, that just causes you to write more lines of code which adds to the stack size.

and as for what everyone else says, use and delete out of the memory as quickly as possible and store least amount of string characters as possible to avoid the stack heap warning.
AND FOR THE LOVE OF MEMORY! dont use // comments and minimize your code as much as possible.

do 
if (something >= nothing) {
}
instead of
// some comment
if (something >= nothing)
{
}

aFunction(string something) {
}
instead of
// some comment
aFunction(string something)
{
}

it will save on memory

Edited January 29, 2020 by VenKellie