How to speed up checksum computations of a string?

[espruino-discuss]

Posted at 2015-09-08 by asez73

Hi all,
I have been analysing the nmea sentences send from a gps module (ublox neo-6m).
What I ended up with was that checking properly those sentences required to compute the xor of all chars.
So finally, it means looping over a string and that takes 55%, approximately 14ms, of the total time required to handle the sentence which takes 25 ms.

I tried various minifications/looping approaches and the code below show the results

// test_checksums.js

// chronometer functionnalities

var Chrono = function () {
  this.reset();
  this.createdAt = new Date(getTime());
};

Chrono.prototype.reset = function () {
  this.nleaps=0;
  this.duration=0;
};

Chrono.prototype.start = function () {
  this.starttime= getTime();
};

Chrono.prototype.leap = function () {
  this.nleaps++;
};

Chrono.prototype.stop= function () {
  this.duration+=getTime()-this.starttime;
};

Chrono.prototype.meanleap= function() {
    return (this.duration/this.nleaps);
};

Chrono.prototype.info= function() {
  return this.nleaps+" leaps (mean leap time "+(this.meanleap())+" s)";
};

Chrono.prototype.toString= function() {
  return this.nleaps+" leaps with a duration of "+this.duration+" s (mean leap time "+(this.meanleap())+" s)";
};


function cks(m) {
  var ck = 0;
  new Uint8Array(E.toArrayBuffer(m)).forEach(function (c) { ck^=c; });  // mean leap time 0.01207760762 s
  return ck;
}

function cks2(m) {
  var ck = 0;
  new Uint8Array(E.toArrayBuffer(m)).forEach(function (c) { ck^=c; });  // mean leap time 0.01207760762 s
  return ck;
}

function cks3(m) {
  var ck = 0;
  for (var s in m) { ck ^= m.charCodeAt(s); }
  return ck;
}

function cks4(m) {
  return new Uint8Array(E.toArrayBuffer(m)).reduce(function (p,c) { return p^c; }, 0);
}

// compute the checksum for NMEA sentences and splits it from ','
function nmea_checksum(s) {
  try {
    var n=s.split('$').pop(); // remove leading uncomplete sentences AND the no more usefull leading $
    n=n.split('*'); // separate checksum from line
    var cksum = parseInt(n.pop(),16); // make checksum a number and remove it from n
    n=n.pop(); // keep content alone
    if (cksum===cks(n)) // mean leap 0.02532994300 s
      return n.split(',');  // mean leap 0.01426320198 s
    else {
      throw "different checksums "+cksum.toString(16)+" versus "+cks(n).toString(16)+" in line "+s ;
    }
  } catch(x) {
    throw "Checksum error "+x+' in sentence '+s; 
  }
}

// chronometer the time it takes to compute the checksums of the following sentences

sentences = [
"$GPRMC,090453.00,A,4540.02686,N,00624.52116,E,0.221,,080915,,,A*71"
,"$GPVTG,,T,,M,0.221,N,0.409,K,A*2F"
,"$GPGGA,090453.00,4540.02686,N,00624.52116,E,1,05,1.57,349.4,M,47.3,M,,*55"
,"$GPGLL,4540.02686,N,00624.52116,E,090453.00,A,A*6C"
,"$GPGRS,090453.00,1,-2.0,-1.3,-1.5,-0.4,-5.8,,,,,,,*4B"
,"$GPGST,090453.00,34,,,,7.6,4.6,18*7F"
,"$GPZDA,090453.00,08,09,2015,00,00*6A"
,"$GPGBS,090453.00,7.6,4.6,17.7,,,,*78"
,"$PUBX,00,090453.00,4540.02686,N,00624.52116,E,396.669,G3,8.8,18,0.409,5.16,0.065,,1.57,2.29,1.62,5,0,0*41"
];

function chrono(func, nbloops) {
  console.log('');
  console.log('Timing of function:\n',func);
  var mychrono = new Chrono();
  mychrono.start();
  for (var i=1; i<nbloops; i++) {
    sentences.map(func);
  }
  mychrono.stop();
  mychrono.nleaps+=nbloops*sentences.length;
  console.log(mychrono.toString());
  return mychrono.meanleap();
}

var nb_loops=300;
chrono(nmea_checksum,nb_loops);
chrono(cks,nb_loops);
chrono(cks3,nb_loops);
chrono(cks4,nb_loops);

Here are the results

Timing of function:
 function (s) {
  try {
    var n=s.split('$').pop(); // remove leading uncomplete sentences AND the no more usefull leading $
    n=n.split('*'); // separate checksum from line
    var cksum = parseInt(n.pop(),16); // make checksum a number and remove it from n
    n=n.pop(); // keep content alone
    if (cksum===cks(n)) // mean leap 0.02532994300 s
      return n.split(',');  // mean leap 0.01426320198 s
    else {
      throw "different checksums "+cksum.toString(16)+" versus "+cks(n).toString(16)+" in line "+s ;
    }
  } catch(x) {
    throw "Checksum error "+x+' in sentence '+s;
  }
}
2700 leaps with a duration of 40.18452930450 s (mean leap time 0.01488315900 s)
Timing of function:
 function (m) {
  var ck = 0;
  new Uint8Array(E.toArrayBuffer(m)).forEach(function (c) { ck^=c; });  // mean leap time 0.01207760762 s
  return ck;
}
2700 leaps with a duration of 32.40455818176 s (mean leap time 0.01200168821 s)
Timing of function:
 function (m) {
  var ck = 0;
  for (var s in m) { ck ^= m.charCodeAt(s); }
  return ck;
}
2700 leaps with a duration of 38.31807804107 s (mean leap time 0.01419188075 s)
Timing of function:
 function (m) {
  return new Uint8Array(E.toArrayBuffer(m)).reduce(function (p,c) { return p^c; }, 0);
}
2700 leaps with a duration of 37.05036735534 s (mean leap time 0.01372235827 s)
=undefined

So, is there a way to speed up it?
"compiled" javascript doesn't seem to be possible in this context.

[gfwilliams]

Posted at 2015-09-08 by @gfwilliams

Wow, thanks! it's great to see the benchmarks for this. If I'm honest it's a surprise that cks is better than cks4. It's been a real struggle to find anything that's faster, but:

// just removing whitespace from the cks callback gives you a tiny bit
function cks9(m) {
  var s = 0;
  new Uint8Array(E.toArrayBuffer(m)).forEach(function (c) {s^=c});
  return s;
}
// and pre-binding the function and using a for in loop helps a surprising amount
function cks10(m) { 
  var s = 0;
  var c = m.charCodeAt.bind(m);
  for (var i in m)s^=c(i);
  return s;
}

But you should be able to use compiled, for instance try:

function xor(a,b) { "compiled"; return a^b; }
function cks5(m) {
  return new Uint8Array(E.toArrayBuffer(m)).reduce(xor, 0);
}
function cks6(m) { 
  "compiled"; 
  var ck = 0;
  var l = 0|m.length;
  for (var i=0;i<l;i++) ck ^= m.charCodeAt(i);
  return ck;
}
function cks7(m) { 
  "compiled"; 
  var ck = 0;
  var l = 0|m.length; // ensure we don't have to check the length each time
  var c = m.charCodeAt.bind(m); // ensure we don't have to look up 'charCodeAt' each time
  for (var i=0;i<l;i++) ck ^= c(i);
  return ck;
}

I just had a quick play and they seem to be 2x or more faster than cks10 (especially the last one). Hope that helps!

[espruino-discuss]

Posted at 2015-09-08 by asez73

@gordon, thanks for your time.

I am trying it now and just face some errors as compiler server seems to be unjoinable.
However, without compiling, cks10 is 16% faster than cks which was my best result.

It is a permanent surprise to see how efficiency can be improved on such a language as javascript.

So, let's hope the compiler will be accessible soon.

[gfwilliams]

Posted at 2015-09-08 by @gfwilliams

Give it a try now - I have no idea what happened there!

[espruino-discuss]

Posted at 2015-09-08 by asez73

Here are the results on my Espruino board 1v4:

Mean execution time of nmea_checksum is 14.92417830008 ms,
Mean execution time of cks is 12.01456811692 ms,
Mean execution time of cks3 is 14.42750400967 ms,
Mean execution time of cks4 is 13.73525796113 ms,
Mean execution time of cks9 is 11.70109007093 ms,
Mean execution time of cks10 is 9.84849823845 ms,
Mean execution time of cks5 is 4.01897854275 ms,
Mean execution time of cks6 is 5.00975432219 ms,
Mean execution time of cks7 is 2.71540111965 ms

So finally, we have a benefit of 442 % in speed which is obviously reasonnable.
I joined the full source for this comparison.

Thank's again.

Attachments:

• test_checksums.js

[gfwilliams]

Posted at 2015-09-08 by @gfwilliams

Great! I'd still be happier if Espruino executed it more quickly - I'll have to try some benchmarks and see if there's any way to speed up the interpreter a bit more.