Graph Theory Behind ImmutableJS

ImmutableJS is a library from Facebook which provides us a set of immutable data, such as Stack, List Map and others. With this you can build predictable and reliable state models on top of your application, doing easy 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 works behind the scenes!

Transcript

1. GRAPH THEORY BEHIND IMMUTABLE.JS @franzejr
2. @franzejr
3. GRAPH THEORY BEHIND IMMUTABLE.JS CONTENT ▸ Immutable.js ▸ Graphs ▸ Graph ▸ Trees ▸ Tries ▸ Data Structures ▸ Analysis of algorithms ▸ HOW ▸ WHY ▸ Benefits
4. CONCEPTS BEFORE IMPLEMENTATION, CODE. Great Software Engineer GRAPH THEORY BEHIND IMMUTABLE.JS
5. “GOOD DEVELOPERS KNOW HOW THINGS WORK. GREAT DEVELOPERS KNOW WHY THINGS WORK.” Steve Souders,(O’Reilly Media, 2013). GRAPH THEORY BEHIND IMMUTABLE.JS
8. LIST STACK MAP ORDENEREDMAP RECORD ORDENEREDSET SET
9. WHY SHOULD I CARE?
10. GRAPH THEORY BEHIND IMMUTABLE.JS Data structures are highly efficient on modern JS VMs Concepts of Functional Programming Facebook is behind it Immutability makes certain things easier. Good theory behind it! :)
11. THEORY
12. MODEL MANY TYPES OF RELATIONS AND PROCESSES IN PHYSICAL, BIOLOGICAL, SOCIAL AND INFORMATION SYSTEMS. MANY PRACTICAL PROBLEMS CAN BE REPRESENTED BY GRAPHS.
13. A complete graph
15. Weighted and Unweighted
16. Routing - Networks Short path
17. Short path
19. Trie
20. RETRIEVE
21. TRIE CAN BE USED AS REPLACED TO SOME DATA STRUCTURES. SIMPLE / STRAIGHTFORWARD
22. AUTOCOMPLETE
23. Words: “a,” “an,” “and,” “are,” and “bee.”
24. WE DON’T NEED TO DESCEND QUITE SO DEEP.
25. Game which can be solved by using a Trie
26. TALK IS CHEAP. SHOW ME THE CODE. Linus Torvalds
27. REALLY WORKS HOW IMMUTABLE.JS
28. import { List } from "immutable" var list = List([1,2,3]) var list2 = list.push(4) list // [1,2,3] list2 === list // false
29. 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
30. SO, IT SEEMS YOU JUST MADE A LOT OF COPIES. ISN'T THAT SLOW?
32. STRUCTURAL SHARING HASH MAP TRIES VECTOR TRIES
33. REMEMBER TRIES?
34. GRAPH THEORY BEHIND IMMUTABLE.JS Simple Data Structure Lookup very fast O(m), where m is the average word size Elements are in Order Can replace some data structures Simple and straightforward
35. HASH ARRAY MAPPED TRIE clojure
36. VECTOR TRIES
37. IS IT FAST?
40. ADD A NEW ELEMENT O(m), m = average word size
41. MUTABLE WORLD
42. IMMUTABLE WORLD Old elements - just copied ( shared ) New elements
43. LOOK UP FOR AN ELEMENT O(m), m = average word size
45. IMPLEMENTATION AS TRIE, INTERFACE AS LISTS AND MAPS
46. WHY IMMUTABLE.JS
47. CONCURRENCY. NO LOCKS.
48. IMMUTABLE DATA DECREASES COMPLEXITY.
49. EMBRACING IMMUTABILITY ENABLES JAVASCRIPT’S HYPOTHETICAL FUTURE.
50. CHANGE TRACKING
53. So, Immutable data structures provides you a cheap and less verbose way to track changes on objects, which is all we need to implement shouldComponentUpdate. Therefore, if we model props and state attributes using the abstractions provided by immutable-js we'll be able to use PureRenderMixin and get a nice boost in perf.
54. PROBLEM: SHARED MUTABLE STATE
55. "MUTABLE SHARED STATE IS THE ROOT OF ALL EVIL IN CONCURRENT SYSTEMS. THE HISTORY OF CONCURRENT COMPUTATION IS A BASICALLY THE STORY OF APPROACHES TO MANAGING MUTABLE SHARED STATE. THE THREAD MODEL, WHICH HAS LONG HELD THE DOMINANT POSITION, LEADS TO INTRACTABLE COMPLEXITY" E. Lee. The Problem with Threads, Computer, v.39 n.5, p.33-42, May 2006. GRAPH THEORY BEHIND IMMUTABLE.JS
56. IF IMMUTABLE IS SO GOOD AND IT SOLVES THE ROOT OF ALL EVIL, WHY PEOPLE KEEP USING MUTABLE DATA?
57. GRAPH THEORY BEHIND IMMUTABLE.JS Stockholm Syndrome Mutability is the default in imperative languages. Inertia of mind, a.k.a., resistance to change Most developers of today have been trained well before immutability (and the containing paradigm, functional programming) became "trendy" in their sphere of influence, and don't keep their knowledge up to date about new tools and methods of our trade.
58. PERSISTENCE IMMUTABLE DATA STRUCTURE WITH A GREAT THEORY AND DATA STRUCTURES BEHIND IT
59. STRUCTURAL SHARING
60. SOLVE PROBLEMS BY LOWERING COMPLEXITY
61. THANKS! @franzejr
62. GRAPH THEORY BEHIND IMMUTABLE.JS REFERENCES ▸ http://ejohn.org/blog/javascript-trie-performance-analysis/ ▸ https://en.wikipedia.org/wiki/Trie ▸ http://www.stoimen.com/blog/wp-content/uploads/2012/08/3.-Weithened- Graph.png ▸ https://auth0.com/blog/2016/03/23/intro-to-immutable-js/ ▸ https://facebook.github.io/immutable-js/ ▸ https://www.toptal.com/java/the-trie-a-neglected-data-structure ▸ http://hypirion.com/musings/understanding-persistent-vector-pt-1 ▸ This talk was totally inspired on Lee Byron Talk from: https://www.youtube.com/ watch?v=YFP8lbdZ0cs&index=6&list=PLfbGQgpcGXI-Ecf77nxzUKuJnZ2XOpNZc