The introduction

Stack structure is very simple, we can simulate a stack structure through an array, but just the stack structure is not the front end, this section from the stack structure began to extend to the browser JavaScript operation mechanism, as well as the storage mechanism used in the stack structure and related data structure, this article thoroughly understand all the front end of the stack knowledge.

When we talk about stacks later, we won’t be limited to LIFos, but a deep stack.

This is a prerequisite for advanced front end applications, and it’s also important to know if you want to build high-performance front end applications. It’s also a common interview spot.

Understanding the stack is crucial to our understanding of the JavaScript language. This article mainly introduces the stack from the following aspects:

  • First, introduce the stack and code implementation
  • Introduce JavaScript mechanism and the application of stack in it
  • How to use the call stack in our development
  • JS memory mechanism: stack (base type, reference type address) and heap (reference type data)
  • Finally, a summary and byte & Leetcode brush problem, to achieve the minimum stack

This section thoroughly stack principle, after a few days will be a daily question, brush through the stack topic, enter the body 👍 below

A stack,

A stack is an ordered collection that follows the LIFO/Last In First Out principle. Its structure is similar to the following:

Stack operations include: push(e) (into the stack), pop() (out of the stack), isEmpty() (to determine whether the stack isEmpty), size() (the size of the stack), and clear() to clear the stack.

Two, code implementation

function Stack() {
  let items = []
  this.push = function(e) { 
    items.push(e) 
  }
  this.pop = function() { 
    return items.pop() 
  }
  this.isEmpty = function() { 
    return items.length === 0 
  }
  this.size = function() { 
    return items.length 
  }
  this.clear = function() { 
    items = [] 
  }
}
Copy the code

Search: search from the stack head, time complexity of O(n)

Insert or Delete: The time complexity between the stack and the stack is O(1)

Third, the JS operating mechanism in the browser

We know that JavaScript is single-threaded, which means that the thread responsible for interpreting and executing JavaScript code in the JavaScript engine is unique and can only perform one task at a time.

Why single-threaded? This is because JavaScript can modify the STRUCTURE of the DOM, and if the JavaScript engine thread is not single-threaded, then multiple pieces of JavaScript can be executed simultaneously, and if these pieces of JavaScript all modify the DOM, then DOM conflicts will occur.

To avoid DOM rendering conflicts, you can use single threading or deadlocks. JavaScript uses a single threaded scheme.

But there is a problem with single threading: if there is a task in the task queue that takes a long time, and the tasks that follow that task stay in the queue, the page will get stuck and the user experience will be severely affected.

To solve this problem, JavaScript divides tasks into two modes of execution: synchronous and asynchronous.

synchronous

// Synchronize tasks
let a = 1
console.log(a) / / 1
Copy the code

asynchronous

// Asynchronous task
setTimeout((a)= > {
    console.log('Time up')},1000)
Copy the code

Synchronization tasks are executed on the main thread (in this case, the JavaScript engine thread), forming a call stack called ** execution stack **;

In addition to the main thread, there is a task queue (also called message queue) that manages the event callbacks for asynchronous tasks. After the tasks in the call stack are finished, the system checks the task queue to see if any asynchronous tasks are ready to be executed.

Note: The task queue holds event callbacks for asynchronous tasks

For example:

setTimeout((a)= > {
    console.log('Time up')},1000)
Copy the code

When this code is executed, it is not printed immediately, but only after the expiration of the timer (1s). The setTimeout itself is executed synchronously, with its callback function placed in the task queue.

Let’s focus on the call stack on the main thread.

Iv. Call stack

We will introduce the call stack from the following two aspects:

  • What does the call stack do
  • How do you leverage the call stack in development

1. Responsibilities of the call stack

As we know, there are many functions in JavaScript, and it is often the case that one function calls another function. The call stack is a stack structure used to manage the relationship between function calls.

So how does it manage function call relationships? Here’s an example:

var a = 1
function add(a) {
  var b = 2
  let c = 3
  return a + b + c
}

// Call the function
add(a)
Copy the code

This code simply creates an add function and then calls it.

Let’s take a step by step look at the process of executing a function call.

Before executing this code, the JavaScript engine creates a global execution context that contains all declared functions and variables:

As you can see from the figure, the global variable A and the function add in the code are stored in the variable environment.

When the execution context is ready, the global code is executed by first performing an assignment of a = 1,

After the assignment, the value of a changes from undefined to 1, and then the add function is executed. JavaScript determines that this is a function call, and then does the following:

  • First, pull out the add function code from the global execution context
  • Next, compile this code for the add function, create the execution context and executable code for the function, and push the execution context onto the stack

  • The code then executes, returns the result, and the execution context for add pops off the top of the stack, leaving only the global context on the call stack.

At this point, the entire function call execution is complete.

So, the call stack is a data structure that JavaScript uses to manage the execution context of a function. It records where a function is currently executing and which function is being executed. If we execute a function, the execution context for the function is created and put on the top of the stack. If we return from a function, we pop its execution context off the top of the stack. It can also be said that the call stack is the stack used to manage this execution context, or execution context stack (execution stack).

2. The advantages of a developer who understands the call stack

Stack overflow

When executing JavaScript code, we sometimes have a stack overflow:

The figure above is a typical stack overflow, so why does this error occur?

We know that the call stack is a data structure used to manage the execution context. It has a size. When too much context is pushed into the stack, it will overflow the stack.

function add() {
  return 1 + add()
}

add()
Copy the code

Add function recursion, constantly push the stack, the capacity of the call stack is limited, it will overflow, so, in our daily development, we must pay attention to the emergence of such code.

Get the call stack information in the browser

Two ways, one is breakpoint debugging, this is very simple, we use in daily development.

One is the console. The trace ()

function sum(){
  return add()
}
function add() {
  console.trace()
  return 1
}

// Call the function
sum()
Copy the code

Five, JS memory mechanism: stack (basic type, introduction type address) and heap (reference type data)

In the day-to-day life of JavaScript development, front end people rarely have the opportunity to learn about memory, but if you want to become a front end expert and build high-performance front-end applications, you need to know about this area, and it’s a common interview spot.

There are three main types of memory Spaces in JavaScript:

  • Code space: Mainly used to store executable code
  • Stack space: The storage space of the call stack is the stack space.
  • Heap space

Code space is mainly used to store executable code. The stack space and the heap space are mainly used to store data. Next we will focus on stack space and heap space.

There are eight variable types in JavaScript, which can be divided into two types: basic types and reference types

Basic types:

  • undefined
  • null
  • boolean
  • number
  • string
  • bigint
  • symbol

Reference type:

  • object

Base types are simple data segments stored in stack memory, while reference types are stored in heap memory.

1. The stack space

Basic types take up a fixed amount of space in memory, so their values are stored in stack space, which we access by value.

Generally, the stack space is not very large.

2. The heap space

Reference types, the value size is not fixed, but the pointer to the value size (memory address) is fixed, so put objects in the heap, the address of the object to be included in the stack, so that context switching in the call stack, just need to pointer down to the last execution context address is ok, at the same time guarantee the stack space will not be huge.

When querying variables of reference types, the memory address is read from the stack and then the value in the heap is found from the address. For this, we call it access by reference.

The heap is usually large and can hold a lot of data, but it takes time to allocate and reclaim memory.

Here’s an example to help you understand:

var a = 1
function foo() {
  var b = 2
  var c = { name: 'an'}}// Call the function
foo()
Copy the code

The way that basic (stack space) and reference (heap space) types are stored determines that basic type assignments are value assignments and reference type assignments are address assignments.

/ / value assignment
var a = 1
var b = a
a = 2
console.log(b) 
/ / 1
/ / b the same

// Address assignment
var a1 = {name: 'an'}
var b1 = a1
a1.name = 'bottle'
console.log(b1)
// {name: "bottle"}
// B1 value changed
Copy the code

3. Garbage collection

Garbage data in JavaScript is automatically collected by the garbage collector and does not need to be manually freed. So most developers don’t know much about garbage collection, but it’s part of the front end of the progression for seniors!

Reclaim stack space

When JavaScript executes code, there is an ESP pointer on the main thread to point to the context in the call stack that is currently executing.

After foo is executed, ESP points down to the global execution context, at which point foo needs to be destroyed.

How to destroy nan?

When the ESP pointer points to the global execution context, the foo execution context is invalid. When a new execution context comes in, the memory space can be directly overwritten.

That is, the JavaScript engine destroys the execution context in the stack space by moving the ESP pointer down.

Reclaim heap space

In V8, the heap is divided into two areas: Cenozoic and old:

  • New Generation: Stores small objects with a short lifetime. The storage capacity ranges from 1 to 8 MB
  • Old generation: Used to store long-lived objects or large objects

V8 uses different recyclers for these two:

  • The new generation uses a secondary garbage collector
  • Older generations use the main garbage collector

In fact, no matter what kind of garbage collector, the same process is used (three steps) :

  • Marking: Marking live (in use) and inactive (recyclable) objects in the heap space
  • Garbage cleanup: Reclaim memory space occupied by inactive objects
  • Memory defragmentation: During frequent garbage collection, there may be a large number of discontinuous memory fragments in the memory. When an object that needs to occupy a large continuous memory space needs to be allocated, there may be insufficient memory. Therefore, it is necessary to defragment the memory.

The secondary garbage collector and the primary garbage collector both use the same process, but the collection strategy and algorithm are different.

Secondary garbage collector

It uses Scavenge algorithm and object promotion strategy to collect garbage

The so-called Scavenge algorithm divides the Cenozoic space into two regions, one is the object region, the other is the free region, as shown in the following figure:

The newly added objects are added to the object area. When the object area is full, garbage collection is performed once. The execution process is as follows:

  • Mark: First mark the objects in the region (live objects, inactive objects)
  • Garbage cleaning: then garbage cleaning: the active objects in the object area are copied to the free area and arranged in an orderly manner. When the replication is complete, the object area and the free area are flipped, and the free area is promoted to the object area, and the object area is the free area

After the rolloff, the object area is defragmented. there is no need for step 3.

However, the new generation area is very small, usually 1 ~ 8M in capacity, so it is easy to fill up, so the JavaScript engine uses the object promotion strategy to handle this, that is, as long as the object is still alive after two garbage collection, it will be promoted to the old generation area.

Main garbage collector

In the region of the old generation, in addition to the long-lived objects promoted from the new generation, large objects will be directly allocated to the old generation when they encounter large objects.

Be insane. Therefore, the main garbage collector mainly stores long-lived or space-occupying objects. It is inappropriate to use the Scavenge algorithm at this time. In V8, the main garbage collector mainly adopts the mark-clearance method for garbage collection.

The main process is as follows:

  • Marking: The call stack is traversed to see if the objects in the old region heap are referenced. The referenced objects are marked as active objects, and the unreferenced objects (to be cleaned up) are marked as garbage data.
  • Garbage cleanup: Clean up all junk data
  • Memory collation: a mark-collation strategy that aggregates live objects together

Incremental tag

V8 will automatically perform garbage collection, but since JavaScript is also running on the main thread, once garbage collection is performed, JavaScript will be interrupted, which may cause more or less page delays and affect the user experience, so V8 has decided to use the incremental markup algorithm to collect:

That is, break garbage collection down into small tasks, interspersed in JavaScript.

Six, summarized

This section starts with the stack structure, an ordered collection that satisfies the last in, first out (LIFO) principle, and then implements a stack through an array.

Then it introduces the asynchronous execution mechanism of JavaScript in the browser environment, that is, the event loop mechanism. The main thread of JavaScript repeats cyclic reading tasks from the task queue (asynchronous event callback) and puts them into the call stack for execution. Call stack, also known as execution context stack (execution stack), is a stack structure used to manage the execution context of a function.

Storage mechanism is divided into JavaScript code space, stack space and heap space, code space to hold executable code, stack space to hold basic data types and reference types address, heap space used to store a reference type data, when completing an execution context in the call stack, the need for recycling the context and the related data space, The data stored in the stack space is collected through the ESP pointer, and the data stored in the heap space is collected through the secondary garbage collector (new generation) and the main garbage collector (old generation).

Chat ran far 🤦♀️, but are the front step will be advanced, then we began to brush the stack topic!! Daily brush, advanced front end and algorithm ⛽️⛽️⛽.

Byte & LeetCode155: minimum stack (including getMin function stack)

Design a stack that supports push, pop, and top operations and can retrieve the smallest element in constant time.

  • push(x)— Push element x onto the stack.
  • pop()Delete the top element of the stack.
  • top()Get the top element on the stack.
  • getMin()Retrieve the smallest element in the stack.

Example:

MinStack minStack = new MinStack();
minStack.push(2 -);
minStack.push(0);
minStack.push(- 3); minStack.getMin(); - > to return- 3.minStack.pop(); minStack.top(); - > to return0.minStack.getMin(); - > to return- 2.
Copy the code

You are welcome to submit your answer to byte & LeetCode155: minimum stack (which includes the getMin function) for more people to see, and Bottler will post his answer tomorrow.

Eight, past wonderful series

  • Video interview uHF online programming questions. This is enough for most companies
  • 10 questions and 10 answers, a quick introduction to front-end algorithms
  • Front-end advanced algorithm 4: the list is so simple (+ Leetcode brush problem)
  • Front-end advanced algorithm 3: learning LRU algorithm from browser cache elimination strategy and Vue keep-Alive
  • Summary of the first week of the advanced algorithm camp
  • Front-end advanced algorithm 2: From Chrome V8 source code to see JavaScript array
  • Front-end advanced algorithm 1: How to analyze and count the efficiency and resource consumption of the algorithm?

Resources: How Browsers Work and Practice (Geek Time)

Nine, know more front-end friends, advance front-end development together

The first phase of the front-end algorithm training camp is free 🎉🎉🎉, free yo!

Here, you can advance the front-end algorithm with like-minded front-end friends (1000+), from 0 to 1 to build a complete data structure and algorithm system.

Here, you can learn a dafang algorithm (Ali, Tencent, Baidu, byte, etc.) or Leetcode every day, and you will answer it the next day!

Scan the code to join the group. If the group number has reached the upper limit, scan the bottom QR code and reply “algorithm” to automatically join the group

⬆️ Scan the code to follow the public account “Front-end Bottle Gentleman”, reply to “algorithm” and the account will be automatically added to 👍👍👍