Last edition of O’Reilly Velocity Conference, Stoyan demonstrated how easy is to build your own YSlow ruleset and following his post and source code I was able to make it.
This first release of this extension of extension of extension features:

• Google Web Metrics from 2010-05-26
• Top and All Sites metrics rulesets
• Use percentile to score when available
• Use SSH metrics for HTTPS pages

Gimme!

• The code is in GitHub
• Install it from Mozilla Addon Page or Download Page

Usage

After installing this extension you will see 2 new rulesets in the YSlow rulesets drop down list:

1. Web Metrics Framework – Top Sites
2. Web Metrics Framework – All Sites

Choose one of these rulesets and click Run Test button. The current page will be evaluated using the Google web metrics data.

Metrics

The metrics provided by Google on its article are mainly averages with some percentiles and SSL data. YSlow rules need a lint function that evaluates an input returning a score from 0 to 100 which is later used to give the F to A score system using weights.
Since not all metrics have percentiles I had to compare the page metrics with the average multiplied by a magic number (4) to create a range from 0 to 4*average (if any statistic savvy here has comments on it please help me out to find a better way to evaluate) which is good enough to have an outcome where being in the average deserves a C. Perhaps Google releases new reports in future updates with all metrics percentiles, this extension could benefit from those numbers and become more accurate.
If the page being checked is secure (HTTPS), the SSL data available on the report is used instead.
The weighting distribution was given by:

1. Every metric starts with 1
2. Metrics with percentile get 1 more
3. Metrics directly related to wire traffic payload or number of requests also get 1 more

* Again: statistics savvy, help me improving this extension with your valuable feedback

Conclusion

Although these metrics aren’t 100% accurate (see Caveats section on Google’s article) it’s a good resource to compare your site with a sample of several billion pages crawled by Googlebot. Have fun!

WARNING: Like JSLint, Web Metrics Framework might hurt your feelings :-)

DISCLAIMER: This extension is not related with Google Inc. or Yahoo! Inc.

During this long off-post period, besides my day job, I’ve been doing some experiments, developing some tools and brainstorming lots of ideas, mostly related to performance and JavaScript. I do have some post drafts and will be publishing them soon. Here are a few topics I’m covering along this year:

• setTimeout minimum delay limit
• Prefetching CSS images
• Problems with gradients filters on IE links hover
• Flipping page direction RTL/LTR easily – RTLzr a Firefox extension
• JavaScript Interviews Exposed (series)
• Lazy Enhancement
• JavaScript video subtitle
• JavaScript video timeline marks
• Deleting a removed node from DOM

Stay tuned!

Although I’m not really into crazy algorithms challenges I thought I’d give it a try just to see how fast the solution would be in JS, note that most of the solutions submitted are in C/C++ or Java, much faster than JS and to make things worst the interpreter was Rhino, anyways we went ahead and recreated the solution in Javascript, so now it was time to test it… a little more tweaking to make it receive inputs via console and we had it running, right away we realized that our output via stdout was slowing us down, printing 10 times in a row all primes until 1 billion in the shell is not really fast but it was required to, I knew we had little or no chances to get approved but anyways we tried… and as I suspected we didn’t get approved :(, but I decided to test locally in different browsers/engines with and without output.

Here are the results, I also built a test runner so you can test on your own:

• Chrome is usually the best, V8 is blazing fast but it chokes when outputting the results through WebKit
• Rhino does a great job specially with a high number of runs because of JVM
• Firefox runs nicely with short ranges but stops the script because of the long time running
• Opera wasn’t fast but it never crashed or stopped

Write a JavaScript function that generates random lotto numbers. This function has to return an array of six different numbers from 1 to 49 (including both) in ascending order. You may use features of ECMA-262 only, that means no Array.contains and stuff. You must not induce global variables.

The function has to look like this

var getRandomLottoNumbers = function () {
    // your implementation here
};

Minify your function using JSMin (level aggressive) and count the bytes between the outer curly braces.

It might look simple but it turns out to be an interesting challenge considering there’s a bunch of ways to solve it where the length of the minified final implementation is the main concern: the smaller the better. He describes his solution and invites others to post their solutions as comments. His final solution for such challenge has 86 bytes:

var n=[],i=0;for(;++i<50;)n.push(i);for(;--i>6;)n.splice(i*Math.random()|0,1);return n

Some readers wrote even smaller solutions such as:

return [,,,,,,].map(function()Math.random()*50|1)

However this one is by far the smallest, 49 bytes only, it is invalid because it doesn’t fulfill the rules for the following reasons:

1. map is not part of ECMA-262 specification
2. [,,,,,,] is inconsistent across browsers, IE would create an array of 7 undefined values
3. it’s not in ascending order
4. may contain duplicated values

So far the smallest solution that fulfills all the rules has 65 bytes:

for(var v=[],m=6,n=49;m;--n)Math.random()*n>m?0:v[--m]=n;return v

Revisiting

I’ve also contributed with my solution but with another fashion way: Using a single line chaining solution, i.e. no semi-colons separating statements, like: return a().b.c().d.e()

My solution has 200 bytes:

return [0,0,0,0,0,0].join().replace(/0/g,function(){Array.a=Array.a||{};var x;while((x=Math.random()*50|1)in Array.a){}Array.a[x]=1;return x}).split(',').sort(function(a,b){delete Array.a;return a-b})

It’s not the smallest compared to the other solutions but it does fulfill the rules and is in a single line chaining. It might be a little obscure for some but I will break it down into smaller peaces:

return
    [0,0,0,0,0,0]   // creates an array with 6 positions filled with 0's
    .join()         // converts the array into string: "0,0,0,0,0,0"
    .replace(/0/g,  // replaces all 0's in the string using the following function
        function () {
            Array.a = Array.a || {};        // augments Array with an object property only once
            var x;                          // variable to store a random number
            while (                         // while condition: assures no dupes
                (x =                        // assigning a value to x:
                    Math.random() * 50 | 1  // generates a random number times 50 or 1 (when 0)
                ) in Array.a                // checks if x isn't in the augmented Array object
            ) {}                            // empty block for while statement
            Array.a[x] = 1;                 // adds number as property into Array object
            return x                        // replaces the "0" found by the random x number
        }
    )               // end of replace function
    .split(',')     // converts string into array of strings using comma as separator
    .sort(          // sorts the array using the following compare function
        function (a, b) {   // elements to be compared
            delete Array.a; // restores Array, removing previously augmented property
            return a - b    // < 0 then a < b; = 0 then a = b; > 0 a > b
        }
    )               // end of sort, a sorted array is returned

I also invite you to post your single line chaining solution as a comment. Happy chaining. ;-)

Go ahead and give it a try, the YUI Blog post is a good starting point YUI 3.0.0: First GA Release of YUI’s Next-Generation Codeline

You can also check all the other cool examples created by Paul Donnelly http://pipes.yahoo.com/31337 or even check Pipes Blog for their latest updates.

Math.max.apply(Math, [4,8,3,5,1,2]);

And bingo! It works!

Previous work

Since it seemed so easy I thought that somebody else would had already figured this out before and I did a quick search for Math.max.apply and *bam!*: the first occurrence was a John Resig’s post back in 07’s where he describes such technique for augmenting Array type. Really handy.

Performance

My main concern to decide whether to use this technique was its performance, so I ran a quick test comparing it to a very popular for loop algorithm and an optimized loop for a given array of random numbers:

var i, max,
    a = [],
    len = 1e4;
 
/* create an array of ten thousand random numbers */
console.time('array creation');
for (i = 0; i < len; i += 1) {
    a[i] = Math.floor(Math.random() * 1e4);
}
console.timeEnd('array creation');
 
/* for loop */
max = -Infinity;
console.time('for loop');
for (i = 0; i < len; i += 1) {
    if (a[i] > max) {
        max = a[i];
    }
}
console.timeEnd('for loop');
console.log(max);
 
/* optimized loop */
max = -Infinity;
i = len;
console.time('optimized loop');
while (i--) {
    if (a[i] > max) {
        max = a[i];
    }
}
console.timeEnd('optimized loop');
console.log(max);
 
/* Math.max */
console.time('Math.max');
max = Math.max.apply(Math, a);
console.timeEnd('Math.max');
console.log(max);

Running this code on my firebug console (Firefox 3.0.14), I got the same largest number on each technique within the array as expected and the following times:

• array creation: 89ms
• for loop: 29ms
• optimized loop: 20ms
• Math.max: 1ms

Wow! This is pretty fast! Huh? You can copy the code above and paste on your firebug console in order to get your own results or you can check it out here.

Conclusion

This technique deserves lots of credit for its simplicity and speed, it’s those one-line codes that beats any fancy and complex algorithm that once you get to know, you start using every time you need, however it’s not true for all browsers :-(

In the article WebKit Page Cache I – The Basics Brady Eidson talks about the Page Cache feature on WebKit, as he stated it’s not about caching in the HTTP sense, storing raw files on disk or even caching resources in memory. “More simply, when you leave the page we pause it and when you come back we press play.”, this totally affects the perceived performance, when you hit the back button, even if you have files cached locally the browser will still have to load it again, run all your scripts, recreate the DOM and so on, so basically “When the Page Cache works it makes clicking the back button almost instantaneous.”

The last time they updated Page Cache was back in ‘02 the web has evolved a lot since then and it’s not easy to keep up to date, you have to take in considetration HTTPS, plugins, frames, page events, although some of these issues have been fixed already like the frames problem, it still a long way to go, anyway it’s great to see that they are working on it.

• Naïve: simple and least inefficient way to search in strings, it basically checks every position in the haystack then every position of the needle. The advantage of using this algorithm is that it needs no initial overhead such as auxiliary tables creation. It has O(mn) complexity, where m is the needle length and n the haystack length.
• Boyer-Moore: Efficient searching string algorithm that preprocesses the needle and doesn’t check every position in the haystack but rather skips some of them on each unsuccessful attempt. It has O(n) complexity with O(3n) in the worst case.
• Boyer-Moore-Horspool: It’s a simplification of Boyer-Moore’s algorithm with less overhear during initial needle preprocessing. It also has O(n) complexity but O(mn) in the worst case.

Algorithms by engines

The String.indexOf algorithms by JavaScript engines follows:

SpiderMonkey

Implements the String.indexOf in C with some verifications in string lengths prior to run BMH algorithm in order to avoid long searching for relatively small strings.

Source code available at: ftp://ftp.mozilla.org/pub/mozilla.org/firefox/releases/3.0.13/source/firefox-3.0.13-source.tar.bz2

TraceMonkey

It has exactly the same String.indexOf implementation as SpiderMonkey but in C++.

Source code available at: ftp://ftp.mozilla.org/pub/mozilla.org/firefox/releases/3.5.2/source/firefox-3.5.2-source.tar.bz2

KJS

The main part of the naïve implementation of indexOf follows*:

/* ... */
for (const UChar* c = data_ + pos; c <= end; c++)
    if (c->uc == fchar && !memcmp(c + 1, fdata, fsizeminusone))
        return (c - data_);
 
return -1;

* taken from KDE 4.0 API reference

Files related to String.indexOf method:

• string_object.cpp: defines the prototype for String object where indexOf is in a switch case statement and calls find function.
• ustring.cpp: defines the find function where the naïve algorithm is implemented.

Browse the source code online: http://api.kde.org/4.0-api/kdelibs-apidocs/kjs/html/files.html

JavaScriptCore & SquirrelFish

These engines are known as JavaScriptCore in WebKit Project and was originally derived from KJS, hence still shares the same algorithm for String.indexOf.

Files related to String.indexOf method:

• root/trunk/JavaScriptCore/runtime/StringPrototype.cpp: this is where indexOf method is defined and call find function
• root/trunk/JavaScriptCore/runtime/UString.cpp: look for find function

Source code available at: http://webkit.org/building/checkout.html
Browse the source code online: http://trac.webkit.org/browser

V8

A very smart strategy is applied to the string searching in order to choose the best algorithm based on the length of the needle:

• First of all it checks if there is a non-ASCII needle for an ASCII haystack and bail out if there is.
• Checks if the needle length is less than 5 then uses a naïve solution called simpleIndexOf, because the max shift of Boyer-Moore on such needle length doesn’t compensate for the overhead. This simpleIndexOf function never bails out, it means that the needle will be checked for a match in the whole haystack.
• If the needle length is greater than or equals to 5 another simpleIndexOf function is called. This one considers how much work have been done (unsuccessful matches) in order to stop trying and switch for a better algorithm. This is called the “badness count” which once reached the max, stop the search and returns the index in the haystack where the next algorithm should continue from.
• The next algorithm in the strategy chain is Boyer-Moore-Horspool which also consider the badness count prior to jump to the next algorithm.
• The last one is Boyer-Moore which has some initial overhead when creating good and bad shift tables.

Source code available at: http://code.google.com/p/v8/wiki/Source?tm=4

Rhino

Rhino runs on top of Java Virtual Machine and uses the java.lang.String.indexOf from Java language implemented for such JVM. Interestingly there is a comment saying:

“Uses Java String.indexOf(). OPT to add – BMH searching from jsstr.c”.

Where jsstr.c is the file for SpiderMonkey JavaScript String implementation. Implementing such algorithm in Java might degrade the search performance, unless the java.lang.String.indexOf implementation is much worse than that.

Source code available at: http://www.mozilla.org/rhino/download.html

Other engines

What about Internet Explorer, Opera and other browsers JavaScript engines? As they aren’t open-source projects I could not check their codes out. :-(

Benchmark

By running a simple test across some browsers we can have an idea how fast/slow is String.indexOf on some JavaScript engines although this doesn’t necessarily mean an algorithm is better than another because the performance of the engine itself might affect the outcome.
The test consists of the average of a 100 times running a search for the word “foobar” in the middle of a ~1200 length “ipsum lorem” text iterating 1 million times each search. Try it yourself.

The results in the follow table were taken by running this test on the same machine (Pentium 4HT, 3GHz, 1Gb RAM, Windows XP SP3).

* running on the same machine with Ubuntu 9.04 live cd
** running on a VM on a different computer
*** running on Sun JRE 6 – 1.6.0_14

Again, these results don’t prove which algorithm is the best due to different browser performances, however it is worth noting that Firefox 3.0.13 performed better than Firefox 3.5.2 on this benchmark. Internet Explorer had the worst results, it can be either the algorithm or the browser performance itself or even both. :-)

W3C advises:

Ensure that foreground and background color combinations provide sufficient contrast when viewed by someone having color deficits or when viewed on a black and white screen.

And suggests the following algorithm* to calculate the perceived brightness of a color:

brightness = ((REDvalue X 299) + (GREENvalue X 587) + (BLUEvalue X 114)) / 1000

If the perceived brightness is greater than 125, choose black, otherwise white.

* This algorithm is taken from a formula for converting RGB values to YIQ values.

On Doug’s CSS color names page, he listed all color names alphabetically in two columns, the first one uses a black label over the colors and the second one uses white. I have created a Greasemonkey script that adds a third column to that page applying this brightness algorithm that decides between black and white which one works better over each color in the list. You can get and install the script here.

Doug’s CSS color names page with the Greasemonkey script

To get the RGB values from an element’s background color you can use the window.getComputedStyle* method as follows:

var element = document.getElementById('foobar'),
    rgb = window.getComputedStyle(element, null).backgroundColor;

* Use currentStyle on IE, see “Get Styles on PPK’s QuirksMode”

This will bring the RBG values list string in the format: “rgb(255, 255, 255)” for a white background color. You can use a regular expression and apply it over the RGB string in order to parse its values:

var re = /rgb\((\d+), (\d+), (\d+)\)/;
rgb = re.exec(rgb);

The rgb variable now has an array with the split background RGB color values, you can get the separated R, G and B values from the index 1 of the array:

var
    r = parseInt(rgb[1], 10),
    g = parseInt(rgb[2], 10),
    b = parseInt(rgb[3], 10);

Finally calculate the color brightness:

var brightness = (r*299 + g*587 + b*114) / 1000;
if (brightness > 125) {
    // use black
} else {
    // use white
}