We're in a very unique position as we're primarily aiming to teach students who've been through our previous math and science-centric curriculum. Because of this we can create some rather compelling exercises and projects that never would've been feasible otherwise.

The prospect of teaching the JavaScript language as a first language is actually really exciting. Teaching prototypal inheritance to experienced classical-inheritance-using developers is normally rather frustrating (and results in many libraries springing up attempting to replicate the classical style of inheritance in JavaScript, which is a whole realm of weirdness in-and-of itself). Teaching prototypal inheritance to someone who has never seen any form of inheritance before will decidedly be an easier task. The same goes for learning functional programming. JavaScript is a great language for experiencing functional programming and can be a major focus of our curriculum as a result.

As we've begun to look at the prospect of JavaScript-as-a-first-language a number of obvious warts stick out (as is obvious to anyone who has worked with JavaScript for any duration). To make sure that general warts don't crop up we will be using some form of linting (either JSLint or JSHint or similar) in the code editor to give the users contextual information on what's happening with their code and why they should be writing their code in a certain way.

We want to go beyond basic syntax tweaks though and find ways of using the language that'll result in an easier learning experience. In particular there are two changes which will likely result in a much simpler on-ramp to learning.

Note: These particular recommendations really only make sense if you're teaching JavaScript to someone who has never seen the language before and is really only programming with a set of specific, well-coded, libraries. Obviously more will have to be taught in order bring the students up to the level of "see any random piece of cross-browser JavaScript code and understand what it does."

Type Coercion

Type coercion is just a complete mess, as many many others have pointed out and as what Douglas Crockford typically teaches, as in JavaScript: The Good Parts.

It might make sense to discuss it far later in the education cycle... like after learning about prototypes, functional programming, and closures. Basically after everything that's actually important.

The first change that I'm recommending is that the students will only ever see, and use, === (and !==). While using '==' does have the advantage of being syntactically shorter there is so much type coercion baggage attached to it as to make it an exercise in futility to try and teach early on in the learning of programming.

The one exception that might be worthwhile to teach later on is the case in which you wish to see if a variable contains a null or undefined value. This can be done easily with a simple someVar == null check and is likely the one useful case of ==. (Another noted exception is the browser bug in IE where === checks against Window objects will always return false, but it's unlikely that we'll cover such specific browser issues in our curriculum.)

Falsy Values

For the same reasons that == can be messy, so can falsy values. Enforcing strict boolean checks would result in less edge cases but would certainly result in longer code. Perhaps education of falsy values can be limited to booleans, null, and undefined with number and string falsy values left for a later exercise.

Function Declarations

Perhaps the most interesting change that we can make is a rather subtle one, but it's eschewing normal function declarations for creating anonymous functions and assigning them to a variable.

There are a number of good habits that are instilled when you use this particular technique.

• Makes it easier to understand "functions as an object". I've found that when you show new developers a function being assigned to a variable it suddenly becomes much more obvious that a function is actually an object and can be manipulated as such (and that a function can be passed as an argument to another function). Thus students are advanced along the path towards a better understanding of functional programming.
• It enforces good semicolon habits. Traditional function declaration is the only situation in which semicolons aren't needed (save for conditional statements and loops, naturally) and it makes it much more obvious when they're required all the time.
• Doesn't have much of the baggage traditionally associated with functions and scope.

Block Scope

This is the remaining area that'll certainly be a challenge for any introductory student to understand and yet I don't see a particularly good solution here. The issue of variables declared within for loops hoisting up is more than enough to make most developers heads spin. I'll have to see if we can't come up with some intuitive ways of explaining how variable declaration works (and combining it with vigilant lint enforcement) rather than having a purely technical solution.

(While (function(){ ... })(); is a solution I'm skeptical that we'll be able to teach that early-enough on as to make it worthwhile.)

JavaScript as a First Language

It should be noted that while we're starting with JavaScript as a first language - largely due to its ubiquity, desirability in the larger workforce, lack of prior installation requirements, and ability to create something that's easy to share with friends - we're not going to be myopic and only focus on JavaScript. There are so many things that can be learned from other languages, not to mention entire skillsets that aren't terribly relevant to in-browser JavaScript, that it behooves us to try and bring as much of them into our curriculum as possible.

I talk a little bit more about our choice to use JavaScript and some of the browsers that we'll want to support in our development in the following video:

By all accounts I want to try and avoid any features that would cause cross-browser weirdness to spring up. As a result we'll be making extensive use of libraries (for drawing to a canvas or manipulating the DOM) and using only JavaScript language features that work consistently in the browsers that we end up supporting.

Today we're pushing live a complete rewrite of the Khan Academy Exercise framework (live demo).

A big push at Khan Academy has been to write more-and-more exercises for students to practice with. Naturally, to increase the number of exercises that we have, we needed to make it easier for team members, and casual committers, to write them.

When I was first looking in to Khan Academy I did a bunch of digging through their code base (which is Open Source) and noticed that a lot of effort was going in to writing exercises. Interestingly all the exercises were being written in pure JavaScript and were dependent upon the server component in order to run properly. To me this seemed like a massive barrier to entry.

Brand New Framework

When I started just over two months ago I immediately went about rewriting the framework to use semantic HTML and not rely upon any server-side components whatsoever. To provide an example of the change that was made here is one particular exercise, Significant Figures 1, written for the old framework and written for the new framework. You can view the live version of the exercise, as well.

Significant Figures 1 went from 191 lines of code down to 58.

Note the dramatic lack of "code" - most logic is encapsulated and reduced to a series of variable declarations (some with minimal logic). Additionally utility functions were made significantly more useful, and generic, shared across exercises (some of this was done in the old framework but a complete rewrite allowed us to find areas of obvious overlap).

The result of the new framework is an interesting mix of semantic markup and logic - wrapped in a form of highly specialized templating. Tons of details regarding the specifics of the framework can be found in the Writing Exercises tutorial.

In short, some of the cool new features of this framework include:

• A full module system for dynamically loading specific utilities (such as graphing).
• A brand new templating framework, including templating inheritance, that makes it easy to reduce repeated code in exercises (some examples).
• A brand new graphing framework (written by Ben Alpert, named 'Graphie') that's built on top of Raphael. This framework provides a simple API for creating all sorts of graphs and charts, it's used extensively throughout the exercises.
• An extensible plugin system for creating new answer types (to expand beyond basic multiple choice or fill in the blank).

Of course, that's saying nothing of the actual user interaction as well. Most of the new framework's logic is contained on the client-side and is generated directly off of Khan Academy's REST API.

By moving logic to the client-side we're able to have a much more interactive experience (doing all problem generation on the client-side, doing Ajax-y background submissions, things of that sort).

Testing

A big concern for us, with this rewrite, was to ensure that the quality and integrity of exercises was maintained well into the future. We wanted to make sure that the content of the exercises were correct and that regressions do not occur over time.

In fact we have three levels of testing:

1. We have unit tests for our modules and utility functions (ensures that stuff like the templating will continue to work correctly).
2. We have an interactive interface for generating unit tests for any given exercise (details below).
3. We have a "Report a Problem" interface for sending post-deployment issues directly to our bug tracker.

The second stage is particularly interesting. On a fundamental level it's hard to unit test something as complex as an exercise. While we can ensure that they still work at a functional level we can't verify if the problems make sense, or if graphs look correct, or if it's even possible to pick the right answer.

For these reasons we've introduced a new testing interface in which we use human developers as unit testers. When in test mode an additional panel is displayed asking the user to provide additional details regarding wether the problem is working correctly, or not. We ask them to really dig into the exercises and make sure that they're working correctly, hints are being displayed properly, and other things of that nature.

All of this information is collected and distilled into a piece of JavaScript code that is dropped into our test suite, all pushed into QUnit. At the moment we have around 2414 unit test collections with over 10,000 assertions.

At the moment we're working on ways of having better reporting and integration with our development process, for all those unit tests.

Development Process

I'm rather pleased with how the overall development process worked out. We actively kept both the code open (it's up on Github and it's MIT licensed) and the process open as well. We've had contributions from over twice as many outside contributors than members of the Khan Academy team (although the vast majority of the development was done by members of the team).

We have a detailed Getting Involved guide that explains how exactly anyone can participate in the development of the framework (or in the authoring of new exercises).

Predominantly we've been coordinating through a public HipChat room, using the Github Issue Tracker, and managing all the exercise work through a series of Google Spreadsheets.

We're going to be transitioning now into creating a ton more exercises and we'd love to have even more help from the community. There is a ton of information on how to get involved in the wiki.

Next Steps and Thanks

There are a few things that we're looking to do in the near future: Bring offline support to the exercises (for those with spotty internet connections or those using the upcoming iPad/Android application), client-side translation of content into other languages, and exercise answer checking using Node.js and JSDOM.

I also want to take this opportunity to thank everyone at Khan Academy, and all the community contributors, for helping to make this project happen. I especially want to thank Marcia Lee, Ben Alpert, Jeff Ruberg, Igor Terzic, Omar Rizwan, and Ben Kamens for their help in getting this out the door.

I should also mention that Khan Academy is hiring devs. We're looking for both server/client devs (Python/JavaScript) and also mobile devs (iOS and Android).

This ends up being a double-edged sword. While it's great to provide a ton of problem variety to the students it's fundamentally tricky as we want to have a manageable sample size of problems so that we can analyze student behavior and responses. For this reason we want to reduce the pool of possible problems to a more-manageable size (like about 200 or so - we'll experiment with exact figures as time goes by). Most students will only do about 10-20 problems before moving on (since we define a 'streak' as having completed 10 problems in a row correctly) - although we want to provide enough of a pool to allow adventurous users to explore more.

Having a smaller pool size creates another issue though: Potential for student overlap. If there's one thing that we've learned so far it's that students are quite resourceful and identify patterns very quickly. They will realize if they start on the same problem together and if the problems go in the same order.

On top of this we need to make it so that every time the student hits the exercise they are presented with the same exact series of exercises. The first problem will always be the same - and the 50th problem will always be the same for that user. (This will allow us to reproduce the problems at a later date, showing them their problems/answers or analyzing the results.)

Thus we need two pieces of information to determine which problem should be presented to a user: The user's ID and the problem # that they're currently tackling.

We start by placing the user into a simple "bin": We take the CRC32 of the student's ID and mod 200 to start the user at one of the 200 possible exercises. (We picked CRC32 as it's a simple function and we only need a basic level of granularity in the results.) Next we use the CRC32 to figure out how the user should jump through the exercises.

We can't jump through the exercises 1 by 1, since the students will instantly recognize that pattern, so we have to take a random approach - one developed by Khan Academy intern Ben Alpert.

We start with a pool of prime numbers (the first 23 primes, to be exact) and use the user's CRC32 to determine which of those primes will become the "jump distance" for that user.

For example:

Thus when I visit a particular problem I will start at problem # 158, then go to problem 29, then problem 100, then problem 171, etc. On the other hand, if user "jeresig2" visits the same problem they start at problem 171 then visit problem 182, 193, 4, etc.

(Note that we leave out 2 and 5 to avoid creating a circular loop of exercises - 2 will result in 100 repeating exercises, 5 will result in 40 repeating exercises. Of course we could just make the number of exercises prime to achieve a similar result - we'll see!)

Even though we're not using any built-in random number generator in this process, the distribution of chosen problems appears to be similar to a random distribution (since we've effectively implemented one ourselves):

To re-emphasize: We're not trying to stop problem overlap - in fact we want overlap to occur, to give us data to study - but a lack of repeatable patterns has definitely been arrived at here.

We chose a collection of 23 primes because it is sufficiently large - but it also doesn't divide into 200 cleanly (giving users that might have an identical starting position a different jump amount).

Also note that in the final solution we're going to be combining the user's ID with the name of the current problem - so that even if, somehow, two students end up with identical start positions and jump rates on one exercise they will have a different start position and jump rate on other exercises.

If all goes well we'll be opening up the new exercise rewrite for beta testing within the next week or two.

Note: I've been posting interesting dev updates over on Google Plus. Feel free to follow me there if you wish to find out more about what I'm working on with Khan Academy or jQuery.

A relatively controversial change in 1.6 was regarding how attributes and DOM object properties were handled. In 1.6 we wanted to take the major step of completely separating the two, allowing us to create an .attr() method that wasn't quite so mealy-mouthed with regards to how attributes were handled. We did this in 1.6 because we felt that it was a substantial change (we only do major changes in the 1.x major releases of jQuery) and had the possibility of affecting people.

We did a considerable amount of testing on the code and we were quite confident that the amount of problems that people would encounter, while upgrading, would be quite minimal. The biggest pain points, we surmised, would be regarding how boolean attributes were handled (attributes like "disabled" or "selected"). However most of this would be mitigated and would likely have worked fine for users that consistently used .attr() to access and update their attributes.

After making the changes, and publishing 1.6, there were enough complaints that we had changed the API to cause us to reconsider and return .attr() to its sometimes-attribute, sometimes-property, state.

jQuery is in an incredibly tricky position now (and has been for some time). We very rarely add features to the library, for fear of bloat and added API maintenance overhead, and are rarely able to make any sort of API change, for fear of preventing people from upgrading.

Thankfully even though we've reverted some of the changes in 1.6, we've done it in a way that still maintains the performance gains that we achieved with the 1.6 release.

I wanted to try and summarize the .attr() method, to explain how it currently works in 1.6.1, but ended up writing up a sample function instead (note that this is a bit of an over-simplification, please read the code for more details):

Ironically this isn't much shorter than the actual .attr() implementation, I recommend that you check it out.

There's a very good chance that your code, written targeting 1.5.2, will continue to work just fine in 1.6.1 using this particular technique.

However this point now begs the question: Why does .prop() exist?

In short, for two reasons:

1. There are legitimate use cases for interacting with some DOM properties (such as nodeName, selectedIndex, or defaultValue) and we want to provide a simple solution for accessing, and mutating, them.
2. Accessing properties through the .attr() method will be slightly slower than accessing them directly through .prop() (as .attr() calls .prop() internally in order to handle all property-related mutation).

In jQuery 1.5.2, and older, in order to access a DOM property you would have to do something like this:

In 1.6+ you can just do:

Summary: There's a good chance that your code won't be affected at all with the changes that've happened, especially so with the changes in 1.6.1, and jQuery now has a convenience method for handling DOM properties in a simpler, and slightly faster, manner.

Tangentially this reminds me of a common question that I hear: What will be in jQuery 2.0? I have no idea what will be in that release, should it ever arrive, but I do know what won't be in it: A massive API change of any sort. Even when we make, relatively minor, API changes like in the 1.6 release the amount of negative feedback that we get is monumental. If we've learned anything after doing 31 releases of jQuery it's that people like having stability in their API and will cherish that over everything else.

I do want to thank the community though for being so vocal and working to communicate with the team so actively. Without the community's communication and support it's doubtful that the team would be able to continue operating.

I would like to take this opportunity to encourage everyone to get involved with the development of jQuery. We hold active discussions every day in IRC and hold public meetings once a week. We also post weekly status updates if you wish to follow along. Right now we're working on the 1.7 release of the library and are actively encouraging contributions and feedback. If you want to help ensure the quality and stability of the next release of jQuery, the best way to do so is to get involved. Hope to see you around the bug tracker.

I joined the Mozilla Corporation in January of 2007, just over 4+ years ago, as a JavaScript Evangelist. During my time at the company I had an amazing opportunity to promote JavaScript. It's been an incredible experience working with everyone at Mozilla. The company is easily one of the most developer-friendly organizations I can imagine, with some of the smartest coders in the world. Mozilla is hiring across the board - I strongly encourage you to apply if you're looking for one of the best jobs you've ever had.

I had the opportunity to promote JavaScript as a JavaScript Evangelist (and build tools like FUEL, Dromaeo, and Processing.js) and work as a JavaScript Tool Developer (building tools like TestSwarm, FireUnit, and improving QUnit).

Over the past year and a half Mozilla gave me the ability to work on jQuery full-time. This has resulted in 9 releases of jQuery (including today's release of jQuery 1.6) and a drastically improved jQuery organization (we're now under the Software Freedom Conservancy non-profit, hold frequent team meetings, public votes, provide public status updates, and actively encourage participation). Thankfully the jQuery project is running quite smoothly these days, allowing me to scale back my involvement to a more-reasonable amount of time and take on other development work.

Lately I've been looking for a chance to get back into active application development again. I've been working on a few applications in my spare time (mostly mobile-centric applications, using jQuery Mobile) and an excellent opportunity has arrived.

Starting next Monday I will be working at Khan Academy full-time leading their Open Source efforts and JavaScript development. If you aren't familiar with Khan Academy I highly recommend watching the excellent talk at Ted given by Sal Khan himself. In short: Khan Academy is attempting to revolutionize how students learn and how teachers are able to help students.

Learning, and teaching others, has been a life-long passion for me. I see Khan Academy as a fantastic realm in which I can help to promote education and work to design better tools for teaching and getting people involved with Open Source. More than anything else I want to increase the size and activity of the community around Khan Academy. This includes everything from getting more casual contributors (such as those writing problems sets) to getting more code and debugging contributions.

When I start I'm going to be working on rewriting the framework for creating problem sets, constructing the initial version of the iPad application, and working to improve Khan Academy's Open Source efforts.

It's incredibly important to me that Khan Academy is a non-profit and is working to ensure that all generated material (videos, exercises, and even the application itself) will be released for free and in the open. I'm going to be working to ensure that this continues into the future with help from contributors in the community.

Khan Academy is very excited to have me continue working on jQuery during my day-to-day along with continuing to speak at conferences. Additionally I will be continuing to live in Boston for the foreseeable future.

I should note that I've made a personal decision to scale back some other aspects of my professional life. I'm no longer accepting any new speaking engagements. For the rest of this year I will only be speaking at Velocity in June, the jQuery Conference in October, and Fronteers in October.

Additionally a new co-author, Bear Bibeault, has been brought on to help with the completion of my book: Secrets of the JavaScript Ninja. With his help the book should be finalized this year.

I'm terribly excited about this new opportunity and can hardly wait to begin. Thank you to Mozilla for the opportunity these past few years and thank you to Khan Academy for accepting me aboard. Here's to a wonderful 2011!

Landing a pull request from Github can be annoying. You can follow the instructions provided by Github (pulling the code, doing a merge) but that'll result in a messy commit stream and external ticket trackers that don't automatically close tickets. The series of commands that you run will typically look something like this:

git checkout -b branchname master
git pull http://url/to/otherrepo branchname
git checkout master
git merge branchname
git push origin master

Additionally you can pull the code and squash it down into a single commit, which lets you format the commit nicely (closing tickets on external trackers) - but it fails to properly close the pull request. The commands for which look something like this:

git checkout master
git checkout -b bug1234
git pull http://url/to/otherrepo branchname
git checkout master
git merge --no-commit --squash bug1234
git commit -a --author="Original Author "

# To get the author:
git log | grep "Author" | head -1

Pulley is a tool that uses the best aspects of both techniques. Pull requests are pulled and merged into your project. The code is then squashed down into a single commit and nicely formatted with appropriate bug numbers and links. Finally the commit is pushed and the pull request is closed with a link to the commit.

Pulley is written using Node.js - thus you'll need to make sure that you have Node installed prior to running it.

How to use:

Download a copy of Pulley or install it via npm: npm install pulley and configure the repo and bug tracker details in the pulley.js file (this is only necessary if you use a custom, non-Github, issue tracker).

You'll also need to set up your Github username and token into your Git repo. More details can be found in the Github docs.

Once that's complete you can run the following command:

node pulley.js PID # Where PID is the Pull Request ID

For example running the command node pulley.js 332 on the jQuery repo yielded the following closed pull request, commit, and tickets:

The configuration is still a bit janky but it works well enough for me - I'm looking forward to landing a few pull requests to improve it.

Out of all the results two techniques seemed to be most interesting - and promising for reducing general memory usage and load time.

String-based Binary Search

The first technique proposed was left as a comment by a commenter named Randall. He utilized a technique posited by Mathias Nater to create a smaller dictionary and search the results using a binary search.

The technique breaks down into two parts: The smaller dictionary and the binary search.

The smaller dictionary is achieved by taking the regular dictionary and grouping the words by length. Thus you'll end up with clusters of words that are all equal lengths. For example:

If all the words in a particular string are the same length then it makes it quite easy to jump around inside it (you just always move forwards or backwards in the string one word's length). This reduces the resulting, uncompressed, file size of the dictionary by about 110,000 bytes (there is now one less space for each word in the dictionary).

Having the words of uniform length makes it easy to implement a binary search. The code written by Randall is rather simple and effective:

Doing a binary search will almost certainly yield a faster result compared to a simple linear search through the string (such as doing a .indexOf).

Trie Stored in a Succinct Data Structure

The other solution that popped up was proposed by Steve Hanov. His solution was to continue utilizing the Trie structure but store it in a succinct data structure. He explains it extremely well so I would highly recommend visiting his blog to get the full details of the solution.

In short all the leaves of the Trie are given a number and stored in a table (resulting in a data structure for lookups and a data structure for the actual data itself). Additionally he went a step further and encoded all the data using Base 64 and modified the algorithm to utilize that encoding - thus all the encoded data can remain as a string and never have to be turned into a large JavaScript data structure.

Ideally this solution will provide a much smaller file size and memory usage.

File Size Analysis

We still want to make sure that the file size of the dictionary isn't too large - saving us some potential bandwidth costs. Digging in to the file size results yields some very interesting data.

Unsurprisingly the uncompressed binary string is smaller than the plain string - but quite surprisingly the final gzipped size actually ends up being larger than the original. I can only assume that the spacing in the original ended up helping the gzip algorithm compress the resulting text easier - definitely not an intuitive result, though.

Additionally when we look at the results for the succinct Trie we do see that it's uncompressed file size is quite small (only about 300KB). Amusingly, its compressed file size ends up being larger than any of the previous Trie structures - but still smaller than the regular strings.

If we were only concerned with file size then the suffix optimized Trie would still be the way to go.

Load Speed Analysis

As with before, analyzing the initial load speed of the dictionary ends up being crucial. If we're utilizing a JavaScript object we have to evaluate it first - and that can end up taking a considerable amount of time.

Thankfully both of the new techniques load virtually instantaneously (taking only 0.65 - 1.7ms to load the whole dictionary, which makes sense, since they're both coming from simple strings and require no code evaluation).

Search Speed Analysis

As I mentioned in my last post, the performance of word lookups wasn't nearly as important in my particular use case as all the other considerations. Having a lookup take a couple milliseconds was OK since they were only going to occur every couple seconds or so. This may not be the case for every application - and I still wanted to make sure that the code wasn't going to take any major performance hits.

The binary string search ends up being quite fast - even faster than the old Trie search, which is quite promising. However the new Succinct Trie ends up being disturbingly slow (taking about 5.5ms to look up a word in Node.js on a fast machine). I double-checked and the lookup time for finding a word on an iPhone 4 using iOS 4.3 is about 46ms. Even taking that into account I think that's still a lookup rate that I can live with in my particular application. However it most certainly will be too slow for many situations (and in those cases they'll likely want to use the Binary String technique).

It's not clear to me how much of the Succinct Trie's performance stems from its implementation. Perhaps there could be some improvements made to it to increase its final word search time.

Memory Usage Analysis

I finally revisited memory usage, as well. This continues to be critical on mobile devices. Using too much memory will cause all sorts of problems and frequently force the browser to reload your application.

The Binary String technique does well. Being a simple string (and of a smaller total size) means that it uses less memory as well. However the Succinct Trie technique does absolutely stellar - as it's a string as well, and since it's total uncompressed size is only about 1/3 of a MB, that's all the memory that it ends up using. This is fantastic and certainly a huge encouragement towards using this technique.

Conclusion

Even though it's not quite as small (compressed file-size-wise) as a regular Trie and even though its lookup speed is significantly slower than any other technique (but still usable) - I'm heavily inclined to use the Succinctly Stored Trie Structure. I would definitely like to encourage everyone to look at this particular technique further as, currently, it provides excellent memory usage, reasonably-small file size, and virtually non-existent startup overhead. If you're OK with having relatively slow word lookups then this is certainly the technique for you.

If slow lookup speed is undesirable then I would be inclined to use the binary string search technique (as it still provides decent memory usage, reasonable file size, and reasonable memory usage).

As always, all the code and tests are up on Github:
https://github.com/jeresig/trie-js

Raw Data

The raw data for the updated tests (which can be found in my Trie.js Github repo) are as follows:

Binary String
--------------
Normal: 806KB
Gzipped: 326KB
Build Speed: 174 (1.74ms per)
Find Speed: 369 (0.0033ms per)
Not Find Speed: 197 (0.0012ms per)
Private Memory: 112.2MB (0.98MB per)

Succinct Trie
--------------
Normal: 317KB
Gzipped: 197KB
Build Speed: 65 (0.65ms per)
Find Speed: 609985 (5.43ms per)
Not Find Speed: 622700 (5.54ms per)
Private Memory: 47.1MB (0.33MB per)

A Trie is a relatively simple data structure. At its simplest form you're building a tree-like structure where each final leaf results in a complete word. This allows for some very efficient use of file size - reducing common prefixes in words quite easily.

I looked through a number of JavaScript Trie solutions and yet was not terribly pleased with them. They were either total overkill (including large object structures and functionality far beyond what I needed) or weren't compressing the resulting data structure enough. The closest in functionality that I found, to what I wanted, was what was written by Henrik Hinrichs, called wordlistparser. Wordlistparser creates a simple Trie structure using Node.js.

I've dumped my work-in-progress JavaScript Trie Generator up on Github (note that it requires Node.js to run).

Generating a Trie

The basic Trie generation functionality is as follows (note that I use '0' or '$:0' to indicate a complete word):

Optimizing the Structure

While this is fine I wanted to go a step further. Rather than having single letters at every leaf of the tree I saw much room for optimization. Dave Ward posted a sample tree structure which was rather similar to what was generated by Henrik's code (only Henrik's code used '$:1' instead of 'end:true' to save bytes). Looking at the resulting tree structure provided by Dave I was not terribly pleased with the resulting number of objects or code length.

Code posted by Dave Ward

I saw that letters that only had a single child could be reduced into a single string. "r a t" could just become "rat". Additionally there was no need to have a bulky {$:1} structure just to denote the end of a word when you could just use the number 1 to indicate that as well.

Possible Optimization

This change compresses the structure of the Trie down to its bare minimum - using only 3 object literals instead of the previous 12. Using the particular Trie structure makes lookups slightly more challenging (you need to look at the entire start of the word string, rather than just the first character) but it still seems to perform well enough.

The code for optimization:

There's still room for some additional improvement, though. I looked at the changes proposed by the directed acyclic word graph and realized that there was a minor tweak that could be made for improving file size even more: Reducing the number of common suffixes.

For example if you had the following words: sliced, slicer, slices, diced, dicer, dices - you would note that they have common endings (d, r, s) that could be reduced. I added another simple improvement to my Trie implementation that took this into account.

While it's not as impressive with only two root words - it ends up working surprisingly well when you have over 100,000 words, reducing file size even more. The full code for finding, and reducing, the common suffixes can be found on Github.

Finding a Word

To find a word in the Trie it requires a little more work than the traditional Trie search:

Note that we have to do the indexOf and slice operations on the word in order to get at the proper substrings that we need for comparison. Additionally we have to make sure that we substitute in the suffix objects that we've removed previously. In all it's likely to add some level of performance overhead, compared with a traditional Trie, but considering how fast it is already that hit really ends up being negligible.

Further File Size Optimization

I did two final tweaks to save on file size. First, I remove all the quotes in the file. Yes, this makes it no longer valid JSON - but that's OK for my particular situation (I'm loading it as a JavaScript file). Second, I go through and re-quote all the reserved words that are used as object property names. Thus { for: 0, in: 0, zoo: 0 } would become: { 'for': 0, 'in': 0, zoo: 0 }. This final result makes the best use of file size while still working properly in all browsers.

File Size Analysis

The biggest win provided by a Trie should be related to its decrease in file size. The plain string dictionary contained 112,429 words in it and clocked in at 916KB so it seems like any decrease should be possible.

I did multiple levels of comparison. Comparing the basic string version of the dictionary (that I discussed in the last blog post), the simple Trie (no optimizations), the optimized Trie, and the suffix optimized Trie.

The result is quite interesting. The unoptimized, uncompressed, Trie is actually slightly larger than the plain dictionary - but shows some solid benefits once compressed. The further optimizations yield even better results. The final suffix optimized, gzipped, Trie yields a file size of 155KB compared to the initial 276KB of the plain string dictionary. Not bad for over 110,000 words!

Load Speed Analysis

If I was only interested in the download size of the dictionary I would've stopped there - however I want to make sure that no other aspect of the application will be hurt by making this switch. Specifically I want to make sure that loading in the dictionary (converting it from a serialized JS string into a usable form) was still fast. I want to make sure that when I do an Ajax request to get the dictionary, or when I load the dictionary from localStorage, the resulting overhead of parsing all the code doesn't cripple the application.

Unfortunately this is where we start to see some serious problems with using anything but a plain string. In the above chart I include the plain string dictionary and the Trie - but also the hash-lookup technique that I described in my last post.

Note that this load process is going to happen every time the application starts (for example having to re-parse the serialized Trie into a usable JavaScript object).

In the above chart I'm only analyzing the code in one of the fastest JavaScript environments in existence: an unhindered Node.js running on a Core i7 processor - and even then loading the Trie dictionary takes over 100ms. I fear how long it would take on a mobile phone or in an older Internet Explorer browser. If you're wondering why this might be the case think about what's happening here: You're loading and evaluating over 506KBs (after being un-gzipped) of JavaScript code. This will bog down any system - especially a phone.

To drive the point home I ran some tests in some browsers:

Sure enough - even one of the fastest mobile browsers (Mobile Safari 4.3) takes over 4 seconds to load the Trie data structure! In fact it crashed the browser on a few test runs.

Considering that Gmail delays nearly all execution of its JavaScript code, on mobile devices, requiring 506KBs of JavaScript code to be executed up front becomes untenable.

Search Speed Analysis

I didn't want to stop there, though. There were (justified) concerns in reply to the previous post regarding the lookup technique being employed to find words in the plain string dictionary (it was using a simple indexOf operation). This is a linear search through the string and will undoubtedly be much slower than using a Hash or a Trie lookup.

I ran some tests (for both finding valid words and invalid words) and confirmed that suspicion: Doing a linear search across a plain string is fundamentally much slower than using a hash or a Trie. However - note the time scale. In the absolute worst case searching the plain string dictionary for a word yielded lookup times of less than one millisecond. Considering that in my game dictionary lookups are only happening every couple seconds (and not thousands of times a second) I can get away with this performance hit. Presumably if you were building a game that required multitudes of dictionary lookups you might want to go with a faster hash or Trie technique.

Memory Usage Analysis

Finally I decided to take a look at memory usage. This was one last factor that I needed to take into account, with regards to mobile. Using too much memory will cause a web site to reload if the user switches tabs on an iOS device - and will likely cause similar problems on other mobile devices.

Once again, having a simple object yields some impressive gains. Using just a plain string (even though it's 916KB) still ends up using less than half the amount of memory that a Trie structure does - and almost 10x less than a naïve hash.

Raw Memory Usage Data:

(I loaded the dictionary 100 times in Node.js in each case in order to try and get an accurate reading from OS X's Activity Monitor monitor application.)

Baseline memory usage of an empty Node.js application:

Memory usage of a the plain string technique:

(Note that even though I loaded the dictionary 100 times it appears to have been smart and cut down on duplicate memory usage. I even tried to inject some randomness into the dictionary string but still ended up with similar results. I ended up just counting this result once, rather than dividing by 100 like with the other results.)

Memory usage of the hash technique:

Memory usage of using a Trie:

Conclusion

So while utilizing a Trie structure could yield some rather significant file size and word lookup performance improvements - it comes at a cost that is rather unacceptable for an application that's attempting to target older browsers or mobile devices (both in terms of initial load and in terms of memory usage).

I hope the Trie JavaScript code that I've written can be useful to some either way.

If anything though, I hope to communicate that when you are making decisions about what technologies to use - just because something may sound better on paper you really should do some careful analysis of the solution before moving ahead.

Raw Data

The raw data for all my tests (which can be found in my Trie.js Github repo) is as follows:

Plain String
--------------
Normal: 916KB
Gzipped: 276KB
Build Speed: 1 (.01 per)
Find Speed: 47331 (0.42ms per)
Not Find Speed: 71902 (0.64ms per)
Private Memory: 10.3MB (1.2MB per)

Hash
--------------
Normal: 916KB
Gzipped: 276KB
Hash Build Speed: 6638 (66.4 per)
Hash Find Speed: 19 (0.0002ms per)
Hash Not Find Speed: 34 (0.0003ms per)
Private Memory: 1014MB (10.05MB per)

Trie
--------------
Simple Trie: 1.0MB
Gzipped: 184KB

Optimized Trie: 761KB
Gzipped: 168KB

Suffix Optimized Trie: 506KB
Gzipped 155KB
Build Speed: 11178 (111.8 per)
Find Speed: 413 (0.004 per)
Not Find Speed: 552 (0.005 per)
Private Memory: 299.2MB (2.9MB per)

Update: Early this morning Mike Koss posted a follow-up on my previous blog post with a compressed Trie implementation. This is quite interesting and will certainly result in a smaller file size than what I've done. However, there's a problem: The result will end up taking a longer amount of time to load than the plain JavaScript structure that I employed. In my solution, since it's already written using JavaScript syntax, the performance will run as fast as the JavaScript engine can parse the code. However in Mike's solution the corresponding JavaScript structure will need to be re-built from the text itself. Theoretically if Mike comes up with a solution that used the compressed file size but leaves the data in its original string - that would be the best of all worlds. I'll be curious to see what he comes up with!

To start, in my game, the user is frequently re-arranging letters - causing the game to look up words in a dictionary to see if they are valid, or not.

I've taken multiple passes at implementing a solution to this problem, ranging all the way from "I don't care about performance, I just want it to work" all the way up to "thousands of people could be playing simultaneously, how do I scale?"

For my seed dictionary I used a variation of the Scrabble dictionary, which can be found via some creative Googling. The full dictionary ends up being around 916KB (with words separated by an endline).

Server-Side Solution

The first pass was stupid simple. It worked, but just barely. I took the dictionary and split it up into 26 files - one for each letter of the alphabet - and put all the words that started with the corresponding letter in the text file.

I then made a little PHP script to handle user requests - reading in the portion of the dictionary file and returning "pass" or "fail" if the word was found.

(Please don't use the above code, it's terrible.)

Thus you would call the PHP script like so:

/words.php?word=test

And it would return either "pass" or "fail" (meaning that it would only work on the same domain).

So while the above worked it wasn't nearly fast enough and it consumed a ton of memory on the server - each request was reading in large portions of potentially 100KB+ files. Time for a better solution.

A Better Server-Side Solution

My next attempt was to write a simple little web server (in Perl, this time) that pre-loaded the entire dictionary into memory, and handled all the requests via JSONP.

You would call the above using something like this:

http://example.com:8338/?word=test&callback=wordFound

There are a bunch of things that I don't like about the above code (like using a hash to lookup the words, when more memory-efficient solutions exist, and instantiating a CGI object on every request - things like that). Also if I were to do this today I'd probably write it in Node.js, which I'm becoming more familiar with.

Compared with the previous solution though there are a large number of advantages. Since the dictionary is being loaded into memory only once, and into a hash, it makes lookups very, very, fast. I was timing entire HTTP requests at only a handful of milliseconds, which is great. Additionally since this solution utilized JSONP it was possible to set up a server (or multiple servers) dedicated to looking up words and have the clients connect to them cross-domain.

A Client-Side Solution

It was at this point that I realized a couple problems with the previous server-side solutions. If my game was going to work offline (or as a distributable mobile application) then a constant connection to a dictionary server wasn't going to be possible. (And if slow mobile connections were taken into account then the responsiveness of the server just wasn't going to be sufficient enough.)

The dictionary was going to have to live on the client.

Thus I wrote a simple Ajax request to load the text dictionary and make a lookup object for later use.

Note that having the dictionary on the client actually allowed for an interesting new form of game play. Previously the player had to select a specific word and send it to the server - and only then would the server say if that word was valid or not. Since the dictionary now lives on the client (making lookups instantaneous, in comparison) we can change the logic a bit: The game now looks for the longest word at the start of the user's letters. For example, if the user had the letters "rategk" then the function would work like so:

Naturally, something similar could've been done on the server-side - but that wasn't readily apparent when working on the server. This is a case where a performance optimization actually created a new, emergent, form of gameplay.

But here's the rub: We're now sending a massive dictionary down to a client. It's 916KB - and that's absolutely massive.

Optimizing the Client-Side Solution

Compression and Caching

Turning on Gzip compression on the server reduces the dictionary file size from 916KB to a much-more-sane 276KB. Additionally configuring the cache-control settings of your server will ensure that the dictionary won't be requested again for a very long time (assuming that the cache in the browser isn't cleared).

There are some excellent articles already written on these techniques:

• Configuring your Cache Settings in Apache
• Configuring your Compression Settings in Apache
• Julien Lecomte also wrote a useful PHP script to do both simultaneously

Content Delivery Networks

Of course, all of this is a bit of a given when you use a Content Delivery Network - which I most certainly do. Right now I'm using Amazon Cloudfront, due to its relatively simple API, but I'm open to other solutions. This means that the dictionary file will be positioned on a large number of servers around the globe and served to the user in the fastest manner possible (using both gzip and proper cache headers).

Cross-Domain Requests

There's a problem, though: We can't load our dictionary from a CDN! Since the CDN is located on another server (or on another sub-domain, as is the case here) we're at the mercy of the browser's cross-origin policy prohibiting those types of requests. All is not lost though - with a simple tweak to the dictionary file we can load it across domains.

First, we replace all endlines in the dictionary file with a space. Second, we wrap the entire line with a JSONP statement. Thus the final result looks something like this:

dictLoaded('aah aahed aahing aahs aal... zyzzyvas zzz');

This allows us to do an Ajax request for the file and have it work as would expected it to - while still benefitting from all the caching and compression provided by the browser.

I alluded to another problem already: If the browser doesn't cache the file, for some reason, or if the cache runs out of space and the file is expunged - it'll be downloaded again. I want to try and reduce the number of times in which 216KB file will be downloaded - if not for the users then for reducing my bandwidth bill.

Local Storage

This is where we can use a great feature of HTML 5: Local Storage. Mark Pilgrim has a great tutorial written up on the subject that I recommend to all. In a crude nutshell: You now have an object that you can stuff strings into and they'll be persisted by the browser. Most browsers give you around 5MB to play with - which is more than enough for our dictionary file. It also has great cross-browser support - with the simple API working across all modern browsers.

With a little tweak to our Ajax logic (taking into account the JSONP request, the CDN, and Local Storage) we now end up with a revised solution:

This gives us an incredibly efficient solution, allowing us to load the dictionary from a CDN (gzipped and with proper cache headers) - and avoiding subsequent requests to get the file if we already have it cached.

Improving Memory Usage

One final tweak that we can make. If you remember the previous dictionary lookup we loaded the entire dictionary into an object and then checked to see if a specific property existed. While this works, and is fast, it also ends up consuming a lot of memory (more so than the existing 916KB, at least).

To avoid this we can be a little bit tricky. Instead of putting the words into an object we can just leave the entire dictionary string intact and then do searches using a JavaScript String's indexOf method.

Thus inside the dictReady callback we'll have something like the following:

and our revised findWord function will look something like this:

All together, as of this moment, this is the most optimal solution to this particular problem that I can think of. It's likely that I'll find some additional tweaks (or ways of improving memory usage) in the future - but at the very least this solution keeps HTTP requests to a minimum, bandwidth usage to a minimum, memory usage to a minimum, and lookups fast.

The Twitter team investigated and determined that if they reverted the version of jQuery that they used back to 1.4.2 from 1.4.4 the site would be responsive again. After more investigation they determined that the code that was slow was doing a contextual selector search for an item by class name, for example: $something.find(".class").

So - what happened? How did this come about? To start, nothing is inherently wrong with jQuery 1.4.4 - this particular performance regression came in jQuery 1.4.3. In 1.4.3 we switched from using the old Sizzle selector engine for contextual queries to using the browser's native querySelectorAll method, if it exists. This change was even explicitly mentioned and highlighted in the 1.4.3 release notes as it's a really good change. In general using querySelectorAll will result in much faster queries, especially for complicated queries and complicated documents (which there seem to be a lot of).

However, as with every performance change, while some things get way faster some things can also get slower. This was the case for some previously-optimized queries like .find(".class") (where we use getElementsByClassName, if it exists) and .find("div") (where we use getElementsByTagName). Both of those aforementioned methods always end up being faster than the queries run through querySelectorAll. Whether this will always end up being the case is another question entirely.

What's interesting here is that we've been using querySelectorAll for our default selector engine in jQuery for quite some time now (doing $('.class') would use querySelectorAll). The only change in 1.4.3 was just filling in a gap where .find('.class') wasn't using querySelectorAll. We've not heard of any particular performance regressions regarding the use of querySelectorAll and $('.class').

This brings up the important point: Just how much faster is getElementsByClassName compared to querySelectorAll? In our preliminary tests it looks like it's about 0.5-2x faster, depending upon the browser. While this is certainly nothing to scoff at the performance hit of this difference is quite negligible. For example the difference between searching by class name and querying in Firefox 3.6 is about 0.007s - certainly nothing that is capable of crippling a large application.

That being said, we don't like performance regressions so today we backported some shortcuts into Sizzle (from jQuery) to improve its performance for some common cases. For example: Sizzle("div"), Sizzle(".foo"), and Sizzle("#id") will all skip using querySelectorAll and try to use the native methods provided by the browser if they exist. (jQuery already did some of these (namely "div" and "#id", we just added the ".foo" shortcut as well).

So. If the performance hit wasn't very large then why was Twitter having so many problems? The reality is that this particular change was just the straw that broke the camel's back. Two things were happening that caused Twitter to have the issues that it was having. These can be distilled down into two general best practices:

Best Practices

It's a very, very, bad idea to attach handlers to the window scroll event. Depending upon the browser the scroll event can fire a lot and putting code in the scroll callback will slow down any attempts to scroll the page (not a good idea). Any performance degradation in the scroll handler(s) as a result will only compound the performance of scrolling overall. Instead it's much better to use some form of a timer to check every X milliseconds OR to attach a scroll event and only run your code after a delay (or even after a given number of executions - and then a delay).

Always cache the selector queries that you're re-using. It's not clear why Twitter decided to re-query the DOM every single time the scroll event fired, but this does not appear to be necessary (since scrolling itself didn't change the DOM). They could've saved the result of that single query to a variable and looked it up whenever they wanted to re-use. This would've resulted in absolutely no querying overhead (which is even better than having the faster getElementsByClassName code!).

Thus, combining these two techniques, the resulting code would look something like:

Hope this helps to clear things up and provides some good advice for future infinitely-scrolling-page developers!

(Note: There doesn't appear to be a way to take screenshots of the Chrome OS UI - making this post a bit less interesting.)

My Workflow

I've seem to have settled upon a workflow that can work for me - to some limited extent. Chrome OS (as I'm sure you're aware) is roughly just enough operating system to get a copy of Chrome running. I've played with Chrome extensively before now so there wasn't anything that was too surprising. I had to install the PasswordMaker extension as I use it to manage all my passwords (thankfully one exists for Chrome, otherwise this laptop would be completely unusable to me).

Typically I have two pinned tabs in my browser: Gmail and Google Calendar. The OS doesn't appear to allow right-clicking so in order to make them pinned I had to add the Gmail and Calendar apps, tweak their options to only open pinned, and then re-open them.

Virtually all of my development is JavaScript-centric (and against Git repos). Thankfully it's easy enough to test JavaScript in Chrome OS - but development is another matter entirely. Right now there doesn't appear to be any good code editors (or file system access, for that matter). This puts a major damper on my ability to work offline.

What I'm doing now is opening a separate terminal view (Ctrl+Alt+T) and SSH-ing to a server where I can develop. The terminal provided by Chrome OS is very very limited. The only truly useful command is 'ssh' and even then it's painfully limited. There is no way to provide an SSH key, for example (meaning that I actually had to set up an account on one of my servers with a password - which is quite lame). There does not appear to be any way to get a useful shell (sh, bash, tcsh - whatever). It seems as if there use to be some ways to boot into a different mode and get at the underlying Linux distro - but that all seems to be disabled on the Cr-48.

Right now I have my primary browser and my secondary terminal. In the terminal I have an SSH connection to my server where I run screen. Within that I split it into two vertical panes which gives me both a text editor and an IRC view (where I spend a vast majority of my day). Using this I can most likely get work done on a day-to-day basis.

The major problem: This really only works if you're connected to the Internet. I know that this should be rather obvious since this is 'Chrome OS' and it is something of a netbook - but the lack of any filesystem access means that I won't use this machine for anything more than a hobby (certainly can't use it while traveling).

I really like the Google Talk pop-overs that persist (making conversation rather easy). I didn't realize it at first but if you click the titlebar of a pop-over it will minimize, which is nice. However if I close a conversation it becomes an exercise in frustration to try and get it back.

Thankfully the Chrome in Chrome OS still has the developer tools installed, together with the JavaScript console.

I'm looking forward to when the Chrome OS store improves - right now it can be rather frustrating to do some simple things. For example I wanted to quickly crunch some numbers and went looking for a calculator. Surprisingly there wasn't one in the store. I ended up having to use the JavaScript console to do the calculations - which, I suspect, is not what Google expects most users to do.

The Hardware

Typically I use a Macbook Pro for my day-to-day development so I'm a bit spoiled when it comes to good hardware.

It appears as if the Cr-48 gets about 8 hours of battery life with the screen turned all the way down - or 6 hours with it all the way up. (Note: There is no brightness indicator when adjusting.) These numbers are about comparable to what I get on my Macbook (although I usually end up running more apps on the Macbook, including Textmate, a web server, and various other utilities).

The trackpad is absolutely infuriating. It's as if Google attempted to create a similar trackpad to the Macbook Pro but just got it all wrong. There is two-finger scrolling (good) but no acceleration. Tap-to-click is frustrating and I disabled it immediately. There is no three-finger swipe-to-go-back gesture (which I miss a lot). Performing text selection is absolutely insane. It seems like any combination of having two fingers on the mouse pad simultaneously throws the laptop into "scroll" mode. It's so bad that it makes me not want to write things on the laptop until it is fixed. As mentioned before there appears to be physical way of doing a right click - but I can't find a single place in the UI where right-clicking has an effect.

I completely miss the power adapter from the Macbook. I've tripped over my cable dozens of times and the lack of a magnetic connector frightens me. Not to mention that the connector isn't very good to begin with - it's already fallen out at least once.

I've been having a mixed experience with the wireless. The regular (802.11) wireless seems to be really... forgetful. I've had to enter my wireless password at least a half dozen times today - and since my password is more of a "pass phrase" it becomes quite tedious. It seems to hate waking up from sleep, the wireless fails to reconnect quite frequently, in that case. That being said the 3G process is quite smooth. The setup is relatively easy and you get 2 years worth of free wireless from Google (this is for 100MB per month of usage). I'm already pleased with it and I'm looking forward to using it while sitting in the Boston Commons this summer (that, combined with the matte screen, will make this an amazing laptop for outdoor usage).

The keyboard is easily the best part of the Cr-48 hardware. Replacing Capslock with a "New Tab" button is truly inspired. I've found myself already starting to rely upon it very heavily. The keyboard feels good to type on and the large Ctrl + Alt keys make for easy key combinations (important when using screen).

Conclusion

As it stands the situation where I could see myself using the Cr-48 the most is if I were to casually explore a city or do work outside. The included 3G wireless and simplicity of design make it ideal for that. I do not plan on using this laptop for any travel (and, thus, I likely won't be using it for any presentations) until I can get some form of shell-based filesystem access. I'd love to be able to have access to a shell and the ability to install vim + screen + git + a web server. If I had that (and, presumably, this would be an easy thing for Google to do - probably just a switch that would need to be toggled) this laptop would easily become a top contender for my primary laptop.

Right now my ideal laptop would be: Take a 13" Macbook Pro, replace the HD with an SSD, replace the DVD drive with more battery, add 3G. I would use that laptop until the end of time.

The conferences / meetups that I spoke at (or will speak at, in the case of MIX), and the talks that I gave, are as follows:

• Webstock (Wellington, NZ) (Introduction to jQuery Workshop, Things You Might Not Know About jQuery)
• Future of Web Apps (Miami, FL) (Introduction to jQuery Workshop, Improve Your Web App with jQuery)
• jQuery Boston Meetup (Boston, MA) (Things You Might Not Know About jQuery)
• MIX (Las Vegas, NV) (Improve Your Web App with jQuery)

Introduction to jQuery Workshop

This workshop starts with an introduction to the fundamentals of jQuery (1 hour) and continues on with two pieces of hands-on coding (Todo list, 30 min, Social Networking Site, 1.5 hours).

Source Code

In the workshop I also had two pieces of hands-on coding. The first was an ajax-y todo list the second was converting a functional social networking site into a one page application (making significant use of jQuery UI).

Source Code Reset Demo Edit Demo

Source Code Reset Demo Edit Demo

Things You Might Not Know About jQuery

A variety of things that people don't know about in jQuery - including new things added in jQuery 1.4 (and newer), data bindings, custom events, and special events.

Source Code

For the first jQuery Boston Meetup I built a game using the avatars of everyone in attendance. Sort of a space shooter style game you need to kick and kill the advancing hordes of users. I used this game as a way of demonstrating constructing an application that makes use of custom events, data binding, and building applications in an event-centric manner.

Source Code

Improve Your Web App with jQuery

A different restructuring of the previous talk that emphasizes a more holistic approach to improving your web applications with jQuery

Source Code

I've been messing around with a new piece of presentation software that I wrote for these talks. It's still terribly crude and buggy (pretty much just got it working enough in order to run my talks in Firefox 3.6 and Chrome) - you've been warned. I hope to refine it at some point and release it for general consumption.

closest() (and by extension, is()) has become a critical function in jQuery. With more people using live events reducing any overhead has become of the utmost importance. Every time an event fires that live is bound to (such as click or mousemove) jQuery uses the closest() method to go from the target element and find the nearest element that matches the specific selector. The more handlers that are bound, though, the more computationally expensive it becomes.

In jQuery 1.4 we've added closest(Array) which gives us the ability to batch these selector checks together and reduce the amount of time that we spend traversing the DOM.

Example

And the following handlers are bound:

Let's pretend that a 'mousemove' event occurs on #mouseme.

In jQuery 1.3.2:

1. #mouseme check on #mouseme (load Sizzle)
2. Return.
3. #main check on #mouseme (load Sizzle)
4. Walk up tree.
5. #main check on #test (load Sizzle)
6. Walk up tree.
7. #main check on #main (load Sizzle)
8. Return.
9. body check on #mouseme (load Sizzle)
10. Walk up tree.
11. body check on #test (load Sizzle)
12. Walk up tree.
13. body check on #main(load Sizzle)
14. Walk up tree.
15. body check on body (load Sizzle)
16. Return.
17. body check on #mouseme (load Sizzle)
18. Walk up tree.
19. body check on #test (load Sizzle)
20. Walk up tree.
21. body check on #main(load Sizzle)
22. Walk up tree.
23. body check on body (load Sizzle)
24. Return.
25. Sort all element results.
26. Loop through the results to trigger.

In jQuery 1.4:

1. #mouseme check on #mouseme (load Sizzle)
2. #main check on #mouseme (load Sizzle)
3. body check on #mouseme (load Sizzle)
4. Walk up tree.
5. #main check on #test (load Sizzle)
6. body check on #test (load Sizzle)
7. Walk up tree.
8. #main check on #main (load Sizzle)
9. body check on #main (load Sizzle)
10. Walk up tree.
11. body check on body (load Sizzle)
12. Return.
13. Loop through the results to trigger.

In summary: There is less walking up the tree, no running of duplicate selectors, and no sorting of element results.

We're still on track to push out a new alpha very soon and the final release on January 14th.

1. The node names of HTML elements are always uppercase, even if they're explicitly created using lowercase characters. <html> will result in a .nodeName === "HTML" (see the HTML 5 draft).
2. The node names of XML elements are always in the original case, as specified when they're created. <data> will result in a .nodeName === "data", <DATA> will result in a .nodeName === "DATA".

Knowing these rules can be useful because it allows you to optimize your code. If you know that you're in an HTML document you can avoid having to upper/lowercase your .nodeName checks and you can just always assume that you're dealing with a .nodeName that's uppercase. This results in faster selectors for Internet Explorer and other minor optimizations.

However recently I've been running across two cases that've been especially problematic and have bucked the trend.

Importing Nodes from XML

The first is for browsers that support the adoptNode/importNode DOM methods. These methods allow you to move (or clone) a node from one DOM document to another. In this way you can move an XML node from an XML document and insert it into an HTML document. Normally this shouldn't matter much but, as it turns out, the original .nodeName case sensitivity is preserved from the original XML-ness of the node.

Thus if you have a lowercase XML element (<data>) and you use adoptNode or importNode to bring it into your HTML document the result will be .nodeName === "data" -- which completely bucks the trend for "all HTML element's node names are always uppercase." I consider this to be a bug, considering that the DOM element is now in an HTML document, not in an XML document, and should behave as such.

Unknown HTML 5 Elements

The second bit of weirdness comes from people attempting to use the new elements from HTML 5 in browsers that don't support it. Most browsers behave perfectly well when using some of the new HTML 5 elements (in that they don't freak out and support some level of styling). For Internet Explorer you must use the HTML 5 Shim technique - this will give unknown HTML 5 elements the ability to be styled and hold contents (such as a <section> element).

However there is an additional gotcha: When Internet Explorer encounters an element that it doesn't recognize it leaves the .nodeName in its original case. Thus if you have a <section> element in your HTML page the result will be .nodeName === "section" -- which directly contradicts the normal case sensitivity of the .nodeName property in HTML documents.

To try and understand all of this I made a bunch of test cases using a number of doctypes and document styles.

• HTML 5 document - uses the HTML 5 Doctype.
• XHTML document served as text/html.
• HTML document served with no doctype.
• XHTML document served with correct mimetype.

The important part of the test page is quite simple:

and the test cases are as follows:

HTML

Accesses the HTML elements that were originally included the page (should be case insensitive).

HTML createElement

Creates new DOM elements using the same document as the page in which it was shipped (should be case insensitive).

innerHTML

Attempts to inject the elements using .innerHTML (should be case insensitive).

For the remaining tests I grab a simple XML document:

like so:

XML

Test the elements in the XML document directly (should be case sensitive).

XML createElement

Same as the HTML createElement but done using the XML document (should be case sensitive).

HTML via importNode

This clones the nodes from the XML document, using importNode, and places them into the HTML document (should be case sensitive).

HTML via adoptNode

This moves the nodes from the XML document, using adoptNode, and places them into the HTML document (should be case sensitive).

The Results

I ran the following tests in IE 6, IE 7, IE 8, Firefox 3.5, Safari 4.0.3, Chrome 3.0.195, and Opera 10.10. Additionally I tested against .tagName in addition to .nodeName and found no discernible difference (you can run your own .tagName tests by appending a ?tagName to any test URL like so.)

Conclusion

What can we learn from all of this? Unfortunately it appears as if we can't really trust our "trusted" rules about .nodeName case sensitivity for HTML documents. XML documents are completely safe and work as expected. XHTML (served with the correct mimetype) documents are nearly safe, save for the one bizarre Opera bug.

How will this change the code that we write? In short we can no longer trust the case insensitive nature of HTML documents - we need to assume that BOTH HTML and XML documents will be serving their content in a case sensitive nature - especially as more people start to adopt HTML 5 elements in their pages and expect some level of support in older browsers. This means that a number of selectors and DOM methods will take a performance hit as we can no longer take a case insensitive shortcut in our codebases.

There are a few outstanding jQuery tickets that are the result of these issues cropping up and now that I know the reasoning behind why they're happening I can now strip out all the case-insensitive performance improvements from the codebase - which is really quite unfortunate but at least it'll behave more consistently. I continue to stand by thesis from my earlier talk about the DOM: The DOM is a mess and every DOM method and property is broken in some way, in some browser.

I typically don't write about most performance analysis tools because, frankly, most of them are quite bland and don't provide very interesting information or analysis. dynaTrace provides some information that I've never seen before - in any tool on any browser.

dynaTrace Ajax works by sticking low-level instrumentation into Internet Explorer when it launches, capturing any activity that occurs - and I mean virtually any activity that you can imagine. I noticed very little slow down when running the browser in tracing mode (although it's sometimes hard to tell, considering the browser). However all of the tracing is recorded and saved for later, making it easy to record sessions for later analysis.

Above is the result of a recorded session, logging in to Gmail, reading a mail, and logging back out again. All aspects of the session are saved: Network requests, JavaScript source, all DOM events, etc. I had a hard time finding information that wasn't saved by the tool.

This is the full timeline view of loading a single the Gmail inbox. All network traffic, JavaScript parsing and execution, browser events, and CPU load can be seen.

You can select a segment of the timeline and get a view that looks like the following:

In the above you can see a clearer picture of the exact interactions happening. A phenomenal amount of inline JavaScript execution followed by page layout calculation coinciding with loading of some data over the network. You can mouse over the individual blocks on the timeline to get more information (such as if the JavaScript execute was the result of a timer or what Ajax requests were firing to cause the network traffic). Additionally you can click the blocks to dive in and take a deeper view of the trace.

Digging in to the execution of an XMLHttpRequest on a page we get to see some of the full execution stack trace - and this is where the tools starts to become really interesting. The tool is capable of tracing across JavaScript, through the native XMLHttpRequest, through the network request, and back to the handler that fires when the request is done. This is phenomenal. This is the first tool that I've seen that's capable of tracing through native methods to give you a picture of what activity triggers which actions and the complete ramifications of what happens (in both CPU usage and execution time).

Note that in the stack trace view you can click any piece of code and see its location anywhere inside the source code (and this even works after you've already closed the browser and have moved on - all source code is saved for later analysis).

While it's interesting to trace through code to look for problems the bigger question is usually: Where are slowdowns occurring? This is where the HotPath view comes into play:

This looks like a typical execution count view - like the one that you might see in Internet Explorer's built in tool or in Firebug - except for one important point: This view includes JavaScript parsing and layout rendering times. This is huge! No other tool provides information on how long it takes to parse all the JavaScript code on your site or how long it takes to do all the rendering. Clicking those entries allows you to see a breakdown of every time JavaScript was parsed or a layout was rendered - from which you can trace back to get even more information about what caused those actions. I don't want to seem too excited but I really am, this is just an incredible amount of information - and it gets even better:

Not only can you see the execution count for your defined JavaScript methods but you can also see execution time for the built-in DOM methods! Wondering what native method calls are slowing down your application? Wonder no more. From the HotSpot view you can filter by DOM or regular JavaScript and see exactly where execution time is going and what methods are so slow.

dynaTrace provides an additional view, called PurePath that attempts to figure out problematic scripts:

Just another way to try and get a full picture as to where your application is slowing down and what may be causing the problem.

In all I'm hugely impressed with this (free!) tool and am already using it to do more testing and performance analysis on my code. I don't think any browser has ever had a tool capable of this type of analysis, let alone Internet Explorer 6 and 7, which are still a very real part of any developer's workflow.

I chatted with some of the dynaTrace guys and asked them to add in memory profiling and to support more browsers. If they can provide this quality of instrumentation for CPU and execution time I hope they can do the same for memory usage, the next un-tapped realm of JavaScript performance analysis.