JavaScript Math.sqrt performance

Question

Through code profiling, I have found the Math.sqrt function specifically to be a major bottleneck in a large doubly-nested loop that runs every timestep in my program. Is there any way to improve its performance? Should I inline some kind of iterative calculation, or lookup table-based calculation?

Any help would be greatly appreciated!

I cannot replace it with a squares calculation instead, since it is not a comparison.

EDIT: The relevant portion of the code looks roughly as follows

var width = 2000;
var height = 2000;

function update() {
    for (var j = 0; j < height; ++j) {
        for (var i = 0; i < width; ++i) {
            array[i][j] = Math.sqrt(/* some expression involving i and j */);
        }
    }
}

var fps = 60;
setInterval(update, 1000 / fps);

Answer 1

Without further details, the question can only be answered in a general sense, I'm afraid.

Do Not Re-Invent the Wheel

So should You, generally speaking, try to re-implement Math.sqrt using lookup tables and whatnot? I would strongly advise against that. You would be hard pressed to even come close to the default JSVM implementation. It's not even a fair fight: The JavaScript Virtual Machine (JSVM) has access to native code and even hardware instructions that You likely do not.

So what can You do? In the following, You will find some suggestions, in the order in which I would personally try them:

Swapping Loop Variables

In Your given example, the order of loop variables is sub-optimal. The better order would be:

for(let i = 0; i < width ; ++i)
for(let j = 0; j < height; ++j)
  array[i][j] = Math.sqrt(/* some expression involving i and j */);

This should be significantly faster because array is actually an Array of Array references, i.e. every time You call array[i] for a different i, a new Array object has to be looked up in memory. It is much more cache friendly to process the inner Arrays one after another.

Motivate the JSVM to use float32

I have not actually tested this, but You might be able to tell the JSVM to use float32 precision instead of float64. One way to do that might be to use a lot of Math.fround calls, something along the lines of:

for(let i = 0; i < width ; ++i)
for(let j = 0; j < height; ++j)
  array[i][j] = Math.fround( Math.sqrt( Math.fround(/* some expression involving i and j */) ) );

You should always benchmark to see if this gives You any performance gains at all.

Another way to to enforce float32 is to use Float32Array as inner arrays. Not only do Float32Arrays give type information to the JSVM. They also have half the memory size compared to Arrays of Numbers, i.e. it should increase Your throughput.

const array = Array.from({length: width}, () => new Float32Array(height));

for(let i = 0; i < width ; ++i)
for(let j = 0; j < height; ++j)
  array[i][j] = Math.sqrt(/* some expression involving i and j */);

For more information on this topic, see this blog post.

Fast inverse square root

If You are using the square root to normalize vectors for computer graphics, there is a bonkers approximation of the inverse square root that was originally used in the Quake 3 engine. It might be faster than 1/Math.sqrt(y). As always, benchmarking is Your best friend.

Math.hypot()

If You do something along the lines of Math.sqrt(x*x + y*y + ...), You can try to use Math.hypot(x,y,...) instead. It might be a tiny bit faster and, on top of that, it is underflow- and overflow-safe.

Use the WebGL/WebGPU/tensorflow.js

If all else fails You can try to use GPU acceleration to speed up Your computations. The easiest way to to that might be using some machine learning framework like tensorflow.js.

import * as tf from '@tensorflow/tfjs';

tf.setBackend('webgl');

const sqrt = await tf.sqrt(array).array();

console.log({sqrt});

Moving data to and from the GPU comes with some overhead, so this might only give performance benefits if You off-load more than just the sqrt operation to the GPU.

You can of course use WebGL or WebGPU direcly, but it will be a lot more work.

Answer 2

As your iterating in a 2-dimensional array you can reduce the iterations by ~2.

For instance :

if your expression is i x j, and your array is 3-3 size starting from 0 your going to compute in your loop :

• 0*1 AND 1*0
• 0*2 AND 2*0
• 1*2 AND 2*1

which is the same

0x0 1x0 2x0

0x1 1x1 2x1

0x2 1x2 2x2