Tuesday, April 30, 2013

Before & After

I attend weekly trivia nights with friends.  One of the categories, Before & After, has piqued my interest.  It works like this: two movies are described, and you have to name both movies.  What makes it a bit easier is that the two movies share a common combining word.  Here are a few examples:

  • Men in Black Swan
  • Sling Blade Runner
  • Law Abiding Citizen Kane
  • My Fair Lady and the Tramp
  • Batman & Robin Hood
  • A Walk to Remember the Titans

I find the answers to be fairly amusing, so I wrote a program that generates before & afters.

You can find the source code here.

I've pumped out a spreadsheet of results (for movies) here.

I used a word list to discover words in common between the start/end of movie names.  For finding the common word, I generated both a forwards and a backwards trie of the first/last word of each movie name.  Tries are pretty much the best for simple text searches.

Ultimately, the program is general enough that it could work on anything.  The main reason I focused on movies was because IMDB is good enough to dump their ratings data, which helped immensely for sussing out good vs. bad results.  I found the best way to rank results was a combination of the # of voters (showing popularity of both items) and the difference in their rating (in that combining two items with vastly different ratings is hilarious).

There was one problem I could not overcome (since I was putting relatively minimal effort into this venture), which is determining when a word was part of a compound word or not.  For example, I would want to match "ball" in "basketball" because "basketball" is a compound word, but I wouldn't want to match "all" in "hall".  Solving this problem would a word list with more data than the word itself, so I just skipped it.

Tuesday, April 9, 2013

Memory Management: A Case Study

During the development of the most recent version of Expedia's Android app we ran into a variety of memory problems.  I thought I'd share some details about the problems we ran into and how we solved them.

Memory Analyzer Tool (MAT)

If you're not familiar with Eclipse's MAT you should be.  MAT should be your first stop for dealing with memory problems.  Not only is it useful for finding out what's hogging memory, it can also be used to find memory leaks.

An important note about using MAT - almost all memory problems I've run into relate to Bitmaps.  In versions of Android previous to 3.x, Bitmaps were stored in native memory (rather than the heap) and thus not viewable in MAT.  This makes it much harder to debug memory problems on 2.x devices, so you might want to stick to 4.x devices for investigating memory issues.

High-Resolution Bitmaps

Bitmaps in memory are uncompressed (even if they were compressed in your APK).  This can cause serious issues if you have high-resolution assets.  For example, we had tablet backgrounds which were the full resolution of the N10 (2560x1600).  That's fine with the N10's beefy heap size, but when scaled down to smaller devices (like the N7) the scaled image would take up 1/8th of the app's memory!  Imagine doing that multiple times and you can see why we ran into memory issues.

We solved this problem one of two ways: first, we reduced the resolution of the asset.  Some of these backgrounds were blurred, meaning we could lower the resolution greatly without losing quality.  When we couldn't lower the resolution without quality suffering greatly, we would sometimes replace the normal asset with a backup color (when we detected low memory situations).

BitmapFactory.decodeResource()

When you're decoding resources yourself (rather than using something like ImageView.setImageResource()), there are a couple things to look out for.

If you're decoding the same resource over and over again, you might want to cache it.  This problem hit us because we had an ImageView in a list show a default asset before we load an image from the network.  If you scrolled through a list quickly, and each one is loading its own default asset, you could create a burst of memory usage that runs you out of memory.  By caching this default, we not only saved memory but also improved performance.

Another issue we ran into with decodeResource() involves device density and BitmapFactory.Options.  If you are using them you should know that the default is to not auto-scale the asset at all.  So if you've only got an xhdpi version of the asset on an mdpi device, you're going to load them in at xhdpi size, taking up more memory than you expected.  So make sure to set that if you're manually loading assets with Options.  (If you're not passing BitmapFactory.Options you don't need to worry, as the default decodeResources() handles density for you.)

LruCache

Having an in-memory LruCache of Bitmaps loaded from the network is all the rage these days. However, it can easily lull you into a false sense of security.  Just because you've limited your Bitmap cache doesn't mean you'll never run out of memory!  If your LruCache is 1/4th the size of available memory, but your app (at one point) needs all of it not to crash... well, you've got a problem.

Things got better for us once we started manually clearing the LruCache at key moments.  Having a DiskLruCache helps a lot if you do this, as you can clear the memory cache but then quickly reload images if you need to without going to the network.

Resources and sPreloadedDrawables

This is a red herring!  You may see in MAT that Resources is taking up a whole ton of memory with a variable called sPreloadedDrawables.  Unfortunately, you can't avoid sPreloadedDrawables; it's a pre-defined set of system resources that are preloaded into memory for every app.  Don't spend any time thinking about them.

Recommendation

Overall, what you should do is find an old phone and use it as your primary development device.  That way you know from the start that your app runs on all phones.  It's much harder to discover these limitations later on.

For example, the Nexus 4 (my primary device) has a whopping 192MB of memory.  Even with all xhdpi assets that thing is difficult to run out of memory on a standard app.  Compare that to what QA was using - devices with 24MB to 32MB.  It's a very different game when you're trying to design a beautiful app to run in 24MB on hdpi!

Tuesday, April 2, 2013

Automatically Managing Bitmaps from URLs via UrlBitmapDrawable

If you develop apps, you'll probably (at some point) need to load images from the internet.  Sometimes you'll load many images at once, as in a ListView or Gallery.  Your first foray will be easy, using BitmapFactory to decode a stream - then you run into the dreaded OutOfMemory error and are suddenly grounded back to the reality that is limited memory space.

There are two equally important problems to handle when using images: loading an image to view it, and unloading it later to save memory.  Last time I looked there were plenty of libraries out there for solving the first problem, but I was unsatisfied with their solutions to the second.  A lot of them simply blow away loaded Bitmaps at some point in time - but what if you still wanted to use it?  Then you end up in this complex tightrope walk, where you're having to constantly check and re-check your Bitmaps for whether they still exist.  It's a gigantic pain and I've been doing this dance forever.

I set out to solve the problem in a better way, such that it would do three things:

1. Load images from a URL into a View.

2. Unload that image later (for memory's sake).

3. Re-load that URL into the View if we ever see it again.

I was able to accomplish all three with the help of a class I wrote, UrlBitmapDrawable.

Introducing UrlBitmapDrawable


You can check out the code here: https://gist.github.com/dlew/69e6557604926d7e1513

You can use it just about anywhere as a Drawable.  Just instantiate it then use it:

UrlBitmapDrawable drawable = new UrlBitmapDrawable(res, myUrl, myFallback);
myView.setBackgroundDrawable(drawable);

With ImageViews there's a bit of a hack I needed to do (in order not to have to use a custom ImageView).  So I setup another method for using UrlBitmapDrawable with ImageViews:

UrlBitmapDrawable.loadImageView(myImageUrl, myImageView, myFallback);

Highlights


This solution has made my life easier in four ways:

It's Simple - All you need to is provide it a URL and it takes care of the rest.  You don't ever have to worry about its state; if the underlying Bitmap is recycled, it will fallback to the default image and start reloading the URL.

It's a Drawable - By making it a Drawable, it meant I could attach it to any View.  Tying it to a custom View would have vastly limited its potential.

It's Compatible - It's not tied to any particular implementation for loading images.  Retrieving images could be a simple network call, or you could hook it up to a complex LRU memory/disk cache.

It's Extensible - The version I've provided is simple; internally we've added some bells and whistles to it.  See "Areas for Improvement" below.

Disadvantages


It's not all sunshine and daisies.  There are two problems with UrlBitmapDrawable; however, I considered them minor in comparison to the larger problem I was trying to solve.

BitmapDrawable - BitmapDrawable does not let you access the underlying Bitmap by default, so you'll have to import your own version that opens it up.  Here's the source code from github.

ImageView Hack - In order to get ImageView to re-measure the Drawable's width/height after loading you have to trick it into thinking the Drawable has changed (by nulling it then resetting it back).  To be honest, there might be a better solution here, but I haven't found it.

Areas for Improvement


Here's ways that we've tricked out our UrlBitmapDrawable:

Default Resources via Id - A default resource is important (so we can show the user something before we load the asset).  In the sample code the UrlBitmapDrawable holds a Bitmap; this is a fine example, but if you're inflating a new default Bitmap per UrlBitmapDrawable, that can wreak its own memory havoc.

Internally, we've gone a more complex route which uses Resources and resIds, and loads the Bitmap automatically from an in-memory cache.  It keeps us from spending a lot of time (and memory) reloading the same default bitmaps.

Fallback URLs - We are sometimes given a list of URLs at differing quality levels.  It's pretty easy to hook that into this system; each time a download fails, try the next URL.

Recycling Bitmaps - If you read the code carefully you may notice that I never actually dealt with the second step - unloading Bitmaps from memory.  We use an LruCache to handle this; as a result of UrlBitmapDrawable it can recycle Bitmaps with impunity.  It also means you can evict the entire cache at any time if you need the memory.