RenderScript in Android - Java optimization in the benchmark program

I got into discussion with Michael Leahy with regards to the benchmark program posted at the end of the previous post. Michael claimed that the Java implementation of the benchmark algorithm in my test program is suboptimal and he contributed an optimized version that he claims could deliver 70% better performance. 

Therefore I decided to re-evaluate the benchmark results - but with a twist. Not only I added Michael's optimized Java implementation but I optimized the RenderScript implementation too. The results are the following.

• Michael's implementation did improve the execution time of the Java implementation by about 2.6 times.
• RenderScript implementation is still about 2.3 times faster than Michael's optimized Java implementation.

The new version is available here. I will continue with explaining this example program in the next post.

RenderScript in Android - the benchmark program

The previous post of this series tried to present argument, why it is a good idea to consider implementing part of your code in RenderScript, instead of Java or native code. This part presents a benchmark that we will use to evaluate the technology. I intentionally chose the benchmark not to be an image manipulation algorithm or a convolution filter. I wanted a use case that processes large amount of data. Sound processing yields itself as a quite evident choice.

The algorithm I am going to present is quite naive and would require a lot of refinement for commercial deployment. But my goal was RenderScript benchmarking so the algorithm's tolerance to all kinds of environmental disturbances was not relevant. We will do voice fingerprinting that takes a voice sample array, compares this sample to a reference sample and returns true or false depending on whether the voice sample is sufficiently similar to the reference sample. The algorithm should return true if the voice sample contains the same word from the same speaker, false otherwise.

I implemented Dynamic Time-Warping (DTW) for the purpose. DTW compares two data series assuming that the timing between the two series may be different. For example the same speaker may say the same word with slightly higher pitch. Therefore DTW calculates a so called warping path, a pair of corresponding timestamps from series1 and series2. E.g. a part of a warping path may be (1,1), (1,2),(2,3),(3,3) meaning that a[1] (data at index #1 from series1) corresponds to b[1], a[1] corresponds to b[2], a[2] corresponds to b[3] and a[3] corresponds to b[3]. Knowing the warping path and a cost function, the distance between the two series can be calculated. DTW finds the warping path with the lowest cumulative cost (i.e. the sum of cost between the corresponding data items along the warping path). A detailed introduction to the algorithm can be found here.

This example program implements classic DTW calculating every possible pairing between the data items of the two series. This requires an NxM matrix where N is the size of series1 and M is the size of series2. DTW(i,n) (element at position (i,n) in this matrix) is the accumulated cost value (sum of the cost function values) of the optimal warping path that leads through the position at i,n. (i.e. with assuming that index i in series1 and index n in series2 correspond to each other). The function calculating DTW(i,n) is thus:

DTW(i,n)=min(DTW(i-1,n),DTW(i-1,n-1),DTW(i,n-1))+c(i,n)

where c(i,n) is the cost between a[i] and b[n]. The example program uses

c(i,n)=abs(a[i]-b[n]))

Cells at the edge of the matrix are initialized like

DTW(i,0)=sum(c(i,0))

and

DTW(0,i)=sum(c(0,i))

Classic DTW can require a large amount of space. Take for example a short voice sample. With a sampling rate of 44100Hz/5=8820Hz, even a short word can generate easily a vector of 5000-8000 elements. If the reference vector is of a similar size, the DTW matrix will consist of 25 million to 64 million elements, all of them integer (meaning 4 bytes each). A data item of that size may easily exhaust the fixed maximum process space allocated to Android applications. Therefore we do a simple optimization. The output of our algorithm is the optimal distance which will be found at DTW(M,N), the right-bottom element in the matrix. In order to calculate elements in row i, we need only elements in row i-1 plus the already calculated elements in row i. We can drop row i-2 and calculate DTW(i,0) on the fly, when we get there. This will reduce the memory requirement to 2*M data items instead of N*M.

DTW, however naive its application in the example program, satisfies our RenderScript benchmark needs because

• The kernel function is non-linear, it is not so evident to break it down to sub-ranges (although FastDTW does precisely that).
• Calculation of matrix cells depend on an intermediate result of the calculation and not only on the input values.

The example program is available here. The application exercises the DTW algorithm on speech samples. Launch the application and record a reference sample. E.g. record a word like "four". Then record a same or different word from the same or different speaker and observe the distance that DTW calculates. If the environment is not too noisy, you will find that same word from the same speaker yields a (normalized) distance below 1000-1200 while other words from the same speaker or the same word from a different speaker yields higher distance. The calculation takes a bit of time because the DTW algorithm is executed twice, once in Java and once in RenderScript. The application displays the execution time for both implementations.



For now, you can observe that RenderScript execution times are 4-5 times smaller than Java execution times even (Update: visit this post for an updated number. After optimization, RenderScript is still 2.3 faster). though the implementation does not exploit any parallelization features. I will go deeper into this observation in the next post.

RenderScript in Android - why should you care?

Before 3.0, Android application development meant either using the SDK - which is a Java toolchain - or the NDK - which is a C/C++ toolchain based on the gcc compiler. The 3.0 version added a third option, RenderScript. RenderScript was positioned as an auxiliary toolchain for special tasks like image manipulation operations. In this post I will investigate whether it makes sense to use RenderScript for more mainstream coding problems.

If you search the web for RenderScript, you won't get too many hits. This is due to the fact that RenderScript is really just the Google name for the technology which is based on two powerful software packages: the clang compiler and the LLVM "virtual machine". Clang is a C/C++ front-end compiler and is a strong challenger to gcc. RenderScript code is processed by clang and is turned into LLVM bytecode. LLVM is not a virtual machine in a strong sense as it does not "execute" this bytecode. Rather, it provides a second compilation step when it turns the LLVM bytecode into machine code of the target processor.

Much like Android's new runtime, the ART, LLVM is an Ahead-of-Time compiler. The second compilation step either happens on the developer's machine or directly on the device. The first option means that the Clang-LLVM toolchain generates code for 3 processor families: ARM, MIPS and Intel so your APK file already contains native code generated from RenderScript code for these processors and no further compilation is needed on the device. RenderScript code may run on graphical co-processors and other DSPs, however. In this case the on-device LLVM compiler accesses the LLVM bytecode which is also packaged into the APK file and may generate code for these specialized processors at install time.

 So if you write RenderScript instead of native implementation with the traditional NDK toolchain, you get the performance of the native code, support of many processor architectures including more exotic GPUs and DSPs without any hassles, get a simpler integration with the Java code and a much smoother integration with the Eclipse developer environment.

RenderScript appeared in Android 3.0 and supporting Java packages reside under the android.renderscript hierarchy. This is called native RenderScript. Google, however, backported the feature to Android 2.2 (and higher) and this backported version is now the recommended way. Instead of being part of the platform, RenderScript support now resides in a support library and is under the android.support.v8.renderscript package hierarchy. Functionality of android.renderscript and android.support.v8.renderscript are largely similar.

Even though the RenderScript runtime is general-purpose, Google positions the technology as a solution for specific tasks. The RenderScript tutorial, for example, concentrates mainly on the filtering runtime that executes a RenderScript function - so called "kernel" - on a large number of data items. This assumes a certain class of algorithm, i.e. when the output of the algorithm depends solely on the input and not on some intermediate result of the computation. Simple convolution filters (e.g. the 2D filters used widely for image filtering) are such algorithms and therefore they are very suitable for parallel execution on multiple CPU cores. We will see, however, that RenderScript can be exploited to speed up algorithms that do not fit into this computation model.

In the next post I will present our benchmark program.

Podcast of my Droidcon London 2013 presentation

For those who prefer the live experience to the presentation, here is the podcast of my Droidcon London 2013 presentation titled "Sensor Fusion Between Car and Smartphone".

Sensor fusion between car and smartphone

My presentation at Droidcon London 2013.

Sensor fusion between car and smartphone from Gabor Paller
See also on Researchgate!

Converting classes with the Parcelable protocol

Many good tutorials can be found about the Parcelable protocol in Android. If the Android framework has to serialize a set of values (either for AIDL-based IPC or for Intent-based message passing), it can serialize basic types or objects that implement the Parcelable protocol. In short, Parcelable objects are able to serialize their states into a Parcel object and they can retrieve their state from the serialized form.

But what happens if the two classes (the one which is serializing and the one which is retrieving its state from serialized form) are not the same? If you remember my post about classloading in Android, there is no way loading a class from another APK. If you pass a serialized object to another application whose codebase comes from a different APK, the target application has to rely on its own version of the class with the same name. Android framework does not verify that the sender and receiving classes are the same, they just have to have the same name (including package name).

Click here to download the example application.



There are two apps in the package. Actually, it is one of my first example programs, here is the description from a 2007 post of this blog. There are two applications, intentsender and intentreceiver. Intentsender has an internal intentreceiver plus it can talk to the external intentreceiver app. Both applications have a version of aexp.data.TwoNumbers class. In this example they are just slightly different - they log different messages.

What happens when you click on the "exp / int" (explicit Intent with internal intentreceiver) button. Both of these activities are residing in the intentsender APK therefore the class which will be used to serialize and deserialize the object are the same.

D/TwoNumbers1( 1090): serializing in TwoNumbers#1: i1: 2; i2: 3
D/TwoNumbers1( 1090): deserializing in TwoNumbers#1: i1: 2; i2: 3

But if you click on the "exp / ext" (explicit Intent with external intentreceiver) button, the message has to pass the APK boundary (it is processed in the intentreceiver app). Intentreceiver has nothing else but its own version of aexp.data.TwoNumbers. The log demonstrates it:

D/TwoNumbers1( 1207): serializing in TwoNumbers#1: i1: 4; i2: 5
D/TwoNumbers2( 1166): deserializing in TwoNumbers#2: i1: 4; i2: 5

Android framework did not care that the two TwoNumbers classes were not the same, it just called them blindly to serialize and deserialize. Actually, if you look into the Parcel implementation, you will see that the serialized version of the Parcelable only stores the fully qualified class name so it is not surprising that intentreceiver loaded whatever version of the class it could find under the given name. Fortunately, the two versions were compatible (they produced and consumed the same serialized stream) so there were no problems.

Why is this useful other than misleading yourself with classes that look the same but they aren't? If you want to expose just part of your serialized object to the receiver application, this trick comes handy. Otherwise it is best to avoid it.

Tap detection supported by the gyroscope

Once upon a time I made a Londroid presentation that briefly mentioned the possibility of detecting taps on the phone's body with an accelerometer (it is in slide 31). You may rightly ask, why do you want to detect taps with the accelerometer when there is the touchscreen? First, the touchscreen may be switched off by the screensaver or the user may have deactivated it because he or she is in a call or put the phone into a position where the touchscreen may be touched unintentionally. Then the user may want to tap the back of the phone. Lastly, the user may be interested in the strength of the tap, not only its location or the fact that the tap happened.

Let's recall that graph in that old Londroid presentation.



The graph shows the absolute value of the acceleration vector while the phone's body was tapped twice. The base rate is the gravity acceleration (about 10 m/sec^2) and the acceleration caused by the taps was added (in the actual configuration, subtracted) from the gravity acceleration, resulting two characteristic spikes.

But where was the phone's body tapped? By looking solely on the accelerometer's data, I don't think there is a way to find it out. But fortunately we have other sensors and the gyroscope is particularly relevant. Here is the well-known image of the sensor axes in Android.

In case of the gyroscope, the sensor measures rotation around the axes. If you tap the device in the right lower corner, we can expect a short rotation around the x and y axes if the phone supported by a reasonably flexible base (e.g. a human hand and not a block of granite).

But can this be really detected? I made a series of measurements to prove it. Note here that I was just interested in the theoretical possibility and did not want to do a product-grade implementation. So I tested only on my Galaxy Nexus.

First here is the absolute acceleration value for 3 consecutive taps.

As expected, the time of the tap can be safely detected. These taps were all in the lower right corner so let's see what the gyroscope measured along the x and y axes.

X axis, just for two taps:



Y axis, just for two taps:



As you can see, the taps are detected by the gyroscope too as short rotations. In case of both axes, there was a spike of positive rotation velocity first.

Now let's see what happens, if we tap the lower left corner.

X axis, just for two taps:

Y axis, just for two taps:

As you see, the X graph has the same character but the form of the Y graph has changed. Instead of a marked positive spike, there is a small negative spike, followed by a positive spike.

Let's see if the experience is repeated in the upper left corner.

X axis, just one tap:

Y axis, just one tap:

Now the character of the spikes on both axes changed. A small positive spike is followed by a large negative spike.

This is not a kind of movement the gyroscope was designed for so it is premature to state that this waveform pattern will be exactly the same for all the Android devices sporting gyroscope out there. But I found these measurements convincing enough to support the statement that it is possible to implement rudimentary tap location using only the accelerometer and the gyroscope in the device.