It's All Geek to Me

Turning website favicons in to 3D

The feedback I recieved from Reddit about locidesktop.com (my hobby project) was encouraging.

One of the comments pointed out that although there is a large choice of icons available, there isn't always a clear recognizable image for each site, and it would be nice if locidesktop would use ‘favicons’. I had considered using favicons previously, but rejected the idea because they are just 16x16 pixels in size, and I wanted to use large images for icons.

I didn't want blurry scaled icons either, and I may have abandoned the idea if a Reddit user hadn't pointed me at this which recommended embracing the pixelated look of favicons for use at desktop icons. I figured I could take this idea a step further and render 3D images from any given 16x16 image, using a combination of Python, Mako templates and Povray – the same combination of technologies I used for my (now defunct) 3D pie chart project.

Evolution of an Auto-Complete

My latests hobby-project has been pushed live, in invite-only beta form. Previously known as Links Desktop, I have now dubbed it Loci Desktop, after the Loci Method.

Auto-complete in Loci Desktop

One feature of Loci Desktop is that it will auto-complete URLs when you add new icons to your ‘desktop’. Auto-complete is one of those features that users expect these days. They want the app to figure out what they want with as few key-presses as possible – and quite rightly so, typing is such a chore!

The auto-complete system for Loci Desktop, in its initial state, was straight-forward to implement. The javascript and front-end was the most time-consuming part of the job, but the back-end Python code was trivial.

Amoeba

Alas, it was too slow to be practical. The list of URLs that I was auto-completing from came from a list of the top one million sites from Alexa.com, stored in MySQL and queried with the Django ORM. The query searched the urls for a substring, and sorted by the Alexa rank so the most popular sites were listed first.

Although it worked perfectly, the auto-complete code at the back-end hammered the server and took to long to return its result. Reducing the number of URLS to 100,000 helped, but didn't make it as usable as auto-complete in a desktop app.

Opposable Thumbs

I'm no expert on what goes on under the hood in a database, but the conclusion I came to was that there was no way that the DB could produce an index for substring searches on-the-fly, and had to resort to comparing the substring with every entry in the database. With a million entries, that could never be fast.

Caching helped, but only for URLs that were previously searched for. But it occurred to me that if the results for all possible searches were cached then auto-complete would be blisteringly fast. I almost dismissed that idea as crazy talk, but mulled it over anyway.

It turned out to be practical. There are a lot of substrings for any given URL. For example, “facebook” contains 8 one-character substrings, 7 two-character substrings ('fa', ‘ac’, ‘ce’, ‘eb’, ‘bo’, ‘oo’, ‘ok’), and so on. So there are going to be a log of substrings for each url – but there will be a lot of substrings common to many urls, and I only need to store 10 ‘hits’ for each substring.

Generating this substring index took quite a bit of brute force processing, but once uploaded to the server it means that I could use a single, extremely efficient query to generate the auto-completed urls. The query time went down from more than a second, to 0.002 seconds! A very satisfying result, which meant that the auto-complete would update almost as fast as I could type, at about 150 milliseconds per request.

Making Tools

Another optimization was to offload a bit of work to the client by caching in Javascript. It was trivial to implement, but not a particularity big win as it only speeded up auto-completed URLs that had been searched for previously (such as when you delete characters).

Geek here, make fire!

Although these optimizations made the auto-complete nice and fast, the small delay in receiving the first list of URLs meant that it wasn't obvious there was auto-complete if you hadn't used it. It would be preferable if the auto-complete selection appeared after the first key-press. So I generated a mapping of every letter and digit on to the corresponding list of urls and used that to auto-complete the first character, rather than make a round-trip to the server.

Making the first character auto-complete virtually instantaneous really made it feel snappier from the start. So a big win, for minimal effort.

Conclusion

Databases are highly tuned pieces of software, but you can get big wins if you massage your data in to a more efficient format!

Links Desktop Teaser Screencast

In past blogs I've hinted on the fact that I'm working on a Javascript application in my spare time. It's not quite done yet, and wont be live for a few more weeks, but I do have something that I can show off.

This project is best explained in the form of a screencast. This is the first screencast I have ever made and I'm not sure if I have done it right, or if my humble server will cope with serving FLV files. If the server doesn't manage to keep up, I'll probably Youtube it.

ETag magic with Django

An ETag is a feature of HTTP that allows for a web server to know if content has changed since the last time the browser visited the page. The client sends the ETag from the cached page in a header. If the ETag in the header matches the current ETag then the server lets the browser know that the cached is up-to-date by sending back a 304 Not Modified response.

Making tileable images with Python

Here's an interesting bit of Python code I hacked together – it's a script that takes an image and warps it so that it is tileable (making it suitable for a repeating backgound or a texture in a game).

A Mandlebrot fractal

If you use it on a photograph, it will come out looking like a fair-ground mirror. But it works well when applied to a pattern, or something more abstract, such as the fractal image on the left.

The code is public domain – use it for whatever the heck you want!

Python Job Alert

My employer is looking for a new Python developer to work here in Oxford, UK. The company I work for runs 2degreesnetwork.com, which is collaboration service for sustainable business. Basically, it's a social networking type of site for businesses to collaborate on climate change and related issues. I'm not officially allowed to say this, but the closest analogy is ‘Facebook for Businesses’.

I take it back, this is the most inneficient code ever

Here's the most convoluted “Hello World!” script I could come up with (in response to this). I don't know if it works. I've proven it correct, but I haven't tested it.

from random import choice
from itertools import count
from zlib import crc32
import sys
any(crc32(h)==472456355 and not sys.stdout.write(h) for h in(''.join(choice('! edHlorW')for _ in '.'*12)for _ in count()))

I promise my production code is (marginally) more readable this this…

A 3D Texture-Mapped Globe Rendered with Javascript and HTML

I've been working on a large-ish Javascript project lately (still in stealth mode). One that could be described as a Javascript application. And since I've been up to my elbows in Javascript, I have found my contempt for the language waning. Not entirely, of course – I'm still a Python fan-boy. But enough for me to knock out a 3D(ish) spinning texture-mapped globe, using nothing but Javascript and HTML, as a way of honing my JS skills.

Without further ado, I present you with a 3D Javascript Globe.

Fuzzy Thinking

I have an idea germinating that involves using fuzzy logic, something I only had a passing knowledge of. After reading the Wikipedia articles and Googling for it I'm more informed but still haven't found a perfect resource.

The only Python code I have found was informative, but it was from way back in 1990. If there are any Pythonistas who know of a more up-to-date fuzzy logic module, or fuzzy logic resource in general, please let me know!

Misleading ImportErrors in Django

I was debugging an issue with our Django app at work today; an admin.py file wasn't being picked up, and nothing was appearing in the admin pages. It turned that an ImportError was being thrown in the admin.py and Django was interpreting this as the file not existing.

I'm assuming that the reason for this is that Django uses __import__ to import the module, and catches ImportError's if the admin.py doesn't exist. The trouble with this is that if admin.py does exist, and throws an ImportError of its own, Django will also interpret that as a missing admin.py – which can be misleading.

The only solution I can think of to more accurately handle this would be to programmaticaly examine the traceback to determine where the ImportError is thrown. If the traceback is one level deep, we know that the ImportError was thrown because the module doesn't exists. If it is greater than one level then we know the module was found, but has thrown an ImportError of its own.

Here's a simple proof of concept:

#check_import.py
import traceback
import sys

def check_import(name):
    try:
        __import__(name)
    except ImportError:
        exceptionType, exceptionValue, exceptionTraceback = sys.exc_info()
        return len(traceback.extract_tb(exceptionTraceback)) > 1
    return True

print check_import("os")
print check_import("noimport")
print check_import("anotherlevel")

#anotherlevel.py
import thismoduledoesnotexist

This produces the following when run:

True
False
True

It would be nice if Django did something similar for its implicit imports. I think the best behaviour would be re-raise the ImportError if it the module does actually exist. That way, it is clear what the problem is. I may attempt to write a patch at some point, unless someone knows of a better solution.