Does JavaScript Process Using an Elastic Racetrack Algorithm

Does javascript process using an elastic racetrack algorithm

Flash's "elastic racetrack" was inherited from the browser. Of course, in browser-land we don't call it that - we call it the event loop.

The history of javascript's event loop started out with progressive GIF and JPEG rendering on Netscape. Progressive rendering - the drawing of partially loaded content - required Netscape to implement an asynchronous download-render engine. When Brendan Eich implemented javascript this asynchronous event loop was already there. So it was a fairly simple task to add another layer to it.

The browser's event loop is therefore something like the following:

    Event loop
        ┌──────────┐
        │          │
        │          │
        │          ▼
        │        check if there's any new ───────▶ parse data
        │        data on the network                    │
        │          │                                    │
        │          ▼                                    │
        │        check if we need to execute  ◀─────────┘
        │        any javascript ──────────────────▶ execute
        │          │                               javascript
        │          ▼                                  │
        │        check if we need to ◀────────────────┘
        │        redraw the page  ──────────────▶ redraw page
        │          │                                   │
        │          │                                   │
        └────◀─────┴─────────────────◀─────────────────┘

The rest, as they say, is history. When Microsoft copied javascript they had to duplicate the event loop to remain compatible with Netscape. So form then on everyone had to do the same to remain compatible with Netscape and IE.

Note that javascript doesn't have any functionality to recurse into the event loop manually (some languages, like tcl for example, can do it) so the browser MUST wait until there is no more javascript to execute before redrawing the page. Page redraws cannot be forced to happen until the end of script.

It is for this reason that calculated values like an element's width or height sometimes return the wrong value when you try to read them immediately after creation - the browser hasn't drawn them yet. The work-around if you really need to execute code after page redraw is to use a setTimeout with a timeout value of 0 to allow the browser to run one round of the event loop.

Additional detail:

There appears to be one exceptional condition that triggers expensive reflows. Note that a reflow is the browser calculating page layout. It's usually triggered if the browser needs to draw a changed page.

When something in the page changes, a reflow calculation is queued - not immediately executed. As in the description above, the reflow will only be executed at the end of the javascript execution. But there is one case that causes the browser to execute reflow calculations immediately: if you try to read any of the calculated values such as width and height.

See this related question for more info: When does reflow happen in a DOM environment?

JavaScript Asynchronicity and Runtime

You really need to stop thinking that everything is about threads. Almost all asynchronous operations in javascript is executed on the main thread.

Note: There will be people who tell you this is wrong, that javascript uses multiple threads and point to node.js documentation about V8. I am telling you that they are wrong. Node.js do run additional threads but they are only for disk I/O (all disk I/O are executed on one disk I/O thread, not one thread per file), DNS (because DNS APIs are blocking), crypto functions (because it uses CPU rather than I/O) and zip compression (same reason as crypto). Everything else including network I/O, mouse and keyboard handling, setTimeout etc. don't run on separate threads. You can read more about this on node's own documentation about the event loop: https://nodejs.org/en/docs/guides/dont-block-the-event-loop/

Asynchronous code in javascript mostly refer to what C programmers call non-blocking I/O. Blocking I/O stops your process until data is available:

// Blocking I/O pseudocode
data = read(file);

Non-blocking I/O returns immediately and does not return the data available. Instead it begins the process of fetching data:

// Non-blocking I/O (javascript's internal asynchronous) pseudocode
beginReading(file);

while (waiting) {
   if (readyToRead(file)) {
       data = read(file);
   }
}

The advantage of non-blocking I/O compared to blocking I/O is that while the OS tells your device driver to fetch some bytes from the file and your device driver begins a PCI transaction and the PCI bus communicates with your disk controller and your disk controller begins addressing operation on the storage medium.. while all that is happening (which is a long time in CPU time).. you can execute code:

// Blocking I/O pseudocode
data = read(file); // several million instructions could have been executed
                   // but our process is blocked waiting for data

// Non-blocking I/O (javascript's internal asynchronous) pseudocode
beginReading(file);

while (waiting) {
   if (readyToRead(file)) {
       data = read(file);
   }
   else {
       executeMoreCode(); // continue processing javascript while waiting
   }
}

In C/C++ most people would hardcode (as in, actually write the executeMoreCode() above) unless they are comfortable working with function pointers (the syntax is absolutely horrible). And even then, C/C++ does not offer an easy way to redefine that function after you've compiled your program (clever people can do wonders with interfaces - consider printer drivers which can be loaded after Windows have been compiled - but it's still complicated).

Javascript has first-class functions so most javascript API allow you to pass a callback as an argument to a function call that starts the non-blocking request.

Internally this is what javascript does:

// pseudocode:
do {
    eventHandlers = executeJavascript();
    // end of execution

    events = waitForAllIO(); // this actually blocks but it is waiting
                             // for ALL I/O instead of just one

    if (events.timeout) {
        foreach (callback from eventHandlers) {
            if (callback is TIMEOUT_HANDLER) {
                callback(events.timeout);
            }
        }
    }
    else {
        foreach (event from events) {
             foreach (callback from eventHandlers) {
                 if (callback is for event) {
                     callback(event);
                 }
             }
        }
    }
} while (eventHandlers.length > 0)

This loop goes by many names. Adobe Flash (which like node.js is an ECMAScript language that is just slightly different from browser javascript) calls it the "elastic racetrack". Most people just call it the event loop.

As you can see, nothing in the above logic requires additional threads. This architecture is so successful in handling concurrency that javascript implement threads (web workers & worker threads) as passing events back to the main thread thus even with threading javascript generally avoid locking (which is why neither web workers nor worker threads have locking mechanisms built in).

The thing to remember as a javascript programmer is:

Javascript is a strictly synchronous language. All lines of code are executed sequentially in order just like C or Java or Python.
Function definitions and reference are not called when defined or passed as argument to other functions just like C or Java or Python.
Asynchronous code does not execute code in parallel it only waits for events in parallel. 100% of the speedup of programs written in something like node.js is due to being able to make 1000 parallel I/O requests and wait for all of them at the same time. The I/O requests will be executed by hardware eg. hard disk, routers or external processes eg. SQL servers, Google, not javascript. Thus javascript does not need to execute any parallel code to get advantages of parallelism.
There is nothing magical about all this. You will face the same asynchronous behavior if you writ GUI code in C++ or Java using frameworks like GTK or WxWidgets or Swing.

I've written much more detailed explanations to specific questions on this subject. If you want to know more you may find my answers to other questions of interest to you:

Is there any other way to implement a "listening" function without an infinite while loop?

Does javascript process using an elastic racetrack algorithm

node js - what happens to incoming events during callback excution

I know that callback function runs asynchronously, but why?

Performance of NodeJS with large amount of callbacks

Is nodejs representing Reactor or Proactor design pattern?

How Nodejs's internal threadpool works exactly?

The single, per-process thread pool provided by libuv creates 4 threads by default. The UV_THREADPOOL_SIZE environment variable can be used to alter the number of threads created when the node process starts, up to a maximum value of 1024 (as of libuv version 1.30.0).

When all of these threads are blocked, further requests to use them are queued. The API method to request a thread is called uv_queue_work.

This thread pool is used for any system calls that will result in blocking IO, which includes local file system operations. It can also be used to reduce the effect of CPU intensive operations, as @Andrey mentions.

Non-blocking IO, as supported by most networking operations, don't need to use the thread pool.

If the source code for the database driver you're using is available and you're able to find reference to uv_queue_work then it is probably using the thread pool.

The libuv thread pool documentation provides more technical details, if required.

Why and when to use process.nextTick?

You have your answer in your post where you share your output with us in:

rahul@rahul:~/myPractise/PlainNodeJSPractise01/Process$ node practise02.js 
Next TICK ONE, 
Next TICK TWO, 
Next TICK THREE, 
Next TICK FOUR, 
TIMEOUT AFTER-ONE
TIMEOUT AFTER-TWO
TIMEOUT AFTER-THRE

If we change your timeout interval from 500 to 0 still same result:

function fn(name){   return f;
   function f(){       var n = name;       console.log("Next TICK "+n+", ");   }}
function myTimeout(time,msg){   setTimeout(function(){       console.log("TIMEOUT "+msg);   },time);}
process.nextTick(fn("ONE"));myTimeout(0,"AFTER-ONE");// set timeout to execute in 0 seconds for allprocess.nextTick(fn("TWO"));myTimeout(0,"AFTER-TWO");process.nextTick(fn("THREE"));myTimeout(0,"AFTER-THREE");process.nextTick(fn("FOUR"));

Is there any other way to implement a listening function without an infinite while loop?

I've written the answer to this question as an aside in another answer. Normally I'd close this question as a duplicate and point to that answer however this is a very different question. The other question asked about javascript performance. In order to answer that I had to first write the answer to this question.
As such I'm going to do something that's not normally supposed to be done: I'm going to copy part of my answer to another question. So here's my answer:

Actual events that javascript and node.js waits on requires no looping at all. In fact they require 0% CPU time.

How asynchronous I/O works (in any programming language)

Hardware

If we really need to understand how node (or browser) internals work we must unfortunately first understand how computers work - from the hardware to the operating system. Yes, this is going to be a deep dive so bear with me..

It all began with the invention of interrupts..

It was a great invention, but also a Box of Pandora - Edsger Dijkstra

Yes, the quote above is from the same "Goto considered harmful" Dijkstra. From the very beginning introducing asynchronous operation to computer hardware was considered a very hard topic even for some of the legends in the industry.

Interrupts was introduced to speed up I/O operations. Rather than needing to poll some input with software in an infinite loop (taking CPU time away from useful work) the hardware will send a signal to the CPU to tell it an event has occurred. The CPU will then suspend the currently running program and execute another program to handle the interrupt - thus we call these functions interrupt handlers. And the word "handler" has stuck all the way up the stack to GUI libraries which call callback functions "event handlers".

Wikipedia actually has a fairly nice article about interrupts if you're not familiar with it and want to know more: https://en.wikipedia.org/wiki/Interrupt.

If you've been paying attention you will notice that this concept of an interrupt handler is actually a callback. You configure the CPU to call a function at some later time when an event happens. So even callbacks are not a new concept - it's way older than C.

OS

Interrupts make modern operating systems possible. Without interrupts there would be no way for the CPU to temporarily stop your program to run the OS (well, there is cooperative multitasking, but let's ignore that for now). How an OS works is that it sets up a hardware timer in the CPU to trigger an interrupt and then it tells the CPU to execute your program. It is this periodic timer interrupt that runs your OS.

Apart form the timer, the OS (or rather device drivers) sets up interrupts for I/O. When an I/O event happens the OS will take over your CPU (or one of your CPU in a multi-core system) and checks against its data structure which process it needs to execute next to handle the I/O (this is called preemptive multitasking).

Everything form keyboard and mouse to storage to network cards use interrupts to tell the system that there is data to be read. Without those interrupts, monitoring all those inputs would take a lot of CPU resources. Interrupts are so important that they are often designed into I/O standards like USB and PCI.

Processes

Now that we have a clear picture of this we can understand how node/javascript actually handle I/O and events.

For I/O, various OSes have various different APIs that provide asynchronous I/O - from overlapped I/O on Windows to poll/epoll on Linux to kqueue on BSD to the cross-platform select(). Node internally uses libuv as a high-level abstraction over these APIs.

How these APIs work are similar though the details differ. Essentially they provide a function that when called will block your thread until the OS sends an event to it. So yes, even non-blocking I/O blocks your thread. The key here is that blocking I/O will block your thread in multiple places but non-blocking I/O blocks your thread in only one place - where you wait for events.

Check out my answer to this other question for a more concrete example of how this kind of API works at the C/C++ level: I know that callback function runs asynchronously, but why?

For GUI events like button click and mouse move the OS just keep track of your mouse and keyboard interrupts then translate them into UI events. This frees your software form needing to know the positions of buttons, windows, icons etc.

What this allows you to do is design your program in an event-oriented manner. This is similar to how interrupts allow OS designers to implement multitasking. In effect, asynchronous I/O is to frameworks what interrupts are to OSes. It allows javascript to spend exactly 0% CPU time to process (wait for) I/O. This is what makes asynchronous code fast - it's not really faster but does not waste time waiting.

This answer is fairly long as is so I'll leave links to my answers to other questions that's related to this topic:

Node js architecture and performance (Note: This answer provides a bit of insight on the relationship of events and threads - tldr: the OS implements threads on top of kernel events)

Does javascript process using an elastic racetrack algorithm

how node.js server is better than thread based server

Do Timers run on their Own threads in Node.js?

No threads are used for timers in node.js.

Timers in node.js work in conjunction with the event loop and don't use a thread. Timers in node.js are stored in a sorted linked list with the next timer to fire at the start of the linked list. Each time through the event loop, it checks to see if the first timer in the linked list has reached its time. If so, it fires that timer. If not, it runs any other events that are waiting in the event loop.

On each subsequent cycle through the event loop, it keeps checking to see if its time for the next timer or not. When a new timer is added, it is inserted into the linked list in its proper sorted order. When it fires or is cancelled, it is removed from the linked list.

If the event loop has nothing to do, it may sleep for a brief period of time, but it won't sleep past the timer for the next timer.

javascript synchronous asynchronous query

The synchronous version (fs.readFileSync) will block the execution until the file is read and return the result containing the file contents:

var data = fs.readFileSync('input.txt');

This means that the next line of code will not be executed until the file is completely read and the result returned to the data variable.

The asynchronous version on the other (fs.readFile) hand will immediately return the execution to the next line of code (which is console.log("Program Ended");):

fs.readFile('input.txt', function(err, data) {
    // This callback will be executed at a later stage, when
    // the file content is retrieved from disk into the "data" variable
    console.log(data.toString());   
});

Then later, when the file contents is completely read, the passed callback will be invoked and so you see the contents of the file printed at a later stage. The second approach is recommended because you are not blocking the execution of your code during the file I/O operation. This allows you to perform more operations at the same time, while the synchronous version will freeze any other execution until it fully completes (or fails).

Does JavaScript Process Using an Elastic Racetrack Algorithm