Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Understanding Event Queue and Call stack in javascript

My curiosity for understanding the concept of "Event Queue" and "Call Stack" Started when I was solving this question:

var list = readHugeList();

var nextListItem = function() {
    var item = list.pop();

    if (item) {
        // process the list item...
        nextListItem();
    }
};

The following recursive code will cause a stack overflow if the array list is too large. How can you fix this and still retain the recursive pattern?

The solution that was mentioned was this:

var list = readHugeList();

var nextListItem = function() {
    var item = list.pop();

    if (item) {
        // process the list item...
        setTimeout( nextListItem, 0);
    }
};

Solution:

The stack overflow is eliminated because the event loop handles the recursion, not the call stack. When nextListItem runs, if item is not null, the timeout function (nextListItem) is pushed to the event queue and the function exits, thereby leaving the call stack clear. When the event queue runs its timed-out event, the next item is processed and a timer is set to again invoke nextListItem. Accordingly, the method is processed from start to finish without a direct recursive call, so the call stack remains clear, regardless of the number of iterations.

Now my question:

Q1) What is the difference between "Event Queue" and "call stack"

Q2) I did not understand the answer. Can someone explain me in detail?

Q3) When I execute a function or call a variable or object in javascript. How does the flow go? What goes in call stack? (Let's say I do setTimeout.. Does it go to callstack or event queue?)

These concepts are very unclear. I googled but most of the results aren't what I was expecting to understand.

Please help!

like image 924
TechnoCorner Avatar asked Sep 12 '16 21:09

TechnoCorner


People also ask

How JavaScript works event loop stack and queue?

The Event Loop has one simple job — to monitor the Call Stack and the Callback Queue. If the Call Stack is empty, the Event Loop will take the first event from the queue and will push it to the Call Stack, which effectively runs it. Such an iteration is called a tick in the Event Loop.

What is an event loop and call stack in JavaScript?

As always, calling a function creates a new stack frame for that function's use. The processing of functions continues until the stack is once again empty. Then, the event loop will process the next message in the queue (if there is one).

What is event queue in JavaScript?

The event queue is responsible for sending new functions to the stack for processing. It follows the queue data structure to maintain the correct sequence in which all operations should be sent for execution. Whenever an async function is called, it is sent to a browser API. These are APIs built into the browser.

What is the difference between call stack and task queue JavaScript?

So in short, a job queue is a queue of things to do (usually stored persistant) and a call stack is a stack of routines. A job would have variables assigned to it, and a call stack would be the abstract implementation. So a job could "call" a method from a call stack.


2 Answers

Answer 1 & 3

There is a very big difference between event queue and call stack. In fact, they have almost nothing in common.

Call stack (simple overview):

When you execute a function everything it uses is said to go on the stack, which is the same call stack you're referring to there. Very simplified, it's temporary memory for functional execution. Or in other words

function foo() {
  console.log("-> start [foo]");
  console.log("<- end   [foo]");
}

foo();

when called it would be given a little sandbox to play with on the stack. When the function ends, the temporary memory used would be wiped and made available to other things. So, the resources used (unless given somewhere to the system) will only last as long as the function lasts.

Now, if you have nested functions

function foo() {
  console.log("-> start [foo]");
  console.log("<- end   [foo]");
}

function bar() {
  console.log("-> start [bar]");
  foo()
  console.log("<- end   [bar]");
}

bar();

Here is what happens when you call the function:

  1. bar gets executed - memory is allocated on the stack for it.
  2. bar prints "start"
  3. foo gets executed - memory is allocated on the stack for it. NB! bar is still running and its memory is also there.
  4. foo prints "start"
  5. foo prints "end"
  6. foo finishes execution and its memory is cleared from the stack.
  7. bar prints "end"
  8. bar finishes execution and its memory is cleared from the stack.

So, the execution order is bar -> foo but the resolution is in last in, first out order (LIFO) foo finishes -> bar finishes.

And this is what makes it a "stack".

The important thing to note here is that the resources used by a function will only be released when it finishes executing. And it finishes execution when all the functions inside it and those inside them finish executing. So you could have a very deep call stack like a -> b -> c -> d -> e and if any large resources are held in a you would need b to e to finish before they are released.

In recursion a function calls itself which still makes entries on the stack. So, if a keeps calling itself you end up with a call stack of a -> a -> a -> a etc.

Here is a very brief illustration

// a very naive recursive count down function
function recursiveCountDown(count) {
  //show that we started
  console.log("-> start recursiveCountDown [" + count + "]");
  
  if (count !== 0) {//exit condition
    //take one off the count and recursively call again
    recursiveCountDown(count -1);
    console.log("<- end recursiveCountDown [" + count + "]"); // show where we stopped. This will terminate this stack but only after the line above finished executing;
  } else {
    console.log("<<<- it's the final recursiveCountDown! [" + count + "]"); // show where we stopped
  }
}

console.log("--shallow call stack--")
recursiveCountDown(2);

console.log("--deep call stack--")
recursiveCountDown(10);

This is a very simplistic and very flawed recursive function but it only serves to demonstrate what happens in that case.

Event queue

JavaScript is ran in an event queue (or also "event loop") which, in simple terms, waits for "activity" (events), processes them and then waits again.

If there are multiple events, it would process them in order - first in, first out (FIFO), hence a queue. So, if we re-write the above functions:

function foo() {
  console.log("-> start [foo]");
  console.log("<- end   [foo]");
}

function bar() {
  console.log("-> start [bar]");
  console.log("<- end   [bar]");
}


function baz() {
  console.log("-> start [baz]");
  
  setTimeout(foo, 0);
  setTimeout(bar, 0);
  
  console.log("<- end   [baz]");
}

baz();

Here is how this plays out.

  1. baz is executed. Memory allocated on the stack.
  2. foo is delayed by scheduling it to run "next".
  3. bar is delayed by scheduling it to run "next".
  4. baz finishes. Stack is cleared.
  5. Event loop picks the next item on the queue - this is foo.
  6. foo gets executed. Memory allocated on the stack.
  7. foo finishes. Stack is cleared.
  8. Event loop picks the next item on the queue - this is bar.
  9. bar gets executed. Memory allocated on the stack.
  10. bar finishes. Stack is cleared.

As you can hopefully see, the stack is still in play. Any function you call will always generate a stack entry. The event queue is a separate mechanism.

With this way of doing things, you get less memory overhead, since you do not have to wait on any other function to release the allocated resources. On the other hand, you cannot rely on any function being complete.

I hope this section also answers your Q3.

Answer 2

How does deferring to the queue help?

I hope the above explanation will make it more clear but it bears making sure the explanation makes sense:

There is a set limit of how deep the stack could be. If you think about it, it should be obvious - there is only so much memory to spare for presumably temporary storage. Once the maximum call depth is reached, JavaScript will throw RangeError: Maximum call stack size exceeded error.

If you look at the recursiveCountDown example I gave above that can very easily be made to cause an error - if you call recursiveCountDown(100000) you will get the RangeError.

By putting every other execution on the queue, you avoid filling up the stack and thus you avoid the RangeError. So let's re-write the function

// still naive but a bit improved recursive count down function
function betterRecursiveCountDown(count) {
  console.log("-> start recursiveCountDown [" + count + "]");
  
  if (count !== 0) {
    //setTimeout takes more than two parameters - anything after the second one will be passed to the function when it gets executed
    setTimeout(betterRecursiveCountDown, 0, count - 1);
    console.log("<- end recursiveCountDown [" + count + "]");
  } else {
    console.log("<<<- it's the final recursiveCountDown! [" + count + "]"); // show where we stopped
  }
}

betterRecursiveCountDown(10);
like image 188
VLAZ Avatar answered Oct 08 '22 17:10

VLAZ


Main reason to use call stack is used to know where to go after end of current function. but most language have size limit to call stack so size of call stack is overflow if you call a function repeatly until function is not finished.

Most implements of setTimeout have queue for save job. and excute them when idle time.

First nextListItem is call self before itself is not finished. so call stack will be long until end of item list.

Second nextListItem is call self after finish itself and call stack is clear also. so call stack will be start at empty when nextListItem is called from setTimeout on idle time.

  1. call stack is made for function call history. and event queue is made for save setTimeout job.

  2. see upper explain.

  3. javascript just execute your statement continually. but will be save where this function is called for return to that after function is finished. call stack is used to save a history of called functions.

like image 20
pius lee Avatar answered Oct 08 '22 16:10

pius lee