Wormholes in JavaScript

Hi, Habr! I present to you the translation of the article "Wormholes in JavaScript" by Mathius Buus.

Computers are interesting machines. In theory, they appear to us to be ideal mechanical mathematicians working with numbers and performing well the operations of addition, multiplication, and subtraction.

However, such an abstraction is rather deceptive. It leads us away from the understanding that a computer handles various mathematical operations at different speeds. If you are writing in JavaScript (or in any other language) and are concerned about the performance of the algorithms you have written, it is very important to understand how computers work under the hood.

If we know what a computer is capable of, we can use shortcuts or wormholes to make our programs much faster than we expected.

Wormhole in the operation of obtaining the remainder of the division

What exactly does this mean? Let's look at an example: imagine that we want to implement a ring list . A ring list is a list with a fixed size in which the inserts are larger than the size of the list are moved to the top of the list and in a circle. Ring lists are very convenient for many things — such as collecting statistics at specific time intervals, data buffering, and more, but look at this implementation:

const list = new Array(15000) function set (i, item) { //  % -   ,     //        //    ,     i    list[i % list.length] = item } 

How fast is this code executed? Let's run a simple speed test

 console.time() for (var i = 0; i < 1e9; i++) { set(i, i) } console.timeEnd() 

On my computer, it took ~ 4 seconds to 1 billion inserts. Not bad.

However, let's apply the computational molehole and change the size of the array to a magic number:

 //     15000  16384 const list = new Array(16384) function set (i, item) { //  % -   ,     //        //    ,     i    list[i % list.length] = item } 

Try running the performance test again. On my computer, the test ran in ~ 1.5 seconds. More than double the increase by simply resizing. In order to understand why this is happening, we need to understand the following, under the hood, the computer works with numbers with a base of 2. It is important to know if we get the remainder of the division (operation%). This calculation is much easier to make if the number is a multiple of 2 (2 ^ n) b 16384 is 2 ^ 14. In fact, the computer looks at the number in binary form and just takes the last n bits.

For example: what will happen when performing such an operation 353,500% 16,384? 353,500 in the binary representation will look like 1010110010011011100. Since 16384 == 2 ^ 14 - we need to take the last 14 bits - 10101 (10010011011100) or 9,346.

We can use this knowledge in relation to another wormhole. It is very easy and quick for a computer to take the last n bits. In fact, it is only necessary to perform a binary and (operation &) with the number (2 ^ n) - 1

 const list = new Array(16384) function set (i, item) { //    &( )  %    2 ^ n list[i & (list.length - 1)] = i } 

By running the performance test on my computer again, we will see that the execution time is reduced to ~ 1s or there is a fourfold increase in performance compared to the first run. And all this by understanding how the computer works.

Smart compilers or VM are capable of such optimization, turning backstage into a bitwise operation and vice versa. In fact, the last V8 Javascript VM (not implemented in NodeJS) does just that.

Numeric wormholes

Another useful wormhole is understanding how reading and writing numbers work. Remember how we used 32-bit computers and how did we get 64 bits? And up to 32 bits we had 16 bits. What exactly does this mean? Usually we think of it this way - how much RAM we have on the computer. 2 ^ 32 = 4294967296 or 4 GB, which means that we can access only 4 GB of memory on a 32-bit computer. When we write a JS program, we usually do not need to think about it, since we usually do not use as much memory.

However, it is very important to understand the difference between 32-bit and 64-bit computers. Since the processors received 64-bit registers on 64-bit computers, the performance of operations became 2 times faster than on 32-bit computers, where you only had 32-bit registers.

How can we use information about this molehill?
Let's write a simple program that copies one Uint8Array to another. If you are not familiar with Unit8Arrays - they are very similar to the Buffers in NodeJS, or simply “pure” memory.

 function copy (input, output) { //    input.length <= output.length for (var i = 0; i < input.length; i++) { //   8-  (byte) output[i] = input[i] } } 

Again, let's measure the speed by running a performance test.

 //    1MB Uint8Arrays     const input = new Uint8Array(1024 * 1024) const output = new Uint8Array(1024 * 1024) console.time() for (var i = 0; i < 1e4; i++) { copy(input, output) } console.timeEnd() 

On my computer, the program ran in ~ 7.5 seconds. How can we use the molehole to accelerate? Using Uint8Array we copy only 8 bits at a time, but having a 64-bit computer - we can copy 64 bits of information in the same time. We can do this in JavaScript by converting our Uint8Array to Float64Array before copying, which will cost us nothing.

 function copy (input, output) { //    input.length <= output.length //       64-  //        , //      64-  //  BigInts   JavaScript,    BigInt64Array. const input64 = new Float64Array(input.buffer, input.byteOffset, input.length / 8) const output64 = new Float64Array(output.buffer, output.byteOffset, output.length / 8) for (var i = 0; i < input64.length; i++) { //   64-  output64[i] = input64[i] } } 

Running the performance tests again we get a runtime equal to 1 sec, which gives an 8-fold increase in speed.

To copy an acceptable solution would be to use the array.set (otherArray) method for Uint8Array, which gives us copying in native code — which is much faster than any other mole holes. For reference, this will give a result of ~ 0.2 seconds of execution in our test on my computer, which is 5 times faster than the previous solution.

The galaxy javascript is full of nipples

Using the wormhole mentioned above will help you make tons of real algorithms much faster. There are many more such wormholes. My favorite is Math.clz32 , a method that returns the number of leading zero bits in a 32-bit binary representation of a number. We can use this method for a variety of interesting algorithms. I used it to speed up the implementation of bit fields by 4 times, which led to a decrease in memory consumption also by 4 times and allowed me to sort the numbers much faster in some situations.

Understanding the basic principles of the computer allows you to write the fastest programs that we need. This knowledge matters even when you write in a high-level language like JavaScript.

PS:

Special thanks for the help in translating and correcting the translation for Olga Pereverzeva