3 ms·

The big thing that makes javascript slow (that the optimizer can’t really fix) is complex data structures. For example, if you want to implement an editable st

The big thing that makes javascript slow (that the optimizer can’t really fix) is complex data structures. For example, if you want to implement an editable string, you have to do so using an array of smaller strings and hope the optimizer can figure it out, or slice() and re-join a single “immutable” string. Either way, your javascript code will be slower than the C/rust equivalent because the language is less expressive. Javascript has the same problem with b-trees, skip lists, ropes, gap buffers, AABB trees, and so on. You can implement all of this stuff in javascript - you just end up with much more memory indirection than you want. And for trees with different internal nodes and leaves, your code will give the optimizer indigestion. In my experience, basically any of these data structures will run about 10-200x slower than their native counterparts. (If both are well optimized). To me this is the big performance advantage wasm has - that we can make high performance data structures. I’m working on a CRDT in Rust. The fastest JS implementation I know of takes about 1 second to replay an editing trace from a user. In rust I can replay the same trace in 0.01 seconds (100x faster), by using a skip list. In wasm I can do it in about 0.03 seconds.

criticaltinker 5y ago
Adding to this great comment with my own experience at work where we extensively use signal processing and time series compression algorithms to visualize large amounts of biological signals in the browser. WebAssembly is less than 10%-20% slower than native code in our benchmarks and tests for algorithms like fast wavelet transform and bit packing. WA allows us to aggressively optimize ahead of time when compiling, and be less sensitive to JS engine performance pitfalls around JIT optimization and garbage collection.
- pistachiopro 5y ago
  Throwing in my data: for physics simulation code, WASM vs native was identical, provided the native code was compiled with automatic SIMD optimizations disabled. On the one hand, that speaks well of the idea of web assembly, on the other, disabling SIMD is highly artificial. It's good to see basic SIMD being made standard, though the 256-bit wide SIMD instructions are still being finalized, and those will be necessary to really have a chance at evening out performance vs. native.
pattrn 5y ago
What are your thoughts on the Javascript YJS CRDT implementation? I'm admittedly pretty new to the space, so I don't know much about performance comparisons. Haven't noticed any significant performance problems with it (using it for collaborative editing on ~100,000 word documents), but would love hearing what you think.
- josephg 5y ago
  Eh. Its fine. I think its the best CRDT out there right now (but Kevin had a few years' head start on me!). I haven't done a lot with yjs personally. And I don't agree with a few of Kevin Jahns's design decisions, but none of them are deal-breakers: - The way deleted data is encoded in yjs is awkward. Versions store a list of which content has been deleted. So versions are bigger than they need to be, and you can't replay the editing history without stored snapshots. I think the knowledge of which elements have been deleted should just be saved into the binary format alongside the inserts. - For javascript objects, yjs pretends each value is actually a list (with everything after the first element ignored) so it can reuse the logic for list editing. This is overcomplicated compared to Shelf or something like it. - Yjs's internal structure is a linked list with cached offsets. This works ok in practice because inserts usually appear close to each other, but it means yjs has O(n^2) performance to process n edits rather than O(n log n). Diamond types (via wasm) is about 30x faster as a result - though as you say, yjs is still plenty fast enough in practice for most applications. And this gap will narrow once Yrs is working well. - Yjs can have an interleaving problem when concurrent items are prepended at the same location in a list. - The current (new) diamond types file format stores the origin-position + parents information instead of storing left-origin / right-origin fields. This lets DT have a smaller file size while storing more information than yjs stores. And I think this format is easier for applications to encode and work with, and it will make pruning easier when we get to it. We should also be able to load & save faster than yjs - but I'm not benchmarking that yet. But all of this stuff is pretty minor. Yjs works well in practice, and its quite mature. Performance will only get better with the yrs rust implementation. For diamond types, I had the benefit of being able to copy some fantastic implementation ideas from Yjs. If diamond types is better than yjs, its because I'm standing on its shoulders.
alephnan 5y ago
> Javascript has the same problem with b-trees, skip lists, ropes, gap buffers, AABB trees, and so on. You can implement all of this stuff in javascript - you just end up with much more memory indirection than you want. And for trees with different internal nodes and leaves, your code will give the optimizer indigestion. I'm building a text editor right now. I'm just using a giant array with one element for each line. I anticipated that it would get slow, and that potentially I can push this into WebAssembly. The problem is that you're going to need to get the data back out of WASM eventually, back into JavaScript and then back to the DOM. I focused on other optimizations and strangely my text editor is able to keep 9 million loC file ( over 500mb ) in memory. The trick is to not render everything to the DOM, just the stuff people are looking at. That's the other bottleneck. V8 is surprisingly smart. Random access for a small section of that 9 million element array is still fast. You'd expect this array to be non linear, too. Moreover, even localized shifts are fast. I'm puzzled. For comparison, VSCode uses a more esoteric data structure called a PieceTree but for me becomes unresponsive at 500k LoC. To be fair, they have other sorts of overhead and processing layers to deal with, namely building an AST with potentially thousands of layer of hierarchical / code folding. Speaking of which, VSCode is built entirely in TypeScript and has a reputation of being a fast and snappy editor. At any rate, I don't buy the argument that because Rust is fast and WebAssembly is comparably fast, then it makes sense to push your data structure, especially a text buffer, down into WebAssembly. The bottleneck is serializing data back and forth between WebAssembly and JavaScript. For text editors, I'm not sure this overhead is worth it, especially when V8 / Chrome is doing some crazy JS optimization behind the scenes. The appealing bit with WebAssembly is potentially that objects will have a smaller memory footprint, therefore we can push further than this 9 million LoC limit where the Chrome tab just runs out of memory, rather than having algorithmic slowdown.
- mejutoco 5y ago
  > The problem is that you're going to need to get the data back out of WASM eventually, back into JavaScript and then back to the DOM. Could you paint everything in a canvas element to avoid the DOM? That is being my approach in a small project, although it admitedly can complicate things.

criticaltinker 5y ago

Adding to this great comment with my own experience at work where we extensively use signal processing and time series compression algorithms to visualize large amounts of biological signals in the browser. WebAssembly is less than 10%-20% slower than native code in our benchmarks and tests for algorithms like fast wavelet transform and bit packing. WA allows us to aggressively optimize ahead of time when compiling, and be less sensitive to JS engine performance pitfalls around JIT optimization and garbage collection.

pistachiopro 5y ago
Throwing in my data: for physics simulation code, WASM vs native was identical, provided the native code was compiled with automatic SIMD optimizations disabled. On the one hand, that speaks well of the idea of web assembly, on the other, disabling SIMD is highly artificial. It's good to see basic SIMD being made standard, though the 256-bit wide SIMD instructions are still being finalized, and those will be necessary to really have a chance at evening out performance vs. native.

pattrn 5y ago

What are your thoughts on the Javascript YJS CRDT implementation? I'm admittedly pretty new to the space, so I don't know much about performance comparisons. Haven't noticed any significant performance problems with it (using it for collaborative editing on ~100,000 word documents), but would love hearing what you think.

josephg 5y ago
Eh. Its fine. I think its the best CRDT out there right now (but Kevin had a few years' head start on me!). I haven't done a lot with yjs personally. And I don't agree with a few of Kevin Jahns's design decisions, but none of them are deal-breakers: - The way deleted data is encoded in yjs is awkward. Versions store a list of which content has been deleted. So versions are bigger than they need to be, and you can't replay the editing history without stored snapshots. I think the knowledge of which elements have been deleted should just be saved into the binary format alongside the inserts. - For javascript objects, yjs pretends each value is actually a list (with everything after the first element ignored) so it can reuse the logic for list editing. This is overcomplicated compared to Shelf or something like it. - Yjs's internal structure is a linked list with cached offsets. This works ok in practice because inserts usually appear close to each other, but it means yjs has O(n^2) performance to process n edits rather than O(n log n). Diamond types (via wasm) is about 30x faster as a result - though as you say, yjs is still plenty fast enough in practice for most applications. And this gap will narrow once Yrs is working well. - Yjs can have an interleaving problem when concurrent items are prepended at the same location in a list. - The current (new) diamond types file format stores the origin-position + parents information instead of storing left-origin / right-origin fields. This lets DT have a smaller file size while storing more information than yjs stores. And I think this format is easier for applications to encode and work with, and it will make pruning easier when we get to it. We should also be able to load & save faster than yjs - but I'm not benchmarking that yet. But all of this stuff is pretty minor. Yjs works well in practice, and its quite mature. Performance will only get better with the yrs rust implementation. For diamond types, I had the benefit of being able to copy some fantastic implementation ideas from Yjs. If diamond types is better than yjs, its because I'm standing on its shoulders.

alephnan 5y ago

> Javascript has the same problem with b-trees, skip lists, ropes, gap buffers, AABB trees, and so on. You can implement all of this stuff in javascript - you just end up with much more memory indirection than you want. And for trees with different internal nodes and leaves, your code will give the optimizer indigestion. I'm building a text editor right now. I'm just using a giant array with one element for each line. I anticipated that it would get slow, and that potentially I can push this into WebAssembly. The problem is that you're going to need to get the data back out of WASM eventually, back into JavaScript and then back to the DOM. I focused on other optimizations and strangely my text editor is able to keep 9 million loC file ( over 500mb ) in memory. The trick is to not render everything to the DOM, just the stuff people are looking at. That's the other bottleneck. V8 is surprisingly smart. Random access for a small section of that 9 million element array is still fast. You'd expect this array to be non linear, too. Moreover, even localized shifts are fast. I'm puzzled. For comparison, VSCode uses a more esoteric data structure called a PieceTree but for me becomes unresponsive at 500k LoC. To be fair, they have other sorts of overhead and processing layers to deal with, namely building an AST with potentially thousands of layer of hierarchical / code folding. Speaking of which, VSCode is built entirely in TypeScript and has a reputation of being a fast and snappy editor. At any rate, I don't buy the argument that because Rust is fast and WebAssembly is comparably fast, then it makes sense to push your data structure, especially a text buffer, down into WebAssembly. The bottleneck is serializing data back and forth between WebAssembly and JavaScript. For text editors, I'm not sure this overhead is worth it, especially when V8 / Chrome is doing some crazy JS optimization behind the scenes. The appealing bit with WebAssembly is potentially that objects will have a smaller memory footprint, therefore we can push further than this 9 million LoC limit where the Chrome tab just runs out of memory, rather than having algorithmic slowdown.

mejutoco 5y ago
> The problem is that you're going to need to get the data back out of WASM eventually, back into JavaScript and then back to the DOM. Could you paint everything in a canvas element to avoid the DOM? That is being my approach in a small project, although it admitedly can complicate things.