Algorithm Blogs

Last Monday I gave a presentation in pywebil on optimization, that’s loosely based on my blog post on the same subject. Here are the slides for that presentation.

Some time ago I was working on optimizing the client side code of my website, plnnr.com, an online trip planner.
This website does automatic trip planning, and the problem was that recalculating trips was slow. After profiling, I found out that most of the time wasn't actually taken up by the algorithm, but by the UI. Rendering the trip to html was the costly part. The process was like so:

Client-side Javascript code generates new trip prefs -> application calculates new trip -> Client-side Javascript gets the new trip, and creates new html.

It's important to note that the app is "ajax based", so the actual trip html was generated by the Javascript code, and not the server. At the time I was using Mochikit to generate the new html. Mochikit has a pretty nifty API for generating html, but it's quite a bit on the slow side. Basically, this API is a wrapper around createElement.

Well, first I did a little test, and found out that generating html with cloneNode and innerHTML is much faster than createElement. Still, there was a problem - I needed to generate many similar elements - similar but not identical. Consider entries on a trip itinerary - they all look the same, yet each one has a different name, a different time string, and a different onclick event.

What I needed was a Javascript based html template library. My requirements:
1. Speed. Html had to be generated quickly.
2. Expressiveness. It had to be able to create pretty arbitrary html with a given context. For example, an anchor element (<a> tag) with a given href property, and a given text content.
3. References to inner elements: Many elements inside the generated html need various events attached to them, or various code processing. This should be easy to achieve.
4. The library has to allow the template html to be written as html, and not only as javascript strings.

So, I sat down with Benny, and we wrote the Javascript Element Creator, which we are now releasing under the BSD license. I originally wrote it to work with Mochikit and the Sizzle library, and Benny changed his version to worked with jquery.

After adding the code to my project, I got two things: first, everything worked much, much faster. Second, it was much easier changing the generated html when it was generated according to a template, and not directly in code.

Instructions

1. Write your html somewhere visible to the javascript code. Add the "template" class to the upper node, and the id will be the name of the template. For example:

2. Similarly to other template engines, add double brackets to signify where text should be inserted:

3. Create a creator object. It will "collect" your template, and will make it available to your code.

4. Generate your DOM object, and add it to the document;

The code

We decided to publish for now only the jquery version. I might publish the mochikit version as well at a later date. Since Benny wrote the jquery version, he also wrote the tests for that version.

All in all, the final code is pretty short, and could probably be even shorter. Still, it's good enough, and gave me a very real performance boost.

Here is the code, have fun with it.

Following my previous post on Optimizing Javascript, I thought I'd write a similar post regarding Python optimization.
(more...)

Profiling, Profiling, Profiling

This seems obvious, but still merits a mention. Don't optimize your code before profiling it. If you need a profiler, just use firebug's. Having tests to make sure that your post-profiling code is equivalent to the original is also nice.

Later is better than now

As is well known, it is usually useful to have some of the page content to be fetched in the original http get, but have non-essential content fetched using ajax after page-load.

In some cases, user interaction with your website does not require fetching new content, but doing some processing. Generating html is especially slow. In that case, the user will have to wait until the processing is done. Unless of course, you can also 'postpone it for later': simply use setTimeout to do the work outside of the even handler.
For example, I used Bill Chadwick's ArrowLine, which redraws on zoom-in/out. Since the redraw isn't quick, this makes zooming in pretty slow, especially when quickly zooming more than once.
My solution: since what takes time is drawing the arrows themselves, I put arrow drawing code in a timeout callback, which means the interface doesn't get unresponsive.

(Of course, this might misbehave, and I had to make sure my code still works if multiple timeouts are enqueued, etc..)

A single div is all you need!

I had to write a dropdown widget for UI, one which could show arbitrary html inside the dropdown box. Problem is, I had to to have a lot of similar dropdowns. This in itself is pretty easy, as we all know how to use a for-loop.
It gets complicated when you find out that adding these dropdowns takes a lot of time. What's worse, the part that takes time is adding the div that gets displayed when you show it, but is otherwise hidden.

To solve this, first you may apply "Later is better than now", and create each dropdown only when it's needed. This will work. In some cases, a different approach is warranted: all of these dropdowns share the same design of the 'dropdown div', and only one of these divs will be shown at any time (I had to write code to make sure of it). So, instead of making a new drop-down div for each dropdown, create just one, and let them share it. This might complicate your code, but the rewards may be great.

To make it work, you may use an object factory, or a function that creates widget classes, or any other pattern that works for you.