Focusing on optimization, surpassing immer, limu finally reaches the top of immutable data performance
Published: 2024-01-06 04:34:08


![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/dftn14u595x0ji6efb2s.png)

[limu](https://github.com/tnfe/limu) is designed for modern browsers. It only considers the operating environment that supports `Proxy` and uses the mechanism of **shallow copy on read and mark update on write**. This allows users to operate variable data like original data. During the operation, only proxy objects are generated for the read nodes and returned to the user. After reading, the parent and child nodes are directly connected with shallow clone nodes. The proxy object is hidden in the meta data of the node. , after the operation is completed, a new data with structural sharing characteristics is generated, and the meta data generated during the reading process is removed.


![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/c0ejvepcx46uxl972jov.png)


![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/sh3u5o87lifazw6ms9j4.png)

This design brings three major benefits:

- Transparent data structure
limu is currently the only immutable operation library that can view the data structure of drafts in real time, and is debugging friendly.

- Excellent performance
Since the shallow cloning operation is done in advance, and only the read path is cloned and the path pointing between the parent and child nodes is changed, when ending the draft, you only need to judge whether the `modified` variable is true or false to instantly complete the new copy generation action. In scenarios with large amounts of data and few reads, the performance exceeds that of `immer` by more than 20 times (the data before 3.12 was about `4` times)

- Simple code structure
Since only supporting `Proxy` is considered, the code design has no historical baggage and can focus on core scenarios of immutable data such as data reading and writing, proxy generation, and frozen implementation, which is conducive to later upgrades and expansion of more features oriented to modern browser standards.


# optimization process

Before `3.12`, although the performance of `limu` was several times better than `immer`, it was far away from [structura](https://github.com/GiuseppeRaso/structura.js) and [mutative](https://github. com/unadlib/mutative) These new immutable data operation libraries still have many gaps, so they can only be debugged friendly and several times faster than `immer` as a promotional point. If you want to pursue the ultimate speed, it is recommended by default. `mutative`.

After `3.12`, `limu` finally smoothed out these gaps. Let’s start to share the performance optimization process to see how `limu` cultivates and reaches the peak of performance.

## Place meta

At the beginning of the article, we mentioned the point of `meta` data hiding. `meta` data records important information such as the proxy object of the current node, father, child, reachable path, data version number, etc. In order to prevent users from perceiving this data exists, and two attempts have been made.

### symbol hides meta

Internally uses a symbol tag to store `meta`

```ts
const LIMU_META = symbol('LIMU_META');
const obj = { a: 1, b: { b1: 1 } };

// When reading obj.b, the object { b1: 1 } hides a meta
{ b1: 1, [LIMU_META]: { parent, path, version, modified ... } }
```

Then at the end of the operation draft, the `levelScopes` operation force needs to use the `delete` keyword to remove these redundant data. The inconvenience caused by this method is that when printing the data, you will see a very dazzling `LIMU_META` attribute in the object. , creating a psychological burden for users to pollute their data.

### proto hides meta

In order to keep the data clean, in addition to continuing to use the symbol `LIMU_META` as a private attribute, this attribute is promoted to `__proto__` and hidden. Then the problem arises. If `__proto__` is directly operated, the prototype chain will be polluted.

```ts
var a = 1;
a.__proto__.meta = 1;
var b = 2;
console.log(b.__proto__.meta); // 1
a.__proto__.meta = 100;
console.log(b.__proto__.meta); // 100 ❌ The prototype chain has been contaminated
```

In order to bypass contamination, a separate prototype object is created for each object and mixed in the original prototype chain, as shown below:

```ts
before:
a.__proto points to Object.Prototype
after:
a.__proto points to Limu.Prototype, Limu.ProtoType points to Object.Prototype
// Each Limu.Prototype is a clean object generated by Object.create(null)
```

The simplified version of the code is implemented as follows

```ts
export function injectLimuMetaProto(rawObj) {
   const pureObj = Object.create(null);
   Object.setPrototypeOf(pureObj, Object.prototype);
   Object.setPrototypeOf(rawObj, pureObj);
   return rawObj;
}
```

This achieves the effect of using `symbol` to hide private attributes and using the reconstructed prototype chain to promote private attributes to the prototype chain without polluting the prototype chain.

## Performance loss analysis

Although `meta` has been used to achieve the goal of generating structural shared data, the test results are still 4 to 5 times different from `structura` and `mutative`, which makes me believe that `limu` must still have huge room for improvement.

So I started to fine-tune the source code and run performance test scripts to find possible performance loss points.

### Remove meta

When finishing the draft, we need to remove meta to avoid memory leaks. Then we will use the `delete` operator to disconnect the `LIMU_META` pointed to by the parent node. After I blocked this `delete` operation, the performance improved by 2 About times, then the key point becomes how to bypass the `delete` operation

```ts
function finishDraft(){
levelScopes()
}

function levelScopes()(
scopes.forEach((scope)=>{
// Comment out deletaMeta, performance improved by 2 times
// deletaMeta(scope);
});
)
```

### Prototype chain reorganization

The `injectLimuMetaProto` mentioned above actually involves a process of prototype chain re-pointing, including two `setPrototypeOf` operations. This function is deliberately shielded and the lower part of `meta` is placed on the object. The performance is improved by about 4 times. It is found that `setPrototypeOf` of a large number of nodes actually causes a lot of performance loss.

```ts
injectLimuMetaProto(obj),
setMeta(obj, newMeta());
// Replace with the following writing method, performance improved by 4 times
obj[LIMU_META] = newMeta();
```

## Customized optimization plan

After analyzing the performance loss points by constantly annotating the code and running the script, our goal is very clear. How to block the two major performance consumers of `delete` and `setPrototypeOf`, and also keep the data clean and `meta` can be obtained normally.

Finally, I came up with the new data structure `Map` of es6. When `createDraft`, a `metaMap` is generated for each draft, which is used to place the `meta` corresponding to the data. The pseudo code is as follows:

```ts
function getProxy(metaMap, dataNode){
  const meta = !getMeta(dataNode);
  if(!meta){
    const copy = shallowCopy(dataNode);
    const meta = newMeta(copy, dataNode);
    // Use the shallow clone reference of the node itself as the key to store meta
    metaMap[copy] = meta;
  }
  // Meta already exists, return the generated proxy object
  return meta.proxyVal;
}
  
function createDraft(base){
  const metaMap = new Map();
  return new Proxy(base, {
    get(parent, key){
      const dataNode = parent[key];
      return getProxy(metaMap, dataNode);
    },
  });
}
```

With this `metaMap`, there is no more `setPrototypeOf` behavior. At the same time, continue to operate this `metaMap` in the `finishDraft` step and cut off the relevant `meta` records. Compared with `delete`, `map.delete` More efficient, our data is stored in `map`, so we no longer need to deal with `delete`.

The pseudo code is as follows

```ts
function finishDraft(){
  levelScopes();
}
  
function levelScopes(){
  scopes.forEach((scope)=>{
  // Comment out deletaMeta, performance improved by 2 times
  // deletaMeta(scope);
  });
}
```

So far, we have completed the purpose of completely blocking `delete` and `setPrototypeOf`. At the same time, the user's data is completely clean and transparent. Next, we enter the optimized performance testing process.

## Performance Testing

We have placed the performance test-related code into [benchmark](https://github.com/tnfe/limu/tree/main/benchmark). You only need to perform the following steps to experience the performance test performance of the latest version.

```bash
git clone git@github.com:tnfe/limu.git
cd limu
cd benchmark
npm i
```

Then execute the following four sets of commands and observe the printing results.
```bash
npm run s1 // Does not operate the draft array, the result is not frozen
npm run s2 // Manipulate the draft array, the result will not be frozen
npm run s3 // Does not operate the draft array, the result is frozen
npm run s4 //Operation draft array, the result is frozen
```

### Test data design

In order to simulate complex data, our [test data](https://github.com/tnfe/limu/blob/main/benchmark/_util.js) contains a dictionary of 20+keys.


![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/jixpdupx70va28o5k02x.png)

The data depth corresponding to the key is 26 layers


![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/dmjczwpdac2qufmhf2kq.png)

At the same time, an array of length `10000` will be generated.


![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/37j1knzjnr3kz2j6q3to.png)

### Test role preparation

In addition to the four libraries `immer`, `limu`, `mutative`, and `structura`, the test role also adds `pstr` and `native`

`pstr` uses `JSON.parse` and `JSON.stringify` to simulate `immer`’s `produce`

```ts
// code of pstr
exports.createDraft = function (obj) {
   return JSON.parse(JSON.stringify(obj));
};

exports.finishDraft = function (obj) {
   return obj;
};

exports.produce = function (obj, cb) {
   cb(exports.createDraft(obj));
};
```

`native` does nothing but manipulates native objects.

```ts
exports.createDraft = function (obj) {
   return obj;
};

exports.finishDraft = function (obj) {
   return obj;
};

exports.produce = function (obj, cb) {
   cb(exports.createDraft(obj));
};
```

The purpose of adding `pstr` and `native` is to compare the performance difference between immutable operation efficiency and hard cloning `JSON.parse(JSON.stringify(obj))` and the original operation.

### Test code writing

In order to test the reading and writing of complex data, multiple deep-level reading and writing operations will be performed, and `operateArr` will be added to control whether it is convenient for array operations. Part of the [suggestion code](https://github.com/tnfe/limu/blob /main/benchmark/caseReadWrite.js) as follows:

```ts
runPerfCase({
   loopLimit: 1000,
   arrLen: 10000,
   userBenchmark: (params) => {
     const { lib, base, operateArr, moreDeepOp } = params;
     const final = lib.produce(base, (draft) => {
       draft.k1.k1_1 = 20;
       if (moreDeepOp) {
         draft.a.b.c.d.e.f.g.h.i.j.k.l.m.n.o.p.q.r.s.t.u.v.w.x.y.z = 666;
         draft.a1.b.c.d.e.f.g.h.i.j.k.l.m.n = 2;
         draft.a2.b.c.d.e.f.g.h.i.j.k.l.m.n = 2;
         draft.a3.b.c.d.e.f.g.h.i.j.k.l.m.n = 2;
         draft.a4.b.c.d.e.f.g.h.i.j.k.l.m.n = 2;
         draft.a5.b.c.d.e.f.g.h.i.j.k.l.m.n = 2;
         draft.a6.b.c.d.e.f.g.h.i.j.k.l.m.n = 2;
         draft.a7.b.c.d.e.f.g.h.i.j.k.l.m.n = 2;
       }

       if (operateArr) {
         draft.arr[draft.arr.length - 1].a = 888;
         // draft.arr.forEach((item, idx) => { // bad way
         lib.original(draft.arr).forEach((item, idx) => { // good way
           if (idx === 100) {
             draft.arr[1].a = 888;
           }
         });
       }
     });

     if (base === final) {
       die('base === final', lib);
     }
   },
}).catch(console.error);
```

Each character will be warmed up before officially starting to execute, and then start 1000 traversals. At the end of each traversal, a time is obtained. The final time consumption is summed and divided by 1000 to get the average time consumption of each traversal. Part of [Schematic code] ( https://github.com/tnfe/limu/blob/main/benchmark/_perfUtil.js) is as follows:

```ts
function oneBenchmark(libName, options) {
   const { userBenchmark, arrLen } = options;
   let lib = immutLibs[libName]; // Get different immutable libraries
   const base = getBase(arrLen);
   const start = Date.now();
   try {
     //Execute user-written performance test cases
     userBenchmark({
       libName,
       lib,
       base,
       operateArr: OP_ARR,
       moreDeepOp: MORE_DEEP_OP,
     });
     const taskSpend = Date.now() - start;
     return taskSpend;
   } catch (err) {
     console.log(`${libName} throw err`);
     throw err;
   }
}

function measureBenchmark(libName, options) {
   const loopLimit = options.loopLimit || LOOP_LIMIT;

   let totalSpend = 0;
   const runForLoop = (limit) => {
     for (let i = 0; i < limit; i++) {
       totalSpend += oneBenchmark(libName, options);
     }
   };
   // preheat
   oneBenchmark(libName, options);
   runForLoop(loopLimit);
   console.log(`loop: ${loopLimit}, ${libName} avg spend ${totalSpend / loopLimit} ms`);
}
```

### Test result display

My machine is `macbook pro 2021`, `M1` chip, `32GB` memory.

Executing `npm run s1` means that the draft array will not be operated and the result will not be frozen. The result is as follows

```ts
loop: 1000, immer avg spend 13.19 ms
loop: 1000, limu avg spend 0.488 ms
loop: 1000, mutative avg spend 0.477 ms
loop: 1000, structura avg spend 0.466 ms
loop: 1000, pstr avg spend 17.877 ms
loop: 1000, native avg spend 0.084 ms
```

The visualization result is (unit ms, the lower the column, the better the performance)



![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/l527bcb2gqjyj6t1riuf.png)

Executing `npm run s2` means operating the draft array and the result is not frozen. The result is as follows

```ts
loop: 1000, immer avg spend 11.315 ms
loop: 1000, limu avg spend 0.95 ms
loop: 1000, mutative avg spend 0.877 ms
loop: 1000, structura avg spend 0.646 ms
loop: 1000, pstr avg spend 9.945 ms
loop: 1000, native avg spend 0.107 ms
```


![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/qjhb076abislvfj8ph6m.png)

Executing `npm run s3` means that the draft array will not be operated and the result will be frozen. The result is as follows

```ts
loop: 1000, immer avg spend 18.931 ms
loop: 1000, limu avg spend 5.274 ms
loop: 1000, mutative avg spend 8.468 ms
loop: 1000, structura avg spend 17.328 ms
loop: 1000, pstr avg spend 10.449 ms
loop: 1000, native avg spend 0.02 ms
```

`structura` and `immer` perform worse than hard clone `pstr` in this scenario, `limu` performs best, and `mutative` comes second.


![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/ish26pb2c3xzzjgax8km.png)

Executing `npm run s4` means operating the draft array and the result is frozen. The result is as follows

```bash
loop: 1000, immer avg spend 58.359 ms
loop: 1000, limu avg spend 26.142 ms
loop: 1000, mutative avg spend 32.264 ms
loop: 1000, structura avg spend 74.851 ms
loop: 1000, pstr avg spend 32.481 ms
loop: 1000, native avg spend 0.481 ms
```

Due to the operation of an array of 10,000 lengths, the time is improved by 2 to 3 times compared to the previous group. `structura` and `immer` are still not as good as hard clone `pstr` in this scenario, `limu` performs best, and `mutative` performs best `The next best thing.


![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/7zdtvn5gd1srajpe8w6v.png)

### Test conclusion

After the above multiple rounds of testing, it is concluded that in the non-freezing scenario, the difference between `limu`, `structura` and `mutative` is not big, all between 10 times and 30 times.

In the frozen scene, `limu` performs best, followed by `mutative`, and `structura` performs worse than `immer`. The performance is as follows when displayed as a radar chart.

> Note: The smaller the area, the better the performance



![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/78du6g9q3jcomhntsl9e.png)


# Conclusion

After the above complete disclosure of optimization details and summary of test results, the performance test results of `limu` in various non-freezing scenarios are on par with `structura` and `mutative`, and are 1 to 2 ahead of `structura` and `mutative` in freezing scenarios. times, it can now be claimed that `limu` has reached the pinnacle of immutable data performance.

In addition to excellent performance, `limu` data can be viewed in real time. After deep expansion, it becomes json instead of Proxy. It is very friendly for debugging. If you have the ultimate pursuit of performance and do not consider compatibility with non-`Proxy` environments, `limu` It will be your best choice. It maintains the same API design as `immer`. If you do not use the `applyPatches` related API of `immer`, you can achieve seamless replacement.

## one more thing

[helux](https://heluxjs.github.io/helux) based on [limu](https://github.com/tnfe/limu) will be announced soon, hoping to redefine the react development paradigm and comprehensively improve react applications `DX`&`UX` (development experience, user experience), welcome to pay attention and understand in advance.


![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/kw5mbs9r37gbfdd6q8br.png)

## Friendly links:

❤️ Your little star is our biggest spiritual motivation for open source. Welcome to pay attention to the following projects:

[limu](https://github.com/tnfe/limu) The fastest immutable data js operation library.

[hel-micro](https://github.com/Tencent/hel) Toolchain-independent runtime module federation sdk.

[helux](https://github.com/heluxjs/helux) A state engine that integrates atom, signal, and dependency tracking, and supports fine-grained response updates