Developing data structures for JavaScript
CC Attribution 2.0 Belgium:
You are free to use, adapt and copy, distribute and transmit the work or content in adapted or unchanged form for any legal purpose as long as the work is attributed to the author in the manner specified by the author or licensor.
Plique, Guillaume
There is a tenacious misconception nowadays that people working with JavaScript do not need to know much about data structures because developing for the web is still often deemed to be, and this cannot be more false, an easier task than "real" programming. Web applications have become complex beasts and node.js allows to build programs that used to be other backend languages' turf. JavaScript developers now need to develop, as with any other programming language, custom data structures to solve particular problems when arrays and objects are simply not enough. The intention of this presentation is therefore to compile series of tips, tricks and use cases regarding the implementation of data structures in JavaScript and the challenges it poses. It is indeed tricky to ensure consistent performance in a high-level language with JIT and where engines like v8 apply a lot of optimization magic. One has to be able to evolve around those constraints. Examples will be taken from libraries such as graphology, sigma.js' newest version and finally mnemonist to demonstrate that 1. performant data structures can be designed for JavaScript using the language's capabilities and that 2. everyone can use them to solve problems more efficiently.
 So, hello everyone. So first thing, who knows about data structures in the room? Can you show your hand? Okay, that's fine. So this talk is called Developing Data Structures for JavaScript. And so I'm really glad to be here on the back again, the JavaScript Dev Room. And so I hope I will be able to entertain you during those next 20 minutes. So who am I? I'm messing up. Ah, okay. So the subject of this talk is why and how to implement data structure for JavaScript and why is that a thing? So who am I? I'm Guillaume. So I go on the internet by the infamous name of Young Githary Old, which is a shitty name, but that's life. And I'm a research engineer working for a research lab in Paris, which is called the Media Lab. So what's a data structure? Just to be sure we agree on the same ground. So a data structure is actually a way to organize and move data around in the computer, so we are able to query and update it efficiently. So basically when you deal with computer, you can sometimes trade off some memory space to be able to do computation faster. And so basically this is what encompasses data structure. So for instance, in JavaScript, you have a lot of data structures. You have arrays, you've got objects, set maps, and so on. So we will start with some quotes from the internet. So web development is not real development. It ends fourth easier. So this is bullshit. Web development is trivial and web developers don't need fancy data structures or any solid knowledge and algorithm. So someone obviously still wrong. So the point of my talk here is to show you that we can use data structure in JavaScript and that's a good thing. And if you do all do that, you will lead a happier life. So the question is, don't we have already data structures in JavaScript? For instance, we have arrays, we have objects, and now with ES6 we've got maps, we've got sets. So why the hell do we bother about custom data structures? Isn't this really enough? So why do we want other data structures? So the first point is because it's convenient. Like any other kind of abstraction, having data structure is convenient and it's easy for you to do some kind of heavy bookkeeping using those custom data structures. So I will use an example to clarify this point. For instance, you can implement something which is called a multi-set. A multi-set is actually a set in which you can store an item more than once. So for instance, if you do some basic JavaScript and you need to count the number of occurrences of an item in a sequence, you can do this Nasi code, you're going to iterate on this list, and then you have to check if your item already exists in the list, and then you set up the item to be zero, and then you increment it and so on. So this is bookkeeping. You have to track a lot of things and so on. Whereas if you have a multi-set, you can just do that. You have abstracted this complexity away, and then you are able to delegate the bookkeeping to the custom data structure. So this is a first example. Another example would be more complex data structures because the multi-set is actually really, really easy and straightforward. But for instance, if you want to implement a graph, so a graph is nodes connected by edges, and so this is actually quite doable if you only use arrays and objects, but you have to keep a lot of indexations running correctly and smoothly. For instance, if you want to check who which are the neighbors of a node, you have to index that. So if you do it by hand and you can do it, it won't prevent you from doing so. It's a bit messy, it's a bit hard to do, and you will forget things, you will stumble on issues and so on. So you can delegate the bookkeeping to a custom structure and it will do that for you. And what's more, it's usually better to have a good and legible interface. So for instance, here you've got an example which is taken from the library graphology, which implements graphs in JavaScript. And so you can just ask the out neighbors of a node, you can just iterate of the edges of a node, etc. So it's quite easy. And all this is done in constant time so you don't have to bother about indexing things. Yeah, so the first point is it's good because abstraction is a good thing. The second point is actually if you only use arrays and objects, you will mess up because it's not good enough. Sometimes you have to develop things which are a bit more complex. So that's just because like nowadays JavaScript and the web is not something for scripted kitties anymore. So Node.js became a thing. We have to process a lot of data on the client to be able to power useful applications. And sometimes you have algorithm which cannot be implemented without the use of custom algorithm and data structures. Dijkstra for instance, for the one who knows. And I will show you a concrete example. For instance, let's say you have a canvas, so HTML5 canvas, and you will draw points on the canvas. And now you just want to answer this precise question. My user has his mouse on the screen and you want to know if the mouse is on a node or a point. So this seems trivial and in the DOM it's really easy to do. But in Canvas, the naive approach is to test in an array all your points and say, is this node under my cursor? No. Is this not under my cursor? No. And so on and so forth. So the more points you have, the longer it will take. So then you will have to implement a structure which is called a quad tree, which is actually a recursive partition of the space. And so you will just like this and recursively into the tree to find the nodes you need to check. So basically it will change your linear time access into something which is more like logarithmic time access. So that was the second point. So first point is bookkeeping and abstraction is good. The second point is arrays and objects will only get you so far. You will need custom data structures. So the question is what are the challenges here when you try to implement data structures on JavaScript? Because you could implement data structures the old way like in C, C++ and so on. And it's quite easy to do. But in JavaScript you've got some traps and some pitfalls that you need to avoid and try to take a step back to be sure what are the challenges here. So the first one is that we JavaScript developers are handling a language which is interpreted. It's not compiled. So we are far from the metal. So we can't really know what's happening. The only thing is we have no control over the memory layout and how the memory is organized by the interpreter. And also we have no control ish over garbage collection. Garbage collection is a system that will like clean unused memory automatically for you. And it's quite painful to do something which can control the logic of this because it will slow down your code. Another challenge is that we all use just-in-time compilation schemes and optimizing engines such as Gecko and Firefox and V8 and Chrome. And those have their own logic and they will transform your code into something that is really alien to you and you don't have any control on what they will do. So how do you do to like implement something which is efficient? So basically the thing is, the gist here is that benchmarking code accurately in JavaScript is pretty hard. But it doesn't mean that we cannot do it and it doesn't mean that we cannot be clever about it. There is a lot of people on the Internet that will argue that since we cannot know anything, it doesn't matter anymore and you don't have to optimize code because all this is pointless and we are all going to die in devoid and oblivion. So don't do that. So I'm going to give you some implementation tips. So generic implementation tips on how to be able to like implement data structures efficiently in JavaScript without being killed by the engine and we are going to try to outsmart the engine in a way. So first thing is minimize your lookups. So lookup, what is a lookup? A lookup is if you need to access an object property, if you need to access, for instance, the key in a map or in a set, etc., those things are the most fucking costly thing in JavaScript. So if you minimize this, you will go up in performance. For instance here, you've got an example where in the graph, I just want to check some attribute of a node and the nodes are stored in the map. So what I do is that I first check that the map has the node to be sure I'm not doing something which is not possible and then I get the node. So there I did two lookups. This is bad. So here, I only made one because I just get the node. I infer from the fact that the data is undefined that the node doesn't exist and that's all. So I made one lookup. And if you do a quick benchmark about it, you will see that it's actually quite straightforward. Two lookups is 30 milliseconds and one lookup is 15. So it's quite half of the time. So the point here is that the engine is really clever, but it's not that clever. It's a bit dumb still. So it improves, frankly, though. So you have to benchmark things to be sure that you are not making something which is stupid. So the approach which is like, oh, I'm going to code like a Dirk or just I will make bad code and the engine will clean up for me and do things which are like blazing fast is stupid. It won't work. So first thing, don't use too much lookups. The second tip here is creating objects and allocating memory in JavaScript like in any language is very costly. So avoid allocating objects when you don't need to allocate objects. Avoid recreating regexes. For instance, if you create regexes in a function, you will have bad issues. And avoid nesting function when you can. So concretely, this looks like this. This is bad. This is good. So just offload the regex outside the function so that the engine won't be created each time. Here it's very, very bad. So you have an array for each. You iterate in here, just here, because you are nesting the look. You are going to create one function per fucking element in your array. So third thing, mixing types is really bad. In JavaScript, you don't mix type. Here you've got an example which is a bit distorted. So that's too bad. Okay, that's a shitty array anyway. So we've got an array which contains number, strings, strings looking a lot like numbers and this will mess up V8, for instance. You've got a regex and you've got an object. So if someone does that here, I want to meet you. Honestly, because I don't understand why you would want to do that. So next tip, and this is actually my favorite one, is the poor man's malloc. The malloc in C is a way to allocate some piece of contiguous memory. And so the gist is the following. So in JavaScript, recently we had a new thing, a new shiny thing which are byte arrays and typed byte arrays, which means that you can allocate an array of n elements using the given number type you want. For instance, you have unsigned integer 8 array. You've got float 32 array and you have a lot of types. And you can simulate a kind of memory allocation with that. And so you can be clever about it and cheat a little bit. So my point here is we can implement our own pointer system. So you can have your own C in JavaScript your own way. And this will speed up things and this will make memory really lighter. So let's use a concrete example to explain that because I guess it's a bit obscure. So who knows here what a linked list is? Okay, that's a fine thing. So a linked list is just like nodes linked to the one another with a pointer here which points to the next item. So here you've got a basic list. So A to B to C to the void in the oblivion of life. And so under it you've got object references as pointers. Because in JavaScript you don't have pointers, you don't have C pointers and so on. So the only way to simulate this is actually to use object properties. So basically any JavaScript person would do it in this way. So create a node which is a class, a kind of class, and have a next property which will be a reference to the next node. And so if you need to change a pointer, you just do node.next and you allocate the thing. This is the same way to do things. This is the insane way to do things but it's way faster. So basically we are going to do a linked list but we are going to roll our own pointers. So you have to keep an index which will be the head. And you will keep an array in which you will have your values, for instance NBAC. And in another array which will be a byte array for instance, and here you only need the UNT8 array, you will have an index pointing toward the next item in the list. So for instance 1, 2, 0. So this means that if you need to check which is the next item after B, you check the index of B in next which is 2. And then you check here, index 2 is here. So the next item is C. So this is how you can try to implement your own C pointers in JavaScript. So let's use a more concrete example to tell you why you would do that because linked lists are quite useless in most languages but you can do nice things with this. So I don't know if you know about a structure which is called an LRU cache but the LRU cache is actually an object which has a fixed size capacity in which you cannot set more than a fixed number of keys. It's a good thing when you have a constrained environment when memory is actually really critical and you need to save up some RAM. The idea here is that you only want to keep the most frequent key in the dictionary or in the object so you can like alleviate the other one in the map. So for instance if we had a new key and the object is already full, we are going to throw away the list recently used one. This is why it's called an LRU cache. So to implement an LRU cache what you have to do is to maintain an object, key to value, and you have to maintain a doubly linked list when you can go forward and backward because when you are going to like add a new thing and you need to throw away something you are going to take the last element and pop it away and take the first element and put it on top of the list. And in the same way if you are going to get an element in the list you are going to take it away from the list, put it back on front and so on. And so you can maintain a list of used items based on the list recently used etc. So what you would do in this precise case, you would have a pointer to the head, a pointer to the tail, an array of pointer pointing to next, an array pointing to the previous item and you would actually manage to do that. And so you only keep items as a JavaScript object pointing the key to the pointer and the pointer is just the index and you keep your values in an array. And so it may seem pointless but it's not. So here you've got this approach used there. So it kind of beats everything that was made before and the really good advantage is that it does not allocate, it does not garbage collect, you don't have garbage collection and it's really, really light in memory. So that was the third and most interesting tips. So to go fast on the last tips, function calls are costly in JavaScript like in any language. So everything is costly and life is hard so don't worry. So this means that usually a recursion is a worse idea than using iterative versions using stacks. So this for instance, recursion scheme to traverse a binary tree is actually slower than doing this strange alien but your mileage may vary so please benchmark it because sometimes it is the case, sometimes it's not. That's pointing back to the challenges earlier. Okay, and so last thing, what about Web SMB and so on? Because we are like, oh yeah JavaScript is so fast but we have faster things so you've got lots of shiny options, you have ASM.js, you've got WebAssembly and in Node.js for instance you can just use native C++ code and optimize things. But for data structure, if you need to keep a bridge to JavaScript and be able to use a set on the JavaScript site, the issue is that communication between those and JavaScript has a really heavy cost. So if you need to do a lot of computation on the WebAssembly side, it might be a good per boost. If you need to call back and forth between the WebAssembly and JavaScript really, really fast it will slow you down. It's improving and for instance in Firefox those kind of performance went really up but we are not there yet. So either you do everything in WebAssembly or you don't. Okay so as a conclusion and to wrap up all we said and learn, some parting words, so yes optimizing JavaScript is hard. But it does not mean we can do it and please do it. We can do it. So most tips I show you here are applicable to any kind of high level languages mostly but JavaScript has its own very kinks. For instance the byte array tips does not work in Python. If you try to use list in Python to simulate this kind of pointer it will go bad and if you use numpy it's even worse because you have like the bridge between native code and Python code. And so the gist is as a conclusion to be efficient your code must be statically interpretable. If you do that the engine will have no hard decision to make and if the engine has no hard decision to make the engine will safely choose the best path to optimize your code. So rephrase optimizing JavaScript is squinting a little and pretending really hard that the language is statically typed and that the language is low level. If you do that you will go fast. So just pretend that JavaScript is C and everything will roll. And so the next frontier if you want to like improve the data structure is that for now nobody has been able to beat associative arrays in JavaScript. It means that you cannot go faster than the map, you cannot go faster than the object. It's not possible yet when do we key value association. But maybe with some kind of trees or some clever hashing schemes we may be able to beat some native optimization on the JavaScript side by being clever. So please implement a way and use all those tips to like flourish and make a new data structure so we can all go lead a happier life. So some references to end and wrap up all those things. So all the examples you shown were actually taken from the following libraries. So you've got Nemonist which is a library implementing a lot of data structures in JavaScript with fancy APIs and TypeScript. You've got Graphology which deal with graphs and SigmaJS which is actually a graph rendering engine in the browser using WebGL and so on. So that's it basically. So thank you for your hour. Thank you a lot. Any questions? What? Here. This one. This one. This one. Yeah. Thank you very much for the presentation. I have two questions. What's your opinion about bubble and TypeScript because this is a transpire. So I heard about TypeScript but what was bubble? What is this? It's transpire. What? Transpire. Okay. So basically the just is a TypeScript will have no impact on your runtime because it's just on the translation time. But basically if you want to write performance code don't use bubble. Because bubble will use by default some kind of helpers to ensure that the specs are respected and sometimes those helpers are function which are costly and you don't have to do that. So either you transpire using the loose option in bubble or you don't use it and you write ECMA 5 code basically. And my second question is what's your opinion because on Medium has a lot of articles about how ECMA scripts use performance if you use only ECMA script 5. I'm not sure to get it. So your point would be some people say that if you use ECMA script 5 it gets better. Yes. Here's what articles for example if you use for each versus. Yeah sure. Sure sure. So yeah it's not about ECMA script 5 it's more generic thing which is if you use for each performances usually are bad because the loop will always be faster. But it's not related to ECMA 6 or 5 it's more like function called are costly so don't use them. Yeah follow up on that function are costly. Should we not use map reduce that often? I use it in application code because I'm like everyone I don't like to do for loops. It's a harsh way to do so. But when I write like optimization critical code I don't. But it's it's a bit weird because like in V8 like recently map became really fast and so it's okay. But if you need to ship code which will work in different node versions or in Gecko or so on you don't use map basically that's all. Any other question? Yeah. Hi thank you for presentation. This one question regarding similar question to the one person already asked about bubble transpiler. So yes if you use transpiler like that it really hurt our performances but code could be more maintainable. So yeah and also some other of your solutions look smart and but where's the boundary between performance and maintainability of project especially if more people are working on. Sure the boundary is yours to draw but basically the like data structures need to be optimized like really optimized so I will write code which is less maintainable in a way but that's the cost I have to pay to be sure that it's the best but for instance if I write application code I will never do those kind of silly things. I don't do that. So for data structures it's okay to have this kind of weird code but for anything over that I guess it's not an issue. Last question? Somebody? Okay. Hey. Hey. Do you use like some... Why no look into the Allah filter? You think you do wrong so you don't know that this is just stupid.
 So, hello everyone.  So first thing, who knows about data structures in the room?  Can you show your hand?  Okay, that's fine.  So this talk is called Developing Data Structures for JavaScript.  And so I'm really glad to be here on the back again, the JavaScript Dev Room.  And so I hope I will be able to entertain you during those next 20 minutes.  So who am I?  I'm messing up.  Ah, okay.  So the subject of this talk is why and how to implement data structure for JavaScript  and why is that a thing?  So who am I?  I'm Guillaume.  So I go on the internet by the infamous name of Young Githary Old, which is a shitty name,  but that's life.  And I'm a research engineer working for a research lab in Paris, which is called the  Media Lab.  So what's a data structure?  Just to be sure we agree on the same ground.  So a data structure is actually a way to organize and move data around in the computer, so we  are able to query and update it efficiently.  So basically when you deal with computer, you can sometimes trade off some memory space  to be able to do computation faster.  And so basically this is what encompasses data structure.  So for instance, in JavaScript, you have a lot of data structures.  You have arrays, you've got objects, set maps, and so on.  So we will start with some quotes from the internet.  So web development is not real development.  It ends fourth easier.  So this is bullshit.  Web development is trivial and web developers don't need fancy data structures or any solid  knowledge and algorithm.  So someone obviously still wrong.  So the point of my talk here is to show you that we can use data structure in JavaScript  and that's a good thing.  And if you do all do that, you will lead a happier life.  So the question is, don't we have already data structures in JavaScript?  For instance, we have arrays, we have objects, and now with ES6 we've got maps, we've got  sets.  So why the hell do we bother about custom data structures?  Isn't this really enough?  So why do we want other data structures?  So the first point is because it's convenient.  Like any other kind of abstraction, having data structure is convenient and it's easy  for you to do some kind of heavy bookkeeping using those custom data structures.  So I will use an example to clarify this point.  For instance, you can implement something which is called a multi-set.  A multi-set is actually a set in which you can store an item more than once.  So for instance, if you do some basic JavaScript and you need to count the number of occurrences  of an item in a sequence, you can do this Nasi code, you're going to iterate on this  list, and then you have to check if your item already exists in the list, and then you set  up the item to be zero, and then you increment it and so on.  So this is bookkeeping.  You have to track a lot of things and so on.  Whereas if you have a multi-set, you can just do that.  You have abstracted this complexity away, and then you are able to delegate the bookkeeping  to the custom data structure.  So this is a first example.  Another example would be more complex data structures because the multi-set is actually  really, really easy and straightforward.  But for instance, if you want to implement a graph, so a graph is nodes connected by  edges, and so this is actually quite doable if you only use arrays and objects, but you  have to keep a lot of indexations running correctly and smoothly.  For instance, if you want to check who which are the neighbors of a node, you have to index  that.  So if you do it by hand and you can do it, it won't prevent you from doing so.  It's a bit messy, it's a bit hard to do, and you will forget things, you will stumble on  issues and so on.  So you can delegate the bookkeeping to a custom structure and it will do that for you.  And what's more, it's usually better to have a good and legible interface.  So for instance, here you've got an example which is taken from the library graphology,  which implements graphs in JavaScript.  And so you can just ask the out neighbors of a node, you can just iterate of the edges  of a node, etc.  So it's quite easy.  And all this is done in constant time so you don't have to bother about indexing things.  Yeah, so the first point is it's good because abstraction is a good thing.  The second point is actually if you only use arrays and objects, you will mess up because  it's not good enough.  Sometimes you have to develop things which are a bit more complex.  So that's just because like nowadays JavaScript and the web is not something for scripted  kitties anymore.  So Node.js became a thing.  We have to process a lot of data on the client to be able to power useful applications.  And sometimes you have algorithm which cannot be implemented without the use of custom algorithm  and data structures.  Dijkstra for instance, for the one who knows.  And I will show you a concrete example.  For instance, let's say you have a canvas, so HTML5 canvas, and you will draw points  on the canvas.  And now you just want to answer this precise question.  My user has his mouse on the screen and you want to know if the mouse is on a node or  a point.  So this seems trivial and in the DOM it's really easy to do.  But in Canvas, the naive approach is to test in an array all your points and say, is this  node under my cursor?  No.  Is this not under my cursor?  No.  And so on and so forth.  So the more points you have, the longer it will take.  So then you will have to implement a structure which is called a quad tree, which is actually  a recursive partition of the space.  And so you will just like this and recursively into the tree to find the nodes you need to  check.  So basically it will change your linear time access into something which is more like logarithmic  time access.  So that was the second point.  So first point is bookkeeping and abstraction is good.  The second point is arrays and objects will only get you so far.  You will need custom data structures.  So the question is what are the challenges here when you try to implement data structures  on JavaScript?  Because you could implement data structures the old way like in C, C++ and so on.  And it's quite easy to do.  But in JavaScript you've got some traps and some pitfalls that you need to avoid and try  to take a step back to be sure what are the challenges here.  So the first one is that we JavaScript developers are handling a language which is interpreted.  It's not compiled.  So we are far from the metal.  So we can't really know what's happening.  The only thing is we have no control over the memory layout and how the memory is organized  by the interpreter.  And also we have no control ish over garbage collection.  Garbage collection is a system that will like clean unused memory automatically for you.  And it's quite painful to do something which can control the logic of this because it will  slow down your code.  Another challenge is that we all use just-in-time compilation schemes and optimizing engines  such as Gecko and Firefox and V8 and Chrome.  And those have their own logic and they will transform your code into something that is  really alien to you and you don't have any control on what they will do.  So how do you do to like implement something which is efficient?  So basically the thing is, the gist here is that benchmarking code accurately in JavaScript  is pretty hard.  But it doesn't mean that we cannot do it and it doesn't mean that we cannot be clever  about it.  There is a lot of people on the Internet that will argue that since we cannot know anything,  it doesn't matter anymore and you don't have to optimize code because all this is pointless  and we are all going to die in devoid and oblivion.  So don't do that.  So I'm going to give you some implementation tips.  So generic implementation tips on how to be able to like implement data structures efficiently  in JavaScript without being killed by the engine and we are going to try to outsmart  the engine in a way.  So first thing is minimize your lookups.  So lookup, what is a lookup?  A lookup is if you need to access an object property, if you need to access, for instance,  the key in a map or in a set, etc., those things are the most fucking costly thing in  JavaScript.  So if you minimize this, you will go up in performance.  For instance here, you've got an example where in the graph, I just want to check some attribute  of a node and the nodes are stored in the map.  So what I do is that I first check that the map has the node to be sure I'm not doing  something which is not possible and then I get the node.  So there I did two lookups.  This is bad.  So here, I only made one because I just get the node.  I infer from the fact that the data is undefined that the node doesn't exist and that's all.  So I made one lookup.  And if you do a quick benchmark about it, you will see that it's actually quite straightforward.  Two lookups is 30 milliseconds and one lookup is 15.  So it's quite half of the time.  So the point here is that the engine is really clever, but it's not that clever.  It's a bit dumb still.  So it improves, frankly, though.  So you have to benchmark things to be sure that you are not making something which is  stupid.  So the approach which is like, oh, I'm going to code like a Dirk or just I will make bad  code and the engine will clean up for me and do things which are like blazing fast is stupid.  It won't work.  So first thing, don't use too much lookups.  The second tip here is creating objects and allocating memory in JavaScript like in any  language is very costly.  So avoid allocating objects when you don't need to allocate objects.  Avoid recreating regexes.  For instance, if you create regexes in a function, you will have bad issues.  And avoid nesting function when you can.  So concretely, this looks like this.  This is bad.  This is good.  So just offload the regex outside the function so that the engine won't be created each time.  Here it's very, very bad.  So you have an array for each.  You iterate in here, just here, because you are nesting the look.  You are going to create one function per fucking element in your array.  So third thing, mixing types is really bad.  In JavaScript, you don't mix type.  Here you've got an example which is a bit distorted.  So that's too bad.  Okay, that's a shitty array anyway.  So we've got an array which contains number, strings, strings looking a lot like numbers  and this will mess up V8, for instance.  You've got a regex and you've got an object.  So if someone does that here, I want to meet you.  Honestly, because I don't understand why you would want to do that.  So next tip, and this is actually my favorite one, is the poor man's malloc.  The malloc in C is a way to allocate some piece of contiguous memory.  And so the gist is the following.  So in JavaScript, recently we had a new thing, a new shiny thing which are byte arrays and  typed byte arrays, which means that you can allocate an array of n elements using the  given number type you want.  For instance, you have unsigned integer 8 array.  You've got float 32 array and you have a lot of types.  And you can simulate a kind of memory allocation with that.  And so you can be clever about it and cheat a little bit.  So my point here is we can implement our own pointer system.  So you can have your own C in JavaScript your own way.  And this will speed up things and this will make memory really lighter.  So let's use a concrete example to explain that because I guess it's a bit obscure.  So who knows here what a linked list is?  Okay, that's a fine thing.  So a linked list is just like nodes linked to the one another with a pointer here which  points to the next item.  So here you've got a basic list.  So A to B to C to the void in the oblivion of life.  And so under it you've got object references as pointers.  Because in JavaScript you don't have pointers, you don't have C pointers and so on.  So the only way to simulate this is actually to use object properties.  So basically any JavaScript person would do it in this way.  So create a node which is a class, a kind of class, and have a next property which will  be a reference to the next node.  And so if you need to change a pointer, you just do node.next and you allocate the thing.  This is the same way to do things.  This is the insane way to do things but it's way faster.  So basically we are going to do a linked list but we are going to roll our own pointers.  So you have to keep an index which will be the head.  And you will keep an array in which you will have your values, for instance NBAC.  And in another array which will be a byte array for instance, and here you only need  the UNT8 array, you will have an index pointing toward the next item in the list.  So for instance 1, 2, 0.  So this means that if you need to check which is the next item after B, you check the index  of B in next which is 2.  And then you check here, index 2 is here.  So the next item is C.  So this is how you can try to implement your own C pointers in JavaScript.  So let's use a more concrete example to tell you why you would do that because linked lists  are quite useless in most languages but you can do nice things with this.  So I don't know if you know about a structure which is called an LRU cache but the LRU cache  is actually an object which has a fixed size capacity in which you cannot set more than  a fixed number of keys.  It's a good thing when you have a constrained environment when memory is actually really  critical and you need to save up some RAM.  The idea here is that you only want to keep the most frequent key in the dictionary or  in the object so you can like alleviate the other one in the map.  So for instance if we had a new key and the object is already full, we are going to throw  away the list recently used one.  This is why it's called an LRU cache.  So to implement an LRU cache what you have to do is to maintain an object, key to value,  and you have to maintain a doubly linked list when you can go forward and backward because  when you are going to like add a new thing and you need to throw away something you are  going to take the last element and pop it away and take the first element and put it  on top of the list.  And in the same way if you are going to get an element in the list you are going to take  it away from the list, put it back on front and so on.  And so you can maintain a list of used items based on the list recently used etc.  So what you would do in this precise case, you would have a pointer to the head, a pointer  to the tail, an array of pointer pointing to next, an array pointing to the previous  item and you would actually manage to do that.  And so you only keep items as a JavaScript object pointing the key to the pointer and  the pointer is just the index and you keep your values in an array.  And so it may seem pointless but it's not.  So here you've got this approach used there.  So it kind of beats everything that was made before and the really good advantage is that  it does not allocate, it does not garbage collect, you don't have garbage collection  and it's really, really light in memory.  So that was the third and most interesting tips.  So to go fast on the last tips, function calls are costly in JavaScript like in any  language.  So everything is costly and life is hard so don't worry.  So this means that usually a recursion is a worse idea than using iterative versions  using stacks.  So this for instance, recursion scheme to traverse a binary tree is actually slower  than doing this strange alien but your mileage may vary so please benchmark it because sometimes  it is the case, sometimes it's not.  That's pointing back to the challenges earlier.  Okay, and so last thing, what about Web SMB and so on?  Because we are like, oh yeah JavaScript is so fast but we have faster things so you've  got lots of shiny options, you have ASM.js, you've got WebAssembly and in Node.js for  instance you can just use native C++ code and optimize things.  But for data structure, if you need to keep a bridge to JavaScript and be able to use  a set on the JavaScript site, the issue is that communication between those and JavaScript  has a really heavy cost.  So if you need to do a lot of computation on the WebAssembly side, it might be a good  per boost.  If you need to call back and forth between the WebAssembly and JavaScript really, really  fast it will slow you down.  It's improving and for instance in Firefox those kind of performance went really up but  we are not there yet.  So either you do everything in WebAssembly or you don't.  Okay so as a conclusion and to wrap up all we said and learn, some parting words, so  yes optimizing JavaScript is hard.  But it does not mean we can do it and please do it.  We can do it.  So most tips I show you here are applicable to any kind of high level languages mostly  but JavaScript has its own very kinks.  For instance the byte array tips does not work in Python.  If you try to use list in Python to simulate this kind of pointer it will go bad and if  you use numpy it's even worse because you have like the bridge between native code and  Python code.  And so the gist is as a conclusion to be efficient your code must be statically interpretable.  If you do that the engine will have no hard decision to make and if the engine has no  hard decision to make the engine will safely choose the best path to optimize your code.  So rephrase optimizing JavaScript is squinting a little and pretending really hard that the  language is statically typed and that the language is low level.  If you do that you will go fast.  So just pretend that JavaScript is C and everything will roll.  And so the next frontier if you want to like improve the data structure is that for now  nobody has been able to beat associative arrays in JavaScript.  It means that you cannot go faster than the map, you cannot go faster than the object.  It's not possible yet when do we key value association.  But maybe with some kind of trees or some clever hashing schemes we may be able to beat  some native optimization on the JavaScript side by being clever.  So please implement a way and use all those tips to like flourish and make a new data  structure so we can all go lead a happier life.  So some references to end and wrap up all those things.  So all the examples you shown were actually taken from the following libraries.  So you've got Nemonist which is a library implementing a lot of data structures in JavaScript  with fancy APIs and TypeScript.  You've got Graphology which deal with graphs and SigmaJS which is actually a graph rendering  engine in the browser using WebGL and so on.  So that's it basically.  So thank you for your hour.  Thank you a lot.  Any questions?  What?  Here.  This one.  This one.  This one.  Yeah.  Thank you very much for the presentation.  I have two questions.  What's your opinion about bubble and TypeScript because this is a transpire.  So I heard about TypeScript but what was bubble?  What is this?  It's transpire.  What?  Transpire.  Okay.  So basically the just is a TypeScript will have no impact on your runtime because it's just  on the translation time.  But basically if you want to write performance code don't use bubble.  Because bubble will use by default some kind of helpers to ensure that the specs are respected  and sometimes those helpers are function which are costly and you don't have to do that.  So either you transpire using the loose option in bubble or you don't use it and you write  ECMA 5 code basically.  And my second question is what's your opinion because on Medium has a lot of articles about  how ECMA scripts use performance if you use only ECMA script 5.  I'm not sure to get it.  So your point would be some people say that if you use ECMA script 5 it gets better.  Yes.  Here's what articles for example if you use for each versus.  Yeah sure.  Sure sure.  So yeah it's not about ECMA script 5 it's more generic thing which is if you use for  each performances usually are bad because the loop will always be faster.  But it's not related to ECMA 6 or 5 it's more like function called are costly so don't  use them.  Yeah follow up on that function are costly.  Should we not use map reduce that often?  I use it in application code because I'm like everyone I don't like to do for loops.  It's a harsh way to do so.  But when I write like optimization critical code I don't.  But it's it's a bit weird because like in V8 like recently map became really fast and  so it's okay.  But if you need to ship code which will work in different node versions or in Gecko or  so on you don't use map basically that's all.  Any other question?  Yeah.  Hi thank you for presentation.  This one question regarding similar question to the one person already asked about bubble  transpiler.  So yes if you use transpiler like that it really hurt our performances but code could  be more maintainable.  So yeah and also some other of your solutions look smart and but where's the boundary between  performance and maintainability of project especially if more people are working on.  Sure the boundary is yours to draw but basically the like data structures need to be optimized  like really optimized so I will write code which is less maintainable in a way but that's  the cost I have to pay to be sure that it's the best but for instance if I write application  code I will never do those kind of silly things.  I don't do that.  So for data structures it's okay to have this kind of weird code but for anything over  that I guess it's not an issue.  Last question?  Somebody?  Okay.  Hey.  Hey.  Do you use like some...  Why no look into the Allah filter?  You think you do wrong so you don't know that this is just stupid.
Developing_data_structures_for_JavaScript_Why_and_how_to_implement_efficient_data_structures_to_use__0_47.png Developing_data_structures_for_JavaScript_Why_and_how_to_implement_efficient_data_structures_to_use__48_107.png Developing_data_structures_for_JavaScript_Why_and_how_to_implement_efficient_data_structures_to_use__108_839.png Developing_data_structures_for_JavaScript_Why_and_how_to_implement_efficient_data_structures_to_use__840_1067.png Developing_data_structures_for_JavaScript_Why_and_how_to_implement_efficient_data_structures_to_use__1068_2507.png Developing_data_structures_for_JavaScript_Why_and_how_to_implement_efficient_data_structures_to_use__2508_2987.png Developing_data_structures_for_JavaScript_Why_and_how_to_implement_efficient_data_structures_to_use__2988_3515.png Developing_data_structures_for_JavaScript_Why_and_how_to_implement_efficient_data_structures_to_use__3516_3899.png Developing_data_structures_for_JavaScript_Why_and_how_to_implement_efficient_data_structures_to_use__3900_4955.png Developing_data_structures_for_JavaScript_Why_and_how_to_implement_efficient_data_structures_to_use__4956_5051.png Developing_data_structures_for_JavaScript_Why_and_how_to_implement_efficient_data_structures_to_use__5052_5123.png Developing_data_structures_for_JavaScript_Why_and_how_to_implement_efficient_data_structures_to_use__5124_6083.png Developing_data_structures_for_JavaScript_Why_and_how_to_implement_efficient_data_structures_to_use__6084_13427.png Developing_data_structures_for_JavaScript_Why_and_how_to_implement_efficient_data_structures_to_use__13428_13739.png Developing_data_structures_for_JavaScript_Why_and_how_to_implement_efficient_data_structures_to_use__13740_14759.png Developing_data_structures_for_JavaScript_Why_and_how_to_implement_efficient_data_structures_to_use__14760_16043.png Developing_data_structures_for_JavaScript_Why_and_how_to_implement_efficient_data_structures_to_use__16044_17855.png Developing_data_structures_for_JavaScript_Why_and_how_to_implement_efficient_data_structures_to_use__17856_18251.png Developing_data_structures_for_JavaScript_Why_and_how_to_implement_efficient_data_structures_to_use__18252_19703.png Developing_data_structures_for_JavaScript_Why_and_how_to_implement_efficient_data_structures_to_use__19704_21011.png Developing_data_structures_for_JavaScript_Why_and_how_to_implement_efficient_data_structures_to_use__21012_21107.png Developing_data_structures_for_JavaScript_Why_and_how_to_implement_efficient_data_structures_to_use__21108_21299.png Developing_data_structures_for_JavaScript_Why_and_how_to_implement_efficient_data_structures_to_use__21300_23339.png Developing_data_structures_for_JavaScript_Why_and_how_to_implement_efficient_data_structures_to_use__23340_24011.png Developing_data_structures_for_JavaScript_Why_and_how_to_implement_efficient_data_structures_to_use__24012_24995.png Developing_data_structures_for_JavaScript_Why_and_how_to_implement_efficient_data_structures_to_use__24996_25163.png Developing_data_structures_for_JavaScript_Why_and_how_to_implement_efficient_data_structures_to_use__25164_25511.png Developing_data_structures_for_JavaScript_Why_and_how_to_implement_efficient_data_structures_to_use__25512_27899.png Developing_data_structures_for_JavaScript_Why_and_how_to_implement_efficient_data_structures_to_use__27900_28847.png Developing_data_structures_for_JavaScript_Why_and_how_to_implement_efficient_data_structures_to_use__28848_30551.png Developing_data_structures_for_JavaScript_Why_and_how_to_implement_efficient_data_structures_to_use__30552_36635.png Developing_data_structures_for_JavaScript_Why_and_how_to_implement_efficient_data_structures_to_use__36636_36752.png