Quod erat faciendum

Strange Loop 2011: Mirah for Android Development

2012-01-02T15:15:32.143-08:00

Video of my Mirah/Android presentation from Strange Loop is available now.

Here are a few extra resources:

Mirah and Pindah on Github.
My slides (pdf).
The demo project I walk through at the end.

I've written about Mirah in the past, too:

The Birth of Hazel Belle Ribera

2011-12-20T22:40:29.275-08:00

On December 20, 2011, Hazel Belle Ribera was born!

We had another great home birth with our wonderful midwives. Jessica was amazing, to say the least.

Hazel is a great little girl, and so snuggly. At 7lbs 5oz and 21.25", she's the lightest and longest of the bunch. She takes after her mother in that way.

I won't write quite so much as I did for Ivo's birth, but not because the experience was lesser. Labor was longer and less obvious this time, but we had good friends and a warm fire to keep us company.

The boys both love her, and love to hold her. They're so tender and sweet together; we feel really blessed.

An Appearance of the Strangest Kind

2011-06-21T13:30:35.570-07:00

Given my current time constraints, a single cogent blog post would constitute a strange enough appearance. But I have something rarer and more fascinating in store for you, Dear Reader:

I'll be giving a talk at this year's StrangeLoop!

I'm incredibly excited about this. I'll be speaking on using Mirah for Android development – something I've written about a little bit in the past.

I attended last year, and found the conference quite excellent. This year promises to be even better, with keynotes from Rich Hickey (creator of Clojure), Gerald Sussman (!), and more. The caliber of the other talks looks incredible, and I'm really honored to be included.

So, grab a ticket before the prices go up, and come watch me fumble difficult questions about the JVM!

Ruby 1.9.2 on Ubuntu 11.04

2011-05-06T14:03:01.763-07:00

I've been building an application from scratch, and I want to go with the latest and greatest of the Ruby world. It's not yet clear to me which of Ruby 1.9.2, JRuby, and REE fit the bill, but I've picked 1.9.2. – at least for now.

I'm building around Ubuntu server, and am automating this process with Chef. I've seen two different companies get stuck on outdated Ruby or Rails versions due to lack of easy provisioning, and I don't want to be in that boat. On the other hand, I want to devote as much time as possible to user facing features; no one's going to use what I make based on our future server maintenance paths.

Ubuntu packages

Ubuntu 11.04 provides a fake 1.9.2 package that is provided by ruby1.9.1. Installing ruby1.9.1 actually installs 1.9.2-p0, but all of the binaries are suffixed with 1.9.1. I hate this false naming on a purely conceptual level, but I'm sure there's some Debian-based compatibility issue and I could get over it. However, there have been three important releases since 1.9.2-p0 that contain significant bug fixes. The combination makes that a show stopper for me.

RVM

RVM is a tempting option. It's PATH magic is a little too incomplete for production use, in my opinion – RVM binaries are conspicuously absent for cron jobs and other non-interactive shells. This could probably be fixed, but that would feel like a hack around a hack. And I really don't want to deal with the eventual and inevitable breakage of all that magic in a production environment.

Compile from source

I considered just compiling a binary on each machine, but this is a quick path to upgrade/maintenance hell. Another downside (that RVM shares) is the time cost – with a precompiled package, Ruby is installed in a matter of seconds. Compiling for minutes could be a minor problem when provisioning a bunch of extra instances in The Cloud.

Roll your own .deb

I decided to combine the source option with the packing option. This allows me to quickly distribute and install a binary while retaining control over patch level, executable names, et cetera. However, it made me appreciate the difficulties faced by Ruby package maintainers – it's not exactly a straightforward process.

Here are some things I learned the hard way:

checkinstall is broken on Ubuntu. You have to pass in --fstrans=no to get it to work properly.
Ruby wants to install in /usr/local, but Ubuntu/Debian would prefer it to live in /usr. I decided to stick with the host system's default.
PATH is tricky here, too. If you install in /opt, your gem binaries won't be on the PATH. You'll need to solve the same sort of PATH issues RVM has if you want to add your /opt bindir to everyone's PATH.
update-alternatives is your friend; use it!

Here's the build process I settled on:

#!/bin/bash
sudo apt-get -y install zlib1g-dev libssl-dev libreadline5-dev
libyaml-dev build-essential bison checkinstall
cd /tmp
wget http://ftp.ruby-lang.org/pub/ruby/1.9/ruby-1.9.2-p290.tar.gz
tar xvzf ruby-1.9.2-p290.tar.gz
cd ruby-1.9.2-p290
./configure --prefix=/usr\
            --program-suffix=1.9.2\
            --with-ruby-version=1.9.2\
            --disable-install-doc
make
sudo checkinstall -D -y\
                  --fstrans=no\
                  --nodoc\
                  --pkgname='ruby1.9.2'\
                  --pkgversion='1.9.2-p290'\
                  --provides='ruby'\
                  --requires='libc6,libffi5,libgdbm3,libncurses5,libreadline5,openssl,libyaml-0-2,zlib1g'\
                  --maintainer=brendan.ribera@gmail.com
sudo update-alternatives --install /usr/bin/ruby ruby /usr/bin/ruby1.9.2 500\
                        --slave   /usr/bin/ri   ri   /usr/bin/ri1.9.2\
                        --slave   /usr/bin/irb  irb  /usr/bin/irb1.9.2\
                        --slave   /usr/bin/gem  gem  /usr/bin/gem1.9.2\
                        --slave   /usr/bin/erb  erb  /usr/bin/erb1.9.2\
                        --slave   /usr/bin/rdoc rdoc /usr/bin/rdoc1.9.2

I'm not 100% confident in my checkinstall/deb-foo – namely, the semantics of --requires and --provides are a little unclear to me. Nor am I sure that the list of required binaries that I provided is completely accurate. What I do know is that all of this works.

I can now automate installation of this package on any machine I provision and instantly have the latest Ruby patch level with properly named binaries. Cool!

Updated 2011-09-01 15:12 to point this script at the 1.9.2-p290 release.

On Flashing OCZ Vertex 2 Firmware

2011-04-26T19:58:53.772-07:00

I recently bought a MacBook Pro (no, my opinions haven't changed) for iOS development. With it, I bought a shiny new SSD. As it shipped, I read nasty reports of a firmware bug that caused the drive to freeze or lose data when awaking from sleep/hibernate in OSX. Yikes!

My drive arrived and did indeed have the affected firmware. There was an updated version, but OCZ does not make a firmware upgrade tool for OSX. And even outside of OSX, the process is not straightforward.

What didn't work:

Plugging the drive into a machine running Windows. The NVIDIA nForce drivers that my motherboard use prevent the tool from detecting the drives.
Plugging the drive in and booting into Linux (at least initially). The tool reports the drive as locked or frozen, and asks for a power cycle. Reboot and retry as one might, the message remains the same. Early investigations led me to believe this was due to an old BIOS.
Booting into an Ubuntu Live CD on a 2011 MacBook Pro and flashing from there. Most Live CDs can't even detect the DVD drive and boot. The ones that can don't detect either network interface, and Internet access is required by the tool.

The solution:

Use Linux, either a Live CD or a full installation. When the drive appears as locked/frozen, suspend the computer and wake it up again. Or even plug the drive in after booting up, although this seems marginally risky for drives that already contain data. Either of these should trick the drive into unfreezing (I only verified the first).

Simple, yet unintuitive.

Implementing a Lazy Loading Android Gallery with Mirah

2011-03-31T20:20:01.134-07:00

Image Galleries

The Gallery is a horizontal scrolling list commonly used for displaying a list of images. Unfortunately, the standard Android Developers Gallery tutorial focuses on displaying a small, static list of local images. An API-based list of remote images is much more useful, but more complex.

Laziness

Needing to fetch remote images is the cause of this complexity. A naïve approach might download all of the images sequentially, but that quickly becomes untenable as the number of images in question grows.

The correct solution will build up a cache of images locally, fetching them only as they need to be displayed. Images that have not yet loaded will be represented by a placeholder.

Mirah

I've grown quite fond of Mirah since I wrote my initial reactions about Mirah-Android development. Despite the bleeding edge kinks and snares, I find myself being much more productive than when using vanilla Java. Since the language is relatively new, I thought it could be useful to walk through some real-world code and demonstrate what it can do.

Designing a Lazy Gallery

We'll make three components:

An adapter to provide image/view information.
A selection listener to load images when they enter the visible window.
A mechanism for downloading the images in question and making them appear.

Implementation

This code is all available on Github; clone it and follow along:

git clone git://github.com/abscondment/lazy-gallery.git

LazyGalleryAdapter.mirah

Android's list-like views are backed by an Adapter, which provides a standard interface for creating or updating Views to represent list items.

This implementation accepts a JSON string and turns it into equivalent Java objects.

def update_from_json(json:String) begin data = JSONArray.new json data.length.times do |i| photo_json = data.getJSONObject(i) @photos.add {'caption' => photo_json.getString('caption'), 'src' => photo_json.getString('src')} end rescue JSONException => e Log.e 'LazyGalleryAdapter', 'Could not load JSON', e end notifyDataSetChanged() end

Using this list of caption/src pairs, it creates ImageViews for the gallery to display. It employs a common adapter optimization and re-uses a few existing views by updating them rather than repeatedly instantiating and discarding many objects.

def getView(pos:int, convertView:View, parent:ViewGroup) layout = RelativeLayout(convertView) image = LazyImageView(nil) url = String(Map(getItem pos).get('src')) if layout.nil? image = LazyImageView.new(@context, R.drawable.placeholder) image.setScaleType(ImageView.ScaleType.FIT_XY) image.setLayoutParams Gallery.LayoutParams.new(@oneeighty,@oneeighty) image.setBackgroundResource(R.drawable.gallery_background) image.setOnClickListener nil image.setClickable false layout = RelativeLayout.new @context layout.setLayoutParams Gallery.LayoutParams.new(@oneeighty,@oneeighty) layout.setGravity Gravity.CENTER layout.addView image else image = LazyImageView(layout.getChildAt 0) end # show changes image.setSrcUrl url image.refresh return View(layout) end

Note that we're not using a standard ImageView – it has extra methods (e.g. refresh), which we'll talk about below.

While I chose to build the layout by hand to demonstrate more, we could have eliminated some of the creation lines by inflating an XML resource:

GallerySelectionListener.mirah

This listener handles selection changes. It figures out which views are visible when a selection is made and initiates loading of the associated images. By using gallery.setCallbackDuringFling false when creating the gallery, we disable the selection listener during flings so that it only gets called when we actually want to load images.

def onItemSelected(parent:AdapterView, view:View, pos:int, id:long) unless @textView.nil? photo_map = Map(LazyGalleryAdapter(parent.getAdapter).getItem pos) if photo_map.containsKey('caption') @textView.setText String(photo_map.get('caption')) @textView.setVisibility View.VISIBLE else @textView.setVisibility View.INVISIBLE end end view.setSelected true # Preload children of the Gallery (i.e. those elements that are visible) unless parent.nil? parent.getChildCount.times do |i| v = RelativeLayout(parent.getChildAt(i)) LazyImageView(v.getChildAt 0).load unless v.nil? end end end

So, we use the LazyGalleryAdapter to get the caption/src map for our given position. We update the caption and show it.

Then we iterate over the parent's children – these are the visible children, mind you – and call load on the LazyImageViews that they house.

LazyImageView.mirah

The LazyImageView is an ImageView with plumbing for loading a remote image asynchronously (i.e. off the UI thread). It attempts to display an image that is already on disk, but defers fetching remote images until its load method is called.

def setSrcUrl(url:String):void @src_url = url @path = File.new(cache_dir, "" + @src_url.hashCode + ".jpg").getCanonicalPath end def load:void unless @loaded || @src_url.nil? || @path.nil? AsyncDownload.new(Handler.new(self), @src_url, @path) end end def refresh:void unless display_from_path() setImageResource @placeholder end end protected def display_from_path d = safe_image_to_drawable(@path, 180) unless d.nil? setImageDrawable(d) @loaded = true else @resizing = false @loaded = false end return @loaded end

LazyImageView also handles large images gracefully by asynchronously resizing them on disk with safe_image_to_drawable and AsyncResize; otherwise, we will get killed for using too much memory.

Finally, it can invalidate the disk-based cache of images based on image age.

def self.cache_dir(c:Context):File @cache_dir ||= File.new(c.getCacheDir, "lazy_image_cache") @cache_dir.mkdirs unless @cache_dir.exists @cache_dir end def self.purgeDiskCache(c:Context):void thread = Thread.new do # 8 hours oldest_acceptable = System.currentTimeMillis - long(28800000) d = LazyImageView.cache_dir(c) files = d.listFiles unless d.nil? unless files.nil? files.each do |f| begin # Skip nils, directories, and current files. next if f.nil? || (!f.isFile) || f.lastModified >= oldest_acceptable Log.v "LazyImageView", "D " + f.getCanonicalPath f.delete rescue IOException => e Log.e "LazyImageView", "purgeDiskCache: Error checking or deleting cache file:", e end end end end # Do this on a different thread LazyGalleryActivity.threadPoolExecutor.execute thread end

AsyncDownload.mirah

AsyncDownload is a fun little helper for downloading basically anything. It uses some java.util.concurrent goodies to ensure that a given URL is only fetched once for a destination path. Imagine the scenario where a user goes back and forth between two neighboring images before either loads – we don't want the two selection events to trigger double downloads of the images.

I won't post source here, but it's worth a read.

Working Together

Using these components is fairly straightforward:

gallery = Gallery(findViewById R.id.lazy_gallery) # Make sure the GallerySelectionListener is only # triggered when the gallery is stopped on an image. gallery.setCallbackDuringFling false # Create our adapter gallery_adapter = LazyGalleryAdapter.new self # When the current item is clicked, create a toast with its caption. this = self gallery.setOnItemClickListener do |parent, view, pos, id| if view.isSelected item = Map(gallery_adapter.getItem pos) c = String(item.get 'caption') || "Item #{pos} (no caption)" Toast.makeText(this, c, Toast.LENGTH_SHORT).show end end # Add the adapter and the selection listener gallery.setAdapter gallery_adapter gallery.setOnItemSelectedListener GallerySelectionListener.new(TextView(findViewById R.id.lazy_gallery_text)) # Expire any old cached images LazyImageView.purgeDiskCache(self) # And finally, send the adapter its data. # A real application will likely abstract away the JSON string details. gallery_adapter.update_from_json json_string

Try it out

The full source is available on Github as a working application. Try it out!

https://github.com/abscondment/lazy-gallery

Using memcached -k to prevent paging

2011-02-27T23:51:12.214-08:00

Memcached is a powerful brute. Since it's basically just a giant in-memory hash map, you can safely run it on just about any machine that has spare memory. But be sure to know the sort of memory profile your machine has.

If something causes memcached to go to swap, performance degrades significantly. Paging can block all queries to the given server, which can in turn block all rendering for every page of your site. The performance degradation I observed was on the order of 30+ seconds, so this is enough for any number of layers in your application stack to time out inscrutably.

Fortunately, memcached provides the -k switch to indicate that its memory should be locked from paging. You'll wind up running like this:

brendan@ishmael:~$ sudo memcached -m 1024 -p 11211 -u memcache -l 127.0.0.1 -k
warning: -k invalid, mlockall() failed: Cannot allocate memory

Oh, wait. Cannot allocate memory?

brendan@ishmael:~$ ulimit -l
64

Ah, I see. We're limited to 64k of locked memory by default. Fortunately, this can be changed with per-user granularity by adding some lines to /etc/security/limits.conf:

root            -       memlock         1048576

That takes the root user's limit up quite a bit. The memcached help output indicates that you should up the limit for the user that launches the program, not for the user that memcached eventually runs under.

Of course, even better than all this would be organizing the system architecture in such a way that the memcached machine never needs to swap.

Benchmarking Ruby Enterprise Edition

2011-01-31T11:42:47.000-08:00

As part of a perpetual quest to make things run faster, I benchmarked various Ruby configurations using the Urbanspoon codebase. We have a smoke test that hits our key pages regularly to ensure things are running well, and I decided to use this for speed comparison as well. My methodology was simple.

Run a local staging server with MySQL & memcache. Run smoke against it a lot to get the caches really hot – we want to test the variations in Ruby, not in other layers.
For each test configuration, start Unicorn and run smoke against that server 10 times ^[1]. This basically tests how quickly Rails can load a few simple objects from the database and squish them together with a pre-rendered page from memcache.
Repeat #2, but clear out memcache^[2] before the start of each run of the smoke test. This tests a lot more of the application's internals, since it makes each test run rebuild the important pages and repopulate memcache. The MySQL cache stays hot throughout both tests and it's not anywhere near breaking a sweat.
Now that we have 2 views of speed recorded 10 times each for all of the configurations, we can crunch some numbers. Throw out the best and worst times, take the average, and learn.

I benchmarked four REE configs, and I used the standard MRI 1.8.7 version as a baseline. The results were gratifying.

Five Pairs of Ruby Benchmarks

Configuration	Cache hot		Cache cold
MRI 1.8.7	10.526875	0.0%	33.77225	0.0%
REE (default)	7.90675	-24.89%	25.43275	-24.69%
REE (tuned GC^[3])	6.972	-33.76%	22.948875	-32.05%
REE (copy-on-write^[4])	9.0375	-14.14%	26.539625	-21.41%
REE (tuned GC, copy-on-write)	7.117625	-32.4%	23.1595	-31.4%

Figures shown are total seconds elapsed and difference relative to MRI 1.8.7

Hey, cool! There's some validation, all right. Garbage collection has a huge impact on the performance of web applications, and proper tuning can mean a world of difference. REE does better out of the box, and really flies with a little tuning. Copy-on-write, which reduces overall memory usage, definitely has some performance penalties. But when GC flags are set it really doesn't degrade things much at all. This could be a huge win.

I'd love to test some other implementations when I get the time, but for now we're going to slowly migrate things to REE.

^[1] I did that with for s in {1..10}; do (time ../bin/smoke) 2>&1 | grep '^real'; done | cut -f 2
^[2] echo -ne 'flush_all\r\nquit\r\n' | nc localhost 11211 will do the trick.
^[3] I used some settings attributed to Twitter.
^[4] This is supposed to reduce a Rails application's memory footprint by 33%. It's obviously a little slower, but appears to be well worth it.

Experimenting with Mirah for Android

2011-01-21T09:42:06.000-08:00

A while ago I wrote about Closures in Duby. Duby is now called Mirah, and it's a promising way to write compiled code without the weight of Java syntax. I've been updating Urbanspoon's Android application, and I decided to use Mirah for portions our next release.

Getting started

Mirah is available as a JRuby gem. Hopefully you use RVM to manage your Rubies, because chances are good that you'll want to switch between them for various purposes.

Here's an install script that will probably be obsolete the second I finish writing it. Enjoy.

Installing mirah

$ rvm jruby
$ gem install mirah

miranhdroid - optional install for new project creation

$ rvm jruby
$ cd ~/code && git clone https://github.com/jackowayed/mirahndroid.git
$ cd mirahndroid && rake gem
$ gem install pkg/mirahndroid-*.gem
$ cd ..
$ mirahndroid create -a NewProjectActivity -n NewProject -p new-project -k com.urbanspoon -t android-9

Welcome to the Wild West

Now you can write Rubylike code that compiles to Java. Cool. There's really nothing different about Android development, but it does showcase Mirah's raison d'être. Alternate JVM languages that require a runtime are often too slow for writing real, interactive mobile applications. Compiled code is a must, and Mirah provides just that. But there are quite a few gotchas...

Not quite Ruby, not quite Java

There are a handful of things from both of these worlds that are missing or different. Familiarize yourself with that list; it'll come in handy.

Mixed-language Source is Hard

Urbanspoon's application has a significant chunk of existing Java. It'd be a waste to rewrite it, since it already works well.

Building a project with mixed source is complicated. The current mirahc can't do anything with .java sources — it infers types from classfiles and can't resolve them from the sources. So if you have an existing class that you want to reference from Mirah, you need to be able to compile it before you compile the Mirah code. Your Java code is conceptually just another .jar for the Mirah code to use.

This places an unfortunate constraint on your application, however: your Java code can never explicitly refer to classes defined in Mirah. That'd result in a circular dependency.

Ideally, mirahc would be able to infer types from both .class and .java files. Then the build process would be easy: mirahc -j to output .java into the gen folder, and javac to compile everything at once. But I think this would require a rudimentary Java parser, and the "Java code can't see Mirah classes" constraint seems easier.

Rough build tools

Android gives you a stock build.xml, but it'll need customization. The mirahndroid project will give you an Ant task like this:

<target name="compile" depends="-resource-src, -aidl"
        description="Compiles project's .mirah files into .class files">
  <exec executable="mirahc" dir="src">
    <arg line="-c ${sdk.dir}/platforms/${target-version}/android.jar:gen/" />
    <arg value="-d" />
    <arg value="../bin/classes/" />
    <arg value="." />
  </exec>
</target>

That's a fine start, but you'll need to customize it to compile the generated R.java class if you want to access your application's resources. To make my mixed Java/Mirah project work, I copied the "compile" task from tools/ant/build.xml in the Android SDK and inserted the mirahc exec call at the end.

Return types in if statements

Update – this has been fixed in commit 7fa9c6294695a391dccd

We're creating statically typed code. Mirah has some cool type inferencing going on, but your variables are typed nevertheless. Even things like if statements have return values, and you need to make sure they match up. You'll probably just start littering 'nil' around at the end of each branch:

if owed > 100
  message = "You owe a lot of money."
  owed += 1
  nil
else
  message = "All paid!"
  nil
end

Nested interfaces

You can't easily implement a nested interface. For example, Android's GpsStatus.Listener — see this thread.

Odd scoping

The block syntax is cool, but scoping of self and instance variables is incomplete.

this = self
grid.setOnItemClickListener do |parent, view, position, id|
  this.launch(int(id))
end

It's super easy to add anonymous listeners with this syntax. But you need to make sure to create local variables to point to the values you'd like to acces inside the block. Inside "self", for example, refers to that anonymous class (you did read about the cool blocks implementation, right? Likewise, instance variables don't exist inside the block. You need to pull them into the scope surrounding the block to access them inside the block.

Bleeding Edge

Some of the problems I encountered were resolved by using a development snapshot of the Mirah gem. If the idea of using bleeding edge technology in a production application makes your blood pressure rise, this might not be for you... yet. As it matures, Mirah will be a more and more attractive alternative to java. I, for one, enjoy running off of unstable branches.

Migrating salted md5sums to Bcrypt

2010-12-16T21:32:45.000-08:00

In light of recent events, I thought it prudent to change our password storage to use bcrypt hashes. Salting md5sums isn't the worst thing you could do, but it's really not as great as it might seem at first blush. Salted md5s are the leather jacket of bullet-stopping apparel: demonstrably stronger than your plaintext cotton T-shirt, but nevertheless insufficient for the task at hand.

Converting a production system to use bcrypt requires a few steps and some sleight of hand. We can't encrypt the plain passwords because we no longer have access to them. Instead, we could use the md5 with salt as a first pass and apply bcrypt to that value.

The process goes like so:

Add a new column to store the bcrypt hash.
Deploy code that saves all of the md5sum, salt, and bcrypt hash when setting the password.
Run a job that populates rows with an md5sum but no bcrypt hash. You'll hash the existing md5. You'll need to ensure a given md5 hasn't been changed since you read it out of the database.
Deploy code that authenticates using the bcrypt hash. You'll check the bcrypt hash against md5sum(plaintext + salt).
Once you're sure your bcrypt setup is working, deploy code to stop saving the md5sum. You can either stop using a salt for updated passwords or use a salt and store it. There's probably some deep cryptographic implication embedded in that decision, but analyzing it is beyond me. This step is the point of no return. Once your md5 column gets stale, you can't authenticate using it.
Drop the md5 column. Keep the salt, since you'll need it for authentication.

That wasn't so bad, was it? Step 3 even gave you a little first-hand demonstration of one chief bcrypt feature: it takes a long time to generate all of those hashes. No one will be brute-forcing your user base any time soon. Just don't forget to properly secure your old backups... which you have, right?

A simple redirect resolver

2010-12-15T20:53:07.000-08:00

Did you know that curl has an option to automatically follow HTTP redirects? Combined with the HEAD method, this can be used to quickly trace the end destination in a chain of redirecting URLs:

#!/bin/sh
(echo $1 && curl -LIs "$1" | grep '^Location' | cut -d' ' -f2) | cat -n

The meat of the work is in the curl options:

-L: if redirected, issue an identical request to the new location.
-I: issues a HEAD command, which allows the server to omit the body.
-s: no progress bar of failure indication

The subsequent grep/cut/cat combo serve to dice up the headers that are sent back and turn them into a pretty list of redirect locations.

Stirling's approximation in Clojure

2010-11-24T23:12:38.000-08:00

In my free time, I've been working through Probability Theory: A Concise Course by Y.A. Rozanov. The first chapter contains a great factorial approximation that anyone doing computer-based statistics or combinatorics ought to know:

This is Stirling's Approximation. As n grows, the relative error of this function compared to n! gets smaller and smaller. More formally, the ∼ symbol expresses asypmtotic equivalence, meaning that when A(n) ∼ B(n),

I was curious about the actual behavior of this formula, so I decided to plot the expected convergence. To do this, I wrote up simple Clojure versions of both functions and charted the expected convergence using Incanter.

(use '(incanter core charts io latex)) (defn stirling [#^Integer n] (* (Math/sqrt (* 2 n Math/PI)) (Math/pow n n) (Math/pow Math/E (* -1 n)))) (defn fact [#^Integer n] (reduce * (range 2 (inc n)))) (let [n-vals (range 5 1000)] (view (xy-plot n-vals (map #(- (/ (fact %) (stirling %)) 1.0) n-vals) :x-label "n" :y-label "factorial(n)/stirling(n) - 1")))

The graph produced by this doesn't exactly pass muster.

We've been bit by one of the classic problems of numerical computing: the way that a number is represented internally limits what can be done with it. In our case, we've exceeded the range of values that a Java Double can handle. It has 8 bytes split into a 52-bit mantissa, an 11-bit exponent, and a single sign bit (in detail). The max value it can hold is 1.7976931348623157×10³⁰⁸. Once we exceed that value, everything is simply "Infinity".

user> (fact 200) 788657867364790503552363213932185062295135977687173263294742533244359449963403342920304284011984623904177212138919638830257642790242637105061926624952829931113462857270763317237396988943922445621451664240254033291864131227428294853277524242407573903240321257405579568660226031904170324062351700858796178922222789623703897374720000000000000000000000000000000000000000000000000 user> (class (fact 200)) java.math.BigInteger user> (stirling 200) Infinity user> (class (stirling 200)) java.lang.Double

Clojure magically moves from Integer arithmetic to BigInteger arithmetic when we overstep the Integer upper bound of 2³¹-1. But we get no such love from the functions in java.lang.Math.*, which quickly (at n=144) overflow to Infinity.

Now, the entire point of this function is to have a fast approximation of the factorial for large n, so this is an issue that we need to overcome. The naïve version is actually completely useless, since it only functions for small n.

So let's fix it.

We need to convert our function to use an arbitrary precision decimal type. As far as I can tell, Math.PI only comes in double precision. We'd need to have an n of, oh, 9,223,372,036,854,775,807 before we exceeded the Double range and needed to change the way we compute first expression. I don't think anyone is actually going to seriously try doing factorials that large, but if you are, you can make use of this free BigSquareRoot class that uses BigDecimals.

For my purposes, only the exponentiation, division, and multiplication in the second expression need to be converted. Java has a handy BigDecimal class that fits the arbitrary-precision bill:

(defn stirling-big [#^Integer n] (.multiply (BigDecimal. (Math/sqrt (* 2 Math/PI n))) (.pow (.divide (BigDecimal. n) (BigDecimal. Math/E) java.math.MathContext/DECIMAL128) n java.math.MathContext/DECIMAL128)))

We also need to use BigDecimal division in the comparison function, but I'll leave that as an exercise for the reader. The outcome is quite pleasing from the numerical error standpoint:

You can see that as n gets larger, the ratio of the functions asymptotically approaches 1. The relative error of Stirling's approximation shrinks with larger n, which is great for most applications. The absolute error grows, but the rate at which it grows is smaller than the rate at which the actual value grows.

And the performance is great, too! Check out the differences:

The raw factorial function is superior for small n, which is to be expected. The factorial function has noticeable performance perturbations in the local view, but these mostly disappear in the full view. The factorial function seems to perform in quadratic time relative to n, while Stirling's formula has a very low constant cost.

So remember Stirling's formula if you find yourself computing large factorials.

Updated 2010-11-25 07:48 to clarify relative error versus actual value. Thanks to David Karapetyan for pointing out the discrepency.

Facebook Connect, IE, and the Mysterious IFrame

2010-11-16T22:36:45.000-08:00

The Facebook Connect JavaScript does some really neat things to function the way it does, but one of its behaviors is unexpected and downright buggy. When attempting to establish a cross-domain communication channel in Internet Explorer (IE8, at least – perhaps not the others), it loads a duplicate copy of the current page in an IFrame. That's right – IE8 users attempt to make two hits to the same page for a single view.

A tale of broken CAPTCHAs

This behaviour is entirely undocumented. I mean, go ahead – check the Javascript SDK – you won't find any mention of it. It's a really bad behavior, too. If you have Facebook Connect (or a Like button, for that matter) on any page that has some transient state (say, a CAPTCHA that gets invalidated and regenerated every time the page loads), loading the page a second time can invalidate the version that the user actually interacts with.

This was the case for our production user registration flow for a long time. The first hit displayed an image for one CAPTCHA, and the second hit surreptitiously invalidated it so that there was no possible way the user could solve the CAPTCHA. Thanks, guys.

The reason for this double hit is straightforward. The same-origin policy restricts how scripts can communicate with different domains. For the most part, interesting interactions are restricted. The whole idea of Facebook Connect is predicated on the idea that their JavaScript will run on your site and provide you with functionality from a different domain, so they had to find a way to bypass the restrictions. There are, quite naturally, some tricky ways to make things work using IFrames. But following the ever-present JavaScript mantra, Not All Browsers Will Behave the Same Way. I actually doubt whether browsers behave at all, ever.

It seems that Facebook's engineers found IE8 wouldn't do their bidding unless the communication channel IFrame was hosted on the same domain as the main site. Oh, and that IFrame needs to run their JavaScript, too. So what better way to ensure this than, uh, reload the current page (which we know has the Connect JavaScript) in a hidden IFrame. No site is going to care if they rack up double hits from a large percentage of their user base, right? As they helpfully append fb_xd_fragment as a query parameter, you can just make a special case short-circuit in your routing based on that. Right? Right?

A solution emerges

Remember how I linked to those oh-so-helpful JavaScript SDK docs that had nothing whatsoever to say about this problem? They are (shock of all shocks) incomplete. Littered all over the Internet, you'll find references to a mythical Cross Domain Communication Channel file that solves this problem. Stale versions of Facebook's own documentation and connect-js Github page hint at it, although the current versions of both are devoid of references.

The channel file is a static chunk of HTML hosted on your domain that does nothing but load the Facebook Connect JavaScript. Through a now-undocumented configuration parameter, you can tell the Connect JavaScript on your site to load that file in the IFrame instead of loading a copy of your current page. Problem solved!

Why wouldn't Facebook document this? Oh, wait – they did... sort of. It's listed as part of the old JavaScript API. Oh, but wait. Apparently the API has changed a little, and xdChannelUrl should just be channelUrl. They're close enough, right? That's like, hardly worth mentioning. Or documenting.

Update 2010-11-26 09:05: It appears this is documented, or at least it is now. Peperone23 points out the FB.init documentation.

So now you do something like this:

FB.init({
          apiKey: 'OMGWTFBBQ',
          status: true,
          cookie: true,
          xfbml: true,
          channelUrl: window.location.protocol + '//example.com/xd_receiver.html'
        });

And in xd_receiver.html, you do this:

<!DOCTYPE html> 
<html><head><title></title></head><body><script src="//connect.facebook.net/en_US/all.js"></script></body></html>

Voilà! Facebook can use this static, lightweight, stateless page to achieve their ends instead of loading the current page a second time. Set some way-in-the-future cache headers on that sucker and call it good.

Rails 2 Upgrade Turbulence: a Series

2010-10-21T07:39:56.700-07:00

Here are several posts on Rails 2 upgrade issues that I encountered at Urbanspoon:

I've found it common for startups to get stuck on old versions of Rails because the incremental upgrade task is always lower priority than feature work (rightfully so). As time progresses, the task becomes more and more daunting. I bit the bullet and upgraded our site.

Considering that Rails 3 is out now, we're still a touch behind the times. That said, there are still interesting things one could learn from the process of taking a real site (that serves quite a bit of traffic) from Rails 1.1.6 to 2.3.10.

Troubleshooting a Slow Production Deployment

2010-10-21T06:55:09.000-07:00

This is part of a series on Rails 2 Upgrade Turbulence.

Staging and testing a big release is important, but there are some factors that can only be obsereved in the true production environment. Sure, I can replay the most interesting 80% of a yesterday's traffic against a test server without it failing – but I'm only one user making sequential requests. This completely dodges the question of how the new code will work at scale.

The ActiveRecord changes around association loading in Rails 2 made me particularly curious about the production behavior of Urbanspoon. We had recently added two identical servers to our production rotation, so I took over one and did a test deploy of the Rails 2 branch.

Initial traffic (balanced to about 3% of our load) looked good – snappy response times and no exceptions. But when I bumped it up to take a full share, performance was substandard. The Rails 2 server was running at nearly twice the load of its counterpart, and was taking on average twice as much time to serve requests. Yech. We loaded up Rails 1, and performance improved... although this test server was still slower than the control. What a quandary.

Monitoring works.

Since we run munin, we have easy access to historical performance. My debugging tools/steps were:

top - get a quick, side-by-side eyeball of CPU, load, iowait, memory usage.
munin
- Rails times: total, views, db
  - total time and db time in Rails 2 was twice that in Rails 1
  - Raised the question of whether these are even comparable across different major Rails revisions.
- Load/Memory graphs – same story as top.
- Interrupt graphs
  - Wow – lots of "Rescheduling interrupts" on the slow server.
cat /proc/cpuinfo, /proc/meminfo, /proc/interrupts, /proc/ioports (AHCI on one, but not the other?), ifconfig, etc.
- Are these machines actually the same? Lots of subtle differences.

These were all useful, but they didn't give me a definitive answer. The machines looked different, but the old code ran significantly faster than the new code. Yet all reports easily reached by Google lead me to believe Rails 2 might even give us a speed boost. So was it really slower, was there a hardware issue, or what?

Debugging works.

At this point, I switched into the :debug log-level to see if I could spot any subtle issues. Was ActiveRecord sending a flood of extra association loads that we should force into a join? Was memcache getting hit at all? Were our DB times slow due to bad network performance?

Very quickly, I noticed something suspicious: our memcache keys looked like absolute urls. Ah, great. Looks like we were being bit yet again by the new Rails 2 named routes – nameley, that *_url routes now produce an absoluter URL instead of a relative one. In addition to this, Rails 2 changed the fragment_cache_key method to include a prefix – so no matter what, fragment caching in Rails 2 would have totally new keys.

So on our most popular pages, we were using a completely different keyspace. All of the Rails 1 servers were using an identical keyspace, and the one Rails 2 was in its own. This memcache filled quickly, but the new server's keys got ejected at a much higher rate. Its cache misses were through the roof, and therefore so were its load and response times (although, isn't it nice when averaging a 120ms response time is "through the roof"?).

Neat. But fixing the keys didn't bring performance up to par with the other server. We noticed two things:

Those pesky "Rescheduling interrupts" were still there – at three orders of maginitude more per second from the slow server to the other.
AHCI was disabled on the slow server.

Even after enabling AHCI and doing an OS reload, the "identical" servers were none too identical. So we took a leap of faith and deployed Rails 2 to the other, faster one, and performance was as expected. We're still working with our hosting company to figure out what's wrong with the slow machine.

git-svn workflow warts

2010-10-21T06:23:23.000-07:00

This is part of a series on Rails 2 Upgrade Turbulence.

Now that I had confidence that the code was production-ready, it was time to merge changes back into trunk. We still have a main SVN repository, although most people use the git-svn bridge. This proved problematic in three ways which have nothing to do with Rails whatsoever, but could prove useful to know about.

git-svn rebase problems

I use a git-svn repository where the master branch tracks the trunk of SVN. I branched from master to create the dev_rails2 topic branch. This follows the canonical example:

          A---B---C dev_rails2
         /
    D---E---F---G master

I also pushed master and dev_rails2 to a remote Git repository. A few co-workers and I worked in the dev_rails2 branch and checked in to the remote repository, and I pulled all changes back into my local branch.

To prevent the gigantic merge that the Rails 2 upgrade would create, I pulled trunk into the topic branch weekly. This involved:

git checkout master
git svn rebase
git checkout dev_rails2
git merge master
(resolve conflicts)

If you do things this way, you have to use a more obscure git-svn command to commit your changes – dcommit won't work. Can you spot the reason from looking at my workflow? No? Well, don't feel too bad; I didn't anticipate the problem either.

If you merge master into dev_rails2 as I did, you will eventually want to merge dev_rails2 back into master to commit. This can happen with no conflicts if you resolved everything in master –> dev_rails2 merges already.

So I'd do this:

git checkout master
git svn rebase
git merge dev_rails2 (succeeded)

But then in order for git svn dcommit to work, I'd need to do this:

git svn rebase (failed spectacularly)
git svn dcommit (doesn't work without the prior succeeding)

The last step will rewind all of your merged changesets (which now include some of the existing commits in Subversion) and apply them to the current state of subversion. This generates conflicts because it's attempting to diff the already resolved state against Subversion, and the resolution often would not apply cleanly.

The correct solution is:

git svn set-tree [first-hash]..[last-hash]

To QTFM:

You should consider using dcommit instead of this command. Commit
specified commit or tree objects to SVN. This relies on your imported
fetch data being up-to-date. This makes absolutely no attempts to do
patching when committing to SVN, it simply overwrites files with those
specified in the tree or commit. All merging is assumed to have taken
place independently of git svn functions.

Huh? set-tree? Yeah, I'd never heard of it either. And I fixed my problem before I learned about it. In order to save revision history, I decided to re-resolve all of the conflicts (sometimes badly, since there were too many commits to remember every bit of minutiae) and fix the bad commits later. This meant I'd have the following:

Changes made in master (and therefore Subversion) that I wanted to keep.
Changes made in dev_rails2 that I wanted to keep, but that also contained random, badly-resolved conflicts.
Changes to fix the bad resolutions.

Because the dev_rails2 branch was in a good (i.e. a correctly merged view of the final product that I wanted to commit) state, I managed to get #3 by making a separate clone of it and copying files into the checkout in which I had run (and resolved) git svn rebase. This allowed me to preserve ~130 commit comments worth of Rails 2 upgrade knowledge. But man, I wish I had known about set-tree beforehand.

git-svn dcommit problems

After finally merging in dev_rails2 and getting a clean git svn rebase, I was ready to commit. Not so fast – git svn dcommit failed rather quickly:

[hash] doesn't exist in the repository at /usr/lib/git-core/git-svn [...]
Failed to read object [hash] at /usr/lib/git-core/git-svn line [...]

Who knows what set-tree would have done here. Two of my changes had made it into Subversion, but the process halted on the commit in which I had copied the new mysql_replication_adapter plugin into vendor/plugins. After Googling around, I discovered this great post about submodules causing this of failure.

Although I didn't have a git submodule, the basic issue turns out to be the same. Something in my commit (I believe it was an empty directory) appeared differently in the subversion changeset. When git-svn attempted to map this back to the git objects it knew about, a mismatch occurred. The object existed in one repository but not the other, so the system (wisely) errored out.

Unfortunately, fixing this was not as simple as deleting the bad directory in HEAD. git-svn has to commit your work sequentially, so I needed to rewrite history.

$ git tag broken [hash that failed to commit]
$ git checkout broken
$ # remove the directory, re-add with correct name, cross fingers
$ git commit --amend
$ git rebase --onto HEAD broken master

After rewriting the svn-incompatible changes, git svn dcommit worked! But of course there was one more issue.

.svn directories in the tree

I had to update quite a few plugins, and I did this by checking out the source code and copying it into place in vendor/plugins. This was a short-sighted way of doing things, but using git-svn puts one in the unenviable position of being able to use neither git submodules nor svn:externals. Unfortunately, git-svn is more than happy to let you check full copies of Subversion repositories into your own Subversion repository. Mind blowing, no?

The affect of this is that when you svn up, Subversion fails to update because it can't actually add the .svn directories that are in the source tree – it'd overwrite the ones that it truly needs! Also unfortunate is that you can't delete them locally because a) they don't exist yet and b) even if they did, the svn client helpfully ignores any attempts to operate on files named .svn. So this is broken and will fail:

svn del -m 'Delete .svn checkin' path/to/bad/.svn

Instead, one must delete the checked-in .svn directory on the remote server:

svn del -m 'Delete .svn checkin' svn+ssh://svn-server/trunk/path/to/bad/.svn

Whew!

ActiveRecord woes

2010-10-21T06:02:13.000-07:00

This is part of a series on Rails 2 Upgrade Turbulence.

ActiveRecord associations have changed. There are some gotchas, at least compared to the Rails 1.1.6 frame of mind.

Join v. Queries

Instead of forcing a join against the tables for every incuded association, ActiveRecord is now smart enough to split things into separate, on-index loads of each model. It then slaps the correct assocations back together. If separate loading is not possible, it can fall back on the join model.

Broken SQL

The nature of programmatically generating SQL is that, well, things break. Specifically, if you find with both :include and :joins statements, you'll be in for a rude awakening. Whether single or multiple, every query will include the specified :joins. If your application expected a single, joined query (as with Rails 1.x), and you now get multiple, this will break.

You can also use :include and have :conditions or :order statements with unqualified column names. These also get applied to each of the queries, but since the columns don't exist in every table we're querying, things break. If you qualify the column names, ActiveRecord is smart enough to perform the join for you instead of executing separate queries.

Associations

As I hinted in code when writing about Bulk-loading associations with ActiveRecord, you need to be careful when using normal Array operators on collection-like associations. You can easily add to an association without expecting an insert.

E.g., Restaurant.find(:first).cuisines << Cuisine.find(:first) now generates an insert statement that establishes that relation instead of simply pushing the Cuisine object into an array.

To manipulate the collection directly without doing anything in the database, you must use association.target:

Restaurant.find(:first).cuisines.target << Cuisine.find(:first)

Disabling Sessions

2010-10-21T05:45:55.000-07:00

This is part of a series on Rails 2 Upgrade Turbulence.

Urbanspoon uses sessions to store various bits of information in the database that users might want to see again. We have a neat hack that Adam wrote to turn off sessions for bots so that we don't need to touch that table unless necessary.

Unfortunately, his trick depends on the Rails 1.x ability to toggle sessions progammatically. Rails 2 opted for lazy loading – if you don't access it, it never gets loaded. There is, in fact, no out-of-the-box way to disable the session progammatically at request time.

The trick I used to make this work is simple: choose the session store for a given request in a before_filter. I made a simple session that dumps all its data into a Hash, but never persists anything.

# NoSession acts like a session, but doesn't get stored anywhere. Sneaky. class NoSession < AbstractSession class << self def find_session(session_id); end def create_session(session_id, data={}) new(session_id, data) end def delete_all(condition=nil); end end def update_session(data); end def destroy; end end

I then created a subclass of our session store (SqlSessionStore, in our case) that has a class-level toggle ("disabled") which it uses to choose the backing session class when it is called.

class OptionalSessionStore < SqlSessionStore cattr_accessor :enabled_session_class cattr_accessor :disabled class << self def disabled=(v) if self.disabled != v @@disabled = v self.toggle_session_class end end def toggle_session_class if self.disabled SqlSessionStore.session_class = NoSession else SqlSessionStore.session_class = self.enabled_session_class end end end def call(env) # Make sure our disabled state is current self.class.toggle_session_class super(env) end end

I now use a before filter to enable or disable sessions even for code paths that attempt to access them.

before_filter :toggle_session def toggle_session # Disable the session if we spy a bot (or it was disabled elsewhere), enable otherwise. if @disable_session.nil? @disable_session = UrbanspoonUtil.is_megatron?(request.user_agent) end OptionalSessionStore.disabled = @disable_session end

General Cleanup

2010-10-21T05:31:37.000-07:00

This is part of a series on Rails 2 Upgrade Turbulence.

Some generic cleanup tasks:

@request/@params/etc are deprecated, drop the '@' everywhere.
application.rb becomes application_controller.rb
start_form_tag and end_form_tag are deprecated; use form_for instead.
ActiveRecord associations have changed.
Named routing has changed. Previously, every route created a method of the form 'some_page_url', which generated a relative path to the related url. Now, both 'some_page_url' and 'some_page_path' are generated. The _url method now gives an absolute url, while _path is relative.
Most gems/plugins need to be upgraded or replaced. Yay for more current versions!

I found these Rails 2 Upgrade Notes to be pretty helpful.

Also, there's nothing like a little grep/cut/sed to make short work of replacing en masse:

Bulk-loading associations with ActiveRecord

2010-09-13T10:55:22.000-07:00

Here's a fairly common problem I've encountered. Say you have two classes; for example, a Restaurant and a Cuisine. They exist in a many-to-many relationship, and have associations defined like so:

class Restaurant < ActiveRecord::Base has_many :restaurant_cuisines, :dependent => :delete_all has_many :cuisines, :through => :restaurant_cuisines end class Cuisine < ActiveRecord::Base has_many :restaurant_cuisines, :dependent => :delete_all has_many :restaurants, :through => :restaurant_cuisines end class RestaurantCuisine < ActiveRecord::Base belongs_to :restaurant belongs_to :cuisine end

This is basically the model we use at Urbanspoon.

Now, there are two interesting aspects to the data we have in this relationship. First, Urbanspoon know about approximately 40x more Restaurants than Cuisines. Second, Cuisine popularity follows a Zipf distribution. That is, the vast majority of Cuisines are associated with very few Restaurants. However, the converse is not true: we enforce that there be ~3 cuisines associated with every Restaurant in the system.

So, it turns out that the top 1000 Restaurants in Seattle comprise about 70 distinct cuisines. That fits well with our graph from above, and provides a good premise for this issue. Let's say we load these 1000 Restaurants and we'd like to display the Cuisines associated with all of them. What's the best way to do this?

Naïve Attempt

10.times do r = Restaurant.find(:all, :conditions => ['id IN (?)', ids]) r.map(&:cuisines).flatten.map(&:id) end # benchmarked 10 times user system total real 10.170000 0.470000 10.640000 ( 11.809886) 9.630000 0.410000 10.040000 ( 11.076710) 11.220000 0.520000 11.740000 ( 12.819519) 11.140000 0.530000 11.670000 ( 12.702499) 10.040000 0.520000 10.560000 ( 11.654553) 10.680000 0.470000 11.150000 ( 12.250775) 10.050000 0.700000 10.750000 ( 11.763682) 11.020000 0.480000 11.500000 ( 12.893516) 10.410000 0.590000 11.000000 ( 12.181406) 11.460000 0.740000 12.200000 ( 13.326383) # memory diff from baseline IRB for each run [1] 8712, 15000, 15092, 15204, 15260, 15324, 15360, 15392, 15424, 15428

This takes an average of ~12.25 seconds to complete with a hot query cache. True to intuition, naïve loading of associations is dog slow in this scenario. We're duplicating work left and right, both in database loading and in ActiveRecord instantiation. If one Cuisine is referenced by N Restaurants, we pull it from the database N times and create N objects with identical information.

Improved Attempt

10.times do r = Restaurant.find(:all, :include => [:cuisines], :conditions => ['id IN (?)', ids]) r.map(&:cuisines).flatten.map(&:id) end # benchmarked 10 times user system total real 5.540000 0.010000 5.550000 ( 5.553716) 5.560000 0.000000 5.560000 ( 5.566566) 5.670000 0.010000 5.680000 ( 5.687871) 5.670000 0.000000 5.670000 ( 5.674870) 5.580000 0.000000 5.580000 ( 5.581576) 5.670000 0.000000 5.670000 ( 5.678692) 5.570000 0.000000 5.570000 ( 5.578353) 5.630000 0.000000 5.630000 ( 5.629657) 5.740000 0.000000 5.740000 ( 5.745029) 5.560000 0.000000 5.560000 ( 5.568952) # memory diff from baseline IRB for each run [1] 8896, 14608, 14800, 14932, 15024, 15152, 15248, 15300, 15300, 15300

Great! We achieved an average speed of almost exactly twice as fast (~5.63 seconds) by using ActiveRecord's built-in association loading. But there are two problems with this approach. Firstly, it's not very flexible or composable. That is, you can't build a handful of specialized Restaurant-finding functions that are agnostic about the decision to load Cuisines or not. You can't cache a list of Restaurants and load the Cuisines later. Basically, if you want to be efficient, you have to do the Cuisine loading at query time.

The second issue is still one of performance. Even though we only load 73 Cuisine rows from the database, ActiveRecord still allocates over 2000 unique Cuisine objects. See?

Oy. That means we're consuming roughly 27.4 times the memory and clock cycles required to instantiate and retain Cuisines. So, what's the really right way to do this?

Bulk Loading, For Real

The pattern I've used is pretty simple. You query the two associations separately, and then use an id-to-record map to squash them back together in code. I did this in a few places in the iLike codebase, and I found this example waiting for me at Urbanspoon. This final version combines and improves on my previous attempts, and I have a few comments to share about it later. But first, the code!

def Restaurant.add_cuisines(restaurants) return [] if restaurants.empty? ids = [] id_map = {} restaurants.each do |r| id_map[r[:id]] = r ids << r[:id] # make sure ActiveRecord won't try to load cuisines again r.cuisines.loaded end # make sure we load each Cuisine once cuisine_map = Hash.new {|h,id| h[id] = Cuisine.find(id)} RestaurantCuisine.find(:all, :conditions => ["restaurant_id in (?)", ids]).each do |row| # use the association target so we don't do an insert id_map[row[:restaurant_id]].cuisines.target << cuisine_map[row[:cuisine_id]] end return restaurants end

OK, that seems reasonable enough. What are the times like?

10.times do r = Restaurant.find(:all, :conditions => ['id IN (?)', ids]) Restaurant.add_cuisines(r) r.map(&:cuisines).flatten.map(&:id) end # benchmarked 10 times user system total real 3.070000 0.040000 3.110000 ( 3.148139) 3.040000 0.030000 3.070000 ( 3.133394) 3.060000 0.050000 3.110000 ( 3.160772) 3.050000 0.040000 3.090000 ( 3.178049) 3.100000 0.010000 3.110000 ( 3.169859) 3.070000 0.030000 3.100000 ( 3.174384) 3.120000 0.040000 3.160000 ( 3.259299) 3.120000 0.030000 3.150000 ( 3.238029) 3.100000 0.040000 3.140000 ( 3.241258) 3.060000 0.030000 3.090000 ( 3.135886) # memory diff from baseline IRB for each run [1] 4388, 10112, 10180, 10252, 10316, 10364, 10408, 10496, 10540, 10472

Wow, an average of 3.18s! That's significantly faster than the association loading version. And it uses far less memory, too. In fact, that's the reason it's so much faster – you can shave off 43.5% of the total time just by instantiating each database row only once. This is a total time reduction of 74% over the naïve method.

Additionally, this function can be called as an afterthought. You can compose various functions and have them still perform well. You can load Restaurants from any cache or other non-DB resource and still fetch their associated Cuisines efficiently. Fun times.

Caveats

I mentioned that I had a few comments about this technique. Most of them pertain to changes in ActiveRecord from Rails 1.x to Rails 2.x.

See, the companies I've been working at have all been stuck on Rails 1.1.6 – deplorable, I know. So, previous versions had a line like this:

id_map[row[:restaurant_id]].cuisines << cuisine_map[row[:cuisine_id]] # note, *not* a call to .cuisines.target

I'm upgrading Urbanspoon, and I discovered (thanks to unique key constraints in the database – don't ever let anyone tell you they're worthless) that modern versions of Rails will treat this as an insert statement. Yikes. Calling .cuisines.target lets you modify the array directly, rather than be intercepted by the associations codebase.

My bungling first attempt at working around this was to use instance_eval to completely override the association during the ids-to-restaurants map building phase:

r.instance_eval { @cuisines = [] ... }

This is a bad idea, as it litters your codebase with instances of Restaurants whose associations may or may not behave correctly.
The fact that each Restaurant now points to a single instance of the same cuisine could lead to unexpected things. That is, if Restaurants A and B both have the 'Chinese' cuisine, you can modify the Cuisines of A and see the change reflected in B without saving and reloading. This different than the normal associations behavior, but I think it's acceptable, and perhaps even preferable.
Finally, I think this technique could be generalized easily and added to ActiveRecord. I haven't researched whether others have gone down this path before, so it's entirely possible that one can do this already with a hip plugin that I haven't seen.

I also don't know if the cloned vs. referenced issue of the previous bullet point would be a problem with inclusion in ActiveRecord. It is the heart of the performance gain, howerever, and it is personally how I'd like associations in general to behave.

^[1] In kilobytes; based on this post.