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.

Herding Code: Episode 28 w/ Miguel de Icaza

Been waiting to listen to this for a few days now. Figured others might also be interested: Herding Code: Episode 28.

Discussion of the history of Mono and some of the new features that have been added recently.

Moonlight 1.0 beta 1

As most of you have probably heard by now, the first Beta release of Moonlight 1.0 has been announced, you can install it from http://www.go-mono.com/moonlight/.

Miguel's got a great post explaining how the multimedia stack works in Moonlight in case that sort of thing interests you.

Re: Black and White

I've just finished reading Linus' blog post entitled Black and White and I have to agree.

It's not productive to be anti-something, it is much healthier and more productive to be for something.

I think Linus' article ties back into the How To Survive Poisonous People presentation I linked to and commented on back in June.

Very often times, the poisonous people in a community are those who try to make everything black and white and typically take the anti approach to things.

We all do it from time to time (myself included, *cough*), but the truly poisonous people are the ones that can't ever let things go.

Mono @ PDC 2008

For those who weren't able to attend Microsoft's Professional Developer's Conference this past week, Miguel gave a presentation (wmv) about Mono detailing some exciting new developments.

For example, Mono 2.2 (slated for the first week of December) will have a C# shell which Miguel and Marek have been working on and which Microsoft has announced will be part of C# version 5, slated for release sometime in 2012 (yes, that means Mono is ahead of Microsoft!).

Also presented was Mono in video games, such as those on the Wii and iPhone platforms (which are both supported targets of the Unity3D game development studio). Some game studios are apparently also using Mono on the PlayStation3, Xbox360, Windows, and Mac platforms. The main interest here was that Unity3D has been rewritten from Objective-C (on the Mac platform) to C# which should make it eventually portable to Linux (C# version now runs on Windows and Mac).

Another interesting development that came about because of interest in using Mono for video games (since some game development studios are now writing games in fully managed code), was that it was important for Mono to get SIMD support which has now been implemented and will be available in Mono 2.2. This has made Mono extremely fast (up to 10x faster) with respect to 3D vector math and other areas that benefit from SIMD.

This is really exciting!

Optimizing Moonlight's InkPresenter

This past week I started out staring at endless amounts of javascript trying to figure out what it was supposed to do so that I could figure out what Moonlight was breaking on in order to fix some bugs. As you can imagine, this is a slow and boring process where one's eyes go dry and it feels like you are getting nowhere fast.

As occasionally happens, I give up and move onto the next bug hoping that the next bug will be easier to fix and/or give me some insight into the previous bug. As it turned out, I moved onto bug #409793 which was a performance bug on sites like Ink Journal and Ink Tattoo Studio.

What was happening on these sites was that as more points got added to the stroke, rendering would get slower and slower (thus causing the line to lag behind the mouse cursor) because Moonlight was invalidating the entire InkPresenter canvas on each frame and so having to render the entire thing even though it was unnecessary.

To optimize this, I added a 'dirty' rectangle that kept track of the actual regions we needed to redraw. As points got added to the collection between frames, I added the bounds of the new point plus the region between the new point and the previous/next points (the 'next' point is obviously only needed if the newly added point was an insertion). The result for sites like InkJournal and InkTattooStudio was that we only invalidated the newly appended points at each frame render, vastly improving our performance which now matches Microsoft's Silverlight performance for these sites afaict.