Android Data Caching

One of the applications I'm building for the Android platform is meant to be used in remote regions of the developing world. While cellular coverage is getting more ubiquitous across the globe, there will inevitably be dead zones. With this in mind, all data-driven aspects of the application are being designed to degrade gracefully when there is no data connection available. One way in which this is being handled is by pre-caching data whenever possible.

Solving this problem in an application-specific manner is fairly straightforward. There are essentially 3 steps:

• Identify those items that you can cache - Since much of the information for this application is geo-coded, deciding what to cache is usually pretty straightforward (I can, for example, pull in all the data points tagged within a given radius of the device's current position).
• Watch for data connectivity changes and download cacheable data whenever a connection is available - registering a broadcast receiver to listen for status change messages makes this fairly trivial
• Store data locally that needs to be sent and send it whenever you have a data connection - again, a broadcast receiver makes this simple.

Beyond this core functionality, I've also built some ancillary features to allow users to better control their bandwidth usage in the event that they're not on an unlimited plan (a user can opt to only perform cache downloads if they have a WiFi connection as opposed to a cellular connection and they can choose what types of data they want to cache).

While this works well for the application, the real problem I'd like to address is doing this in a generic, reusable fashion. I haven't done so yet, but I am planning on building a library that can handle both cache population and data upload. The library would handle the nuts and bolts of listening to status changes and initiating downloads/uploads based on user preferences while delegating the decision of what to download (and how to do it) to user-supplied helper classes. These helpers can extend a base CacheAwareHelper class that, on invocation can first check to see if the data is already in cache and, if not, then invoke the method that actually performs the fetch of the data from the remote location. The result, in addition to being returned to the calling method, can then be cached.

This is still just a thought and I'm sure the details will flex a bit once I start writing the real design and implementation. I am still thinking about how to handle cache invalidation such that things are only evicted when they absolutely need to be. Stay tuned for a follow-up post once the library is done. At that time I'll include a few diagrams to show how it works. If anyone is actually reading this blog, I'd love to hear some feature suggestions in the comments as I'm planning on releasing this library as open-source.

An Exercise: Porting a Java Applet to Android

In 2003 I wrote a simple casual game for a computer graphics course as part of my masters' degree program. While the game itself was nothing special -- a simple 2-dimensional app where balls bounced around the screen and the player had to click on each of them in ascending order before a timer expired -- I thought it would be worth revisiting since it would provide a way to learn the way in which to handle graphics and animation on the Android platform.

Since the initial implementation of the game was an assignment to introduce the concept of double-buffering and simple animation, not much attention was paid to organizing the game logic in a manner that made it easy to add new game modes and rules. To facilitate this, the code was completely reorganized into a few discrete components. In the newly refactored game, the overall architecture is still pretty simple. It consists of a model class that implements all the game rules, score keeping, and the current state of the game, a custom data-structure to maintain the state of individual "balls", an animation thread that determines if and when to draw the objects and a view class that services as the bridge between the Android system (and things like touch events, menu key presses, etc) and the game. In the sections that follow, each of the components will be outlined with special emphasis on anything that was done differently due to capabilities/limitations of the Android platform.

Model & Data Structures:

The model class was responsible for maintaining the current state of the game. This state includes the score, the current level, the amount of time remaining, the list of all the Ball objects which, in turn, contain their position, that will be displayed and the current game mode (running, paused, game-over, etc). For simplicity of maintaining game state upon activity pause, all members of the model class must be serializable since they will be serialized into and out of a Bundle object when the game's Activity is suspended or resumed.

In addition to holding the state, the model class needed to contain the game logic. This consists of two main functions: determining if a particular set of coordinates are within the "target" ball and determining if two balls have collided. In the original implementation, this was done via an inelegant, brute-force manner that was expensive in terms of both memory and CPU cycles. Since the Android platform is more resource-constrained than your average desktop, reducing the processing required for each iteration through the program's main loop was necessary.

Collision Detection:

In the old version of the game, a two-dimensional array of bits the same size as the screen was allocated and the bits were set to either 0 or 1 based on whether or not some ball occupied that pixel. Every time the ball moved, the bits at its origin location were cleared and the bits at the destination were checked. If they were already set, a collision occurred and the ball changed direction and speed (i.e. it bounced) but if the bits were clear, then the space was empty so the ball's position was updated and the bits were set.

To reduce the need to iterate over every pixel on the screen, the new implementation segments the playing surface into a grid where each cell is approximately 100x100 pixels. An ArrayList is allocated for each cell in the grid and balls are to the list that corresponds to the cell in which their center lies. Since balls are always smaller than the cells, a ball in cell i,j can only collide with a ball that is in the 9-cell "superblock" surrounding it (cell i,j and the up-to 8 cells that surround it). To check for collisions, the list of all balls in the superblock is retrieved and the Euclidian distance is calculated between the ball being checked and every other ball in the list. If the distance measure is less than the sum of the balls radii, then the balls are overlapping and thus have collided.

Animation:

The actual logic for updating the state of all the model components (i.e. moving all the balls) remained fairly unchanged from the original implementation. What was added, however, was logic to attempt to keep the frame rate constant regardless of the CPU clock speed on the target device (something that, in retrospect, should have been in the original implementation too). To keep the animation looking smooth, a frame rate of 25 fps was desired. This equates to 40 milliseconds per frame. The code in the animation loop tracks how long it takes to do the state update and the drawing and if that time was less than 40 ms, it will sleep for the remaining time. This approach is about as simple a mechanism as can be employed and, obviously, it is totally ineffectual if the actual time needed to render the frame exceeds 40 milliseconds. Luckily, for this game, that time is sufficient on all device configurations tested.

Communication between the animation thread and the UI thread was another item that needed to be handled in an Android-specific manner. Some events in the game were not triggered by user interaction but rather by a condition within the model (the timer expiration, for instance). When the timer expired, a modal dialog box showing the final score was to be displayed. Rather than drawing one on the surface manually, it was much easier to use the built in DialogBuilder to pop-up an AlertDialog. If this was done directly in the model class as part of the updateState method (the method called by the animation loop to update the ball positions, timer and other state information) it would throw an exception since this was not running on the UI thread. Instead, a Handler had to be used to pass a message from the animation thread back up to the UI thread. The message could, in turn, contain a custom GameEvent class that allowed the UI thread to react appropriately.

View:

To adapt the view classes, the first thing that had to be done to port the game was to re-plumb all the drawing logic. Since the original implementation was created using the Java AWT and drawn directly to the ContentPanel of an Applet using the methods of java.awt.Graphics all the code that actually wrote the pixels to the screen needed to be revisited.

Android provides a Canvas upon which arbitrary shapes and text can be drawn. If you want to add the canvas to a view that may or may not contain other views, a SurfaceView is a good choice since it provides a drawing surface embedded in the normal view hierarchy. As the developer, you can control the contents and size of the surface but the system takes care of positioning it at the right place on the screen (based on whatever else is in your view hierarchy).

Drawing on an Android Canvas was not that different from drawing on a JPanel. The difference, however, was in the view life cycle. Just like any other Android application, the system can suspend your Activity any time the user does something that causes app to lose focus (like taking a call, for instance). At that point, the surface on which you're drawing may be destroyed (but not always).

In response to the Activity pause event, the game pauses the animation (by setting a volatile flag on model class) which tells the animation routine to stop updating the position of the balls and to stop decrementing the timer. At this point, the animation thread runs to completion (to be a good citizen and avoid busy-waiting in the background). When the user returns to the game, the game animation can be resumed. What we cannot do, however, is resume the thread (since you cannot call Thread.start() on the same thread more than once). Instead, the handler must create a new thread and seed it with the information from the "old" game model (instead of creating a new model instance) and start the thread.

Understanding the life cycle of the view classes is important. It is worth pointing out that it is not handled correctly in the Lunar Lander sample application included on the Android development site. In that example, the surfaceCreated method on the view class starts the thread that was initialized in the constructor. The problem is that surfaceCreated can be called by the system whenever the surface regains the foreground (even though the View's constructor may not have been called since it is the same view instance). Since the thread is a member variable and may have already been started, calling start could (and often does) result in an exception. This isn't meant to be a critique of the example code (I've said it before and I'll say it again: the wealth of examples and documentation is one of the strengths of the Android platform) but it should be noted that not everything in the example code is 100% correct all the time and if something "feels" wrong, it very well may be.

Impressions and Future Work:

Porting this application was a worthwhile exercise. Since the "game" portion was already done, it allowed me to focus on the nuances of the platform itself rather than the mechanics of the game play. All said and done, it took approximately 15 hours from start to finish (it could have been a lot shorted had I kept the brute-force collision detection instead of refactoring that). It was time well-spent in that it helped illustrate some of the finer points of handling the animation (frame rate limiting, surface life cycle, percolation of events back up to the UI thread).

Despite the fact that game itself is exceedingly simple, I plan on adding to it in the coming weeks. I am contemplating using the game as a proof-of-concept for a server-side component that can handle reporting high scores, issuing user challenges and handling teams/clans. I plan on exposing the server platform via a REST API and building a client library that could be included in any Java application for easy integration. I'd be interested in hearing if any of the (few) people who read this think there is any merit in a system like that and, if so, what other features it should support. I hope to have more to say on this topic soon.

Google Maps API Keys on Android

For any Android devices with the Google APIs add-on installed, there is a very convenient way to integrate Google Maps with your application: the MapView. Using this view allows an app developer to create custom interfaces using other components rather than just launching the built-in Google Maps application via an intent. Needless to say, it is a very powerful feature that can be added with minimal effort.

To use this feature, however, one has to register for an application key from Google. Normally, this would be a reasonable request. In this day and age of mash-ups and public APIs, registering for keys is the status quo. What differs here is that the public-key fingerprint of certificate used to sign the application must be submitted in order to get the key. The key is generated using this fingerprint as a seed for the key generation and will only work when deployed in an app signed by that same certificate. At first glance, this too is perfectly reasonable. The annoyance comes when one realizes that a different certificate is used to sign your application for development/debugging than is used for production release (which is the default behavior for the Android Development Toolkit). If 2 different certificates are used, two different keys are needed and, since the key is embedded in the layout file that uses the MapView, one must have two different build configurations - one that uses the debug key and another that uses the release key in the layout file.

This leaves one with little recourse but to either use the production certificate during development/debug, manually change the key in the layout file before doing a build, or use a tool like ANT or Maven to swap in the right version of the file at build time based on a profile. I was planing on configuring Maven for this project using an open-source Maven ADK plug-in at some point anyway, looks like I have another reason to do so.

Android Optimization

Since the Android platform uses the Java programming language and, at a high level, seems to support a large portion of the language, it is easy to forget that one is still developing for an embedded device. I am, by no means, an expert -- in fact, this is my first foray into the world of embedded programming but there is no harm in outlining the little bit I've learned if it has a slight chance at helping someone else. This is the first platform on which I've really had to think of "micro" level optimizations (rather than macro, algorithmic optimization). It definitely adds another dimension to the analysis one must undertake when attempting to solve a problem.

To understand the best way in which to write Android programs, one first must understand a bit about the virtual machine at the heart of the system: The Dalvik VM. I won't go into details about the internals of the VM, but suffice it to say that the fact that it is made to run on devices with limited memory and CPUs, the compiler makes some choices in bytecode generation that differ from those that would be made by Sun's compiler.

In starting development on my Android project, I came across this page on the developer resources site. While the page listed a number of things that I would not have even thought of -- the way in which enhanced for loops, for example, result in the implicit allocation of an Iterator -- I was glad that the first bullet point was "Optimize Judiciously." This advice is probably the most important on the page. They even goes as far as including one of my favorite quotes on the subject:

We should forget about small efficiencies, say about 97% of the time: premature optimization is the root of all evil.
—Donald E. Knuth

The dangers of premature optimization are by no means limited to the realm of embedded programming (though they may be even more precarious since some of the optimizations done in this space may seem odd to developers accustomed to working in the desktop world) and I've seen them derail or over-complicate a number of projects in the past. Maintainability and understandability are just as important as correctness when writing software.

Pontificating aside, here is the process I am taking with respect to optimization:

1. Devise the most efficient algorithm for the logic I'm performing: this is no different than I would do on any other platform (just because you have more resources doesn't mean your software should use all of them).

2. Make the "easy" optimizations the first time around: this includes things like declaring variables using concrete classes rather than interfaces, only using the enhanced for loop when an iterator would be needed anyway, etc

3. Make the code as simple and clean as possible: again, this is no different than any other platform

4. Refactor often: this is probably the most important step. At this point, I've refactored so much of the application that I've basically rewritten it twice over. After each refactoring round, the code is cleaner, more efficient and more maintainable. I have paid special attention to the view portion of the code as small changes there can have a huge impact on performance.

There is nothing novel about the approach outlined above. My only point in calling it out is that the sequence is important. I don't start the refactoring phase until I'm sure that the algorithm is correct and the code implementing the logic is as simple as it can be. This helps keep things maintainable. I also endeavor to keep my layers and object dependencies clean. Performance "optimization" is not an license to throw away decades of solid software design principles. Keeping the components well-defined an clean may seem like you're leaving a few more CPU cycles of performance gain on the table but, in the long run, one is probably still better off with quality code that (so long as it performs well enough -- and what "enough" is varies depending on the application) versus spaghetti code that uses the fewest possible CPU cycles.

Android Development

I have recently started programming for the Android platform. This post is the first in what I plan to be a series discussing my experience writing code for this environment. That being said, I'll jump right into it.

We chose the Android platform for our application because it offered a lot of capabilities that we could take advantage of right out of the box (camera for video/image capture, GPS for location-awareness, Wi-Fi and Bluetooth for fast data transfer, etc). The free/open nature of the platform was also appealing. At this point, I've implemented the core use cases for all those features and am now concentrating on improving the user experience, bug fixes, and overall polishing. So far, I have no regrets as I have not yet come across a use case I could not implement in a fairly straightforward manner.

At the risk of sounding like a Google Fanboy, I have to say that I really do enjoy working on the Android platform. The core reason is that Google really put a lot of thought/effort into the SDK and development tools. For Eclipse users, there is an Android Development Tools plug-in that makes building and debugging applications as simple as a single click. Additionally, since Android has gone through a fairly rapid evolution and there is a wide variety of devices running a number of different versions of the OS, the emulator provided with the SDK makes it simple to test different device configurations running differing platform versions. While emulators are great for initial debugging, there is no substitute for running on an actual device. Since the platform is designed to be open, deploying one's applications to a real device is as simple as turning on an option in the phone's settings menu, plugging it into your PC and clicking a button in Eclipse. Again, none of these things are groundbreaking, but having full IDE support makes it much easier to concentrate on the details of the application rather than the nuances of packaging.

That last point applies to a lot more than just Android. Whether it is IDE plug-ins or a life-cycle management tool like Maven, comprehensive tooling makes getting up and running on a project easy. I cannot overstate how much of a difference Maven has made on other projects, especially those with complex builds and many dependencies. That being said, I am planning on trying to integrate Maven with my Android builds using this plug-in shortly (for reasons I'll outline in a subsequent post).

Proper System Properties

In sandboxed programming platforms like .Net and Java, the developer is insulated from the details of the underlying machine upon which the code is running. At times, however, it is often useful to have more knowledge about the environment. One way to provide such information without introducing any machine-dependent code into the sandbox is via system properties. They can be implemented in a number of ways, but the most common is a set of name/value pairs that can be accessed via a core class in the language runtime. In java, one can get a list of all the system properties using System.getProperties().

The properties are not limited to those set by the language virtual machine; they can be extended to include any property the developer wants to set. Most languages provide a way to do this at virtual machine initialization or programmatically within the application code. Having system properties is a powerful tool and can enable code to handle certain conditions based on the capabilities of the underlying machine in an elegant way. With power, though, comes responsibility.

Some developers have been abusing this construct and using it as if were a container for global variables: instead of passing parameters into methods, a method will simply look up a value from the system properties. This is especially egregious when the property is not universally true from the system perspective. One such example is specifying a HTTP proxy. In Java, the default HttpConneciton class uses system properties to specify a proxy. In most cases, this is fine, but in some enterprise environments, the proxy server one must use depends on the address being accessed. If your program needs to access two addresses that use different proxies, then changing proxies involves updating the values in the system properties. Again, this is usually not a big problem, but if you have a multi-threaded program, this could cause a race condition unless one enforces the atomicity of the property update with the HTTP request. Depending on the application requirements, this may or may not be an acceptable answer.

While there is not much one can do about the proxy issue (outside of using some other library to make HTTP requests), developers can prevent imposing similar limitations on their own code. Since it is impossible to anticipate every way in which code may be used and it is equally impossible to know every possible system configuration, the use of system properties that do not actually describe the system upon which the code is executing should be avoided.

Threads & Exceptions

In this age of multi-core processors, being able to write efficient and correct multi-threaded programs is becoming increasingly important. Unfortunately, however, writing such programs is not a trivial task. Deadlocks, race conditions, and thread starvation are among the myriad pitfalls that could break one's programs. Complicating matters further are “legacy” (for lack of a better term) third-party libraries that may or may not be thread-safe.Errors due to threading issues are among the worst class of bugs: the elusive Heisenbug. The use of a good profiler tool is essential in tracking down and eradicating bugs like this.

Just as important as knowing how to avoid writing code subject to deadlocks and race conditions is knowing how your programming environment responds to bugs that occur in child threads. In the Java programming language, for example, one's program could find itself in an unexpected state due to an uncaught exception in a child thread. When one is running a single-threaded program and an uncaught exception occurs the system will exit and print the exception's stack trace to standard error. Not graceful, but also not a very subtle error condition. When an uncaught exception occurs in a child thread, however, the flow of control is as follows:

1. The JVM checks the UncaughtExceptionHandler of the Thread object. This is null by default. If you wish to specify your own handler, you must call the setUncaughtExceptionHandler method on the thread instance (usually before starting its execution). Setting this handler only applies to the thread instance upon which you installed the handler (not descendant threads).
2. If the thread does not have an UncaughtExceptionHandler, then the ThreadGroup is checed to see if it has a handler of its own.


3. If the thread's ThreadGroup does not provide a handler, then the default handler is invoked. Unless the programmer changes it (by calling the static Thread.setDefaultUncaughtExceptionHandler method) the default handler simply prints the exception's stack trace to standard error.

The Java API documentation contains a very important warning for those programmers who want to provide their own default UncaughtExceptionHandler:

The default uncaught exception handler should not usually defer to the thread's ThreadGroup object, as that could cause infinite recursion.

When developing code that has any potential for reuse in other applications, one has a responsibility to take threading considerations into account. If it is decided that a method or class will not be thread-safe, then it is the developer's responsibility to clearly document this limitation in both the in-code documentation (i.e. JavaDoc) and any other API/Development guides.