Boosting Android Apps Performance

While mobile vendor giants struggle to produce the most intellectual device, it appears that a huge amount of users want to buy a device as cheap as possible but still prefer smartphones over old-school feature-phones. This trend is mostly driven by a huge demand from emerging markets such as China and other Asian countries. Sub-$100 Android devices become a significant part of the market. There are rumors that the next version of Android will be aimed at low-end phones market, which means that this trend will continue to emerge.
This trend is leading to a great opportunity for app developers. However, with every great change come new challenges. Low cost devices usually have limited memory, small screen, slow CPUs and other limitations. App developers should care about performance of their code like never before.
There are three basic rules of writing applications with a great performance:

1. Write efficient code.
2. If the code is not efficient - profile and fix it.
3. Continuously ensure that code is still efficient (ideally, after every single commit to your source control system). 

While items 1 and 2 are obvious, item 3 requires additional explanation. Our experience shows that most software developers start to care about performance of their app after users already posted angry comments on Google Play. It comes even harder to track app performance metrics when your app is big and complex and you ship new versions frequently. The problem is that it is much easier to fix performance issue right after it was introduced than in case it is here for a few weeks and tons of code dependent on that issue were written. Of course manual regression testing is inefficient in this case - you simply can’t do it frequently enough. Fortunately, there are things like continuous integration that make it possible to automate this routine and thus detect and fix performance issues as early as possible.
In this document we are going to focus on items 2 and 3, as the art of writing efficient code is bit complicated for a single publication.

Performance Optimization

Performance tuning of every Android application differs from application to application. However there is a general flow. It looks like this:

This is the so-called measure-evaluate-improve-learn cycle. This process can be applied to a variety of life activities. When tuning Formula 1 car, the same technique would be used. You just need different tools.
To start the optimization cycle we need to learn about the problem This can be done in the beginning of development, after manual testing with unsatisfactory performance results. This can be a report from CI tool, which was triggered after unsafe commit. This can also be a report from users on Google Play with complaints about low performance on specific device. Such an optimization may be needed before implementing new features, which is dependant on existing, not-fast-enough functionality.
After we learned about the problem we start the optimization. In order to improve performance, we need to identify the problem. And this is the place where measuring comes handy. Android SDK has built-in capabilities for profiling. With the help of traceview and DDMS one can profile and analyze performance of the application. Apart from that, measuring is helpful for automation of testing process, by giving determined data for comparison.
After the measurements are done, detecting the bottleneck is pretty straightforward. When the problem is found, it’s time to fix it by optimizing the code. That’s where you would need all your creativity and knowledge of the domain. If you know some hardcore techniques and cheats which still maintain the sustainability of code, try them! In case of Android, think about NDK and RenderScript usage. Good idea is to check how often GC is called inside your app. On low-cost devices heap size can be surprisingly small, which will lead to often garbage collection and therefore low responsiveness. Good practice is reusing memory, instead of allocating new blocks. Also in case of intensive IO operations, asynchronous reads/writes are a must, and probabilistic variations of algorithms together with intelligent caching techniques can save the day.
After each step of improvements we should again test the application, i.e. learn if the problem is fixed. If the results are not satisfactory, the process goes all over again until the problem is gone.
Performance optimizations usually involve a decent amount of refactorings. In order to make refactorings safe it’s a good practice to cover code with tests. In this case Continuous Integration tools can greatly simplify testing and maintenance job.

Continuous Application Support

Rome wasn’t build in a day. Even though people can make alpha mockups of applications in several days, a good application needs a lot more time to become mature.
When you own 1 application, you can choose couple of target devices and test your app on them. If you have 2 apps, you need twice as much time to test everything by hand. If you are an established mobile development company with a big mobile portfolio, costs for manual application testing can blow up your budget. Moreover, it’s hard to track how all the apps evolve over time.
Continuous Integration tools automate the process of application testing, deployment and maintenance. They help finding bugs early, save time and money during the lifespan of the project.
In case of Android projects, CI tools have proven their effectiveness, especially when there is a need to test applications on a variety of configurations. Currently, the most used CI for Android is Jenkins. It has an active and vibrant community of users, lots of useful plugins and is easily extensible.
Below is the proposed architecture for the private continuous integration testing environment, based on Jenkins CI:

This environment would allow:

• testing multiple device configurations
• tracking multiple projects
• measuring test execution performance over time
• analysing source code on every commit
• finding android lint issues
• automating deployment tasks

Actually, there’s almost no limit for the Jenkins CI improvements and customizations. With the help of custom plugins this system can be enriched with various kinds of actions, which automate daily DevOps routines.
Of course, there is no silver bullet and implementing CI environment also needs a lot of resources, intelligence and of course people. Tests have to be implemented by people who have programming skills, testing infrastructure has to be set up and maintained by an administrator, and whole environment needs additional hardware and software expenses.  The effectiveness of automation start to show off after certain amount of manual work redundancy, which is often the case with Android development.

Conclusion

Keeping up with fast-changing industry standards is far from trivial. Supporting thousands of different devices with different OS versions each is indeed not easy. Supporting several apps for this market is even harder. Keeping it all fast is close to impossible. Maintaining this with every new release or bugfix is a pure nightmare. Without a right tool.
Implementing functionality changes is very similar to production of goods on factory. Every good, as every update, is designed with accuracy and intelligence. But before reaching end users each one of them passes same strict quality control, keeping the production massive, continuous and reliable.

by Ostap Andrusiv, Victor Haydin and Markiyan Matsekh

A short note on automatic differentiation

Do you remember your undergraduate calculus course? Frankly speaking, I don’t. But I do remember a big blackboard completely covered in chalk scribbles. That was a nightmare! Hopefully, those times are gone. I mean, why would we care about derivatives now?

Here at ELEKS, we do care about derivatives. We create and deliver precise models of various dynamic processes. The application field doesn’t matter: it may be physics, finances, or biology. What really matters is once you need to simulate something – most likely you’ll need to compute derivatives. And you need to compute them fast and with great precision. Thus, we created ADEL – a C++ template based-library that fits our needs. But let’s start with some background information.

The requirements listed above do not allow for solutions such as symbolic derivation or finite difference schemes. The first approach generates the exact formulae for derivatives of all levels and directions. This is a very memory/time consuming method. It produces enormous formulae. While the second one computes the numerical approximations of the value of a derivative. These suffer from various round-offs, cancellation and discretization errors.

Fortunately, there is a middle ground – automatic differentiation (AD). The way it computes derivatives is essentially through a chain rule. It generates evaluations (but not formulii) of the derivatives. As the result, there are none of the drawbacks(accuracy loss) of numerical differentiation where the step size needs to be carefully chosen to avoid errors. All intermediate expressions are evaluated as soon as possible; this saves memory, and removes the need for later simplication. Moreover AD is not as complicated as symbolic representation.

There are two modes of automatic differentiation – the forward mode and the reverse mode – both use different directions of the chain rules to propagate the derivative information. There are two main implementations of automatic differentiations:

Operator overloading is straightforward and easy to understand – one overloads the operators not only to compute function values but also to compute derivative information or build up the computational graph. 

Source transformation works like a compiler, which reads in the code that computes the function, analyzes the code and exports a source code that computes the derivatives. This implementation normally generates more optimized programs but involves a lot of implementation efforts.

ADEL contains the implementation of operator overloaded versions of both forward and reverse modes. This is an open source project; one may find all the required materials at: https://github.com/eleks/ADEL.

The main feature of ADEL’s forward mode is careful handmade optimization. Template based implementation with loop unrolling is compiled into very efficient sequential code. This implementation suits GPU computing architecture very well. The support of CUDA makes the solution truly unique.

The reverse mode of the ADEL library is special in the way it stores the computational graph. It uses the stack of the application for this purpose. Each overloaded operation creates the data structure that is placed on the top of the stack; the life-time of these structures is just enough to compute the derivative data. This makes the algorithm extremely efficient since the most of the operations could be inlined.

We compared our implementation with some of already existing solutions in order to see how it stands up against the others. We implemented Newton’s method for testing the accuracy of our tools. For testing the performance, a random expressions generator was used. It is capable of generating some monstrous things (your professor would never dream of such things). Here is an example of a test function:

template<typename ADType>

ADType TestFunction(const ADType(&x)[6]) {

  y[0] = x[1]; y[1] = -2.730; y[2] = 4.555;

  for (int i = 0; i < 1000; i++) {

    ADType y[3];

    y[0] = x[1]+x[5]+4.624/x[0]+(x[3]-y[0])/x[4]+(atan(-y[2])-x[2])*y[1];

    y[1] = (sin(y[1])-y[2])/x[2]/x[4]*(x[3]+log(x[0])/(y[0]-x[5]))+x[1];

    y[2] = atan(x[5])*(-y[2])/x[3]/(x[4]/(x[2]/x[1]+acos(y[1])))*y[0];

  }

  return 2.658/log(x[0])*(log(y[2])/x[4])*(x[1]+x[5])*(y[0]/y[1])*x[3];

};

The main characteristic of the test case is the number of independent (x) and dependent (y) variables as well as total number of functions/operators. The given task was to compute the gradient and hessian of the return value with respect to all independent variables. In the example above, we have 6 independent and 3 temporary (dependent) variables that produce a single output. 

We tested the following third-party AD implementations:

FADBAD (http://www.fadbad.com/fadbad.html) – a lightweight, user-friendly library. We used a combined mode: the gradient was computed via the reverse mode, while the hessian – via the forward mode.

ADOL-C (http://www.coin-or.org/projects/ADOL-C.xml) – a huge math package that is capable of computing literally everything. The reverse mode was used in the experiments.

There were four test cases of differing sizes with 5/10/20/30 input and 1/5/10/15 intermediate variables. The results were normalized, in such way that the slowest execution was scored with 100 time units, therefore less is better.

Looking at the results one can see that we did not create an ultimate AD tool - not yet. In smaller tests both ADEL modes greatly overrun their rivals. When the number of variables increases, the performance of ADEL [Forward] degrades because of the large memory overhead per variable. ADEL [Reverse] shows the best average performance; FADBAD comes second; ADOL-C received no prize at all.

Automatic differentiation is a very promising but extremely underused tool. The majority of the community still does not recognize it. This article is just a small but solid step into the bright future of AD tools. As a final word, we encourage you to download the source code and to experiment with ADEL on your own. If there is something we can improve, feel free to contact us.

Games Localization – Mind the pitfalls

When working on the adaptation of the game, we keep seeing the same issues, which mostly result from bad game internationalization. Open source projects are the most notable example.

Internationalization bugs are usually caused by the fact that the game was not even considered to be localized in future. This is where the troubles for localization engineers start. It does not necessarily mean that it is impossible to adapt these games for other locales, but it makes the localization much more difficult.

As it often happens, if the game was developed without localization in mind, the whole localization process becomes not just a mere translation of text strings and fixing geometry bugs or adapting the graphics. It is an incredible process of looking for work-arounds at different program levels.

As a rule the internationalization problems require attention of developers to avoid extra complicated fixes multiplied by the number of target languages.

In particular, I would like to draw your attention to the following types of problems:

•          Hardcoded strings. These are texts coming from the functional part of the game that are visible to users. Even having access to the source code but without knowledge of the whole project structure, it is difficult to get the hardcoded strings translated without the risk of bugs which will be caused by this translation.
•          Regional settings support. This presents the most painful issue: support of fonts, correct displaying of regional standards for dates, units etc.
•          The last point worth highlighting is the separation of functionality and UI parts. Otherwise the engineering of localized files will become a headache for localization engineers.

Please keep in mind that even if you work on the realization of the fantastic idea and want to implement it as quickly as possible, do not forget that this great game may get so popular that users from other locales would want to play it too… in their native language.

by Ihor Kuznietsov

Senior Localization Engineer

Scaladroids: Developing Android applications using Scala

Scala is a functional and object-oriented programming language. It is statically typed and designed to concisely express your programming ideas in an elegant, type-safe and lightweight manner. Moreover, Scala compiles down to Java bytecode. This allows Scala applications to leverage the usage of existing Java libraries.

On the other side, Android is one of the most popular mobile operating system nowadays. Android applications are usually developed with Java. Source code compiles down to JVM bytecode and later gets translated into Android's 'dexcode'.

Why not try combining both of the technologies?

The presentation below explores the ways in which Scala can be applied to Android development. Look inside and comment, how you leverage the power of Scala!



Presented by Ostap Andrusiv, Software Engineer during Android Developer Days 2013 in Ankara.

Parallel Testing in Action

At ELEKS we tried out an alternative approach to testing localized software product versions, called Parallel Testing.  

This time we tried parallel testing approach for game localization testing. It is a very simple online game, called "Cut the Rope" which is localized into English, German and French languages. The results were impressive!

The main challenges in game localization testing are: context issues and content preparation for linguistic review. Parallel testing helped to overcome the challenges. It allows to capture screen shots and video of entire game in just one round.

Anyway, see it for yourself in this short demo video:) 

by Nazariy Popov, R&D Expert, Localization

Introducing Intel Xeon Phi - hardware and installation

Few days ago we have got Intel Xeon Phi 5110P Coprocessor - 60-core x86 accelerator that is direct competitor of GPGPU on HPC market and is based on Intel Many-Integrated Core (MIC) architecture.
As Xeon Phi is a quite new piece of hardware there are very few information in the Internet regarding its usage, installation and compatible hardware (especially motherboards). We would like to fill that gap and write about our experience of assembling custom server with Xeon Phi installed.
Technically, Xeon Phi looks very much like high-end 2-slot PCIe graphics card, except of the fact that it doesn't have DVI output on its back. We have 5110P model with passive cooling, hence there are models with active cooling. Without additional cooling there might be some temperature issues, so make sure that you have a case with additional cooler. Our server case has additional cooling installed and is placed in server room with powerful air conditioning, so no problems for us there.
Not every single motherboard can support this kind of accelerator. The trick is that it has to support 64-bit PCIe addressing and you can find this feature only on modern high-end motherboards. As Intel doesn't have official list of supported motherboards it could be quite tricky to choose motherboard for your Xeon Phi server, in case you buy it separately and assemble by yourself. We managed to run the accelerator with ASUS P9X79 WS motherboard (thanks ASUS for clear information that it supports Xeon Phi). Our motherboard had outdated version of BIOS, so we had to flush the latest version and change settings there in order to enable Xeon Phi support. If you visited a link above you might have noticed a statement that it supports only Xeon Phi 3100 series with active cooling, but in fact it works perfectly with 5110P, just don't forget about additional cooling in your case.
At peak loads Xeon Phi 5110P consumes 225W of power. 3100 series devices use even more, up to 300W, so make sure that your power-supply unit is able to feed it with that amount of energy.
Officially Xeon Phi works only with RHEL and SLES, but in our case it works perfectly with CentOS (open source clone of RHEL).
We are going to write more posts about Xeon Phi very soon. Stay tuned!

Parallelism in Testing – To Be or Not To Be?

Today I would like to uncover the topic of parallel testing in context of test automation approaches: its potential benefits and possible scenarios.

So let’s dwell on the matter of test automation as we know it.  What can we call a common benefit on this regard?  The most obvious one can be referred to as “resource savings”.  How about we stop for a minute and try to define the tasks that are most frequently automated.  These can be – repetitive inputs, UI navigation, performance measuring, etc.  The next point would be the product areas which are eligible for the automation itself.  In case when one has to achieve 100% test automation coverage, he/she may claim – “It is possible to automate every bit of the program functionality!” – fine by me, but is it reasonable?  Is it worth spending hours of work to produce an automated test that will be run only once or twice, but can actually be tested manually in just a few minutes?  Don’t expect a unanimous answer, but in majority of such cases - resources spent are not worth results provided.  Another point that can be hard to overcome during the automation tests implementation is the maintenance of test cases.  This problem mostly affects products that tend to change frequently during the development process or during the product lifecycle. 

Speeding up MR Image Reconstruction with GeneRalized Autocalibrating Partially Parallel Acquisitions (GRAPPA)

This time we would like to share some details about realization of one of our projects in medical imaging.
Currently one of the bottlenecks in MR image reconstruction is speed improvement. Improving the speed of image reconstruction is difficult from algorithmic point of view. But it’s becoming more popular to improve algorithm performance using GPU.

Introduction

In magnetic resonance (MR) image reconstruction raw data measured from the scanner correspond to the Fourier coefficients of the target image, so the fast Fourier transform (FFT) is used for reconstruction. An important procedure called the density compensation is necessary in the very beginning to account for the non-uniform sampling. GeneRalized Autocalibrating Partially Parallel Acquisitions (GRAPPA) is a partially parallel acquisition (PPA) method which is used to reduce scan times. In this case only partial data is acquired and missing data is mathematically calculated from available data.

Subject for optimization

Original implementation was based on FFTW library for Fast Fourier transforms and adapted Singular Value Decomposition (SVD) algorithm from ACM Collected Algorithms for GRAPPA preprocessing. These two algorithms are the most computationally intensive parts of the whole image reconstruction. FFTW library is claimed to be the fastest CPU implementation using all possible optimizations like SSE2/3 and hyper threading, however it does not leverages the power of modern GPU cards. SVD algorithm was done on CPU as well. It is known to be badly parallelizable for small matrices, but in case of GRAPPA algorithm we have many image frames with same size which can be processed in parallel. Besides there are many intermediate steps which consume a lot of CPU and they can be easily parallelized on GPU.

Technical analysis

FFTW library performance is comparable with Intel MKL implementation. NVidia provides comparison for their CUDA based cuFFT library with MKL implementation (Figure 1):

Figure 1 Comparison of CUDA based cuFFT library with MKL implementation

According to this we should achieve up to 8-10x faster FFT processing  when using GPU accelerated cuFFT library from Nvidia. GPU accelerated SVD algorithm is also available, for example CULA library by EM Photonics. However, current CULA library implementation does not support batch mode, so we will need to process all image frames as a sequence. Brief testing showed that 64 image frames (256*256) are processed even slower than CPU based version. Since we haven’t found any good alternative to CULA library we decided to implement our own GPU accelerated version of SVD algorithm.

Implementation

FFT part of image reconstruction when using cuFFT library was straightforward, however we had to deal with image frames which does not fit into available GPU memory. We had to write algorithm to run FFT over portions of the large data frame with subsequent aggregation. Figure 2.1 below shows case when all data fits into GPU memory.

Figure 2.1 

Figure 2.2 illustrates the case when huge data is processed. Solid lines in figure below show measured performance, dashed lines show estimated time in case data fits into GPU memory.

Figure 2.2

Much more interesting was to implement GPU accelerated SVD algorithm with batch mode. All implementations we had found are focusing on maximum parallelization of a single SVD run, hence we had to change approach. Basically SVD algorithm consists of HouseHolder Reduction, QR Diagonalization and Back Transformation steps. All are iterative processes when next step depends on results from previous step. In case of small matrices each CUDA kernel can’t effectively utilize all parallel processing units of modern GPU. So we had to write kernels in a way when every iteration for all matrices is processed by a single kernel run. This way in case of 64 matrices with 128x128 size each we can process 64*128 elements at a time instead of 128. Figures 3.1 and 3.2 show performance comparison for CULA Library and our implementation. 

Figure 3.1

Figure 3.2

With more than 8 frames per batch our implementation shows much better performance comparing to sequential CULA calls, although it is not so efficient for a single frame.

Results

As a result we have developed a pure C++ library with a set of specialized functions which perform various stages of image reconstruction. It requires only CUDA runtime libraries and free cuFFT library provided by NVidia. In addition we have implemented lightweight C# wrapper for convenient usage. Also we have run a lot of benchmarks with various GPU cards and on different platforms. On test cases provided by customer we received up to 150x speedup comparing to original single-threaded CPU implementation. However significant part of received speedup was due to poorly optimized original code which was completely rewritten and ported to CUDA whenever possible. 

While it is usually understood what FFT stage does in image reconstruction, GRAPPA stage is not so obvious. Due to parallel acquisition of different frames arises distortion of acquired data which is effectively eliminated. Figure 4 shows visual representation of images before and after reconstruction. 

Figure 4 The image before the reconstruction (left), image after reconstruction (right)

Additionally, you can find a case-study on ELEKS website or download it in PDF. Stay tuned!

/by Volodymyr Kozak, Principal Developer, ELEKS R&D

ELEKS open-source projects directory

Even though ELEKS is a software development services company and we mainly develop proprietary software for our customers, we have our own open-source projects and contribute to projects maintained by other people and organizations. We are proud to be a part of the open-source community. Recently we have launched GitHub page where you can find a list of our projects and projects we contribute to: http://eleks.github.io/.
We are going to publish more open-source projects soon. Stay tuned!

20x performance for the same HW price: GPGPU-based Machine Learning at Yandex

Russian search-engine Yandex has disclosed some details about their machine-learning framework, FML. The most interesting detail is that it runs on 80 TFLOPS cluster powered by GPGPU. This is quite unusual application for GPU, as ML algorithms are usually hard to be paralleled. However they have managed to adapt their decision tree algorithm for high-level of parallelism. As a result Yandex has achieved more than 20x speed-up for the same hardware price.
They are going to upgrade their cluster to 300 TFLOPS. Yandex expects its cluster to be in the list of top 100 most powerful supercomputers in the world after that upgrade.