Graph Theory behind ImmutableJS

ImmutableJS is a library from Facebook which provides us a set of immutable data structures, such as Stack, List Map and others. With this you can build predictable and reliable state models on top of your application, making it easier to handle state.

These structures are highly efficient on modern Javascript VMS by using structural sharing via hash maps tries and vector tries. But how they do this?

The point is: there is a lot of graph and algorithm theory behind this. Direct Acyclic graphs and complexity of algorithms.

There is a difference between implementation and interface. On this talk we will have these two visions.

At the end of this talk, you should understand how the things really work behind the scenes!

Transcript

1. GRAPH THEORY BEHIND IMMUTABLEJS
2. @FRANZEJR
4. “concepts before implementation, code.” — Great Software Engineer
5. “Good developers know how things work. Great developers know why things work.” — Steve Souders,(O’Reilly Media, 2013).
7. LIST
8. MAP
9. STACK
10. RECORD
11. ORDERED SET
12. ORDERED MAP
13. WHY SHOULD I CARE?
14. DATA STRUCTURES ARE HIGHLY EFFICIENT ON MODERN JS VMS
15. CONCEPTS OF FUNCTIONAL PROGRAMMING
16. FACEBOOK IS BEHIND IT !
17. IMMUTABILITY MAKES CERTAIN THINGS EASIER
18. GOOD THEORY BEHIND IT! !
19. BEFORE WE BEGIN: NOT A TUTORIAL
20. BEFORE WE BEGIN: IDEAS, NOT IMPLEMENTATIONS
21. BEFORE TALKING ABOUT THEORY. LET'S TALK ABOUT...
22. HISTORY
23. REACT WAS CREATED IN 2012. LEE BYRON NEEDED TO CONVINCE JORDAN WALKE THAT REACT WAS A BAD IDEA. FOR SOME REASONS...
24. XHP AN HTML COMPONENT FRAMEWORK FOR PHP
25. REACT --> HTML NOT WORKING WITH DATA STRUCTURES
26. HARD TO TRACK CHANGES.
27. REACT WOULD BE SLOW.
28. DURING THIS PROCESS...
29. IMMUTABLEJS STARTED AS A PET PROJECT
30. PURE RENDER MIXIN HTTPS://FACEBOOK.GITHUB.IO/REACT/DOCS/PURE-RENDER-MIXIN.HTML
31. SHOULDCOMPONENTUPDATE()
33. A GOOD TEXT: HTTP://JAMESKNELSON.COM/SHOULD-I-USE-SHOULDCOMPONENTUPDATE/
34. A 10X SPEEDUP OF LESS THAN 1 MILLISECOND IS STILL LESS THAN 1 MILLISECOND.
35. THERE IS NO SILVER BULLET
36. SOLUTION?
37. WELL STRUCTURED DATA/STATE.
38. RECONCILIATION
39. TRACK CHANGES AND RE-RENDERS THE WHOLE APP
40. Everyone wants to track changes. !
41. VIRTUAL DOM
42. TRACK CHANGES 1. Key Value Observables 2. Dirty Checking
43. DREAM: DESTROY ONE PART OF THE DOM AND RE-CREATED IT. !
44. UPDATE
45. DOM IS STATEFUL !
46. Coming back to Virtual DOM > Whenever anything may have changed, re-render everything to a virtual DOM representation
47. > Diff the previous representation with the next one
48. > Only update the real DOM with what actually changed
49. A SIGNAL TO SAY: "HEY! SOMETHINGH MAY HAVE CHANGED!"
50. SIGNAL: RECONCILIATION DIFF ALGORITHM.
51. YOUR VIEW IS USUALLY SMALLER THAN YOUR MODEL.
52. O(v) vs O(m) Size of your view vs size of your model
53. v << m (real apps, not microbenchmarks)
55. PERFORMANCE IS NOT THE MAIN GOAL OF THE VIRTUAL DOM. SIMPLICITY IS.
56. IMMUTABLEJS!
57. WHAT IT CAN SOLVE?
58. 1. IMMUTABLE
59. 2. PERSISTENT
60. 3. STRUCTURAL SHARING
61. THEORY?
62. MANY PRACTICAL PROBLEMS CAN BE REPRESENTED BY GRAPHS. MODEL MANY TYPES OF RELATIONS AND PROCESSES IN PHYSICAL, BIOLOGICAL, SOCIAL AND INFORMATION SYSTEMS.
63. A COMPLETE GRAPH
64. A TREE
65. A TRIE!
66. DIGITAL TREE RADIX TREE PREFIX TREE
67. PRONOUNCED AS "TRY" ORIGINATED FROM THE WORD RETRIEVAL
68. TRIE WERE FIRST DESCRIBED BY R. DE LA BRIANDAIS IN 1959.
69. TRIE CAN BE USED TO REPLACE SOME DATA STRUCTURES.
70. SIMPLE / STRAIGHTFORWARD
71. SEARCHING TREES -> FIXED SIZE TRIES -> VARYING LENGTH
72. ORDERED TREE DATA STRUCTURE
73. THE POSITION IN THE TREE DEFINES THE KEY WITH WHICH IT IS ASSOCIATED.
74. POSITION IN THE TREE
75. ELEMENTS ARE NORMALLY IN PRE-ORDER
76. AUTOCOMPLETE LEXICOGRAPH SEARCH TREES
77. WORDS: “A”, “AN”, “AND”, "ARE" AND “BEE”,
78. O(M) where m is the average word size
79. AUTOMATON?
80. A general trie [10, 13] is a lookup structure for finite strings that acts like a Deterministic Finite Automaton (DFA) without any loops: the transitions are the characters of the strings, the internal nodes encode prefix sharing, and the accept nodes may point to values associated with the strings
81. TALK IS CHEAP. SHOW ME THE CODE.
82. Not really !
83. HOW IMMUTABLEJS REALLY WORKS
84. LIST import { List } from "immutable" var list = List([1,2,3])
85. LIST import { List } from "immutable" var list = List([1,2,3]) var list2 = list.push(4)
86. LIST import { List } from "immutable" var list = List([1,2,3]) var list2 = list.push(4) list // [1,2,3] list2 === list // false
87. LIST import { List } from "immutable" var list = List([1,2,3]) var list2 = list.push(4) list // [1,2,3] list2 === list // false console.log(list.toString()) // List [ 1, 2, 3 ] console.log(list2.toString()) // List [ 1, 2, 3, 4 ]
88. MAP var Immutable = require('immutable'); var map1 = Immutable.Map({a:1, b:2, c:3});
89. MAP var Immutable = require('immutable'); var map1 = Immutable.Map({a:1, b:2, c:3}); var map2 = map1.set('b', 50);
90. MAP var Immutable = require('immutable'); var map1 = Immutable.Map({a:1, b:2, c:3}); var map2 = map1.set('b', 50); map1.get('b'); // 2 map2.get('b'); // 50
91. JAVASCRIPT FIRST API BRINGS INTERESTING ASPECTS FROM CLOJURE, SCALA AND HASKELL
92. Accepts raw Javascript objects var map1 = Immutable.Map({a:1, b:2, c:3, d:4}); var map2 = Immutable.Map({c:10, a:20, t:30}); var obj = {d:100, o:200, g:300}; var map3 = map1.merge(map2, obj); // Map { a: 20, b: 2, c: 10, d: 100, t: 30, o: 200, g: 300 }
93. Converts back to raw JavaScript objects. var deep = Immutable.Map({ a: 1, b: 2, c: Immutable.List.of(3, 4, 5) }); deep.toObject() // { a: 1, b: 2, c: List [ 3, 4, 5 ] } deep.toArray() // [ 1, 2, List [ 3, 4, 5 ] ] deep.toJS() // { a: 1, b: 2, c: [ 3, 4, 5 ] } JSON.stringify(deep) // '{"a":1,"b":2,"c":[3,4,5]}'
94. IT SEEMS YOU JUST MADE A LOT OF COPIES. ISN'T THAT SLOW?
95. (...) highly efficient on modern JavaScript VMs by using: — ImnmutableJS website
96. STRUCTURAL SHARING
97. HASH MAP TRIES
98. VECTOR TRIES
99. POPULARIZED BY CLOJURE AND SCALA,
100. MINIMIZING THE NEED TO COPY OR CACHE DATA.
101. MINIMIZING ?
102. STRUCTURAL SHARING?
104. THIS IS IMPORTANT!
105. REMEMBER TRIES?
106. SIMPLE DATA STRUCTURE
107. LOOKUP VERY FAST O(M), WHERE M IS THE AVERAGE WORD SIZE
108. ELEMENTS ARE IN PRE-ORDER
109. CAN REPLACE SOME DATA STRUCTURES
110. SIMPLE AND STRAIGHTFORWARD
111. HASH ARRAY MAPPED TRIE
112. VECTOR TRIE
113. RUBY ?
114. IMMUTABILITY IN RUBY A HAMT IMPLEMENTATION ! HTTPS://GITHUB.COM/HAMSTERGEM/HAMSTER
115. person = Hamster::Hash[name: "Simon", gender: :male] # => Hamster::Hash[:name => "Simon", :gender => :male]
116. friend = person.put(:name, "James") # => Hamster::Hash[:name => "James", :gender => :male] person # => Hamster::Hash[:name => "Simon", :gender => :male] friend[:name] # => "James" person[:name] # => "Simon"
117. MORE INFORMATION HTTPS://GITHUB.COM/FRANZEJR/AWESOME-IMMUTABLE-DATA
118. IMPLEMENTATION AS TRIE, INTERFACE AS LISTS AND MAPS
119. WHY [IMMUTABLEJS]
120. WHAT PROBLEMS DOES THIS SOLVE ANYWAY?
121. CONCURRENCY. NO LOCKS. ❤
122. IMMUTABLE DATA DECREASES COMPLEXITY.
123. EMBRACING IMMUTABILITY ENABLES JAVASCRIPT’S HYPOTHETICAL FUTURE.
124. CHANGE TRACKING.
125. IF IMMUTABILITY IS SO GOOD,
126. WHY PEOPLE KEEP USING MUTABLE DATA?
127. STOCKHOLM SYNDROME
128. MUTABILITY IS DEFAULT IN IMPERATIVE LANGUAGES.
129. INERTIA OF MIND, A.K.A., RESISTANCE TO CHANGE
130. LET'S REVIEW IT
131. PERSISTENCE IMMUTABLE DATA STRUCTURE WITH A GREAT THEORY AND DATA STRUCTURES BEHIND IT
132. STRUCTURAL SHARING
133. SOLVE PROBLEMS BY LOWERING COMPLEXITY
134. THANKS! @FRANZEJR
135. References
136. Pete Hunt - The Secrets of React's Virtual DOM (FutureJS 2014) https://www.youtube.com/watch?v=-DX3vJiqxm4
137. React.js Conf 2015 - Immutable Data and React https://www.youtube.com/watch?v=I7IdS-PbEgI
138. Episode 8 - React, GraphQL, Immutable & Bow-Ties with Special Guest Lee Byron Thursday 31 December 2015 > Link > reactpodcast.com