internal-typed-array-vs-vars-sha1

JavaScript performance comparison

Revision 4 of this test case created

Info

This test compares using several local variables vs a Uint32Array for the words (32 bit uints) used internally in the sha1 algorithm. I find it very interesting that the behavior varies a lot by browser.

Preparation code

<script src="http://underscorejs.org/underscore-min.js">
</script>
<script>
Benchmark.prototype.setup = function() {
    function stringToBuffer(string) {
      string = unescape(encodeURIComponent(string));
      var length = string.length;
      var buf = new Uint8Array(length);
      for (var i = 0; i < length; i++) {
        buf[i] = string.charCodeAt(i);
      }
      return buf;
    };
    var zeroPad = function(howManyZeros) {
        return _.reduce(_.range(howManyZeros), function(m) {
          return '0' + m
        }, '')
        }
       
       
       
    function sha1_array2(input) {
      var arraybuffer = input.buffer
      var byteLength = arraybuffer.byteLength
   
      // The total byte length must be congruent to 56 mod 64
      //Increment the byteLength because we are apending the bits 1000 0000
      ++byteLength
   
      // Figure out how many bytes of zero we need
      var padding = (64 + (56 - byteLength % 64)) % 64
   
      var originalMessageLength = arraybuffer.byteLength,
          originalMessageLengthHex = originalMessageLength.toString('16'),
          originalMessageLengthHex = originalMessageLengthHex.length == 16 ? originalMessageLengthHex : zeroPad(16 - originalMessageLengthHex.length) + originalMessageLengthHex
         
          //lets fake shift everything left 4bits
          ,
          hi_length_bits = '0x' + originalMessageLengthHex.substring(1, 9),
          lo_length_bits = '0x' + originalMessageLengthHex.substring(9) + "0"
         
         
         
         
      var messageLength = new Uint32Array(2)
   
      messageLength[0] = parseInt(hi_length_bits)
      messageLength[1] = parseInt(lo_length_bits)
   
      //bring it back with a one right bit shift
      //first lets do the bottom part
      messageLength[1] >>= 1
      messageLength[1] = messageLength[1] | ((messageLength[0] & 0x1) << 31) // carry over the lsb of the high bits
      // now we can do the hi bits
      messageLength[0] >>= 1
   
   
      var message = new Uint8Array(arraybuffer)
   
      var paddedBuffer = new ArrayBuffer(byteLength + padding + messageLength.byteLength)
   
      //represent the padded message as 32 bit numbers, we are still sharing the data from the origin padded message
      var paddedMessage32bit = new Uint32Array(paddedBuffer),
          paddedMessage8bit = new Uint8Array(paddedBuffer)
         
         
         
         
          //copy the original message part
         
      for (var index = 0; index < message.length; index += 4) {
        //since the 8 bit bytes translate to the 32bit array as little endian we need to copy it so (e.g. 8bit [0x1,0x2,0x3,0x4] == 32bit [0x04030201]
        var i = 0,
            max = 4
           
        if (message.length < 4 + index) max = message.length % 4;
   
        //copy the bytes downward
        while (i < max) {
          paddedMessage8bit[(3 - i) + index] = message[i + index]
          i++
        }
   
        //we are done here
        if (i + index === message.length) {
          // If the message didn't end early we need to put it on the next 32bit chunk at the very front which happens to be i+3 bytes since the order mentioned above
          if (i === 4) {
            paddedMessage8bit[3 + i + index] = 0x80
          } else {
            // if it did end early we can just tak it on
            paddedMessage8bit[(3 - i) + index] = 0x80
          }
        }
      }
   
   
      //The rest are will automatically be zeros so we don't need to explicitly create the padding
      //set the end message bytes
      paddedMessage32bit[paddedMessage32bit.length - 1] = messageLength[1]
      paddedMessage32bit[paddedMessage32bit.length - 2] = messageLength[0]
   
   
      var leftRotate32BitWordNtimes = function(word, times) {
          return (word << times) | (word >>> 32 - times)
          }
         
         
         
      var h = new Uint32Array([0x67452301, 0xefcdab89, 0x98badcfe, 0x10325476, 0xc3d2e1f0])
   
      var hashTerms = new Uint32Array(7) //a, b, c, d, e, f, temp
      ,
          K = new Uint32Array([0x5A827999, 0x6ED9EBA1, 0x8F1BBCDC, 0xCA62C1D6])
         
         
         
         
          //Create the array for the words
         
      var words = new Uint32Array(80)
   
      //get the range of chunks, at 16 step intervals because 32bits*16=512bits which is the chunksize we need
      var chunkLocation = 0
      while (chunkLocation < paddedMessage32bit.length) {
   
        //This is what the chunk would look like
        var chunk = paddedMessage32bit.subarray(chunkLocation, chunkLocation + 16)
        chunkLocation += 16;
   
        for (var i = 0; i < 16; i++) {
          words[i] = chunk[i]
        }
   
        //Create the rest of the words
        for (var wordIndex = 16; wordIndex < 80; wordIndex++) {
          words[wordIndex] = leftRotate32BitWordNtimes(
          words[wordIndex - 3] ^ words[wordIndex - 8] ^ words[wordIndex - 14] ^ words[wordIndex - 16] // xor all the words!
          , 1)
        }
   
   
   
        hashTerms[0] = h[0]
        hashTerms[1] = h[1]
        hashTerms[2] = h[2]
        hashTerms[3] = h[3]
        hashTerms[4] = h[4]
   
        //BIT TWIDDILING
        //Main Loop
        for (var i = 0; i < 80; i++) {
          if (i < 20) {
            hashTerms[5] = (hashTerms[1] & hashTerms[2]) ^ ((~hashTerms[1]) & hashTerms[3])
          } else if (i < 40) {
            hashTerms[5] = hashTerms[1] ^ hashTerms[2] ^ hashTerms[3]
          } else if (i < 60) {
            hashTerms[5] = (hashTerms[1] & hashTerms[2]) ^ (hashTerms[1] & hashTerms[3]) ^ (hashTerms[2] & hashTerms[3])
          } else if (i < 80) {
            hashTerms[5] = hashTerms[1] ^ hashTerms[2] ^ hashTerms[3]
          }
   
          hashTerms[6] = leftRotate32BitWordNtimes(hashTerms[0], 5) + hashTerms[5] + hashTerms[4] + K[Math.floor(i / 20)] + words[i]
   
          hashTerms[4] = hashTerms[3]
          hashTerms[3] = hashTerms[2]
          hashTerms[2] = leftRotate32BitWordNtimes(hashTerms[1], 30)
          hashTerms[1] = hashTerms[0]
          hashTerms[0] = hashTerms[6]
   
   
        }
   
   
   
        h[0] += hashTerms[0]
        h[1] += hashTerms[1]
        h[2] += hashTerms[2]
        h[3] += hashTerms[3]
        h[4] += hashTerms[4]
      }
   
      var digest = _.reduce(h, function(memo, num) {
        var hex = num.toString(16)
        return memo + (hex.length == 8 ? hex : zeroPad(8 - hex.length) + hex)
      }, '')
      return digest
   
   
   
    }
   
    // input is a Uint8Array bitstream of the data
   
   
    function sha1_array(input) {
      var H = new Uint32Array([0x67452301, 0xefcdab89, 0x98badcfe, 0x10325476, 0xc3d2e1f0]),
          m = [],
          l = input.length * 8,
          w = [];
   
      for (var i = 0, b = 0, end = l / 8; i < end; i++, b += 8) {
        m[b >>> 5] |= input[i] << (24 - b % 32);
      }
   
      m[l >> 5] |= 0x80 << (24 - l % 32);
      m[((l + 64 >>> 9) << 4) + 15] = l;
   
      for (var i = 0, end = m.length; i < end; i += 16) {
        var a = H[0],
            b = H[1],
            c = H[2],
            d = H[3],
            e = H[4];
   
        for (var j = 0; j < 80; j++) {
          if (j < 16) {
            w[j] = m[i + j];
          } else {
            var n = w[j - 3] ^ w[j - 8] ^ w[j - 14] ^ w[j - 16];
            w[j] = (n << 1) | (n >>> 31);
          }
   
          var t = ((H[0] << 5) | (H[0] >>> 27)) + H[4] + (w[j] >>> 0) + (
          j < 20 ? (H[1] & H[2] | ~H[1] & H[3]) + 0x5a827999 : j < 40 ? (H[1] ^ H[2] ^ H[3]) + 0x6ed9eba1 : j < 60 ? (H[1] & H[2] | H[1] & H[3] | H[2] & H[3]) - 0x70e44324 : (H[1] ^ H[2] ^ H[3]) - 0x359d3e2a);
   
          H[4] = H[3];
          H[3] = H[2];
          H[2] = (H[1] << 30) | (H[1] >>> 2);
          H[1] = H[0];
          H[0] = t;
        }
   
        H[0] += a;
        H[1] += b;
        H[2] += c;
        H[3] += d;
        H[4] += e;
      }
   
      return new Uint8Array(H.buffer);
    }
   
   
    // input is a Uint8Array bitstream of the data
   
   
    function sha1_vars(input) {
   
      var H0 = 0x67452301,
          H1 = 0xefcdab89,
          H2 = 0x98badcfe,
          H3 = 0x10325476,
          H4 = 0xc3d2e1f0,
          m = [],
          l = input.length * 8,
          w = [];
   
      for (var i = 0, b = 0; i < l / 8; i++, b += 8) m[b >>> 5] |= input[i] << (24 - b % 32);
   
      m[l >> 5] |= 0x80 << (24 - l % 32);
      m[((l + 64 >>> 9) << 4) + 15] = l;
   
      for (var i = 0; i < m.length; i += 16) {
        var a = H0,
            b = H1,
            c = H2,
            d = H3,
            e = H4;
   
        for (var j = 0; j < 80; j++) {
          if (j < 16) w[j] = m[i + j];
          else {
            var n = w[j - 3] ^ w[j - 8] ^ w[j - 14] ^ w[j - 16];
            w[j] = (n << 1) | (n >>> 31);
          }
   
          var t = ((H0 << 5) | (H0 >>> 27)) + H4 + (w[j] >>> 0) + (
          j < 20 ? (H1 & H2 | ~H1 & H3) + 0x5a827999 : j < 40 ? (H1 ^ H2 ^ H3) + 0x6ed9eba1 : j < 60 ? (H1 & H2 | H1 & H3 | H2 & H3) - 0x70e44324 : (H1 ^ H2 ^ H3) - 0x359d3e2a);
   
          H4 = H3;
          H3 = H2;
          H2 = (H1 << 30) | (H1 >>> 2);
          H1 = H0;
          H0 = t;
        }
   
        H0 += a;
        H1 += b;
        H2 += c;
        H3 += d;
        H4 += e;
      }
      var H = new Uint32Array([H0, H1, H2, H3, H4]);
      return new Uint8Array(H.buffer);
    }
   
    var inputs = [
    stringToBuffer("Hello World"), stringToBuffer("Hello World, This is a much longer message to test multiple chunks")]
};
</script>

Test runner

Warning! For accurate results, please disable Firebug before running the tests. (Why?)

Java applet disabled.

Testing in unknown unknown
Test Ops/sec
internal-vars
a = sha1_vars(inputs[0])
b = sha1_vars(inputs[1])
pending…
inner-typed
a = sha1_array(inputs[0])
b = sha1_array(inputs[1])
pending…
other-typed
a = sha1_array2(inputs[0])
b = sha1_array2(inputs[1])
pending…

Compare results of other browsers

Revisions

You can edit these tests or add even more tests to this page by appending /edit to the URL. Here’s a list of current revisions for this page:

0 comments

Add a comment