2
\$\begingroup\$

I am wondering how I can improve the runtime of this code. I was solving this task at leetcode, and came up with this solution. But I got the result that my runtime is 88 ms, which beats a bit more than 79% of other submissions, so I wonder what else could be improved in this code.

var hammingDistance = function(x, y) {
   const startPoint = x > y ? x : y;
   let count = 0;
   for (let i = Math.floor(Math.log2(startPoint)); i >= 0; i--) {
      xPositiveBit = x/Math.pow(2, i) >= 1;
      yPositiveBit = y/Math.pow(2, i) >= 1;
      if (xPositiveBit) {
        x = x%Math.pow(2, i);
      }
      if (yPositiveBit) {
        y = y%Math.pow(2, i);
      }  
      if (( xPositiveBit || yPositiveBit ) && !( xPositiveBit && yPositiveBit )) {
        count++
      }
   }
   return count;
};
\$\endgroup\$
2
\$\begingroup\$

Performance review.

There are some obvious performance problems that can be fixed.

Style and performance.

Use strict mode. Strict mode give code that runs slightly quicker than code not in strict mode. This is because the engine does not have to test and vet many common bad practices.

Declare all variables. In strict mode all variables need to be declared or the code throws an error. The vars xPositiveBit and xPositiveBit are undeclared and thus become global variables.

Global variables are significantly slower than local function scope variables. This is because of the way the engine searches for variables, it starts at the current scope and if the var can not be found it moves up one level of scope. It does this until the var is found. This slows down access to global variables.

Don't repeat calculations. You calculate the bit position you are testing up to 4 time per loop. Math.pow(2, i) can be done only once per loop. (Note that different JS contexts will have different optimisation strategies, some will spot the repeated calculation and store the result rather than recalculate)

Using these methods we get a tiny improvement with the following

Solution A

function hammingDistance2(x, y) {
  "use strict";
  var i;
  var count = 0;
  for (i = Math.floor(Math.log2(x > y ? x : y)); i >= 0; i--) {
    const pow = Math.pow(2, i)
    const xPositiveBit = x / pow >= 1;
    const yPositiveBit = y / pow >= 1;
    if (xPositiveBit) { x = x % pow }
    if (yPositiveBit) { y = y % pow }
    if ((xPositiveBit || yPositiveBit) && !(xPositiveBit && yPositiveBit)) {
      count++
    }
  }
  return count;
};

Getting a benchmark of 4.4 compared to the original 4.6 which is about a ~4% performance increase. Not much but every bit helps.

Smarter logic

If you look at the logic you are testing each loop the bit location defined Math.pow(2,Math.floor(Math.log2(x > y ? x : y))) shifted right depending on the loop count.

If we consider that the input values are limited to only positive doubles less than ((2^31) -1) you can use bitwise operators to give a major improvement in performance.

The following code benchmarks 2.0 compared to the original 4.6 so that is a massive improvement of ~57% and would bring your 88ms down to ~38ms But remember that has a limited input range.

Solution B

function hammingDistance(x, y) {
  "use strict";
  var xPos, yPos;
  var count = 0;
  var i = Math.pow(2, Math.log2(x > y ? x : y) | 0);
  while (i > 0) {
    xPos = x / i >= 1;
    yPos = y / i >= 1;
    if (xPos) { x %= i }
    if (yPos) { y %= i }
    if ((xPos || yPos) && !(xPos && yPos)) { count++ }
    i >>= 1;
  }
  return count;
};

Note that benchmarking was on a set of random values in the range 2^27 to 2^29 selected such as to amplify the performance benefits of optimising code inside the loop. Testing the code on a larger range 0 to 2^29 reduces the performance improvements with the first snippet's improvements having error bars overlapping the original, in other words too close to call. However the second snippet kept the same performance increase mainly due to using | 0 to floor the value of i outside the loop.

All benchmarking on Firefox.

Update

Dont trust leetCode performance results.

At the time of writing the answer I had no clue what the hamming distance was. Now that I know it is just the number of bits that are different the solution is very simple. Count the on bits when you xor x and y.

So I came up with Solution C

var hammingDistance = function(x, y) {    
    return (x ^ y).toString(2).replace(/0/g,"").length;
}

And submitting to keetCode it got a lower score than using a loop, being only ahead of 73% of submissions ???

Then I tried

var hammingDistance = function(x, y) {    
    var ones = (x ^ y).toString(2).match(/1/g);  
    return ones ? ones.length : 0; // ones is null if no matching 1s
}

This only gained a slight advantage, ahead of 82%.

I then looked to see what code gave the best result, it was almost identical????

Code from leetCode best answer in terms of performance.

var hammingDistance = function(x, y) {
    var xor = x ^ y;
    var str = xor.toString(2);
    var match = str.match(/1/g); 
    return match ? match.length : 0 ;
};

So I submitted that as an answer and it bombed big time being only ahead of 52% of submissions.

NOTE Your (OP) code runs 33% faster than the above.

I used my own benchmarker to test the different functions and the code I first gave (Solution B) running much faster than the updated solutions.

Inconsistencies

I have zero trust in the leetCode results, they are completely inconsistent with proven benchmarking results and even for their own results. I would guess there is a bug in there timing solution (JS is notoriously hard to benchmark) so be happy for a pass, and give no credence to the performance as that is based on luck.

Best JS solution I could come up with.

So the updated best performance as tested on a independent benchmarker is the following snippet run in strict mode. Out performing all the above by an order of magnitude. BenchMarked 0.1 compared to the next best at 2.0 for (Solution B) and OP's 4.6

33 times faster than OP's original.

    function hammingDistanceA(x,y){
        var xor = x ^ y;
        var count = 0;
        while(xor > 0){
            count += xor & 1;
            xor >>= 1;
        }
        return count;
    }

Which on leet got above 91% on the first submission and on the second submission only managed to get ahead of 43%

\$\endgroup\$
1
\$\begingroup\$

Instead of using floating point operations, you should only use integer operations.

Instead of analyzing two variables, you should xor them and only analyze the result.

Instead of the while loop, you should use the bit manipulation recipe popcount from the book A Hacker's Delight. If you are lucky, the JavaScript optimizer recognizes the pattern of that code (the constants 0x55555555 and 0x00ff00ff are well-known) and converts the whole code into two machine instructions, so that the code looks like this:

t1 = a xor b
t2 = popc t1
return t2
\$\endgroup\$
  • \$\begingroup\$ Javascript has no equivalent to popc so will never compile down to that instruction. \$\endgroup\$ – Blindman67 Dec 3 '17 at 12:35
  • \$\begingroup\$ @Blindman67 The C programming language also doesn't have a popc operator. Nevertheless a compiler can compile to that CPU instruction. Your argumentation is flawed. \$\endgroup\$ – Roland Illig Dec 3 '17 at 20:56
  • \$\begingroup\$ @Blindman67 See Google's V8 JavaScript engine, which has a definition for Word32Popcnt. \$\endgroup\$ – Roland Illig Dec 3 '17 at 21:20
  • \$\begingroup\$ So how does that change the fact that there is no equivalent in JS. If you believe that JS will compile to a single popc instruction do please show an example, or at least a reference to how that can be achieved? \$\endgroup\$ – Blindman67 Dec 4 '17 at 3:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.