The relationship between variables and memory

In JS, memory space is generally divided into stack, heap:

  • Stack general storage rules, occupy a small space and the size of the basic fixed data, soBasic data typesGeneral basic data types are stored in stacks
  • The heap generally stores irregular, occupies large space and the size of the data is not fixed, so the generalReference data typeStored in the heap

Reference data types typically store a reference address on the stack. Therefore, when accessing a reference data type, we first access the reference address stored on the stack, and then access the actual data through that address

const a = 1
const b = {
  b1:1.b2:2
}
Copy the code

Why do I need to copy data?

let a = 1
let b = {
  b1:1.b2:2
}

const c = a
const d =b

a = 2
b.b1=1.1
Copy the code

As you can see, d creates a new space in the stack, but it points to the same heap pointer as B, so when you modify the heap, d also changes.

Most of the time, however, we need them to be independent of each other, just like the basic data types. In this case, we need to make a copy of the heap data and point to the new heap data

Consider: why is data required to be a function when writing vue templates?

// test1
var a = {
  test1:1.test2:2
}
var b = a
var c = a
console.log(b === c) // true

// test2
var a = function (){
  return {
    test1:1.test2:2}}var b = a()
var c = a()
console.log(b === c) // false
Copy the code

Can be found, when we create objects within the function returns the object way to create, to ensure that every assignment is a fresh each other objects, so the data in the vue template to create data by means of function, can guarantee multiple local reference the same template, data will not affect each other between each other

A copy of the reference type

Generally when we talk about copy, we think about shallow copy and deep copy;

  • Shallow copyIf there is a reference type in the second layer, then there is still a problem.
    • I explicitly know that the object I want to copy is a simple, one-layer data
    • Even though the object is more complex, shallow copy has a slight performance boost when it is clear that only the first layer of simple variable data will be changed and there is no second layer of variable data
  • Deep copyIs a complete copy of an object, no matter how deep, how complex, generally for the companyUtil methodDeep copy is used

Shallow copy implementation

Method 1: Object.assign

const obj = {a:1.b:2};
const cloneObj = Object.assign({}, obj); 
Copy the code

Note: Object.assign copies only the source Object’s own enumerable attributes, using the source Object’s [[Get]] and the target Object’s [[Set]]. Therefore, if the Object to be copied contains inherited and non-enumerable attributes, these attributes will not be copied

Method two: by deconstructing the method of assignment

const obj = {a:1.b:2};
constcloneObj = {... obj};Copy the code

Tip: The expansion syntax is identical to the behavior of object.assign ()

Deep copy implementation

Method 1: json.parse

Json.stringify converts the data to a JSON string, stores it on the stack, and then converts it back to objects via json.parse and stores it in the heap. A copy of the object is cleverly recreated by converting it to a string

const obj = {
    a: {a1:1.a2:2},
    b: {b1:1.b2:2}};const cloneObj = JSON.parse(JSON.stringify(obj)); 
Copy the code

For such a simple deep copy, there are limitations:

  • For such asMap.Set.RegExp.Date.ArrayBuffer 和Other built-in typesCan be lost or changed during serialization.
var obj = {
  a: function() {}, / / lost
  b: new RegExp(/ab+c/.'i'),
  c: 123.d: new Set([1.2.3])}console.log(JSON.parse(JSON.stringify(obj)))
/ / {
// b:{},
// c:123,
// d:{}
// }
Copy the code
  • An error is reported if there is a circular reference relationship inside the object
var obj = {
  a:1
}
var obj2 = {
  b: obj
}
obj.c = obj2
console.log(JSON.parse(JSON.stringify(obj)))
// Uncaught TypeError: Converting circular structure to JSON
Copy the code
  • If the object is too deep, it willStack overflow
var obj = {}, cur = obj;
for (let i = 0; i < 10000; i++) {
  cur.next = {}
  cur = cur.next
}
JSON.parse(JSON.stringify(obj))
// RangeError: Maximum call stack size exceeded
Copy the code

Therefore, if you know the structure and complexity of the object to be copied, you can consider whether to use this method. Extension: Implement the json.stringify function

Method two: recursion

// This is an interview
function deepClone(obj){
  if (obj instanceof RegExp) return new RegExp(obj)
  if (obj instanceof Date) return new Date(obj)

  if (typeofobj ! = ="object" || obj === null) return obj;

  let newObj=Array.isArray(obj)? [] : {}for(var attr in obj){
      if (Object.prototype.hasOwnProperty.call(obj, attr)) {
          newObj[attr]=deepClone(obj[attr])
      }
  }
  return newObj
}
Copy the code

However, the deep copy of this recursive version still has the problem of method 1:

  • The presence of circular references will burst the stackRangeError: Maximum call stack size exceeded
  • Objects that are too deep in the hierarchy will also burst the stackRangeError: Maximum call stack size exceeded

Solve recursion is a circular reference problem

The circular reference problem can be solved by storing objects that have already been traversed in a Map or other way, then determining whether the Map has been stored in each recursion, and returning the stored objects if so

function deepClone(obj, map = new Map(a)){
  if (obj instanceof RegExp) return new RegExp(obj)
  if (obj instanceof Date) return new Date(obj)

  if (typeofobj ! = ="object" || obj === null) return obj;

  let newObj=Array.isArray(obj)? [] : {}if (map.get(obj)) {
    return obj;
  }
  map.set(obj, newObj);

  for(var attr in obj){
      if (Object.prototype.hasOwnProperty.call(obj, attr)) {
          newObj[attr]=deepClone(obj[attr], map)
      }
  }
  return newObj
}
Copy the code

Fixed a problem with too deep burst stack

It is theoretically possible to solve this problem recursively using tail calls. Tail-call optimization: The ES6 specification states that as long as tail-calls are implemented, there will be no stack overflow errors in recursion. The reality is that many browsers do not implement this specification, and stack overflow errors are still reported, and tail calls are restricted only in strict mode. The V8 engine used to do this, but later removed call optimization because tail-recursive optimization would destroy the function’s call stack information. TC39 is also looking for new syntax to explicitly indicate the need to use tail-recursive optimization.

Solve the problem of level too deep blasting stack 2: DFS | | BFS

In theory, all recursion can be done iteratively, and iterating doesn’t cause stack overflow, but it’s just not as easy to do! In the case of deep copy, we can implement it by stack + iteration: depth-first traversal (DFS) or breadth-first traversal (BFS). The implementation principle is similar. We use BFS as an example: source

function getEmpty(o){
    if(Object.prototype.toString.call(o) === '[object Object]') {return {};
    }
    if(Object.prototype.toString.call(o) === '[object Array]') {return [];
    }
    return o;
}
function deepCloneBFS(origin) {
  let queue = []; // Stack destruct
    let map = new Map(a);// Record the occurrence of the object, used to process the ring

    let target = getEmpty(origin);
    if(target ! == origin){ queue.push([origin, target]); map.set(origin, target); }while(queue.length){
        let [ori, tar] = queue.shift();
        for(let key in ori){
            // Handle the loop
            if(map.get(ori[key])){
                tar[key] = map.get(ori[key]);
                continue;
            }

            tar[key] = getEmpty(ori[key]);
            if(tar[key] ! == ori[key]){ queue.push([ori[key], tar[key]]); map.set(ori[key], tar[key]); }}}return target;
}
Copy the code

Structured cloning algorithm

MDNThe HTML5 specification defines the algorithm for copying complex JavaScript objects, can avoid infinite traversal loops, support more data types, however, should only be built into the API to achieve this function, so if you need to use this function will need to use the built-in API, indirect cloning! Channel Messaging API Channel Messaging interface implementation compatibility is relatively good.

Node Serialization API (v8.0.0 +)

Node provides a serialization API comparable to HTML structured cloning and is relatively simple to use

const buf = v8.serialize(obj);
const clone = v8.deserialize(buf);

console.log(clone);
Copy the code

Immerjs takes a different approach

Actually the above methods has a problem, that is, whether we use the data, will be a traversal of all data on, for huge data, the performance is not very good, so you can consider to use objects by means of Proxy agent way to copy, unused part, is still the same data. Immer is through this idea, with the minimum cost to implement JS immutable objects

The last

The best method of cloning depends on the environment used and the complexity of the object.

The starting address

reference

  • Headline Interviewer: Do you know how to implement a high-performance version of deep copy?
  • Deep-copying in JavaScript
  • JavaScript deep copy performance analysis