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?
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
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.
If both the divisor and dividend are negative, then both truncated division and floored division return the negative remainder.
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.
The modulus operator ( % ) returns the division remainder.
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)
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With