Okay. Hi, everyone. My name is Maxim Koretskyi, but I'm also known as the Wizard because I like to talk and write about complicated stuff, topics that sometimes are seen as mysterious, and hence the name The Wizard. I'm going to be talking about why Angular and React, the top web frameworks we have today, are so fast.
This is where we develop the best data grid in the world, so, if you need the data grid, we have a free community version with a lot of features, so definitely give it a try if you need data grid. I'm also the founder of Angular and dev community where we write and publish articles about advanced topics of Angular. So, we will be talking about three things today: monomorphism, bitfils, and filters. How many know about monomorphism, watch talks? Something? Okay. I watched a talk by Benedict last year, gave a talk about monomorphism.
I will give you an overview of what it is. I will talk about bitfils and how Angular uses structure known as bloom filters. Let's start with monomorphism. I do a lot of reverse engineering. I sit at the computer with debugger and go through the sores of the frameworks.
These are the comments that I found inside Angular and React sources. So these are the comments by technical leads of the frameworks, and they talk about hidden class. And internal data structures called fibre and view nodes. They want to ensure that these internal data structures share the same hidden class, and that is to make property access monomorphic.
So a bunch of words when I first encountered that, I didn't really know what they were talking about. We need to clarify today what is hidden class? What is monomorphic property access? Why is it important in what are these data structures, like fibre and view nodes? Let's start with data structures. Fibre nodes and view nodes in Angular are used internally to represent a template, basically. When you define a component, this is the declaration of a component in Angular.
Angular uses view nodes, data structures, that it creates to represent a template. They define the metadata needed to render the DOM, and it also specifies which part of the DOM needs to be up dated.
Something called bindings. How many of you work with Angular? The same thing in React. We also define components, we define a template, and React uses fibre node. This is new React fibre 16 architecture.
It uses fibre node to represent the DOM. How many use React? About 40 per cent. Fibre nodes and view nodes are used by these frameworks to represent a template. This is something in between the declaration of a component template and the DOM. What is common between these data structures is that they are used a lot when these frameworks process changes.
Imagine there's a function called update node, an example of a function, there are a bunch of functions similar to this one in both frameworks. This function takes in a data structure, fibre or view node as the first parameter and then it reads some property. What is interesting that these kind of functions and the property access to easily exceed 10,000 times.
Hence the virtual machine has optimisation techniques they use to make the process faster. First, let me explain to you: when I was trying to figure out all that stuff, the question I had is why is it complicated? Why is it complicated to figure out where the value is, right? And the answer is because of something called shapes or hidden classes.
So, if we have two objects, on 1,000 objects, right, there's no need to describe the layout every single time. We can describe the layout only once, and then link this object to the shape that describes the layout, right? In this way, we only describe the layout once, even though we have, I don't know, potentially millions of objects in memory. But then, it creates a problem. What if we want to add an extra property? Now we want to extend the object A. We want to introduce the new property "W".
Well, we need to introduce a new shape. We cannot add the W property to the original shape. Because it would mean that the other object, the object B that points to the same shape has this property, which is not true. We need to introduce the new property and then the new shape.
Then we update links. The object now, the object points to the new shape. The same thing happens if we introduce another property we create one more shape. And so, in fact, we end up with something called Transition Chains.
And it means that, when you try to access the property, for example, X, the original property on the A object which points to the button on the chain. It needs to go through every single property upwards and will until it finds the shape that describes the property.
Okay? You can imagine that, if you add a lot of properties in different places and modify object shape, you will have a transition shape potentially with hundreds of transitions. And so, every single time when you access a property, the virtual machine has to go through all that process to figure out the shape that describes the layout and memory of that and retrieve that information. So a technique that V8 uses is to make that process faster. The idea is simple: the ...
So let me give you an example of how it works. Suppose we are calling the function Get X and passing in an object with the X property. The virtual machine figures out the shape for this object, right, and then what it can do is that it can cache the shape of the object, and then the property, right, because we are getting access to the X property, and it can couch the offset, right? So the next time when we execute this function and pass in an object that has the same shape, the virtual machine can only compare the shapes, and, if they match, there's no longer need to figure out the shape.
You can just take the cache value from the offset and use it to resolve the value in the memory. And what it also does is it defines the state of the function, and the state there can be three types of states: monomorphic state, monomorphic property access, and polymorphic. In this case, it's monomorphism because it - it's monomorphic because it has been called with one type of shape. Polymorphic is when a function has seen four types of shapes up to four times, and megamorphic is when you've been passing objects of different shapes, more than four types of shapes.
It's important that you pass objects of the state to one function so the state remains monomorphic. I read the comment that monomorphic property access can be up to 100 times faster than megamorphic.
If you take into account this 10,000 times of access during each change detection cycle that can happen several hundred times a second, you can imagine the kind of impact monomorphic property access can have on the speed. So frameworks use this to create - actually, what they do is they want to enforce this function that takes these nodes, it uses the same shape, same hidden class for fibre and view nodes, and that makes property access monomorphic. You can have HTML elements, child opponents, and if you follow object-orientated programming principles, you would create different classes for different elements. These frameworks actually merge everything into one data structure, one class, with all set of fields and they use one tag filled to distinguish between types of node. This is the code from the React framework.
This is a function that is executed for every single DOM element, so potentially thousands of times during each cycle, and you can see here that they try to distinguish by tag, and then run the corresponding logic. Okay, so that is monomorphism. Now, let's talk about bitfils. This is the other things that both frameworks happily used. Bitfils is a low-level concept.
If the bit is zero, it means that there is nothing to do here. And I found that when I was debugging React, I'm sitting with a debugger, and I'm following the spun element, and I've just updated the tag on the spun element, so I'm trying to figure out what changes it will have. So the effect tag is this effects filled, and it's a bitfil, so right after the render face when it has process changes, the number, the value, is four, and, because it's a bitfil, it's binary, so I converted it into like - here, it is actually the decimal, but I know it's binary, so I converted it to binary and I got 100. If you explore the fill, you can see it's a third bit, and that's exactly what I expected.
React encoded the update operation, so later - for example, here, when the function update hosts the facts, it's executed, so, React will check every single bit and see what kind of operations it needs to perform. For example, update will up date the tags.
With the bitfil, it's a smaller contiguous memory usage and allows for fast access for a single bit. It's one twice operator, and that's it. So that is bitfils. They're used by both Angular and React. The last date structure is bloom filters.
It's an interesting data structure. This data structure is designed to answer one simple question: is it element in the set or not? Well, you can use an array, of course, and just go over each element, make a comparison and figure out whether there is an element in the set or not. It's quite long.
You can imagine you have one million objects, you need to go through every single one, and it's pretty long. Well, bloom filters allows you to do that with just one operation. I show you how to do that. What is good about bloom filters is you can get two types of answers - yes or no - and, when you get the answer no, it means the element is definitely not in the set.
But when you get the answer yes, it's not actually yes, it's maybe. The probability varies.
Because of that, this data structure is called probabilistic, right? There is probability here. You might be looking at that and thinking to yourself, "Who needs a data structure that doesn't give you correct answer s?" This data structure is used most often when you expect the answer no most of the time. And this is exactly the case that I will present to you now. But first, I will show you how this data structure works, so each element in the set is encoded in a bitfil - one bitfils, or a few bitfils - you will have a hashing function that will take a value and produce some number.
For example, for John, if we run the function and we get the number 2, for example, we use the first letter and the code, for the letter, we will just use a binary or operator to set the second bit. And later, we will use the same function to get the number for John, but now we will use the B twice or operator to check if the John is here. You can imagine if the bit is not set, if it is zero, it means that John is not here. Now, where the problem is why, yes, it's not guaranteed. The problem is collisions.
If we use the same hashing function and we use, for example, the only first letter to figure out the number, we're passing John and Jane, they have the same first letter. Here we have a collision, right? We end up with the John being in the set and Jane not being in the set, but the hash function would produce the same value and we get a wrong result. So where does Angular use this? It uses in a dependency injection system. So the cornerstone of the dependency injection system is an injector.
It's a service, a container, where you can con figure the dependencies between services, and then the injectors responsible for instantiating them. Whereas most systems have only single injector called Global Injector, Angular has a hierarchical dependency injection, so, for the hierarchy of components, it creates an injector. For each component, you get an extra injector, so you end up with a hierarchy of injectors, and let's say the widget manager is provided in the top-most injector, or the bottom-most one requires on the widget. Angular would have to go through every single injector to figure out where exactly is this service, and only when it reaches the bottom-most injector it will be able to resolve the component. You can imagine it could take quite a while, for example, if every single injector has ten dependencies, ten services, it would need to go through every single one of them and do comparison which is a long time.
So what Angular does, it introduces a bloom filter for every single injector, and with bloom filter, as I showed you, it's one operation to know whether the service is in the set or not. As I told you, the answer is most likely to go to be no, to so here, no here, and the last, the top-most, the answer is maybe. If we get the answer maybe, then we can do our actual comparison and find the service if it is there. So that is bloom filter for you.
Okay, so here's a bunch of protocols that, if you're interested in that kind of flow-level details, I've written about reverse engineering, because I've reverse engineered webpack, other tools, change detection in Angular, and reconciliation in React. So here are the articles for you to check out. Also, if you want to learn more about this kind of topics, you can follow me on Twitter. I regularly write about some findings that I pick in these frameworks, and I've written about my journey, the article you can also read. So I hope that the knowledge that I've told you today that is awakened your curiosity to learn more about this kind of stuff, and I want you never to stop learning, and, by doing so, you will be able to reach new heights every day.
Because I want you all guys to be extraordinary engineers. Thank you for your attention, and good luck. [Applause].