The problem

The team has been doing code review for some time. Recently, I have been thinking about a question: how to evaluate a piece of code from the code level without business logic?

Both good and bad are relative. How can a piece of code that is not so good be optimized be standardized to show the difference before and after refactoring?

All of our code runs on the computer, and the core of the computer is CPU and memory. From this perspective, efficient code should take up less CPU time and less memory space.

So the question becomes, how much CPU usage and memory usage is optimized for a piece of code?

Cpu-time complexity

Time complexity

In data structures and algorithms, big O is often used to represent the time complexity of algorithms. The common time complexity is as follows :(source: algorithms, 4th edition)

Time complexity describes the time growth curve of an algorithm as the problem size increases. Therefore, these increase orders of magnitude are not an accurate performance evaluation, can be understood as an approximate value, time growth is approximately logN, NlogN curve. As shown below:

Above is the explanation of time complexity, but let’s take a look at the time complexity of code with a concrete example

A code:

(function count(arr=[1.2.3.4.5.6.7.8.9.10]){
  let num = 0
  for(let i=0; i<arr.length; i++){let item = arr[i]
    num = num + item
  }
  return num
})()
Copy the code

This is a code that sums the numbers in the array. We estimate roughly that the above code takes the same amount of time to calculate the expression on the CPU. We calculate how many avg_times the above code takes.

Starting with the second line, the expression assignment counts to 1 avg_time; Lines 3, 4, and 5 of the code run 10 times each. The third line is a special one that computs arr.length and i++ each time, so it requires (2+1+1)*10 avg_time; That’s (2+1+1)*10+1=41 AVg_times

Next, let’s optimize the above code as follows: Code two

(function count(arr=[1.2.3.4.5.6.7.8.9.10]){
  let num = 0
  let len = arr.length
  while(len--){
    num = num + arr[len]
  }
  return num
})()
Copy the code

It is not difficult to calculate that the optimized code only consumes 1+1+(1+1)*10=22 AVg_time. Compared with code 1, code 2 saves 41-22=19 AVg_time and improves code performance 19/41=46.3%!

How to write low time complexity code?

1. Use break, continue, and return flexibly

These three keywords are generally used to reduce the number of loops, achieve the goal, exit immediately. As follows:

    (function check(arr=[1.2.3],target=2){
      let len = arr.length
      while(len--){
        if(arr[len]===target){
          // The subsequent loop is not continued
          return len
        }
      }
      return - 1}) ()Copy the code

2. Space for time

A common approach is to use caching to save the results of the last calculation to avoid double calculations.

3. Better data structures and algorithms

Choose appropriate data structures and algorithms according to different situations. For example, if you need to frequently query data from a set of data by key, and if you need to choose between JSON objects and arrays, you can preferentially use JSON objects to avoid array traversal.

Memory-space complexity

In addition to evaluating a piece of code by how much time it takes to execute, you also need to look at how much space it takes. When it comes to the space footprint of your code, you must know the memory management of JS

JS memory management is divided into three parts:

  • Memory allocation. This contains the memory required to contain the code itself, which is allocated on the stack, as well as the static and dynamic data, which is allocated on the heap

  • Use allocated memory.

  • Memory reclamation.

So here I’m going to put a diagram of the JS Runtime

Static memory allocation

It refers to the allocation of memory in the stack, where data of the base data type is placed. In addition, the stack has a fixed size, exceeding the length of the stack, will report an error, so you must economize.

Burst stack

// Do a stack explosion on purpose
function foo(){
  foo()
}
foo()
/ / the result
VM201:1 Uncaught RangeError: Maximum call stack size exceeded at foo (<anonymous>:1:13) at foo (<anonymous>:2:3) at foo (<anonymous>:2:3) at foo (<anonymous>:2:3) at foo (<anonymous>:2:3) at foo (<anonymous>:2:3) at foo (<anonymous>:2:3) at foo (<anonymous>:2:3) at  foo (<anonymous>:2:3) at foo (<anonymous>:2:3)Copy the code

How did we get there? Because for all function calls, there is a stack of function calls in memory, and we keep making recursive calls without terminating conditions, eventually bursting the stack.

As shown in the figure:

Function call stack

How do you prove the existence of a function call stack? See the code below:

function second() {
    throw new Error('function call stack');
}
function first() {
    second();
}
function start() {
    first();
}
start();
// The result is as follows
VM266:2 Uncaught Error: function call stack
    at second (<anonymous>:2:11)
    at first (<anonymous>:5:5)
    at start (<anonymous>:8:5)
    at <anonymous> : nowCopy the code

The order of function calls in the stack is as follows: start, first, and second; Print second first and start last. Satisfy the data structure characteristics of stack in – out.

Memory footprint

Again, the core purpose of this is to guide us to write better code, we know that the basic data types are on the stack, and the objects are on the heap. In addition, according to chapter 3 of the Sixth edition of the JavaScript Authoritative Guide, the digits in JS are double precision types, occupying 8 bytes of 64-bit space and 2 bytes of 16-bit character space.

With this knowledge, we can estimate roughly how much memory our code takes up.

These are all theoretical knowledge, after all, can not help but doubt, is it really so? Now let’s take advantage of the stack burst principle and look at it in code

let count = 0
try{
  function foo() {
    count++
    foo()
  }
  foo()
}finally{
  console.log(count)
}
// The final print result is 15662
Copy the code

We know that a number is eight bytes long and the stack size is fixed; Change the code slightly

let count = 0
try{
  function foo() {
    let local = 58 // A number of 8 bytes
    count++
    foo()
  }
  foo()
}finally{
  console.log(count)
}
// The final print result is 13922
Copy the code

So we can calculate the total stack size using the following method

N = the size of a single element in the stack 15662 * N = 13922 * (N + 8) Total stack size equals (15662-13922) x N = 13922 x 8 1740 x N = 111376 N = 111376/1740 = 64 bytes Total Stack size = 15662 x 64 = 1002368 = 0.956 MBCopy the code

Note: different environment may have different results

Next, let’s determine if the numeric type takes up 8 bytes of space

let count = 0
try{
  function foo() {
    // Number, 8 bytes, 16 bytes here
    let local = 58
    let local2 = 85
    count++
    foo()
  }
  foo()
}finally{
  console.log(count)
}
// The final print result is 12530
Copy the code

Calculate the memory usage of Number

// Total stack memory space/number of stack elements = size of single stack element 1002368/12530 = 80 // Compare the code without any extra variables, size of single stack element is 64, add two 16s here, add up to exactly 80 80 = 64+8+8Copy the code

In Chrome, Safari, and Node environments, the value of any variable takes up 8 bytes in the stack. Strings don’t seem to work as expected, no matter how long a string is in practice it takes up 8 bytes in the stack, and I suspect that browsers by default convert strings to objects and end up taking up heap space

Dynamic memory allocation

Heap refers to the allocation of memory in the heap. All objects are placed in the heap, and only references to objects are placed in the stack.

How much memory do JavaScript Arrays take up in Chrome?

How to write code with low memory footprint?

Low memory footprint, from the perspective of static memory allocation can be considered, as little as possible use of base type variables; From the perspective of dynamic memory allocation, make code more concise, do not recklessly new an object, put fewer things in the object;

Here are some tips: 1. The ternary operator

    // Conditional assignment
    if(a===1){
      b = 'aa'
    }else{
      b = 'bb'
    }
    // can be simplified as
    b = a===1 ? 'aa' : 'bb'
Copy the code

2. Return the result directly

   if(a===1) {return true
   }else{
     return false
   }
   // can be simplified as
   return a===1
Copy the code

Can’t think of a good example in a while, the above sample at least saves the space of the code! . Comments are welcome at……

Memory recovery

My understanding is that when the function call stack is empty, the occupied memory is cleared; Only the data in heap memory needs to be collected through the garbage collection mechanism.

Common garbage collection algorithms are as follows:

  • Reference count Counts references to no object. If there are no external references, the object is cleared. One of the drawbacks of reference counting algorithms is that they cannot clean up the objects that cycle bad dependencies.

  • Mark clearance: Each collection starts with the root object. Objects that can be traversed are counted as available. Objects that cannot be traversed are counted as objects that need to be garbage collected. This algorithm can solve the problem of object cyclic dependence.

  • Integrated algorithm: In fact, garbage collection is a very complex process, garbage collector will take different garbage collection algorithms according to the situation of memory blockage, to achieve the maximum efficiency.

Here’s an article about Garbage Collection: A Tour of V8: Garbage Collection translated into Chinese.

How to avoid memory overflow?

As you can see from the garbage collection mechanism above, an overflow of memory occurs when memory cannot be collected and increases in some cases. Here are some common code that runs the risk of running out of memory.

1. Control global variables From the principle of garbage collection, we know that global variables are definitely not collected. Therefore, we should try to bind data to global variables, and should avoid continuously increasing the size of global variable data through user operations. Special attention should also be paid to unexpected global variable generation, such as:

function foo(arg) {
    a = "some text";
    this.b = "some text";
}
// Add attributes a and B to the window object
foo()
Copy the code

2. SetInterval notice memory usage Because setInterval is always active, the data on which it depends cannot be reclaimed. Especially prone to data accumulation

3. Note that the closure closure depends on the data of the main function. In order for the closure to continue to access the data, it is necessary to avoid the risk of memory overflow by reclaiming the data corresponding to the variables of the closure that depend on the main function when the main function exits.

Information:

  1. JS memory Management
  2. How JavaScript works: an overview of the engine, the runtime, and the call stack
  3. JavaScript stack size

Author’s Official Account: