Saturday, March 17, 2012

Introducing MonoTouch.SQLite

I've been working on a personal side-project writing an app for the iPad that makes use of SQLite-Net, displaying that data in a UITableView.

Up until this past week, I had been using Miguel de Icaza's wonderful MonoTouch.Dialog library for displaying my data. Unfortunately, I wanted search filtering to be persistent, which means that I really needed to use Apple's UISearchDisplayController but I couldn't find an easy way to retrofit that onto MonoTouch.Dialog's DialogViewController to replace the simpler UISearchBar API that it currently uses. Since I had to look at creating an alternate solution, I figured I might as well solve the other potential problem I had with MonoTouch.Dialog, which is that my app really needed to be able to handle tables with a massive number of items. This brings us to...

MonoTouch.SQLite

MonoTouch.Dialog really made using UITableViews in iPhone and iPad apps trivial and I wanted to try and repeat at least some of that with MonoTouch.SQLite.

The first thing I had to do was to figure out a way of modeling the data in such a way as to allow a generic class to do most of the work for the developer. After a few sleepless nights of hacking last weekend, I figured out a fairly simple approach that seems to work pretty well. I started off thinking that I wouldn't be able to get around having to have a subclassable model, so I made most everything virtual. This is the public API that I came up with:

public class SQLiteTableModel<T> : IDisposable where T : new ()
{
    public SQLiteTableModel (SQLiteConnection sqlitedb, int pageSize, SQLiteOrderBy orderBy, string sectionExpr);

    // 2 ways of setting the search criteria
    public SQLiteWhereExpression SearchExpression { get; set; }
    public string SearchText { get; set; }

    // Gets the total number of table rows
    public int Count { get; }

    // Gets the number of table sections
    public int SectionCount { get; }

    // Gets the section titles
    public string[] SectionTitles { get; }

    // Gets the row count for a particular section
    public int GetRowCount (int section);

    // Get the index of an item
    public int IndexOf (T item, IComparer<t> comparer);

    // Convert item index into a section and row
    public bool IndexToSectionAndRow (int index, out int section, out int row);

    // Convert section and row into an item index
    public int SectionAndRowToIndex (int section, int row);

    // 2 ways of getting an item
    public T GetItem (int section, int row);
    public T GetItem (int index);

    // Reset the state of the model
    public void ReloadData ();
}

You can see the full class implementation here.

It turns out, though, that it really isn't necessary to subclass my model unless you want to have finer control over the specific SQL query commands that it makes (all of those methods are virtual).

SQLiteTableViewController<T>

As I started porting my iPad app to use my SQLiteTableModel class, I started to realize that I could abstract a lot of my usage of the model into a reusable base class. What I came up with will blow your mind.

Are you ready?

In order to populate a UITableView with the contents of an SQLite table, all you have to do is subclass SQLiteTableViewController<T> and implement 1 method:

protected UITableViewCell GetCell (UITableView tableView, NSIndexPath path, T item)

That's it.

I've written up a sample iPhone app that illustrates just how easy this is.

But wait! There's more!

If you order in the next 30 minutes, you can also get this free complimentary Sham-Wow!

Okay, just kidding about that Sham-Wow! bit, but I wasn't kidding about there being more:

Remember when I said one of the problems I wanted to solve was persistent search filtering? Yea, well, I did it. SQLiteTableViewController handles all of that for you as well. In fact, give searching a try in that sample above.

At this point I bet you're thinking, "wow, how could this get any better?"

I'll tell you. Remember how SQLiteTableModel had 2 methods for setting the search criteria? Well, the one that takes a string parses it to create a SQLiteWhereExpression allowing the user to match against specific fields. For example, if you had the following data item:

public class Contact {
    public string FirstName;
    public string LastName;
    public string PhoneNumber;
    public string Address;
    public string Comments;
}

...the user could type:

address:"Newton, MA"

and SQLiteTableModel would construct a query to match "Newton, MA" against only the Address field.

If the user, instead, types:

address:"Newton, MA" firstname:Jane

then the matches that would display in the list would be limited to contacts with a first name of "Jane" who live also in "Newton, MA".

I've also taken the liberty of implementing a SQLiteSearchAliasAttribute that allows you to specify aliases for your fields (or even the same alias to multiple fields!). For example, you could do this:

public class Contact {
    [SQLiteSearchAlias ("first")][SQLiteSearchAlias ("name")]
    public string FirstName;
    [SQLiteSearchAlias ("last")][SQLiteSearchAlias ("name")]
    public string LastName;
    [SQLiteSearchAlias ("phone")]
    public string PhoneNumber;
    public string Address;
    public string Comments;
}

This would allow your users to use "name" to match against either FirstName or LastName!

It also means they can type "first" instead of "firstname" to match against only the first name, as in the above example.

Where Can I Find This Awesome Library?

Glad you asked! You can find it on my GitHub page: MonoTouch.SQLite.

Well? What are you waiting for? Get hacking!

Sunday, February 12, 2012

Meet the Hackers

This past week, I've started to get back into photography a bit more (thanks, Nina!) and started taking my camera into the office with me every day to remind myself to take photos. As a result, I've taken a bunch of photographs of my co-workers in the office.

Would you like to meet the hackers?

The Founders

Most of you would probably recognize the infamous Miguel de Icaza, Xamarin's CTO:

Miguel de Icaza

Next up is our very own Steve Jobs, Nat Friedman, our CEO and the man who reminds us to pay attention to the details:

Nat Friedman

Another person many of you will recognize is our very own COO, Joseph Hill:

Joseph Hill

MonoDevelop Team

Well, okay, I've only got a photo of the famous Michael Hutchinson, but he's a very important player in the development of MonoDevelop.

Michael Hutchinson

QA Team

Next up, we have the QA team. They do their best to make sure that we, the developers, didn't break anything. When they aren't testing a specific application before a launch, they hammer away at our products and try to find weak spots in our code (but we still love them anyway!)

This is PJ, and as you can see, he's demonstrating how to QA popcorn corn cobs:

PJ

(Did it pass the test, PJ?)

Next up is Lindsey. She's been working on writing automated tests to make it less likely for releases to include regressions. Let's hope she's successful!

Lindsey

Release Team

Alex Corrado is the man behind the curtain. He's our head Release Team engineer and also the brilliant mastermind that started CXXI, the Mono C++ interop project that we hope to give him time to finish someday soon.

Alex Corrado

Web Team

The newest addition to our ranks (just this week, in fact!), but long-time contributor to the Mono project, is Bojan Rajković. You can see we've already put him to work (he is no doubt puzzling over some ASP.NET code on his screen).

Bojan Rajković

Documentation Team

Nina is the only Cambridge resident on our Docs Team. Specifically, she hacks on our Documentation Portal. She's also the one who has encouraged me to get back into taking photographs, so she'll have to put up with me using her as a guinea pig the most. Here she is taunting me with her hot cup of Chaider:

Nina

Thursday, September 15, 2011

MonoTouch Tips & Tricks: Updating the Location of an MKAnnotation

I just spent a day figuring this out, so figured I'd share it with the world because I'm sure other people are going to want to know how to do this...

So the question is,

How can I get my MKMapView to respond to coordinate changes in my custom MKAnnotations?

As it turns out, this is incredibly simple. In your MKAnnotation subclass, whenever you want to change your Coordinate property value, you need to do the following:

void UpdateCoordinate (CLLocationCoordinate2D newCoordinate)
{
    this.WillChangeValue ("coordinate");
    this.Coordinate = newCoordinate;
    this.DidChangeValue ("coordinate");
}

That's it! It really is that simple...

The reason this works is because MKMapView observes changes in its list of MKAnnotations, you just need to signal to it that changes are about to happen (and did happen).

Happy hacking!

Sunday, August 14, 2011

GMime 2.5.10: A Call For Testers

I've just released GMime 2.5.10 which I hope to be the last of the 2.5 releases before I release 2.6.0. I feel that I've stretched the development of 2.6.0 out for far too long (2.5 development began at the end of April, 2009) and even though I didn't get around to doing everything I had hoped to do, I feel that the latest 2.5.x releases are such an improvement over 2.4.x that I just want to get it out there for developers to start using. But before I make a 2.6.0 release, I'm hoping to get some feedback and some testing.

What's new?

New for the release of 2.5.10 is GMimePartIter which replaces the need for g_mime_object_foreach()and its awkward callback requirement, instead allowing you to take the far nicer iterator approach that is popular in the C# and Java worlds (known as IEnumerator in C#). This new iterator, like the foreach function it replaces, iterates over the MIME tree structure in depth-first order.

Inspired by IMAP's FETCH body part-specifier syntax, I've implemented a method allowing you to jump to a part based on a part-specifier string (aka a path): g_mime_part_iter_jump_to(). Also implemented is a function called g_mime_part_iter_get_path(), which can be used to tell you the current part-specifier path of the iterator.

For example, if you had the following MIME message structure:

multipart/related
  multipart/alternative
    text/plain
    text/html
  image/jpeg

The body part-specifier paths would be:

1    multipart/alternative
1.1  text/plain
1.2  text/html
2    image/jpeg

This means that g_mime_part_iter_jump_to(iter, "1.2") would jump to the part specified by the path "1.2" which, as we can see above, would be the text/html part. Calling g_mime_part_iter_next(iter) would iterate to the next part, being the image/jpeg, while calling g_mime_part_iter_prev(iter) would iterate backwards to the text/plain part and calling it again would iterate backwards to the multipart/alternative.

What I Need From Testers

My feeling is that developers will want to use this cool new body part-specifier path functionality for aiding them in implementing IMAP servers and/or clients. Because of this, it would be great if GMime's implementation matched IMAP's specification exactly. The problem is that I don't have the time or energy to verify that the paths work out to be identical in all cases. So... if you are one of those developers who is interested in using this functionality and need it to be identical to IMAP's syntax (or would really like it to be), I'm hoping that you could test it out and make sure that it matches. Especially worthwhile of testing, I'd imagine, is having message/rfc822 parts in the tree. I suspect that, if anywhere, this is where differences may be.

If body part-specifier paths aren't something you care about, don't fret; the rest of the iterator API needs testing as well and if you have no interest in the iterator API at all, perhaps you'd be willing to test the S/MIME functionality (especially since I haven't figured out how to test it myself, given that I don't have an S/MIME cert nor have I figured out how to generate one or add one to my gpgsm keyring).

Your help will be greatly appreciated.

Wednesday, August 3, 2011

Debugging Your MonoTouch Apps: The Future

One of the "paper cuts" developers have been having with developing their MonoTouch 4.0.x (and earlier) applications is that for some networking setups, the IP of the developer's workstation detected by MonoDevelop and given to the iPhone or iPad device for debugging purposes is not correct. This often happens if the WiFi is a different network than the network that the developer's machine is connected to (although there are other scenarios as well).

Since it does not seem to be widely known about, allow me to point out that current versions of MonoTouch allow developers to modify the IP that the runtime should connect to for debugging via the iOS Settings app found on any iPhone or iPad (or Simulator). You can see a screenshot of this per-App Settings page in the screenshot to the left. Each of these fields are editable, allowing you to override the defaults filled-in by MonoDevelop.

For our upcoming 4.1 release, Rolf Kvinge and I (but mostly Rolf) have been working on improving this. Rolf has modified the code to check the value of the IP provided in the per-App Settings and if it is set to nil or "automatic", the debugger falls back to checking for a file bundled with the app called MonoTouchDebugConfiguration.txt which can list any number of IP's to try and connect to, each one being on a separate line prefixed with "IP: ". For example:

IP: 10.0.1.31
IP: 192.168.1.31
IP: 204.11.102.79

The runtime will then attempt to connect to each of these IPs asynchronously until it establishes a connection to one of them (at which point it aborts the other waiting connections). This config file solution will hopefully help simplify things for developers a bit by allowing them to pre-configure which IPs to try for their local network configuration w/o having to manually override the iPhone debug settings on the device or simulator.

For Phase 2 of our plan for World Domination, Rolf is hard at work adding support to MonoDevelop and the runtime to allow for USB debugging which will obsolete the above functionality in future versions where the developer has a MonoDevelop which supports USB debugging. For developers stuck on an older MonoDevelop (like 2.4), the solution illustrated above requires no changes to MonoDevelop and so will be available for use.

Thursday, April 14, 2011

Moonlight on Android

For the past week, the Moonlight team has been busy porting Moonlight to Android devices and today, showed it off at Mix 11.

The video shows Moonlight running on both a Motorola Xoom tablet and a Nexus S phone.

Keep in mind that we're still in the early phases of porting and there's still a lot of work left to do before we can ship a product, but it's still exciting!

Update: For those of you reading my blog from Planet GNOME (or some other planet that doesn't show the video above), you can find it here, on YouTube.

Update: Now you can see Moonlight rendering video with 3D transforms, too!

Thursday, April 7, 2011

Optimizing Merge Sort

A number of years ago I wrote about the Merge Sort algorithm. One of the advantages of Merge Sort is that it is a stable sort, meaning that elements that compare as being equal remain in their original order after being sorted.

Well, today I had need of employing a stable sorting routine for sorting elements by a ZIndex in Moonlight. Up until today, we had been using qsort() which, while not guaranteed to be a stable sort on any platform, happens to be implemented in glibc as a stable sort except in out-of-memory conditions. Since we'd like Moonlight to work on platforms other than Linux+glibc (such as Mac OS or BSD), it has become important enough to implement properly.

To start, I dusted off my generic MergeSort() implementation from years ago when I was writing articles about various sorting algorithms. This is what I had to start with:

#define MID(lo, hi) (lo + ((hi - lo) >> 1))

static void
msort (void *array, void *buf, size_t low, size_t high, size_t size,
       int (* compare) (const void *, const void *))
{
    register char *lo, *hi, *b;
    char *al, *am, *ah;
    size_t mid;
    
    mid = MID (low, high);
    
    if (mid + 1 < high)
        msort (array, buf, mid + 1, high, size, compare);
    
    if (mid > low)
        msort (array, buf, low, mid, size, compare);
    
    ah = ((char *) array) + ((high + 1) * size);
    am = ((char *) array) + ((mid + 1) * size);
    al = ((char *) array) + (low * size);
    
    b = (char *) buf;
    lo = al;
    hi = am;
    
    while (lo < am && hi < ah) {
        if (compare (lo, hi) <= 0) {
            memcpy (b, lo, size);
            lo += size;
        } else {
            memcpy (b, hi, size);
            hi += size;
        }
        
        b += size;
    }
    
    if (lo < am)
        memcpy (b, lo, am - lo);
    else if (hi < ah)
        memcpy (b, hi, (ah + size) - hi);
    
    memcpy (al, buf, ah - al);
}

int
MergeSort (void *base, size_t nmemb, size_t size,
           int (* compare) (const void *, const void *))
{
    void *tmp;
    
    if (nmemb < 2)
        return 0;
    
    if (!(tmp = malloc (nmemb * size))) {
        errno = ENOMEM;
        return -1;
    }
    
    msort (base, tmp, 0, nmemb - 1, size, compare);
    
    free (tmp);
    
    return 0;
}

Since performance is very important, I clocked this implementation against qsort() and got the following results on my Intel Core2 Quad Q6600 2.4 GHz machine using arrays of 10 million ints:

  • Randomized input: 14.13s vs qsort()'s 6.77s
  • Sorted input: 4.41s vs qsort()'s 1.54s
  • Reversed input: 4.26s vs qsort()'s 1.90s

Clearly the above MergeSort() implementation did not fare well against glibc's qsort() on my system, so it was time to look at what I could do to improve the performance.

The most obvious optimization I could see was to try and batch my memcpy() calls. In other words, instead of calling memcpy() to copy each and every element into our temporary buffer, it'd be more efficient to copy blocks of elements at a time:

static void
msort (void *array, void *buf, size_t low, size_t high, size_t size,
       int (* compare) (const void *, const void *))
{
    char *al, *am, *ah, *ls, *hs, *lo, *hi, *b;
    size_t mid;
    
    mid = MID (low, high);
    
    if (mid + 1 < high)
        msort (array, buf, mid + 1, high, size, compare);
    
    if (mid > low)
        msort (array, buf, low, mid, size, compare);
    
    ah = ((char *) array) + ((high + 1) * size);
    am = ((char *) array) + ((mid + 1) * size);
    al = ((char *) array) + (low * size);
    
    b = (char *) buf;
    lo = al;
    hi = am;
    
    do {
        ls = lo;
        hs = hi;
        
        if (lo > al || hi > am) {
            /* our last loop already compared lo & hi and found lo <= hi */
            lo += size;
        }
        
        while (lo < am && compare (lo, hi) <= 0)
            lo += size;
 
        if (lo > ls) {
            memcpy (b, ls, lo - ls);
            b += (lo - ls);
        }
 
        if (lo < am) {
            /* our last compare tells us hi < lo */
            hi += size;
            
            while (hi < ah && compare (hi, lo) < 0)
                hi += size;
            
            memcpy (b, hs, hi - hs);
            b += (hi - hs);
        }
    } while (lo < am && hi < ah);
    
    if (lo < am)
        memcpy (b, lo, am - lo);
    else if (hi < ah)
        memcpy (b, hi, ah - hi);
    
    memcpy (al, buf, ah - al);
}

The results were promising. For the exact same inputs (including the exact same random array), we now get:

  • Randomized input: 10.45s
  • Sorted input: 2.08s
  • Reversed input: 2.03s

The only other way that we can reduce the number of memcpy() calls we make is to avoid copying leading and trailing elements into our temporary buffer if it's not necessary to merge them. Here's the solution I came up with:

static void
msort (void *array, void *buf, size_t low, size_t high, size_t size,
       int (* compare) (const void *, const void *))
{
    char *a1, *al, *am, *ah, *ls, *hs, *lo, *hi, *b;
    size_t copied = 0;
    size_t mid;
    
    mid = MID (low, high);
    
    if (mid + 1 < high)
        msort (array, buf, mid + 1, high, size, compare);
    
    if (mid > low)
        msort (array, buf, low, mid, size, compare);
    
    ah = ((char *) array) + ((high + 1) * size);
    am = ((char *) array) + ((mid + 1) * size);
    a1 = al = ((char *) array) + (low * size);
    
    b = (char *) buf;
    lo = al;
    hi = am;
    
    do {
        ls = lo;
        hs = hi;
        
        if (lo > al || hi > am) {
            /* our last loop already compared lo & hi and found lo <= hi */
            lo += size;
        }
        
        while (lo < am && compare (lo, hi) <= 0)
            lo += size;
        
        if (lo < am) {
            if (copied == 0) {
                /* avoid copying the leading items */
                a1 = lo;
                ls = lo;
            }
            
            /* our last compare tells us hi < lo */
            hi += size;
            
            while (hi < ah && compare (hi, lo) < 0)
                hi += size;
            
            if (lo > ls) {
                memcpy (b, ls, lo - ls);
                copied += (lo - ls);
                b += (lo - ls);
            }
            
            memcpy (b, hs, hi - hs);
            copied += (hi - hs);
            b += (hi - hs);
        } else if (copied) {
            memcpy (b, ls, lo - ls);
            copied += (lo - ls);
            b += (lo - ls);
            
            /* copy everything we needed to re-order back into array */
            memcpy (a1, buf, copied);
            return;
        } else {
            /* everything already in order */
            return;
        }
    } while (hi < ah);
    
    if (lo < am) {
        memcpy (b, lo, am - lo);
        copied += (am - lo);
    }
    
    memcpy (a1, buf, copied);
}

Once again, reducing the amount of copying paid off:

  • Randomized input: 9.80s
  • Sorted input: 0.95s
  • Reversed input: 2.05s

Update 2011-05-18: One final optimization that can be tried is pre-calculating the optimum way to copy elements between buffers. This calculation, while not terribly expensive itself, adds up with every call to memcpy(). Let's start off by writing some handy macros:

#define COPYBY(TYPE, a, b, n) {         \
    long __n = (n) / sizeof (TYPE);     \
    register TYPE *__a = (TYPE *) (a);  \
    register TYPE *__b = (TYPE *) (b);  \
                                        \
    do {                                \
        *__a++ = *__b++;                \
    } while (--__n > 0);                \
}

#define MEMCOPY(dest, src, n) {                 \
    switch (copy_mode) {                        \
    case 1: COPYBY (long, dest, src, n); break; \
    case 2: COPYBY (int, dest, src, n); break;  \
    default: memcpy (dest, src, n);             \
    }                                           \
}

Now that these handy macros are written, we can plug them into our Merge Sort implementation:

static void
msort (void *array, void *buf, size_t low, size_t high, size_t size,
       int copy_mode, int (* compare) (const void *, const void *))
{
    char *a1, *al, *am, *ah, *ls, *hs, *lo, *hi, *b;
    size_t copied = 0;
    size_t mid;
    
    mid = MID (low, high);
    
    if (mid + 1 < high)
        msort (array, buf, mid + 1, high, size, compare);
    
    if (mid > low)
        msort (array, buf, low, mid, size, compare);
    
    ah = ((char *) array) + ((high + 1) * size);
    am = ((char *) array) + ((mid + 1) * size);
    a1 = al = ((char *) array) + (low * size);
    
    b = (char *) buf;
    lo = al;
    hi = am;
    
    do {
        ls = lo;
        hs = hi;
        
        if (lo > al || hi > am) {
            /* our last loop already compared lo & hi and found lo <= hi */
            lo += size;
        }
        
        while (lo < am && compare (lo, hi) <= 0)
            lo += size;
        
        if (lo < am) {
            if (copied == 0) {
                /* avoid copying the leading items */
                a1 = lo;
                ls = lo;
            }
            
            /* our last compare tells us hi < lo */
            hi += size;
            
            while (hi < ah && compare (hi, lo) < 0)
                hi += size;
            
            if (lo > ls) {
                MEMCOPY (b, ls, lo - ls);
                copied += (lo - ls);
                b += (lo - ls);
            }
            
            MEMCOPY (b, hs, hi - hs);
            copied += (hi - hs);
            b += (hi - hs);
        } else if (copied) {
            MEMCOPY (b, ls, lo - ls);
            copied += (lo - ls);
            b += (lo - ls);
            
            /* copy everything we needed to re-order back into array */
            MEMCOPY (a1, buf, copied);
            return;
        } else {
            /* everything already in order */
            return;
        }
    } while (hi < ah);
    
    if (lo < am) {
        MEMCOPY (b, lo, am - lo);
        copied += (am - lo);
    }
    
    MEMCOPY (a1, buf, copied);
}

int
MergeSort (void *base, size_t nmemb, size_t size,
           int (* compare) (const void *, const void *))
{
    int copy_mode;
    void *tmp;
    
    if (nmemb < 2)
        return 0;
    
    if (!(tmp = malloc (nmemb * size))) {
        errno = ENOMEM;
        return -1;
    }
    
    if ((((char *) base) - ((char *) 0)) % sizeof (long) == 0 && (size % sizeof (long)) == 0)
        copy_mode = 1;
    else if ((((char *) base) - ((char *) 0)) % sizeof (int) == 0 && (size % sizeof (int)) == 0)
        copy_mode = 2;
    else
        copy_mode = 0;
    
    msort (base, tmp, 0, nmemb - 1, size, copy_mode, compare);
    
    free (tmp);
    
    return 0;
}

This handy trick seems to have worked out rather well:

  • Randomized input: 7.79s
  • Sorted input: 0.99s
  • Reversed input: 1.69s

At this point, I can't think of any other obvious optimizations so I'm going to call it a day.

For a recap, here are the results of all 4 implementations compared side-by-side with the results from qsort():

qsort()msort() v1msort() v2msort() v3msort() v4
random:6.7714.1310.459.807.79
sorted:1.544.412.080.950.99
reversed:1.904.262.032.051.69

Code Snippet Licensing

All code posted to this blog is licensed under the MIT/X11 license unless otherwise stated in the post itself.