Thursday, October 09, 2008

Encoding Optimizations for IE

Recently I had to tackle some performance issues in a set of AJAX web parts. We experienced unexpected slowdowns, which were increasing exponentially with the increase of the data being handled. After some investigation I found that the code is using the very popular base64 algorithm in JavaScript. This encoding is has the advantage that it has a counterpart in the ASP.NET server side and can be used to encode data send to and from the client when this is needed. It is a very popular algorithm and the JavaScript implementation can be found on many sites. Here is one of them: http://www.webtoolkit.info/javascript-base64.html.

It turns out that the string concatenations in this algorithm are killing IE and shooting the CPU utilization to 100%, locking up the UI. The situation progressively worsens as we go back to older browsers. In IE6 the performance is miserable. In IE7 it is better but still unacceptable. In IE8 BETA things looked much better, but still not in the range of performance in other browsers.

After poking around and getting some advice, Torben H. suggested that the string concatenation can be replaced by a simple buffer/array operation in JavaScript. This eliminates the recreation of the strings on each iteration of the encoding loop. In addition the performance of the modified algorithm increases in a linear progression when the amount of the encrypted characters grows. I also wrapped the algorithm in a separate JavaScript class, so it's use is a bit more intuitive.

You can see that on line 2, I create a buffer to hold the encoded string. On line 22 instead of using

output = output + this._keyStr.charAt(enc1) + this._keyStr.charAt(enc2) + this._keyStr.charAt(enc3) + this._keyStr.charAt(enc4);

I use buffer.push(...). Finally on line 25 the encoded string is returned as a join of the array. This is the complete code:

 

   1:  StringBase64Encoder.prototype.encode = function(to_encode) { 
   2:  var buffer = new Array(Math.round(to_encode.length / 3) + 1 * 4); 
   3:      var chr1, chr2, chr3; 
   4:      var enc1, enc2, enc3, enc4; 
   5:      var i = 0; 
   6:   
   7:      do { 
   8:          chr1 = to_encode.charCodeAt(i++); 
   9:          chr2 = to_encode.charCodeAt(i++); 
  10:          chr3 = to_encode.charCodeAt(i++); 
  11:   
  12:          enc1 = chr1 >> 2; 
  13:          enc2 = ((chr1 & 3) << 4) | (chr2 >> 4); 
  14:          enc3 = ((chr2 & 15) << 2) | (chr3 >> 6); 
  15:          enc4 = chr3 & 63; 
  16:   
  17:          if (isNaN(chr2)) { 
  18:              enc3 = enc4 = 64; 
  19:          } else if (isNaN(chr3)) { 
  20:              enc4 = 64; 
  21:          } 
  22:          buffer.push((this.key.charAt(enc1) + this.key.charAt(enc2)) + (this.key.charAt(enc3) + this.key.charAt(enc4))); 
  23:   
  24:      } while (i < to_encode.length); 
  25:      return buffer.join(""); 
  26:  } 
  27:   
  28:  StringBase64Encoder.prototype.decode = function(to_decode) { 
  29:      var chr1, chr2, chr3; 
  30:      var enc1, enc2, enc3, enc4; 
  31:      var i = 0; 
  32:      var buffer = new Array(Math.round(to_decode.length / 4) * 3); 
  33:   
  34:      // remove all characters that are not A-Z, a-z, 0-9, +, /, or = 
  35:      to_decode = to_decode.replace(/[^A-Za-z0-9\+\/\=]/g, ""); 
  36:   
  37:      do { 
  38:          enc1 = this.key.indexOf(to_decode.charAt(i++)); 
  39:          enc2 = this.key.indexOf(to_decode.charAt(i++)); 
  40:          enc3 = this.key.indexOf(to_decode.charAt(i++)); 
  41:          enc4 = this.key.indexOf(to_decode.charAt(i++)); 
  42:   
  43:          chr1 = (enc1 << 2) | (enc2 >> 4); 
  44:          chr2 = ((enc2 & 15) << 4) | (enc3 >> 2); 
  45:          chr3 = ((enc3 & 3) << 6) | enc4; 
  46:   
  47:          buffer.push(String.fromCharCode(chr1)); 
  48:   
  49:          if (enc3 != 64) { 
  50:              buffer.push(String.fromCharCode(chr2)); 
  51:          } 
  52:          if (enc4 != 64) { 
  53:              buffer.push(String.fromCharCode(chr3)); 
  54:          } 
  55:      } while (i < to_decode.length); 
  56:   
  57:      return buffer.join(""); 
  58:  } 
 
 
The results show a significant improvement in performance in both IE6 and IE7.

Performance in IE6

Algorithm\Chars

62917

125834

188751

 

encode

decode

encode

decode

encode

decode

original base64 (seconds)

11.313

6.453

48.531

32.594

128.203

53.516

modified base64 (seconds)

0.547

1.203

1.437

3.906

4.703

8.078

XOR

0.719

0.703

2.125

2.141

4.015

4.016

image

Performance in IE7

Algorithm\Chars

62917

125834

188751

 

encode

decode

encode

decode

encode

decode

original base64 (seconds)

2

1.672

7.359

5.25

21.172

9.36

modified base64 (seconds)

0.64

0.781

1.344

1.641

5.937

2.578

XOR

0.485

0.515

1.016

1.031

1.547

1.547

image

 

Just for fun I added an alternative encoding to the mix to see how it performs. This is the well know XOR algorithm, which is not as stable as the base64, because you can get unwanted characters in the encoded string, but it can be certainly used in AJAX applications. As you can see the performance is better for the XOR algorithm in IE7, but not really so much better in IE6. If your application is targeting older browsers there is no significant advantage in the performance of the XOR algorithm versus the base64. Here is the code I used for the XOR algorithm:

 

   1:  function StringXOREncoder(key) {
   2:      this.key = key;
   3:  }
   4:   
   5:  StringXOREncoder.prototype.encode = function(to_encode) {
   6:      var buffer = new Array(to_encode.length);
   7:      var i = 0;
   8:      do {
   9:          buffer.push(String.fromCharCode(this.key ^ to_encode.charCodeAt(i++)));
  10:      } while (i < to_encode.length);
  11:      return escape(buffer.join(""));
  12:  }
  13:   
  14:  StringXOREncoder.prototype.decode = function(to_decode) {
  15:      var rawinput = unescape(to_decode);
  16:      var buffer = new Array(rawinput.length);
  17:      var i = 0;
  18:      do {
  19:          buffer.push(String.fromCharCode(this.key ^ rawinput.charCodeAt(i++)));
  20:      } while (i < rawinput.length);
  21:      return buffer.join("");
  22:  }

 

Similar test in other browsers such as Firefox and Chrome did not have any issues with either the original or the modified algorithms. They handle JavaScript string operations much better. However most corporate environments are IE based and such optimizations may have dramatic impact on the performance of AJAX applications.

Happy encoding :)

 

Dovizhdane!