Epic Weekly News

A lot of cool stuff happened this past week:

• Mono 2.2 was released with the new SIMD and LinearIR optimizations
• Moonlight 1.0 was released
• Obama sworn in as the US President, streamed live via Moonlight
• ...and Linus Torvalds switches to GNOME

Watched Obama via Moonlight

Found out about Larry's, Aaron's, Rusty's, and Geoff's work at making a Moonlight 1.0 release that could view the Obama Inauguration this morning, so I absolutely had to use Moonlight today to watch it and it was great. Flawless.

Way to go guys!

Once again proving that the Mono team is unstoppable!

GO MONO! GO!

Moonlight TextBox

This past week I've been furiously hacking away on my reimplementation of the Silverlight TextBox control for Moonlight. I never realized just how much work goes into writing such a simple text-entry widget before this past week, even after having written Moonlight's text layout and rendering engine for the 1.0 release.

Keyboard input, keyboard navigation, keyboard selection, mouse selection & cursor positioning, key repeat, cursor blink, etc. The list goes on.

Most of it isn't hard, it's just time consuming.

At the same time, it's also fun in the sense that it's a new challenge for me to overcome (I love a good challenge). It makes you think a lot about designing for performance because you just don't know how much text you'll be rendering. It could be a short sentence or it could be an entire document, and the way you design your layout/rendering engine could mean the difference between taking 5 minutes to render or a fraction of a second.

GNU/Emacs font-lock suckage

For months now, my GNU/Emacs has decided to sometimes not syntax highlight my source or ChangeLog files and I didn't know why.

The other day, emacs' failure to syntax highlight xaml.cpp was the final straw. I decided enough was enough with having to M-x font-lock-fontify-buffer everytime I opened a handful of source files, especially ones that I often find need to edit and/or to refer to.

A little digging later and I discovered that GNU/Emacs must have added a feature that disabled font-lock (even if you've specified (setq font-lock-support-mode t) in your ~/.emacs) if the buffer was over some arbitrary size. Either that, or they lowered the arbitrary size to something ridiculously small.

The solution seems to be to add the following line to your ~/.emacs file: (setq font-lock-maximum-size 1000000)

Feel free to append a few more 0's to that number if you find that Emacs still fails to syntax highlight any of your source files.

Update: Another Emacs annoyance can be turned off by adding (setq inhibit-startup-message t) to your ~/.emacs file. I'm not sure why this isn't inhibited by default.

Quick Review of Microsoft's Seadragon

Just got around to installing Seadragon on my iPhone and took it for a quick spin. First impressions are that it rocks. If I load the map views, for example, zooming seems far far smoother than Google Maps. Zooming in on the articles in the Library of Congress Set was amazingly smooth as well.

Herding Code: Episode 29 w/ Miguel de Icaza (Part 2)

Part 2 of the Herding Code podcast w/ Miguel de Icaza is up: http://herdingcode.com/?p=114

I'll be listening to this tonight when I get home.

Fun with Tries

A number of years ago, Michael Zucchi introduced me to the Aho-Corasick algorithm which he implemented in Evolution for the "Find in Message" feature. Later, I ended up extracting that logic out and refactoring it a bit into the ETrie class which I ended up using to replace the regex logic (which is common among most GNOME apps that do this) to scan for urls in the message body (in order to insert hyperlinks, etc). This turned out to be an order of magnitude faster.

For those who aren't in the know, the Aho-Corasick algorithm is for searching for multiple strings in a given input. In other words, it searches for one of multiple needles in a single haystack.

The pseudocode for the search itself would look something like this:

q = root
FOR i = 1 TO n
  WHILE q != fail AND g(q, text[i]) == fail
    q = h(q)
  ENDWHILE
  IF q == fail
    q = root
  ELSE
    q = g(q, text[i])
  ENDIF
  IF isElement(q, final)
    RETURN TRUE
  ENDIF
ENDFOR
RETURN FALSE

Of course, ETrie has a slight modification to the above algorithm, which is that instead of returning TRUE or FALSE, it returns a pointer to the beginning of the match or NULL if it find no matches.

The problem with this particular implementation, though, is that it would simply return a pointer to the offset into the string of the first match found. But what if you had multiple pattern strings that started with identical characters?

Like the ETrie implementation, the traditional Aho-Corasick algorithm (if I am remembering correctly) stops searching as soon as it finds any match. The difference, of course, is that given access to the current to the state / tree structure, a programmer could choose to continue matching to see if there is a more greedy match. With ETrie, however, in the interest of simplicity, it just returned the first / shortest match it got to.

In case I'm explaining this badly, say our search patterns are "the", "there", and "therefor". In the case of ETrie, it would always return that it matched "the" even when the "the" that it matched was the starting substring of the larger string, "therefor".

In something I was working on more recently (in c++), I wanted a greedier match (e.g. I wanted it to match "therefor" instead of "the").

In order to achieve this, I modified the implementation a slight bit:

const char *
Trie::Search (const char *buf, size_t buflen, int *matched_id)
{
    const char *inptr, *inend, *prev, *pat;
    size_t matched = 0;
    TrieMatch *m = 0;
    TrieState *q;
    char c;
    
    inend = buf + buflen;
    inptr = buf;
    
    q = &root;
    pat = prev = inptr;
    while (inptr < inend) {
        c = *inptr++;
        
        if (icase && (c >= 'A' && c <= 'Z'))
            c += 0x20;
        
        while (q != 0 && (m = g (q, c)) == 0 && matched == 0)
            q = q->fail;
        
        if (q == &root) {
            if (matched)
                return pat;
            
            pat = prev;
        }
        
        if (q == 0) {
            if (matched)
                return pat;
            
            q = &root;
            pat = inptr;
        } else if (m != 0) {
            q = m->state;
            
            if (q->final > matched) {
                if (matched_id)
                    *matched_id = q->id;
                
                matched = q->final;
            }
        }
        
        prev = inptr;
    }
    
    return matched ? pat : 0;
}

I have published the full source code for trie.cpp and trie.h on my website for your perusal.