Android and Singleton Classes

Recently in my Android programming escapades I found something interesting and bothersome in an API I had written. I had created a singleton class for the main renderer of my graphics API. With the first app I was making I had no problem, and it in fact was quite helpful and easy to write, after all each app using this API would only have access to one renderer.

The problem arose out of some strangeness with the Android VM. It turns out that static fields of a class can but not necessarily cross from one app to another, effectively sharing one singleton across more than one activity. This might not sound too bad but it can be a problem if you use an API in multiple apps and they happen to run on the same device. This can result in undesirable effects.

So I removed the singleton property from the renderer object, and thus had to pass it around in method parameters like a cheap whore. It’s not an ideal solution but it worked, and if you believe some people on the internet it’s probably a better design. Whilst there was minimal impact on the API, an app I was writing needed to be hacked a little to make it work properly. The funny thing is if there was a separate JVM or classloader for every instance of all apps it would have been fine to have the renderer as a singleton and it would work.

So why are singletons a problem on Android? It seems that there is a single JVM running all the Android apps together. This means that static variables (including singleton classes) can end up hanging around long after an activity ends. If a class is shared with another app they can end up using the same singleton class. The other half of the problem is the Android OS will sometimes destroy an app or use a different class loader for a new activity thus making the static/singleton unreliable for any kind of storage or communications across activities or apps.

So it’s best to avoid the use of singletons on Android.

There seems to have been some debate about singletons and their use. Whilst it is true that many programmers over use the pattern and they can be a problem, they do have a place in a developers toolbox. There are common interfaces such as OpenGL and others which cannot be accessed in an easily nice OO way.

OpenGL in particular is a good example, it is not thread safe and basically requires all rendering be done in a single thread. It also is not Object oriented and as such there is only one instance of it per application at best. Because of its nature it is essentially an interface to the hardware acceleration of a machine, which is better suited to a singleton/procedural style interface.

The thing with OO design is it isn’t suited 100% to all programming problems. There are in fact many instances where using an OO design is a bad idea, such as embedded systems and applications that require high performance. The trouble is all the OO loveliness comes at a performance and memory size cost, that luckily isn’t a problem for most applications. This leads to the situation where something OO needs to interface to something that isn’t, this is where singletons are a useful construct.

Something my Dad always said is “a bad tradesmen blames the tools”. It seems there are many people out there blaming the singleton as if it is at fault for being used incorrectly. Sure there may be many cases of people using it poorly, but that just means they are poor designers/coders. The singleton pattern is just a tool, used appropriately it can make your coding life easier, used badly it can make your life harder. This is true for all the basic design patterns, it’s up to the designers and coders how good their designs and code are.

Code Optimisation

Recently I started reading a book about code optimisation that focuses on the x86 architecture and assembly language. The book is called Graphics Programming Black book and is written by Michael Abrash who is well known for his work writing technical articles and coding on games such as Doom and Quake. Whilst the book has a graphics focus, the skills you can learn from the book can be applied to any high level language or assembly language you may happen to be using. I’ve dabbled with assembly code in the past and have found some parts of the book quite interesting. You can find the book on-line to read via html or PDF download. You can find it pretty easily if you just google Michael Abrash and the name of the book.

After my recent testing of data structure performance and beginning to read this book, I decided that I should look over all the Java code I had in order to try and optimise it. I have been for some time working on writing some android games, and in the process have built for myself a nice graphics library and the basics of some games. In testing and tuning my code I’ve found some good rules of thumb for making fast code in Java not just for the android platform but in general.

The first thing I’d recommend you do is to not use Iterator classes anywhere in your code, but use for loops instead. Iterators are objects and add overhead to your applications in multiple ways. Firstly the occupy heap space and need to be garbage collected when finished with. Now this may not seem all that bad, but if you have several nested loops, this could mean thousands of Iterator objects being created and destroyed on a regular basis in your code. Secondly it adds extra method call overhead every time you call hasNext() or next(), slowing down your loops. Again for small numbers of loops it seems insignificant, but when added up over a large number of loops the time taken to make the calls can become quite significant. For these reasons, even when using the API data structures such as ArrayList, I would avoid using Iterators.

In very time critical code, it is best to build your own data structures out of primitive arrays rather than to rely on the API code. The JIT compiler seems quite adept and optimising simple array based code to run a lot faster than pretty much any API or object based solution. It’s also best to try and minimise the number of method calls in your important loops to keep overhead down.

An interesting problem I recently had was to do with path finding within a maze in one of the games I am writing. Obviously I had a randomly generated maze that whilst being perfect to start with, has cycles (or loops) introduced to it to make the game more playable. When I first wrote the path finder I used a depth first approach that works quite well on perfect mazes as there is only one path from each point to each other point. The problem I had with it was two fold, the algorithm was slow in the larger mazes and with cycles being introduced it often chose longer paths than it had to. This perplexed me no end, so I went in search of what the problem might be, optimising some of the code to get better speed, and writing some extra code to try and get a better path. After having tried without any luck I decided to try using the breadth first search algorithm implemented iteratively. It turned out to be a whole bunch faster! I investigated into why this might happen given that depth first search should be faster to find a path (even if it’s not optimal). Upon comparing the code of the two algorithms I came to a simple conclusion. The depth first search code took a lot longer to execute a single iteration because it had many more method calls and comparisons than the simple breadth first search does. So whilst on paper the depth first search looked good, its performance is poor in comparison, because the simpler breadth first search could get through more iterations in the same amount of time. The breadth first search is so much better I was able to generate larger mazes and still find paths within a reasonable response time, even with worst case paths that searched most of the maze!

It’s interesting how sometimes the unexpected solution turns out to be the best. It shows you should always test your code, and spend a bit of time optimising your critical code. It will in the end make the experience of the end user all that much better, and enable you to do more with less.

Java Data Structure Performance

Recently I was browsing Stack Overflow looking at questions asked about Java. One theme that kept on recurring is that of the performance of various data structures within the Java API, in particular the Vector and ArrayList classes were frequently compared. So I decided that i would have a go at working out which data structures perform well.

The first thing I needed to decide upon was what kind of test was fair, and what kind of circumstances would I run the tests. I made a small test framework in Java so I could apply exactly the same algorithm to each data structure. I built the program to perform tests one after another with increasing data sizes to see how the data size affected the results. I wasn’t worried about factors such as the garbage collector and other tasks running on the OS as these would affect all the tests and I could take some precautions to minimise their effect. I’ll make my code available in the code section when I’ve finished tidying it up a bit.

I made code to test several different major aspects of a data structure. I recorded how long (in milliseconds) it took to create, insert into, remove an item by index, and remove an item by its value. I was just using the System.currentTimeMillis() to work out how much time was used, so small-scale accuracy can’t be assured. If you want to be more accurate you could use a profiler on the same code. I chose to not require the data be ordered within the collections as the tests are not dependant upon ordering within the data structure.

I tested 4 different data structures and had a dummy test with no data store to check the algorithm for the tester wasn’t causing extra overhead. I tested an implementation of a standard primitive array and LinkedList as well as the Vector and ArrayList classes. I’ve graphed some of the results I had at the bottom of this post. The first result that I found very interesting is with 1000 or fewer records there are no significant differences between the various data structure types. So if you aren’t storing large amounts of data there is little to gain by picking one data type over another.

The LinkedList data type interestingly had some of the worst performance values getting worse comparatively as the data size increased. Particularly for the remove by index and remove by value operations. In theory it should have similar performance to the others so this is a bit confusing. Perhaps it is all the extra reference handling that makes it significantly slower. It’s no surprise that it isn’t faster than the other data types as the operations that work well are adding and removing at either end of the list. This means that the LinkedList data type is best suited to implement structures such as a stack or queue as that allows for dynamically sized structures that are relatively fast.

Vector and ArrayList showed some slight difference in performance but are for the most part pretty similar. This is in part because they use exactly the same underlying data storage mechanism. The only difference being that Vector is synchronized and therefore thread safe. The results from testing seem to indicate that the cost for acquiring the synchronization lock is a smaller factor the larger the data set you have. Even on smaller data sizes the difference wasn’t incredibly large. On a faster machine with a different JVM the difference between the two was even smaller, looking almost identical. So differences between these classes will largely depend on what kind of system you are running on, and will in most cases not be a huge difference. Again if the data size is small it doesn’t really matter which one you use.

Interestingly the Data type that did the best was the standard primitive array implementation. It was significantly faster than all the other data structures! The simple answer is that primitive arrays in java require fewer operations to manage when converted into machine code by the JVM compared to other methods of storage. In this case it is also faster for removal by index because the array did not worry about keeping items in order when removing an item. I simply moved the item at the end to occupy the space to be deleted and then decremented the size. This is a common practise for lists of items in games where the order in the array is not important.

Classes such as Vector, ArrayList and LinkedList preserve the order of items within them whether you require it or not. This carries an intrinsic cost when removing items, and at worst can be O(n) to remove an item. When order of the items isn’t a concern any item can be removed in constant time as I have done in this implementation of the primitive array.

So which data storage technique should you favour? There isn’t a simple answer to this question as it will depend on each particular problem. However it does seem that you will get the best results most often when you create a data structure tailored to your problem. In this particular instance a simple array was best. You can construct pretty much any type of data structure with a primitive array, so many different solutions can be implemented with better performance than the classes in the API. In my experience the Vector class is fine for most things and easy to use, but when I’ve required speed I often use a primitive array, or another type of data structure altogether such as a HashMap which is useful for creating a cache.

So why do the data store classes in the API exist in the first place? Simply put convenience and generality, when performance or data size are not going to cause problems it’s easier to use a pre-constructed class to store data in. The java storage classes are also implemented in a generic way so that they can be used for any purpose, this has a performance cost but you benefit by having data structures you can use for many different data types and situations. If you want some of that convenience and better performance, you could use the Trove library for data storage. Trove is faster than the java API but does not really have generality like the classes in the API. Check it out here.

1,000,000 records on the slower machine

100,000 records on the slower machine

1,000 items on the faster machine

100,000 on the faster machine

New Hardware! Android ASUS Nexus 7

I don’t often buy new hardware, but the time had come to buy an Android tablet for software testing. So I went searching for a device that would suite my needs. I wanted my device to be able to play some games, browse the web and perhaps play some music or multimedia. It would of course be best for it to have the latest version of the Android OS as well.

I checked out many tablets of varying cost, size and power. I found that the ASUS Nexus 7 fit the bill. Many other tablets were larger, but had poorer quality displays. Some of the tablets the shops had in stock were old ones that have been around for a while, and had outdated software. The Nexus 7 has a quad-core processor that makes many of the other tablets look silly and obsolete, and a clean and crisp display that whilst not being the largest, certainly looks very nice, and in many cases better than it’s larger cousins. The touch display is very responsive, and I’ve found it to be quite good for the few games that I have tried. Battery life is very good, I played Angry Birds and browsed the web for about 3 hours and only used up about a third of the battery.

That being said there are some negatives to go with it. It doesn’t have a port to add extra storage in the form of an SD card, or any other ports at all for that matter. So there is no using USB memory sticks with this device. It does support bluetooth, but that’s just another device with more batteries to carry around. The glass on the screen can be very reflective, so you need to choose a good, low glare situation to use the device. The in-built camera is also of a fairly low megapixel count, so not really useful for anything more than web chatting.

The software package containing a lot of google apps pre-installed is excellent. There is the obvious facilities for you tube, email and web, but also a nice app for looking at maps and using the GPS built-in. I found a few apps in google play that are handy for connecting via ssh, and VNC to machines remotely. The built-in software has been pretty easy to use, the only downside being there isn’t a flash player built-in so I can’t watch TV via ABC iView (an Australian TV streaming service). Other types of web-based video seem to work fine.

In conclusion the Nexus 7 is a fantastic device for browsing the web, you tube, and android games. You can put your music on it, but there isn’t really enough space for any amount of video. 16G may sound like a lot, but if you were to want to store a lot of any kind of media you’d quickly run out. I have enough computers to handle my multimedia needs so this isn’t really a problem for me. Now that I have the device I’ve found it’s really handy for browsing the web, and watching you tube videos, but also performs a few other useful things I hadn’t anticipated. It’s good in that I don’t have to wait for a computer to boot up, or use as much electricity to perform some of my common day-to-day tasks. It’s also nice to be able to do these things anywhere in the house. Sitting up in bed has been a favourite, especially on a cold night.

Profiling an Android Application

As you may or may not know, I have been writing an app for the Android platform using OpenGL. Anyone writing for OpenGL on the Android platform should know that it is important to make sure your code is memory efficient, and most importantly fast. In order to achieve this it is important that you test and analyse your code on a regular basis. There are some useful tools that come with the Android SDK and some that can be downloaded with eclipse that you should use.

For profiling you application you should use Traceview. In order to make effective use of this tool you need to make a trace file covering the time frame that you are interested in. You can do this with eclipse, but the length of the trace is limited, and it can be inaccurate. I suggest that you make use of the android.os.Debug class to make the trace file, because you can control the size of the trace buffer.  I have used Traceview to analyse the lengths of time it takes to execute elements of my rendering code, and to monitor the changes in timings when I have changed my code.

For analysing how much memory you are using there are several things you should do. Firstly take a look at the output of logcat and see how often the garbage collector runs and how much memory it frees each time it does. If your app creates and releases objects on a regular basis, the garbage collector will spend a lot of time cleaning up memory which will slow your app down. The garbage collector will also tell you how much heap memory you are using. You need to be aware that there is limited heap space available to apps on Android phones. Some have a limit of 24Mb of heap, but it differs from device to device. So you need to be careful of the amount of RAM used by your app, even if the target device has a lot of RAM. A good way to find out how your app uses memory is to use the eclipse memory analysis tool. It is fairly simple to get working in eclipse, and like method tracing can also be activated by the Debug class. I found that I had to limit the results of all my searches to my project classes to get useful results. There are a number of other classes that belong to the Android API that take up a significant memory space in a small app. Either way the analysis tool is very good, but can be a little complex to use if you don’t know the terminology.

The tools have been useful to me in finding some areas of my code which could be improved, and quantified the improvement. I found a section where I had created a String object implicitly in a method call. When the method finished the String was no longer needed and the garbage collector would kick in once every two seconds. I changed my code to use a different data type and not create objects implicitly and got the relevant code to run twice as fast in addition to not requiring the garbage collector as often. I have also been able to determine the amount of memory my objects require and tune them appropriately.

The analysis tools are only half the solution. Your application needs to have a good solid design, to make it easier to diagnose and correct problems. Lastly it is important to know how to interpret the information from the tools. Many parts of the analysis tools cause slow down or extra memory use, so you need to be aware that the statistics presented are relative to each other and don’t always represent the result on real hardware. If used effectively profiling and memory analysis will allow you to significantly improve the performance of your applications.

OpenGL on Android tips

I’ve been working on an 2d rendering engine for OpenGL on the Android platform using the standard Java API. In my ramblings around the internet there seems to be a misunderstanding about how some portions of the API were intended to be used. In particular the use of vertex, texture and colour arrays and the draw arrays function seems to be commonly misused from what I have read on forum posts around the net. Here I will list a few short tips about making your OpenGL apps on the Android platform run a bit smoother.

The first mistake that seems to happen a lot is the constant creation and destruction of objects in the rendering thread. Android devices and other mobile or embedded systems are very limited in their nature, they do not have much RAM and the processor is not as powerful as your standard PC or mac. Because of this it is important to keep the number of objects pretty constant within your games, otherwise the garbage collector will slow things down constantly recycling objects that you create and destroy on a regular basis.

The second mistake I’ve seen has to do with how the buffers are mis-used. It seems many people are regularly changing the contents of the buffers to move or change the location, size or even rotation on-screen. My mind boggles as to why you would do this over using the standard GL model view matrix operations. It’s my belief that you should create the buffers that hold the actual vertex information once, then in your renderer use glTranslate, glRotate and glScale to achieve any transforms required. The reasons for this are two-fold, firstly if you modify your buffers all the time you will need to modify all the vertices to achieve simple things like translate. Some people have reported that functions on the buffer objects can be slow on some devices, so it is best to use them sparingly. Secondly using the GL functions and matrix operations should be optimised in native code for each device, and so they should be faster. This should also apply to using the OpenGL library on other platforms with Java, mostly because of its interpreted nature. This would be different in some cases if you were writing code for a native language, as I’m told state changes to the GL matrices can be slower than changing the vertices, but this is only true for a small number of vertices where the computation time to change them is trivial.

The final tip I have for you is to make use of multiple threads for your app. You have a very limited amount of processing power so taking advantage of the fact many of the more modern devices are dual core is imperative. The simplest way to do this is to create a separate thread for the main logic of your app, leaving the main rendering thread to perform the main task you want it to, updating the display. Writing multithreaded applications is more complicated in some instances, but java provides some nice mechanisms that you should take advantage of. Declaring objects or just some methods on an object synchronized is a good way to achieve this. Java only allows one thread to execute synchronized methods on objects at a time, but the lock is done at the object level and not the method level. This means you can effectively make an interface object between both threads that is what we call thread safe. This means you are less likely to run into race condition bugs, and hopefully you’ll also avoid deadlock. Please note you should try to keep synchronized methods short to minimise the amount of time another thread is held up. This will help improve the responsiveness of your app. For more information on Java synchronization click here.

I hope this information helps some of you out there trying to build your own apps for Android. Many of these tips are also pretty good advice for building Applications using Java and OpenGL on any platform. If you still run into performance problems you should run a debugging tool called a profiler to find out which code is causing the most slow down. It’s quite important to remember the limited nature of resources on mobile devices, and that disposing of objects can come at quite a price in processing power when the garbage collector kicks in.