Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Javascript Performance: Modulus operation of negative Number within decrementing loop slowing the code by more than 100%

I was going through Eloquent JavaScript (again) and came across exercise "Chess Board" of Chapter 2. I had my one decent version of solution written back in the day when I was first time reading it, and another version of solution provided at the Elequent Javascript website. I'm one of the newbies that wanna be super-efficient programmers with only one question in their head: "Can I make it work a tad faster or smaller in anyway?"

So, during my search on the web few months ago, I came across a question on Stack Overflow, regarding for loop vs while loop on basis of performance. Since in that thread it was mentioned for loops are slower than while and loops with decrementing iterator are faster so I rewrote the code for better performance.

Here's the new version with for replaced with while and conditions edited for decrementing:

console.time("looping");
var gridSize = 5000, str = '', i = gridSize, j;
while (i--) {
  j = gridSize;
  while (j--) {
    if ((i - j) % 2 === 0)
      str += " ";
    else
      str += "#";
  }
  str += "\n";
}

//console.log(str);
console.timeEnd("looping");

But to my surprise this code had even worse performance. Then, after a while I found out that if ((i - j) % 2 === 0) was the main culprit, replacing minus sign with plus reduced the total time of execution to ~ 750ms

//Checked on NODE.js = v6.11.2
Book version of code         -->    893.76 ms
while loop with subtraction  -->    1562.43 ms
while loop with addition     -->    749.62 ms


//firefox Benchmark v54.0 (64-bit) (OS Ubuntu 16.04)
Book version of code         -->    725.10 ms
while loop with subtraction  -->    1565.29 ms
while loop with addition     -->    601.12 ms

Why is subtraction having such huge impact on total execution time?

Edit 01 6:30 AM (GMT) 8th August

After looking at @jaromandaX answer I'm Pretty sure that it is not the subtracting thats slowing down this loop, its the modulo of negative Number. Again I wanna know what makes modulo of negative number slower

like image 802
Syed Huzaifa Hassan Avatar asked Aug 08 '17 04:08

Syed Huzaifa Hassan


People also ask

How does JavaScript handle negative modulo?

When remainder or %(modulo) is calculated on positive numbers then both behave similar but when negative numbers are used then both behave differently. The JavaScript %(modulo) behaves like remainder operation and gives the remainder and as the number is negative therefore remainder also comes out to be negative.

What happens when you use the modulo operator with negative numbers?

If both the divisor and dividend are negative, then both truncated division and floored division return the negative remainder.

How do you modulo operation on a negative number?

The modulus of a negative number is found by ignoring the minus sign. The modulus of a number is denoted by writing vertical lines around the number. Note also that the modulus of a negative number can be found by multiplying it by −1 since, for example, −(−8) = 8.

What is the purpose modulo (%) operator in JavaScript?

The modulus operator ( % ) returns the division remainder.


1 Answers

instead of using the costly modular operation in

((i - j) % 2 === 0)

you can use bitwise operations

(((i-j)&1) === 0)

As suggested by SBS in the comments you should also try

(((i^j)&1) === 0)
like image 142
marvel308 Avatar answered Oct 14 '22 00:10

marvel308