Moment For Technology

Immutable. Js - Persistent data structures and structure sharing

Posted on Aug. 2, 2022, 8:34 a.m. by Alex Hussain
Category: The front end Tag: javascript react.js The front end Immutable.js

Why Immutable js instead of ordinary JS objects?

Treating data as immutable will do you a lot of good. In fact, this is the principle behind React: The React elements are immutable.

But what good is Immutable?


First there is a very large object...

Here are 100,000 items to do:

Var todos = {⋮ t79444DAE: {title: 'Task 50001', completed: false}, t7eAF70C3: {title: 'Task 50002', completed: false }, t2fd2ffa0: { title: 'Task 50003', completed: false }, t6321775c: { title: 'Task 50004', completed: false }, t2148bf88: { title: 'Task 50005', completed: false }, t9e37b9b6: { title: 'Task 50006', completed: false }, tb5b1b6ae: { title: 'Task 50007', completed: false }, tfe88b26d: { title: 'Task 50008', completed: False}, ⋮ (100,000 items)}Copy the code

I want to change the completed for Task 50,005 to ture.


Use normal JavaScript objects

function toggleTodo (todos, id) { return Object.assign({ }, todos, { [id]: Object.assign({ }, todos[id], { completed: ! todos[id].completed }) }) } var nextState = toggleTodo(todos, 't2148bf88')Copy the code

This operation ran for 134ms.

Why did it take so long? Because when using object. assign, JavaScript copies each attribute from the old (shallow) Object to the new Object.

We have 100,000 to-do items, so that means 100,000 properties that need to be (shallow) copied.

That's why it took so long.

In JavaScript, objects are mutable by default.

When you copy an object, JavaScript has to copy every property to keep the two objects independent of each other.

100,000 attributes are (shallow) copied to the new object.


Using Immutable. Js

Var todos = Immutable. FromJS ({⋮ t79444dae: {title: 'Task 50001', completed: false}, t7eaf70C3: {title: 'Task 50002', completed: false }, t2fd2ffa0: { title: 'Task 50003', completed: false }, t6321775c: { title: 'Task 50004', completed: false }, t2148bf88: { title: 'Task 50005', completed: false }, t9e37b9b6: { title: 'Task 50006', completed: false }, tb5b1b6ae: { title: 'Task 50007', completed: false }, tfe88b26d: { title: 'Task 50008', completed: False}, ⋮ (100000 items)}) / / use [updeep] (https://github.com/substantial/updeep) function toggleTodo (todos, id) { return u({ [id]: { completed: (completed) = ! completed } }, todos) } var nextState = toggleTodo(todos, 't2148bf88')Copy the code

This operation ran for 1.2ms. It's 100 times faster.

Why so fast?


Persistent data structures

A persistent data structure forces all operations to return the new version of the data structure and leave the original data structure unchanged, rather than directly modifying the original data structure.

This means that all persistable data structures are immutable.

Given this constraint, third-party libraries can better optimize performance by applying persistent data structures.


Performance improvement

For intuition, let's try a small example.

Key-value pair mapping data:

We can save it with a normal JavaScript object:

const data = {
  to: 7,
  tea: 3,
  ted: 4,
  ten: 12,
  A: 15,
  i: 11,
  in: 5,
  inn: 9
}
Copy the code

Convert to a data tree like this:

Photo source:wikipedia

In general, you can get the value you want by following the path shown above from the root node.

If you want to get data.in, start at the root node and follow I, n to the node with the value 5.

How do you fix it?

Let's say we want to change the key tea from 3 to 14.

I'm going to build a new tree and reuse the existing nodes as much as possible

Green indicates the new node.

Grey nodes lose indexes that will be reclaimed

As you can see, we just recreated four new nodes to update the tree. All other nodes are reused.

This is called structure sharing

Immutable. Js implements Immutable Map in this way. Create a tree with up to 32 branches per node.

This picture shows a real oneImmutable.Map

When we update a node, only a few nodes need to be recreated.

Immutable. Js keeps the tree structure compact and powerful by creating multiple types of nodes:


Everything has two sides...

Don't take this article to mean "you should always use Immutable. To be precise, I'm just telling you all the benefits of using it and why you should use it.

When I write code, I first use ordinary JavaScript objects and arrays, but when I use Immutable. Js, I need to be very sure that an object contains 10,000 properties. I almost never use Immutable. Js because most of the time objects are small.


Thanks for reading!

Search
About
mo4tech.com (Moment For Technology) is a global community with thousands techies from across the global hang out!Passionate technologists, be it gadget freaks, tech enthusiasts, coders, technopreneurs, or CIOs, you would find them all here.