Account Options

  1. Sign in
The old Google Groups will be going away soon, but your browser is incompatible with the new version.
Google Groups Home
« Groups Home
SpiderMonkey cache optimisation, first results
There are currently too many topics in this group that display first. To make this topic appear first, remove this option from another topic.
There was an error processing your request. Please try again.
flag
  6 messages - Collapse all  -  Translate all to Translated (View all originals)
The group you are posting to is a Usenet group. Messages posted to this group will make your email address visible to anyone on the Internet.
Your reply message has not been sent.
Your post was successful
 
From:
To:
Cc:
Followup To:
Add Cc | Add Followup-to | Edit Subject
Subject:
Validation:
For verification purposes please type the characters you see in the picture below or the numbers you hear by clicking the accessibility icon. Listen and type the numbers you hear
 
riadh chtara  
View profile  
 More options Oct 11 2012, 1:51 pm
Newsgroups: mozilla.dev.tech.js-engine
From: riadh chtara <riadh.cht...@gmail.com>
Date: Thu, 11 Oct 2012 10:51:37 -0700 (PDT)
Local: Thurs, Oct 11 2012 1:51 pm
Subject: SpiderMonkey cache optimisation, first results
Hi guys,
I was playing with spidermonkey.
I ran a js script( its a simple js file that encode text to md5)  with the js shell and I calculate the time needed to open the file(ReadCompleteFile), compile(compile) the code and execute( JS_ExecuteScript) the script.
I found the following result (my computer is almost two years old, and it cost me 600$ when I bought it so its hard drive is not super fast)
open file = 0,814 ms
compile = 27,194 ms
JS_ExecuteScript = 33,821 ms
So,maybe it's not a stupid idea to save the compiled script in the cache.It will take maybe 2 ms for it to be read and same space to save it. But like this we will save 27 ms in compiling time the second time.
We will gain 25 ms (40%) in this script execution)
For saving the file, js file are small and we have a lot of space in hard drive to save them so this is not a big deal.
Maybe I was so lucky with my js file, but even if we gain 10%, I think that this worth to be implemented
What do you think please?
Best
Riadh

By the way, this is the js file I use

/*
 * A JavaScript implementation of the RSA Data Security, Inc. MD5 Message
 * Digest Algorithm, as defined in RFC 1321.
 * Version 2.2 Copyright (C) Paul Johnston 1999 - 2009
 * Other contributors: Greg Holt, Andrew Kepert, Ydnar, Lostinet
 * Distributed under the BSD License
 * See http://pajhome.org.uk/crypt/md5 for more info.
 */

/*
 * Configurable variables. You may need to tweak these to be compatible with
 * the server-side, but the defaults work in most cases.
 */
var hexcase = 0;   /* hex output format. 0 - lowercase; 1 - uppercase        */
var b64pad  = "";  /* base-64 pad character. "=" for strict RFC compliance   */

/*
 * These are the functions you'll usually want to call
 * They take string arguments and return either hex or base-64 encoded strings
 */
function hex_md5(s)    { return rstr2hex(rstr_md5(str2rstr_utf8(s))); }
function b64_md5(s)    { return rstr2b64(rstr_md5(str2rstr_utf8(s))); }
function any_md5(s, e) { return rstr2any(rstr_md5(str2rstr_utf8(s)), e); }
function hex_hmac_md5(k, d)
  { return rstr2hex(rstr_hmac_md5(str2rstr_utf8(k), str2rstr_utf8(d))); }
function b64_hmac_md5(k, d)
  { return rstr2b64(rstr_hmac_md5(str2rstr_utf8(k), str2rstr_utf8(d))); }
function any_hmac_md5(k, d, e)
  { return rstr2any(rstr_hmac_md5(str2rstr_utf8(k), str2rstr_utf8(d)), e); }

/*
 * Perform a simple self-test to see if the VM is working
 */
function md5_vm_test()
{
  return hex_md5("abc").toLowerCase() == "900150983cd24fb0d6963f7d28e17f72";

}

/*
 * Calculate the MD5 of a raw string
 */
function rstr_md5(s)
{
  return binl2rstr(binl_md5(rstr2binl(s), s.length * 8));

}

/*
 * Calculate the HMAC-MD5, of a key and some data (raw strings)
 */
function rstr_hmac_md5(key, data)
{
  var bkey = rstr2binl(key);
  if(bkey.length > 16) bkey = binl_md5(bkey, key.length * 8);

  var ipad = Array(16), opad = Array(16);
  for(var i = 0; i < 16; i++)
  {
    ipad[i] = bkey[i] ^ 0x36363636;
    opad[i] = bkey[i] ^ 0x5C5C5C5C;
  }

  var hash = binl_md5(ipad.concat(rstr2binl(data)), 512 + data.length * 8);
  return binl2rstr(binl_md5(opad.concat(hash), 512 + 128));

}

/*
 * Convert a raw string to a hex string
 */
function rstr2hex(input)
{
  try { hexcase } catch(e) { hexcase=0; }
  var hex_tab = hexcase ? "0123456789ABCDEF" : "0123456789abcdef";
  var output = "";
  var x;
  for(var i = 0; i < input.length; i++)
  {
    x = input.charCodeAt(i);
    output += hex_tab.charAt((x >>> 4) & 0x0F)
           +  hex_tab.charAt( x        & 0x0F);
  }
  return output;

}

/*
 * Convert a raw string to a base-64 string
 */
function rstr2b64(input)
{
  try { b64pad } catch(e) { b64pad=''; }
  var tab = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/";
  var output = "";
  var len = input.length;
  for(var i = 0; i < len; i += 3)
  {
    var triplet = (input.charCodeAt(i) << 16)
                | (i + 1 < len ? input.charCodeAt(i+1) << 8 : 0)
                | (i + 2 < len ? input.charCodeAt(i+2)      : 0);
    for(var j = 0; j < 4; j++)
    {
      if(i * 8 + j * 6 > input.length * 8) output += b64pad;
      else output += tab.charAt((triplet >>> 6*(3-j)) & 0x3F);
    }
  }
  return output;

}

/*
 * Convert a raw string to an arbitrary string encoding
 */
function rstr2any(input, encoding)
{
  var divisor = encoding.length;
  var i, j, q, x, quotient;

  /* Convert to an array of 16-bit big-endian values, forming the dividend */
  var dividend = Array(Math.ceil(input.length / 2));
  for(i = 0; i < dividend.length; i++)
  {
    dividend[i] = (input.charCodeAt(i * 2) << 8) | input.charCodeAt(i * 2 + 1);
  }

  /*
   * Repeatedly perform a long division. The binary array forms the dividend,
   * the length of the encoding is the divisor. Once computed, the quotient
   * forms the dividend for the next step. All remainders are stored for later
   * use.
   */
  var full_length = Math.ceil(input.length * 8 /
                                    (Math.log(encoding.length) / Math.log(2)));
  var remainders = Array(full_length);
  for(j = 0; j < full_length; j++)
  {
    quotient = Array();
    x = 0;
    for(i = 0; i < dividend.length; i++)
    {
      x = (x << 16) + dividend[i];
      q = Math.floor(x / divisor);
      x -= q * divisor;
      if(quotient.length > 0 || q > 0)
        quotient[quotient.length] = q;
    }
    remainders[j] = x;
    dividend = quotient;
  }

  /* Convert the remainders to the output string */
  var output = "";
  for(i = remainders.length - 1; i >= 0; i--)
    output += encoding.charAt(remainders[i]);

  return output;

}

/*
 * Encode a string as utf-8.
 * For efficiency, this assumes the input is valid utf-16.
 */
function str2rstr_utf8(input)
{
  var output = "";
  var i = -1;
  var x, y;

  while(++i < input.length)
  {
    /* Decode utf-16 surrogate pairs */
    x = input.charCodeAt(i);
    y = i + 1 < input.length ? input.charCodeAt(i + 1) : 0;
    if(0xD800 <= x && x <= 0xDBFF && 0xDC00 <= y && y <= 0xDFFF)
    {
      x = 0x10000 + ((x & 0x03FF) << 10) + (y & 0x03FF);
      i++;
    }

    /* Encode output as utf-8 */
    if(x <= 0x7F)
      output += String.fromCharCode(x);
    else if(x <= 0x7FF)
      output += String.fromCharCode(0xC0 | ((x >>> 6 ) & 0x1F),
                                    0x80 | ( x         & 0x3F));
    else if(x <= 0xFFFF)
      output += String.fromCharCode(0xE0 | ((x >>> 12) & 0x0F),
                                    0x80 | ((x >>> 6 ) & 0x3F),
                                    0x80 | ( x         & 0x3F));
    else if(x <= 0x1FFFFF)
      output += String.fromCharCode(0xF0 | ((x >>> 18) & 0x07),
                                    0x80 | ((x >>> 12) & 0x3F),
                                    0x80 | ((x >>> 6 ) & 0x3F),
                                    0x80 | ( x         & 0x3F));
  }
  return output;

}

/*
 * Encode a string as utf-16
 */
function str2rstr_utf16le(input)
{
  var output = "";
  for(var i = 0; i < input.length; i++)
    output += String.fromCharCode( input.charCodeAt(i)        & 0xFF,
                                  (input.charCodeAt(i) >>> 8) & 0xFF);
  return output;

}

function str2rstr_utf16be(input)
{
  var output = "";
  for(var i = 0; i < input.length; i++)
    output += String.fromCharCode((input.charCodeAt(i) >>> 8) & 0xFF,
                                   input.charCodeAt(i)        & 0xFF);
  return output;

}

/*
 * Convert a raw string to an array of little-endian words
 * Characters >255 have their high-byte silently ignored.
 */
function rstr2binl(input)
{
  var output = Array(input.length >> 2);
  for(var i = 0; i < output.length; i++)
    output[i] = 0;
  for(var i = 0; i < input.length * 8; i += 8)
    output[i>>5] |= (input.charCodeAt(i / 8) & 0xFF) << (i%32);
  return output;

}

/*
 * Convert an array of little-endian words to a string
 */
function binl2rstr(input)
{
  var output = "";
  for(var i = 0; i < input.length * 32; i += 8)
    output += String.fromCharCode((input[i>>5] >>> (i % 32)) & 0xFF);
  return output;

}

/*
 * Calculate the MD5 of an array of little-endian words, and a bit length.
 */
function binl_md5(x, len)
{
  /* append padding */
  x[len >> 5] |= 0x80 << ((len) % 32);
  x[(((len + 64) >>> 9) << 4) + 14] = len;

  var a =  1732584193;
  var b = -271733879;
  var c = -1732584194;
  var d =  271733878;

  for(var i = 0; i < x.length; i += 16)
  {
    var olda = a;
    var oldb = b;
    var oldc = c;
    var oldd = d;

    a = md5_ff(a, b, c, d, x[i+ 0], 7 , -680876936);
    d = md5_ff(d, a, b, c, x[i+ 1], 12, -389564586);
    c = md5_ff(c, d, a, b, x[i+ 2], 17,  606105819);
    b = md5_ff(b, c, d, a, x[i+ 3], 22, -1044525330);
    a = md5_ff(a, b, c, d, x[i+ 4], 7 , -176418897);
    d = md5_ff(d, a, b, c, x[i+ 5], 12,  1200080426);
    c = md5_ff(c, d, a, b, x[i+ 6], 17, -1473231341);
    b = md5_ff(b, c, d, a, x[i+ 7], 22, -45705983);
    a = md5_ff(a, b, c, d, x[i+ 8], 7 ,  1770035416);
    d = md5_ff(d, a, b, c, x[i+ 9], 12, -1958414417);
    c = md5_ff(c, d, a, b, x[i+10], 17, -42063);
    b = md5_ff(b, c, d, a, x[i+11], 22, -1990404162);
    a = md5_ff(a, b, c, d, x[i+12], 7 ,  1804603682);
    d = md5_ff(d, a, b, c, x[i+13], 12, -40341101);
    c = md5_ff(c, d, a, b, x[i+14], 17, -1502002290);
    b = md5_ff(b, c, d, a, x[i+15], 22,  1236535329);

    a = md5_gg(a, b, c, d, x[i+ 1], 5 , -165796510);
    d = md5_gg(d, a, b, c, x[i+ 6], 9 , -1069501632);
    c = md5_gg(c, d, a, b, x[i+11], 14,  643717713);
    b = md5_gg(b, c, d, a, x[i+ 0], 20, -373897302);
    a = md5_gg(a, b, c, d, x[i+ 5], 5 , -701558691);
    d = md5_gg(d, a, b, c, x[i+10], 9 ,  38016083);
    c = md5_gg(c, d, a, b, x[i+15], 14, -660478335);
    b = md5_gg(b, c, d, a, x[i+ 4], 20, -405537848);
...

read more »


 
You must Sign in before you can post messages.
To post a message you must first join this group.
Please update your nickname on the subscription settings page before posting.
You do not have the permission required to post.
Boris Zbarsky  
View profile  
 More options Oct 11 2012, 2:49 pm
Newsgroups: mozilla.dev.tech.js-engine
From: Boris Zbarsky <bzbar...@mit.edu>
Date: Thu, 11 Oct 2012 14:49:53 -0400
Local: Thurs, Oct 11 2012 2:49 pm
Subject: Re: SpiderMonkey cache optimisation, first results
On 10/11/12 1:51 PM, riadh chtara wrote:
 > open file = 0,814 ms

How was this time measured?  It's an order of magnitude lower than I
would expect for any non-SSD.

Or were you in a configuration where the file was actually in the OS
memory cache and hence not hitting the disk at all?

-Boris


 
You must Sign in before you can post messages.
To post a message you must first join this group.
Please update your nickname on the subscription settings page before posting.
You do not have the permission required to post.
Nicolas B. Pierron  
View profile  
 More options Oct 11 2012, 4:41 pm
Newsgroups: mozilla.dev.tech.js-engine
From: "Nicolas B. Pierron" <nicolas.b.pier...@mozilla.com>
Date: Thu, 11 Oct 2012 13:41:04 -0700
Local: Thurs, Oct 11 2012 4:41 pm
Subject: Re: SpiderMonkey cache optimisation, first results
On 10/11/2012 10:51 AM, riadh chtara wrote:

> I ran a js script( its a simple js file that encode text to md5)  with the js shell and I calculate the time needed to open the file(ReadCompleteFile), compile(compile) the code and execute( JS_ExecuteScript) the script.
> open file = 0,814 ms

It seems to me that your file is in your cache.  Have you tried flushing
your hard-drive read cache to reflect a real use case?  I get time which are
between ~10ms and ~60ms on a few random small (smaller than your test case)
files on my hd and during the first read.

--
Nicolas B. Pierron


 
You must Sign in before you can post messages.
To post a message you must first join this group.
Please update your nickname on the subscription settings page before posting.
You do not have the permission required to post.
riadh chtara  
View profile  
 More options Oct 12 2012, 6:16 am
Newsgroups: mozilla.dev.tech.js-engine
From: riadh chtara <riadh.cht...@gmail.com>
Date: Fri, 12 Oct 2012 03:16:45 -0700 (PDT)
Local: Fri, Oct 12 2012 6:16 am
Subject: Re: SpiderMonkey cache optimisation, first results
Hi guys
I was having a problem with timing (I put timing in wrong place)
But now, I fix it.
I ran a file for the first time, I got 17ms.
I ran it the second time,and surprise I get 0.8ms.(the file is in the cache)
I'm using ubuntu, but if this works on all platform(windows) it would be awesome.
Because, when I'm using gmail, I open it in one tab for the first time, then I open many other tabs.(it's a just an example, I think it's the same for you with many website)
So, if we save the compiled js(byte code) files to the hard drive, these files will be in the hard drive cache and we will spend less than 1ms to read them.
And we will save a non negligible amount of time by doing that.
When we open the second tab, we could calculate time needed to open the compiled js file as we open it,and if it takes a lot of time, we don't use these optimization next time, or better find a real way to  check if a file is in the hard driver cache)
So what do you think?
Riadh

 
You must Sign in before you can post messages.
To post a message you must first join this group.
Please update your nickname on the subscription settings page before posting.
You do not have the permission required to post.
Dave Mandelin  
View profile  
 More options Oct 12 2012, 9:20 pm
Newsgroups: mozilla.dev.tech.js-engine
From: Dave Mandelin <dmande...@mozilla.com>
Date: Fri, 12 Oct 2012 18:20:50 -0700 (PDT)
Local: Fri, Oct 12 2012 9:20 pm
Subject: Re: SpiderMonkey cache optimisation, first results

I don't quite understand the initial results, because it looks like you're testing something like crypto-md5, which runs in less than 15ms on a Mac mini, and I would think only a small fraction of that would be bytecompile time.

It should not be hard to collect a lot of good quality data around this idea.

First, you could instrument SpiderMonkey to record the total bytecompile time and the total execution time and then run that on all of SunSpider, to see how it looks on many benchmarks.

Next, just about as easily, you could collect similar data for a web browsing session. Going to sites that use jQuery would be good, because that's a prime use case for this sort of thing.

At this point you can look at the parse times to see how long they are to see how much it might matter. For example, if they are only 10 ms, it would probably never be noticed. However, since things are slower on mobile, that 10 ms on desktop could turn out to be 100-300ms on mobile, which could matter.

Then you'd want to get an estimate of how long it would take to load the bytecode from cache. That's going to be hard to do accurately without something that looks a bit like the final system, but I'd bet you can get close. The easy thing to do would be to remember how long the bytecode was, and then read that much data from a file. You could do versions where it would always and never hit disk cache to get an idea of the range. You could also just write out the bytecode to a new file and remember what the file is, and then read it back when you get a cache "hit". I.e., do some version of the caching, except don't bother to write it out or read it back *correctly*, just use the approximate same amount of data.

You could do a similar experiment with keeping the bytecode in memory and seeing what hit rate and potential speedup you get with different sizes of memory cache.

At that point it should be possible to read off a decent estimation of how much the technique would help and how to build it.

Dave


 
You must Sign in before you can post messages.
To post a message you must first join this group.
Please update your nickname on the subscription settings page before posting.
You do not have the permission required to post.
riadh chtara  
View profile  
 More options Oct 13 2012, 5:08 am
Newsgroups: mozilla.dev.tech.js-engine
From: riadh chtara <riadh.cht...@gmail.com>
Date: Sat, 13 Oct 2012 02:08:22 -0700 (PDT)
Local: Sat, Oct 13 2012 5:08 am
Subject: Re: SpiderMonkey cache optimisation, first results
Hi Dave
Thanks for your great suggestions
I will follow them.
This will keep me busy for a while. So, I will stop bothering you for a moment :-)
I will keep you update with results.
Best
Riadh

...

read more »


 
You must Sign in before you can post messages.
To post a message you must first join this group.
Please update your nickname on the subscription settings page before posting.
You do not have the permission required to post.
End of messages
« Back to Discussions « Newer topic     Older topic »