How is Immutable sharing implemented
The mobx-state-tree release allows for free conversion of mutable to IMmutable data, seamlessly integrating mobx-written data streams into the Redux ecosystem or continuing to use the Mobx ecosystem.
This is a combination of transactional, traceable, and dependency tracing features that address both the development experience and data flow maintainability. What if this idea catches on? Let’s start by preheating its important features, structure sharing.
1 the introduction
Structure sharing is not just “structure sharing”. It includes Hash maps tries and vector tries. What points should we consider when designing a structure sharing function? This close reading gives the answer.
2 Content Summary
Speed can be a bottleneck when using object. assign for large objects, such as objects with 100,000 attributes, which took 134ms. The main reason for the performance loss is that the “structure share” operations need to traverse nearly 100,000 attributes, and these reference operations take more than 100ms of time.
Solution is to reduce the amount of the operation of the reference point, and with reference to the loss of any object are almost uniformly (regardless of the small target limit or infinity, reference consumption time is almost no difference), we need a well-designed tree structure will draw with a reference to establish depth, to reduce the reference number of operations, Vector tries is one solution:
The above key: T0143c274, the hash value is 621051904 (different from MD5, such as hash(“a”) == 0, hash(“c”) == 2). The value is 10010 10000 01001 00000 00000 00000 00000, this path is unique, and in order to reduce the depth of the tree, the path after the segmentation is also unique. So the addressing path looks like the figure above.
Therefore, the core idea of structure sharing is to exchange space for time.
3 intensive reading
This intensive reading is a discussion of Recoder Ascoders Cisen BlackGanglion Jasonslyvia TingGe Twobin Camsong, as well as a summary of my own blood spitting reading paper.
A property of the Immutable tree structure
Camsong dynamic diagram is used to describe the operation process of sharing:
However, as the tree grows wider (with more child nodes), the height of the corresponding tree decreases, resulting in higher query efficiency but lower update efficiency (think of the limit case, which is equivalent to a linear structure). In order to find a balance between updates and queries, we chose a 5bit split.
As a result, each node ends up with 2^5=32 child nodes, while squeezing the spatial structure with Vector trie and Hash Maps trie to minimize depth and maximize performance.
Vector trie
Check out this article for details.
The principle is that binary trees are used to store all values in the leaf nodes in order from left to right. When data needs to be updated, only nodes on the update path will generate new objects, and the nodes that have not changed will continue to share.
Hash maps trie
Immutablejs optimizes the Map in this way, and compresses the tree width and tree height, resulting in the effect in the example diagram in this paper (10010 10000 is aggregated into a node, and the empty nodes of the same level are removed).
Tree width compression:
Object. Assign can replace Immutable?
Structure sharing means that the reference to the root node is changed, but for unmodified nodes, the reference still refers to the old node. So object. assign can also implement structure sharing
See the following code:
const objA = { a: 1, b: 2, c: 3 }
const objB = Object.assign({}, objA, { c: 4 })
objA === objB // false
objA.a === objB.a // true
objA.b === objB.b // true
Copy the codeProve that Object.assign is fully capable of Immutable scenarios. However, as mentioned in this article, object-assign is inefficient when the Object attributes are large. Therefore, it is not suitable to use Object-. Assign to generate IMmutable data in special scenarios. However, you can use object. assign for most scenarios, because performance is not the bottleneck. The only problem is that deep-level Object assignments are cumbersome to write.
Map provides better performance than Object.assign. Can IT replace Immutable?
When the number of layer 1 nodes reaches 1000000, immutable. Get query performance is more than 10 times that of object.key.
It is an alternative to Immutable for performance, but not for use with REdux.
Redux determines whether the data is updated if the object reference is changed and if the parent object reference is modified when the child attributes of the object are modified. The Map kneels on this feature, which makes it impossible for a set Map object to produce a new reference.
This will result in the reRender not being triggered when the backgroundColor property of the Style object changes after it is connected. So while Map performance is good, it’s not up to redux support from the Object.assign or imMutableJS libraries.
3 summary
To be truly usable, data structure sharing needs the help of Hash maps tries and Vector tries data structures, as described above. Now that you know how structure sharing works, you’ll want to know how mobx-state-tree is able to convert mutable data to immutable data. Look forward to the next source code analysis (not necessarily in the next issue).
In most cases, you can use object. assign instead of Immutablejs, as long as you’re not afraid of the cumbersome syntax of deep assignment. The effect is exactly the same as Immutablejs. Only, Immutablejs can be used instead on large data fields to improve performance.
Discuss address is: how is the Immutable structure shared? · Issue #14 · DT-fe /weekly
If you’d like to participate in the discussion, click here. There are new topics every week, published every Friday.