Erik Vold's Blog - Daily UserScript

Greasemonkey Optimization: Convert2RegExp

Sun, 24 Jan 2010 01:18:00 -0400

Over the last week I've been spending a great deal of time looking over the Greasemonkey and Webmonkey source code, both because I want to understand both code bases more, but also because I'm interested in Firefox extension internals in general. While looking through these two code bases I saw a common file which could be optimized. This file was the convert2RegExp.js file, which looks like it came from Adblock at some point, at least in part. In fact I saw a number of changes that I could try in order to speed up the function, so I decided to time them all.

Test Factors

Factor I: Check for /\.[^\.ld]t[^\.td]l[^\.lt]*d/ in pattern string character loop

The first thing I noticed was that the regular expression that checks the pattern string for a ".tld" string was being run on every pattern input, this seemed obviously bad to me since there was a loop prior to the regular expression which runs through the pattern string's characters, so why didn't that loop at least check for the ".tld" substring first? the check could be as simple as making sure all of the required letters exist in the string first, or make sure that the ".tld" substring, exactly, is in the pattern string, or what I found to be the best way was to make sure the regular expression /\.[^\.ld]*t[^\.td]*l[^\.lt]*d/ matched the pattern string via the character loop through the pattern string. The average cases and best cases will go much faster despite the fact that the latter case would be matching some pattern strings that following tld regular expression (that is already in convert2regexp) would not match, thus just adding work in this case, and making the worst possible case even slower.

Factor II: Cache tldStr and tldRegExp

The convert2RegExp( pattern ) function creates the tldRegExp and tldStr from literals on every execution! that might be a faster operation I thought, but I expected it to be slower than simply looking up the value of a variable when I timed it, and even though I haven't figured out how to test the memory consumption yet, I expect creating a large string from a string literal over and over again would increase the peak memory usage, and thus the garbage collector pause time as well. So, caching the tldStr and tldRegExp seemed like it would be a small win.

Factor III: Use array.push()/array.unshift() and array.join() instead of +=

From what I've read about Firefox 3.6 the += operator in loops is optimized to use a single StringBuffer, but there were a few += outside of the loop, and I figured some people will probably use versions of Firefox < 3.5 for some time to come still, and using an array there would certainly improve/decrease the peak memory usage. I didn't know what the affect on performance would be, but this change is commonly said to be the better approach for JavaScript in the past to present, mainly because of the memory issue. Furthermore, the more memory that is used, the more work there is for the garbage collector to deal with, which means your computer is even slower, and that time is hard to measure. I do know that a new feature to Firefox 3.6 is that the garbage collector frees the memory in a new thread, which means that older versions of Firefox did not, and that means that the chances of pauses were even greater. For more reading on these changes I am mentioning in Firefox 3.6 please read this article.

The Tests

Description

In order to test the factors listed above I knew I needed a number of different versions of the convert2RegExp function, but the other piece I needed was a collection of pattern strings to test. I made the different versions of convert2RegExp easily, but when it came to making the pattern set(s) to test I had to do some more thinking.

Test Pattern Sets

I may not have made the best choice, but I decided to use two pattern sets:

Pattern Set 0: 3/50 patterns use the magic tld expression, 2/50 do not use the tld expression, but match /\.[^\.ld]*t[^\.td]*l[^\.lt]*d/
Pattern Set 1: 2/50 patterns use the magic tld expression

In retrospect I think testing an even worse case might be advantages, although I don't suspect the tld expression is used very often. It's hard to say however, I would like to see an audit of userscripts.org, but even with that it'd hard to know what the average case is for all Greasemonkey users, even when you take the install counts from userscripts.org into account, although all of that perspective would be nice to have.

I am an avid user of Greasemonkey and I write quite a few userscripts, and I find that in practice that there are very few times when I would need to userscript to use the magic tld expression, so my feeling is that the ratio is probably closer to 1 tld pattern per 100 or more.

Test Pages/Versions

I decided to run my tests of the different factors listed above for FF3.5/FF3.6 on WinXP, OSX, and Ubuntu (only FF3.5). The test pages worth pointing out are:

Original
Alternate 3: test of only factor I
Alternate 5: test of only factor II
Alternate 6: test of factor II + minor change to return a value asap.
Alternate 11: test of factor I + II, uses array.unshift() and array.join(), and returns a value asap
Alternate 12: test of factor I + II, uses array.push() and array.join(), and returns a value asap
Alternate 13: test of factor I + II, and returns a value asap
Alternate 15: test using array.unshift() and array.join() as only change

Test Results

Here are the tests I ran and the results I record (the links are to published google docs spreadsheets, all values are in seconds):

Each test was using a version of convert2RegExp, on a set of 50 patterns, 2500 times.

Results

In all cases alternate 3 was faster than the original.
In all cases alternate 5 and 6 were faster than the original.
In all cases alternate 6 seemed to be slightly faster than 5.
In all cases alternate 15 is much faster than the original for FF3.6, and slightly slower for FF3.5.
For FF3.5 alternate 13 > alternate 12 ~= original ~> alternate 11
For FF3.6 alternate 11 > alternate 13 > alternate 12 > original.

Although for FF3.5 we know that alternate 13 is a bad choice because it uses the += operator which result in O(N^2) characters copied, so we can't use that in my opinion. The final choice has to be between alternate 11 and alternate 12.

This is where I need your help, I have no idea why using array.unshift() is so much faster in Firefox 3.6, and taken that it is, and that the majority of Greasemonkey users will be using the latest version of Firefox, should we use array.unshift() and not array.push()?

Tweet Me!

Goo.gl Now Open For General Use

Thu, 17 Dec 2009 18:55:00 -0400

Three days ago Google announced it's release of Goo.gl a url shortener which is more reliable and trust worthy (to a user) than other services such as tinyurl.com, tr.im, bit.ly, etc.

Now I think all web publishers should maintain their own url shortener which only they can create urls for and control, for example I bought the domain evold.ca, and use the subdomain r.evold.ca as my url shortener. I primarily use this domain to shorten urls to my other domains, like erikvold.com, but I can and do occasionally use it to create short urls for domains that are not mine. As a user, when I see a blog post that I want to share, I first check if the publisher has published a short url for the page, which any smart web publisher does, but for the other web publishers (the majority atm) I have to create a short url, which I can now use Goo.gl to do.

The problem is that Goo.gl does not allow users to use it to shorten links directly. Currently, the Google URL Shortener is only officially available via the Google Toolbar and FeedBurner.

Well, I noticed that this problem was solved yesterday by a Google Chrome extension called goo.gl shortener. Amit Agarwal drew my attention to this extension in a blog post he wrote yesterday, where he pointed out the important javascript parts needed to create goo.gl short urls. So I took this information and opened Goo.gl up with a userscript, a ubiquity command, and a jetpack to help everyone create short urls with Goo.gl, check them out!

A Jetpack: Java Settings

Sun, 13 Dec 2009 11:05:00 -0400

This Jetpack is meant to help Firefox users quickly enable and disable Java or JavaScript, and it is my third entry for the Jetpack 50-line Code Challenge.

Java Settings Jetpack

About

This Jetpack will add a "Enable Javascript" and "Enable Java" menu items to your "Tools" menu for quick access to these settings.

Screen Shot

How To Install

[More]

A Jetpack: Firefox 'Restart' Menu Item

Sun, 13 Dec 2009 09:03:00 -0400

I wrote this Jetpack as another entry for the Jetpack 50-line Code Challenge, it is simply a 'Restart' menu item for Firefox's 'File' menu.

When I was trying to come up with ideas I starting thinking about replacing a number of Firefox extensions I currently use with a lightweight Jetpack. So I instantly thought about Quick Restart, by Juan Carlos Avila B, which I have used a lot in the past, but it had a bunch of extra data packaged with it that I didn't want such as localization (albeit I'm sure this is something others want), xul, css, and images files.

I've used Quick Restart for some time now, and still think it is a great addon, but I'm pleased to say that there is a Jetpack option available now.

Firefox 'Restart' Jetpack

About

This Jetpack is using source lifted from the Ubiquity Firefox extension's built-in 'restart' command.

Screen Shot

How To Install

[More]

A Jetpack: Tweet This!

Sat, 12 Dec 2009 23:18:00 -0400

I wrote my first entry for the Jetpack 50-line Code Challenge a few weeks ago and I would like to share it with you now. The Jetpack is called Tweet This!, and it is meant to help you quickly tweet about a page you are viewing in Firefox with the document's published short url, if it is defined (otherwise tr.im is used).

Tweet This!

Details

The Tweet This! Jetpack adds a 'Tweet This!' menu item to Firefox's 'Bookmarks' menu and context menu, which when used, will allow the user to Tweet about the page they are on. A user can select some text on the page, or else the page's title will be used for some text in the tweet, and then the Jetpack will first check if the text + long url is less than 140 characters long, and just use the long url if so, but otherwise it will use my Get Short URL service (hosted by Google App Engine) to find the shortest url for the page, which is published by the page, and if one has not been published which is smaller than a length you can change in settings, but is by default 35. If the shortest url found is not shorter than the setting length specified then the tr.im service is used to create a short url for the page.

After the Jetpack has a short url for the page, and some text to tweet about it, it will finally trim the text so that the tweet is equal to 140 chars if necessary, then send the tweet, and notify you with the tweet if it has been sent (also the username that it was sent from is displayed).

Notes

If you do not see a notification, then an error occurred, and no tweet was sent, so it will be safe to try again, just make sure you wait about a minute before trying again (don't be too hasty). An error would only occur if the Tr.im or Twitter servers return an error.
The jetpack settings are pretty basic, and while they provide a range type they do not show the range to the user, or the value the user has selected in the range. Hopefully this will be changed in short time, but until then I'll just let you know here the Max URL Length range is from 20 to 100.

[More]

Would You Like To Know More?

Sat, 28 Nov 2009 21:05:00 -0400

This is just a last moment idea inspired by the movie Starship Troopers which flashed in to my mind a couple of days ago as I was thinking about Jetpacks for the Jetpack for Learning Design Challenge. It is primarily a Microformat/Link Type proposal for rel-info with some ideas and prototypes demonstrating how it could be used.

Abstract

When you are reading something on the web there are usually pages which exist elsewhere on the web that would provide background information, and further reading if you desired to dig deeper into the subject(s) you are reading about. Sometimes some of those pages are linked to from the article you are on, but often the link wouldn't make sense in the context of the content, and using a link tag isn't very useful to a user, so the link is not made.

I propose a rel-info link type, even if just as a Microformat, for 'a' and 'link' tags to provide a link to context-sensitive information.

With rel-info a user can read more about the Movie that was discussed at Netflix or IMDB easily for example, because the publisher (or a script the user subscribes to, more on this later) provided a rel-info link which the user can easily find and follow with a Jetpack, Firefox extension, or some other browser extension.

Proposal

When rel-info links are provided on a page browser extensions can easily extract them from the page, which can lead to a large number of use cases, of which I am sure I have only just scratched the surface. There is another side to this coin however which is that there are a large number of ways that rel-info links might be added to a page.

Let's explore the latter case, first the person who published the page could add rel-info links, but then browser extensions could add rel-info links, they could also search for and remove rel-info links. A user could subscribe to a person's or institution's suggestion feed or script which adds and/or removes rel-info links to pages, along with using a AI based browser extensions to add rel-info links.

When the rel-info links are going to be consumed there are some other interesting possibilities, for example a browser extension could filter the links by a HTML 5 'data-topic' attribute by keeping a list of topics that the user dislikes or likes, the domain could also be used for filtering. A browser extension could allow the user to mark pages as read so that they are removed from pages in the future as another example.

Prototypes

To test this link type out with a Jetpack I first had to add it to some pages, so I decided to write a couple of UserScripts to do this demonstrating how they can be dynamically added to pages by anyone even users themselves. The first userscript was to add the rel-info link type to IMDB links, and another to add the rel-info link type to Wikipedia links.

If you install the above UserScripts then you should find rel="info" or rel="... info" on your IMDB and Wikipedia links. Once you have done that you can check out and install the "Would You Like To Know More?" Jetpack. This is a slidebar Jetpack, and when you open this slidebar the focused tab is then scanned for rel-info links, if any are found then they are displayed in a list for you to choose from, if you click one of the provided links a new tab will be opened for the new page.

These UserScripts and the Jetpack take advantage of HTML 5 'data-' attributes, by adding a 'data-source' attribute to the rel-info links added on the userscript side, which the jetpack was written to check for and display if found. This is an example of how HTML 5 'data-' attributes can be used with the rel-info link type which I propose to create more interesting results.

A Jetpack: Google Web History

Wed, 18 Nov 2009 05:48:00 -0400

This Jetpack adds a "Show Google Web History" menu item to your Firefox "History" menu.

Get it at:

Jetpack Gallery: http://jetpackgallery.mozillalabs.com/jetpacks/123
Userscripts.org: http://userscripts.org/jetpacks/270
GitHub: http://github.com/erikvold/google-web-history-jetpack

A Jetpack: Greasemonkey Context Menu

Wed, 18 Nov 2009 05:32:00 -0400

This Jetpack will add the Greasemonkey menu commands to your context menu.

Screen Shot

Get it at:

Jetpack Gallery: http://jetpackgallery.mozillalabs.com/jetpacks/118
Userscripts.org: http://userscripts.org/jetpacks/267
GitHub: http://github.com/erikvold/greasemonkey-menu-jetpack

The Daily UserScript: UserScripts.org Linkify Tag Clouds

Mon, 16 Nov 2009 20:24:00 -0400

This userscript will linkify some (maybe all) tags clouds on userscripts.org that are not already linkified.

The Unpleasantry:

The tag cloud on user profile pages is not linkified, meaning users have to manually search for the tag..

The Alleviation:

Once you install the "UserScripts.org Linkify Tag Clouds" UserScript the tag clouds on user profile pages will be linkified.

A Jetpack: Twitter Message Notifier

Mon, 16 Nov 2009 20:11:00 -0400

This is a simple Jetpack Twitter notifier, which checks for new mentions or direct messages for your account and notifies you of them.

The Jetpack loops through tweets to notify you about every 7.5 seconds, until it has no more remaining, then waits 5mins and checks for more DMs or mentions from your Twitter account.

Get it at:

Jetpack Gallery: http://jetpackgallery.mozillalabs.com/jetpacks/115
Userscripts.org: http://userscripts.org/jetpacks/266
GitHub: http://github.com/erikvold/twitter-msg-notifier-jetpack

The Daily UserScript: Add The "I'm Feeling Lucky" Button To Google Searches

Sat, 14 Nov 2009 06:57:00 -0400

This userscript adds the "I'm Feeling Lucky" button to Google search result pages.

Once you install the "Add The "I'm Feeling Lucky" Button To Google Searches" UserScript then Google search results pages will have the "I'm Feeling Lucky" button.

The Daily UserScript: Stumble On Blank "I'm Feeling Lucky" Google Searches

Sat, 14 Nov 2009 06:45:00 -0400

If you leave the Google search field blank and hit the "I'm Feeling Lucky" then this userscript will have StumbleUpon send you to a random page.

Get the Stumble On Blank "I'm Feeling Lucky" Google Searches UserScript here.

The Daily UserScript: GitHub Auto Expand Watched Repository List

Sat, 14 Nov 2009 06:25:00 -0400

This userscript will automatically expand your watched repository list on your dashboard at GitHub.

The Unpleasantry:

Having to click the link that expands my watched repository list every time I want to see the whole list.

The Alleviation:

Once you install the "GitHub Auto Expand Watched Repository List" UserScript the watched repository list will expand automatically.

The Daily UserScript: w3schools Ads Remover

Sat, 14 Nov 2009 06:11:00 -0400

This userscripts removes most of the ads from w3schools.com.

The Unpleasantry:

Seeing ads.

The Alleviation:

Once you install the "w3schools Ads Remover" UserScript most, if not all, ads will be removed from w3schools.com.

The Daily UserScript: Remove Ads From Mixx

Tue, 10 Nov 2009 20:30:00 -0400

Today's userscript is another simple one to remove ads, this time from Mixx.com. Even if you are using Adblock Plus or something similar to block ads from being displayed at Mixx, the space where they would be still remains, this userscript will remove those spaces that that the pages at Mixx are easier to read.

The Unpleasantry:

Seeing Ads at Mixx.

The Alleviation:

Once you install the "Mixx Ads Remover" UserScript most if not all of the ads will be removed from Mixx.

Erik Vold's Blog - Daily UserScript

Greasemonkey Optimization: Convert2RegExp

Test Factors

Factor I: Check for /\.[^\.ld]*t[^\.td]*l[^\.lt]*d/ in pattern string character loop

Factor II: Cache tldStr and tldRegExp

Factor III: Use array.push()/array.unshift() and array.join() instead of +=

The Tests

Description

Test Pattern Sets

Test Pages/Versions

Test Results

AMD 2.21Ghz, DDR2, WindowsXP

Intel Duo 2.0Ghz, DDR3, Mac OSX

Intel Duo 2.0Ghz, DDR3, Windows XP

Intel 2.0Ghz, DDR, Ubuntu

Results

Goo.gl Now Open For General Use

A Jetpack: Java Settings

Java Settings Jetpack

About

Screen Shot

How To Install

A Jetpack: Firefox 'Restart' Menu Item

Firefox 'Restart' Jetpack

About

Screen Shot

How To Install

A Jetpack: Tweet This!

Tweet This!

Details

Notes

Would You Like To Know More?

Abstract

Proposal

Prototypes

A Jetpack: Google Web History

Get it at:

A Jetpack: Greasemonkey Context Menu

Screen Shot

Get it at:

The Daily UserScript: UserScripts.org Linkify Tag Clouds

The Unpleasantry:

The Alleviation:

A Jetpack: Twitter Message Notifier

Get it at:

The Daily UserScript: Add The "I'm Feeling Lucky" Button To Google Searches

The Daily UserScript: Stumble On Blank "I'm Feeling Lucky" Google Searches

The Daily UserScript: GitHub Auto Expand Watched Repository List

The Unpleasantry:

The Alleviation:

The Daily UserScript: w3schools Ads Remover

The Unpleasantry:

The Alleviation:

The Daily UserScript: Remove Ads From Mixx

The Unpleasantry:

The Alleviation:

Factor I: Check for /\.[^\.ld]t[^\.td]l[^\.lt]*d/ in pattern string character loop