Tuesday, March 3, 2009

Jaro-Winkler implementation in Ruby for User-Agent matching

Working in the mobile web, it's hard to keep up with the constant glut of devices on the market and their rapidly evolving capabilities. Of course, progressive enhancement is key; the markup you use in a mobile site should be minimal and look good without any CSS, JavaScript, or images, which is the worst-case. But we don't want to stop there; we want our sites to look as good as they can on as many mobile devices as possible.

WURFL is here to help with that. A crowd-sourced database of mobile devices, updated regularly, WURFL gives you detailed information on the capabilities of over 10,000 mobile devices indexed by user-agent string and grouped by manufacturer. It's relatively straightforward to set up a cronjob for a rake task that downloads an updated WURFL file and stores it in a table in your database; using an ActiveRecord model, you can then query the data provided by WURFL to get all the details for any device which has a user-agent string in the database.

But device makers throw a wrench in these efforts: user-agent strings are frequently updated or modified from their canonical form without rhyme or reason.

Fortunately, we have the Jaro-Winkler distance algorithm, which gives us a quick-and-dirty matching algorithm for strings that are mostly the same but may vary in arbitrary ways. Using this algorithm, we can run indexed queries for exact matches, then pull in some subset (perhaps matching the first 20 characters of the mystery UA string), iterate over these devices, and find the best match to return. Failing to find any implementation of the Jaro-Winkler algorithm in Ruby, I had to cobble together my own; I hope you find it useful.

module JaroWinkler

    def self.distance(str1, str2)
      str1.strip!
      str2.strip!

      if str1 == str2
        return 1
      end

      # str2 should be the longer string
      if str1.length > str2.length
        tmp = str2
        str2 = str1
        str1 = tmp
      end

      lmax = str2.length

      # arrays to keep track of positions of matches
      found1 = Array.new(str1.length, false)
      found2 = Array.new(str2.length, false)

      midpoint = ((str1.length / 2) - 1).to_i

      common = 0

      for i in 0..str1.length
        first = 0
        last = 0
        if midpoint >= i
            first = 1
            last = i + midpoint
        else
            first = i - midpoint
            last = i + midpoint
        end

        last = lmax if last > lmax

        for j in first..last
          if str2[j] == str1[i] and found2[j] == false
            common += 1
            found1[i] = true
            found2[j] = true
            break
          end
        end
      end

      last_match = 1
      tr = 0
      for i in 0..found1.length
        if found1[i]
          for j in (last_match..found2.length)
            if found2[j]
              last_match = j + 1
              tr += 0.5 if str1[i] != str2[j]
            end
          end
        end
      end

      onethird = 1.0/3
      if common > 0
        return [(onethird * common / str1.length) +
                (onethird * common / str2.length) +
                (onethird * (common - tr) / common), 1].min
      else
        return 0
      end
    end

end

This will return a value such that 0 <= value <= 1. Matches near the beginning of the strings are weighted more heavily than matches near the end, making this a good algorithm to use with user-agent strings which are typically long and have minor variations toward the end.

That said, this isn't necessarily the optimal method to detect user-agent strings, and since it can easily give false positives in cases where a desktop and a mobile version of the same browser exist, it should be used in conjunction with a whitelist of known desktop browsers (which, though substantial, is much shorter than the list of all mobile browsers). So I offer this code with the disclaimer that Jaro-Winkler may not be the most effective algorithm for user-agent string matching.

By the way, I'm just learning Ruby, so if I'm doing anything atrocious here please let me know.

Wednesday, February 25, 2009

Asynchronous Image Caching with the iPhone SDK

Coming from the web world, I'm used to not having to think about all the functionality implicit in the humble HTML <img> tag, including client-side resource caching and asynchronous loading. In fact, the browser will cache any resource sent with the appropriate HTTP response headers, but by far the most common use of this cache behavior on most websites is images of all kinds.

So in building a couple of simple iPhone apps recently that display a list of search results retrieved from a server call, one piece that was missing was an asynchronous image loader that retrieves and displays thumbnail images in UITableViewCells.

[UIImage imageWithData:[NSData dataWithContentsOfURL:url]] gives you default iPhone HTTP caching behavior using NSURLCache, but it turns out that's not good enough: NSURLCache only stores URL contents in memory for the duration of the use of the application. We also need a URL cache that writes results to disk so that frequently-accessed responses only, and it also needs to manage its capacity. After that, we need an image loader that will abstract away the work of downloading images asynchronously, so that when a cell needs an image, it can request the image from the CachedImageLoader, and the CachedImageLoader will call back with the image, whether loaded from cache or remotely. Let's start with the data cache, DiskCache, which simply caches NSData objects in files in the application's file path:

extern const NSUInteger kMaxDiskCacheSize;

@interface DiskCache : NSObject {
@private
        NSString *_cacheDir;
        NSUInteger _cacheSize;
        NSUInteger _diskCapacity;
}

@property (nonatomic) NSUInteger diskCapacity;
@property (nonatomic, readonly) NSString *cacheDir;
@property (nonatomic, readonly) NSUInteger size;

+ (DiskCache *)sharedCache;

- (NSData *)dataInCacheForURLString:(NSString *)urlString;
- (void)cacheData:(NSData *)data
                  request:(NSURLRequest *)request
                 response:(NSURLResponse *)response;
- (void)clearCachedDataForRequest:(NSURLRequest *)request;


@end

The implementation for this one will be pretty straightforward: it's a singleton class that obscures as much activity as possible, including the cache path and file naming scheme (the implementation actually just uses the original URL filename, though this is potentially brittle when resources with the same name are located in different paths). One detail that I find interesting is determining folder size, which is less straightforward than I expected under Cocoa. To determine the size of all files in a given directory, you have to walk the directory and add up their sizes:

- (NSUInteger)size {
    NSString *cacheDir = [self cacheDir];
    if (_cacheSize <= 0 && cacheDir != nil) {
        NSArray *dirContents = [[NSFileManager defaultManager]
                                directoryContentsAtPath:cacheDir];
        NSString *file;
        NSDictionary *attrs;
        NSNumber *fileSize;
        NSUInteger totalSize = 0;

        for (file in dirContents) {
            if ([[file pathExtension] isEqualToString:@"jpg"]) {
                attrs = [[NSFileManager defaultManager]
                         fileAttributesAtPath:[cacheDir
                             stringByAppendingPathComponent:file]
                         traverseLink:NO];

                fileSize = [attrs objectForKey:NSFileSize];
                totalSize += [fileSize integerValue];
            }
        }

        _cacheSize = totalSize;
        DLog(@"cache size is: %d", _cacheSize);
    }
    return _cacheSize;
}

Here, I'm only interested in files with the "jpg" extension, though this is the only hard-coded reference to images in the entire implementation and could easily be changed. Note the Objective-C syntax

for (NSString *file in dirContents)

which is known as fast enumeration and gets compiled down into pointer arithmetic, much faster than indexing using NSArray's objectForKey: method. Perhaps there's a more concise way to perform this task, but I haven't run across it yet.

While we're here, it's also worth taking a look at the mechanism for trimming the old files out of the disk cache when it reaches capacity. This involves first filtering the directory contents, then sorting the filtered contents by date modified; welcome to the wonderful world of NSArray sort functions:

NSInteger dateModifiedSort(id file1, id file2, void *reverse) {
    NSDictionary *attrs1 = [[NSFileManager defaultManager]
                            attributesOfItemAtPath:file1
                            error:nil];
    NSDictionary *attrs2 = [[NSFileManager defaultManager]
                            attributesOfItemAtPath:file2
                            error:nil];

    if ((NSInteger *)reverse == 0) {
        return [[attrs2 objectForKey:NSFileModificationDate]
                compare:[attrs1 objectForKey:NSFileModificationDate]];
    }

    return [[attrs1 objectForKey:NSFileModificationDate]
            compare:[attrs2 objectForKey:NSFileModificationDate]];
}


- (void)trimDiskCacheFilesToMaxSize:(NSUInteger)targetBytes {
    targetBytes = MIN([self diskCapacity], MAX(0, targetBytes));
    if ([self size] > targetBytes) {
        NSArray *dirContents = [[NSFileManager defaultManager]
                                directoryContentsAtPath:[self cacheDir]];

        NSMutableArray *filteredArray = [NSMutableArray 
                                arrayWithCapacity:[dirContents count]];
        for (NSString *file in dirContents) {
            if ([[file pathExtension] isEqualToString:@"jpg"]) {
                [filteredArray addObject:[[self cacheDir]
                                stringByAppendingPathComponent:file]];
            }
        }

        NSInteger reverse = 1;
        NSMutableArray *sortedDirContents = [NSMutableArray arrayWithArray:
                                     [filteredArray
                                sortedArrayUsingFunction:dateModifiedSort
                                                                             context:&reverse]];
        while (_cacheSize > targetBytes && [sortedDirContents count] > 0) {
            id file = [sortedDirContents lastObject];
            NSDictionary *attrs = [[NSFileManager defaultManager]
                                   attributesOfItemAtPath:file
                                   error:nil];
            _cacheSize -= [[attrs objectForKey:NSFileSize] integerValue];
            [[NSFileManager defaultManager] removeItemAtPath:file
                                                       error:nil];
            [sortedDirContents removeLastObject];
        }
    }
}

Next, we take a look at the CachedImageLoader, which uses a protocol ImageConsumer to for its clients; this keeps us from being locked into any particular image renderer (such as UITableViewCells or what have you); in fact, it's used in a few different places in the GoTime apps:

@protocol ImageConsumer <NSObject>
- (NSURLRequest *)request;
- (void)renderImage:(UIImage *)image;
@end


@interface CachedImageLoader : NSObject {
@private
        NSOperationQueue *_imageDownloadQueue;
}


+ (CachedImageLoader *)sharedImageLoader;


- (void)addClientToDownloadQueue:(id<ImageConsumer>)client;
- (UIImage *)cachedImageForClient:(id<ImageConsumer>)client;

- (void)suspendImageDownloads;
- (void)resumeImageDownloads;
- (void)cancelImageDownloads;


@end

Again, this is a singleton class, which is basically a wrapper for NSOperationQueue, which is a really handy high-level threading implementation. (There are reports that NSOperationQueue is broken on OS X Leopard, but the single-core chip architecture on the iPhone avoids the cause of this bug, so it can be safely used; indeed, I haven't had any problems with it.) NSOperationQueue allows you to add NSOperations, which get run FIFO on a number of threads specified in maxConcurrentOperationCount. I've found that a single image download thread is sufficient, even on edge networks: the network speed is always the bottleneck, not lack of concurrency. This allows the implementation of CachedImageLoader to be single threaded (counting the operation thread) and use synchronous downloading. A image consumer needing an image implements the ImageConsumer protocol, then calls addClientToDownloadQueue: passing itself as the argument:

- (void)addClientToDownloadQueue:(id<ImageConsumer>)client {
    UIImage *cachedImage;
    if (cachedImage = [self cachedImageForClient:client]) {
        [client renderImage:cachedImage];
    } else {
        NSOperation *imageDownloadOp = [[[NSInvocationOperation alloc] 
                        initWithTarget:self
                              selector:@selector(loadImageForClient:)
                                object:client] autorelease];
        [_imageDownloadQueue addOperation:imageDownloadOp];
    }
}

- (void)loadImageForClient:(id<ImageConsumer>)client {
    NSAutoreleasePool *pool = [[NSAutoreleasePool alloc] init];

    if (![self loadImageRemotelyForClient:client]) {
        [self addClientToDownloadQueue:client];
    }

    [pool release];
}

In cachedImageForClient, CachedImageLoader uses both the in-memory NSURLCache as well as our DiskCache class above, in turn. Failing to find the image in the cache, the loader creates an NSInvocationOperation which, in turn, gets called on our download thread; we create an autorelease pool and download the image synchronously, caching the image data when we have it (in both DiskCache and NSURLCache.)

So there you have it, most of an implementation of an asynchronous, caching image downloader for iPhone.

UPDATE 11/26/2009: The complete source code for the cache is available here.

Tuesday, February 24, 2009

Cracking Supercollider

SuperCollider is an amazing language, if you are in the super genius club who can understand the extensive documentation or pursue graduate studies at CCRMA. I've been out of audio synth for a while, but recently found myself needing to apply a recursive delay line to an audio recording I'm working on for my music project, Midday Veil.

SuperCollider dates from the mid-90's, and is thus a peer to Ruby, sharing influences like Smalltalk and Lisp. As languages go, it's pretty nice, though the compiler leaves something to be desired - inexplicably, variables must be declared before use at the top of a function, much like in C. Other than minor gripes like that, it's a pretty nifty package: functions as first-class objects, native arrays and maps, garbage collection, dynamic typing, and classical OOP features to boot. However, there's a lot more to the platform than just the language, and the learning curve is quite steep. Much like Ruby, some of the syntax is "optional" or has multiple ways to express the same thing; functions need a "value" message sent to them to be executed. Also, most of even the basic language-level concepts are mixed in with advanced platform-specific concepts like OSC messaging, client-server internals, audio buffers, and so on, so getting your feet wet takes a lot of immersion in the concepts to understand SuperCollider's terse yet expressive syntax and impressive power. Getting started with Processing, which uses a much uglier language, is a cakewalk by comparison.

It doesn't help that the "introductory tutorial" launches first thing into a detailed description of how to use the platform to send OSC messages over the Internet, then SynthDefs, then SynthDescLibs, and then instantiating both them and their UDP equivalents, none of which, it turns out, are required to get started, when you really just want to figure out how to play a sound file from your hard disk and feed it through some reverb. Oh no, you don't get to that until you've drudged through page after page of detailed docs, explaining each concept in depth before moving on to the next incremental step. Memo to documentation writers: people (especially people making music) need to be able to sit down and play something after their first lesson. You don't come home from your first piano lesson with a stack of reading on Cristofori and the development of the modern soundboard, told that maybe you can start playing after you've written a 200-page treatise on the inner mechanics of the thing. Oh sure, that's all useful to understand before too long, but to start off you want to learn just enough of a subset of the thing to feel like you can begin to be creative with it. For an example of just how jargony the whole thing feels, I treat you to an excerpt from page 3 of the docs:

When notated as code in client programs, the engines have two essential parts: a name and a function. In the jargon of SuperCollider, the function is called a ugenGraphFunc. The term ugenGraphFunc derives from the notion of a graph, which is the data structure that SuperCollider uses to organize unit generators. SuperCollider constructs the graph for you from the code it finds in your function which means that don't have to know how a graph works or that it even exists.

Ok, so basically it's a parse tree with a funny name. I assumed something like that was under the hood, but if I don't have to know this, why the hell are you telling me on page 3 of the documentation?

With that in mind, I present to you my first hard-won miniature piece of software in SuperCollider, which I wrote from scratch with scant help from the docs:

(
 r = { |input, gain, decayTime = 0.5, decayFactor = 0.9|
 var output, buf;
 if (gain > 0.1, {
         buf = Buffer.alloc(s, 44100, 2);
         output = input + r.(BufDelayC.ar(
             buf,
             input,
             decayTime,
             gain
             ), gain * decayFactor)
     }, {
         output = 0
     });
 output;
 }
)


(
 var filepath = "remember-pans-cropped.aiff";
 var synth = Buffer.cueSoundFile(s, filepath, 0, 2);
 {
 r.value(DiskIn.ar(2, synth), 1, 0.5, 0.9);
 }.play;
)

Ok, it ain't much, but it's mine and I'm proud of it. I'll probably look at that example a few months from now and cringe knowing all the mistakes I just made, but know what? Hell with it. This is music, and if you leak a bit of memory here or there on your own machine before you learn how to fix it, well, that's not too steep a price for some wicked tunes. Start with what you want, then learn just enough to get yourself there.

Monday, August 11, 2008

Hitting the limits on iPhone Safari

Hit a hard iPhone resource limit:

<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN"
"http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<meta http-equiv="content-type" content="text/html; charset=utf-8"/>
<meta name="viewport" 
    content="width=device-width; initial-scale=1.0; maximum-scale=1.0; user-scalable=no;" />
<meta name="apple-touch-fullscreen" content="YES" />
<title>iPhone image loading test</title>
<script type="text/javascript">
var n = parseInt('02123003022000310', 4),
    nTiles = 0;

function drawTile() {
    n++;
    nTiles++;
    document.getElementById('img').src = 
        'http://h0.ortho.tiles.virtualearth.net/tiles/h0' +
        n.toString(4) + '.jpeg?g=131';
    document.getElementById('count').innerHTML = nTiles+'';

}

window.onload = function () {
    window.setInterval(drawTile, 500);
};
</script>
</head>
<body>
    <img src="#" id="img" />
    <p>Total tiles: <span id="count">0</span></p>
</body>
</html>

After downloading about 210 images, the iPhone simply stops downloading new ones. This is probably due to hitting the hard 30MB same-page resource limit as as documented on A List Apart. Apple itself documents the limit at 2 megapixels. Who knew that they also didn't free such resources when no longer in use?

I don't see any easy way around this one, and the implications are huge: even if your app is scrupulous in conserving JavaScript and DOM memory resources, sooner or later the browser itself will fail you. This precludes especially any browser-based Ajax mapping application, and many long-running Ajax apps in general.

So much for Web 2.0 on the iPhone.

Tuesday, July 8, 2008

Where are the JavaScript unittesting frameworks?

Now that JavaScript has been patched together into a number of promising server-side frameworks (Synergy, Jaxer, and, coming soon(ish), Rhino on Rails), JavaScript is really taking off as a potentially full-stack enterprise solution.

One serious failing, however, seems to be the continued lack of decent developer support tools, the worst of which has got to be testing. Sure, there are a number of decent browser test automation frameworks out there:

Sure, these are all great platforms - for AUTOMATION. Let's be clear, however: Automation is in no way the same thing as unit testing. Automation requires a full environment, and seeks to replicate the end-user experience on the full product stack by means of emulated behaviors - mouse clicks, key presses, and so on. Usually, such tests launch a browser app, set up the environment, execute the test case steps (which can mean multiple page loads), and then close the browser app, for EVERY TEST CASE. Such tests are absolutely necessary for any non-trivial user-facing product.

At the same time, developers need more granularity than that. We need to test hundreds of individual methods and edge cases in our code that target specific functions. We need a framework that can be run at build-time, and can plow through hundreds of focused test cases in a matter of seconds. We need a browser, sans GUI.

For the purpose of headless, command-line browser code testing, it seems only the GPL Crosscheck framework offers the robustness of browser emulation required for any serious work. Built on Rhino with a Java layer of cleverly reverse-engineer browser behaviors, Crosscheck itself has numerous bugs and drawbacks in common browser features (no cookie emulation, poor DOM Level 0 support, nonexistent IFrames, incomplete CSS emulation), the greatest of which seems to be that development has stalled on the project.

It should be immediately apparent to any front-end developer maintaining a moderate-to-large codebase why command-line unit-testing is important. Also, I realize that, as a developer, I should be getting things done and building solutions. One could investigate building a command-line app for Windows (and perhaps a fork for Linux using Wine?) that would instantiate the actual browser binaries from the command line and run code without launching the browser chrome; it seems this should work at least for Internet Explorer (COM objects) and Firefox (XULRunner) and maybe Safari too. I would like to submit patches to Crosscheck, but I'm not sure if the core developers even have time to review patches, and I don't personally have the time to sink into development of a competing framework right now. My hope is that someone out there in the development community will take notice of this need and have the time and/or resources to tackle this problem, and maybe one day I'll be that person. In the meantime, we'll have to settle for running our test suites in a matter of hours and not minutes.

Tuesday, April 15, 2008

History

$ history | awk '{print $2}' | sort | uniq -c | sort -rn | head

 149 cd
 138 ls
  42 svn
  27 python
  23 vim
  18 exit
  16 locate
  11 ssh
  10 rm
   8 less
via

Saturday, March 29, 2008

New blog

For all 2.3 of you out there reading this, I'd like to announce a new blog on "metaphysics?" so I can keep a clean sterile separation between work and life. My postings on this blog will continue to be exactly as infrequent as they have been since I started. Thank you.