Results tagged “Performance”

At work I regularly stumble across a specific type of processing: sorting a collection/list and afterwards only retrieving the first or last element. Such code constructs are clearly for fetching the minimum or maximum element but sorting the whole collection for just a single item seems to be a bit of overhead. And indeed it is and the Collection class provides methods for these purposes without having to juggle items in memory and creating new collection objects which are never really required.


Advice

If you have a collection and want to retrieve the minimum or maximum element from it you don't have to sort it and retrieve the first or last but java.util.Collections offers its min() and max() methods for that which are much more efficient for that exact purpose. These can also be used with custom Comparators.

Code-Example

Before

// retrieve smallest element
Collections.sort(elementList);
Element smallest = elementList.get(0);    
...
// fetch item with highest custom value
Collections.sort(customItemsList, Collections.reverseOrder(new MyCustomComparator()));
Item largestItem = customItemsList.get(0);

After

Element smallest = Collections.min(elementList);    
...    
Item largestItem = Collections.max(customItemsList, new MyCustomComparator());

Benefit

Readability gain. Possible huge performance gain, as min()/max() run in O(n) while sorting takes O(n log(n)).

Remarks

If the comparison methods (compare(), equals()) do not fulfill the Comparator requirements according to the Java SDK (see here) (i.e. A.equals(B) != B.equals(A) or (A<B)!=(B>A), etc.) then the result of min()/max() may be different than the result from the approach using sorted collections.

|

Happy New Year! I planned to have a blog post finished before 2013 ended but this didn't work out. Hopefully this one compensates that a bit.

A little while ago I began preparing another post in my series of Java Tips. Well, this posting is still due but for now I can present you another one where I give a short look on some investigation the preparation of this Java tip required.

It originated in a couple of Sonar warnings on one of our development systems on my job. Specifically the warning about the inefficient way of converting a number to String spiked my interest and I began evaluating the places where these warnings showed up. The warning itself told that there were conversions of numbers to Strings in the form of

String s = new Integer(intval).toString();

which should be better expressed from a performance point of view as

String s = Integer.toString(intval);

Some time during this investigation I became curious if there is really a large effect between the different solutions and wrote a short test case which measured the time of different ways of converting an Integer to a String. Interestingly it did not exactly turn out as clear as I hoped. Initially it seemed that the error claim did not match the reality as my testcase did not show a clear performance advantage of any specific solution. Most ways of converting values to strings were pretty close to each other and the results varied with each execution a bit so I considered this to be mainly a measuring inaccuracy.

// Results with 100000 invocations of each method, timed using System.nanoTime()
new Integer(int).toString()      : 7075890
String.valueOf(int)              : 6570317
Integer.valueOf(int).toString()  : 9597342
Integer.toString(int)            : 11398929

With those combined results I could have been satisfied and discard the Sonar warning as just some hint to write more readable code. But something didn't feel right and after some time I had another look at this. Especially the last measurement looked quite odd. What was the difference between a static call (line 4) and a method call on a new object (line 1) so that the results are about 25% apart. And if so, why is the static call the slower one? Using the Java Decompiler Eclipse plugin I inspected the underlying source. I could have used the the source search engines available elsewhere (e.g. GrepCode) but that was just too cumbersome for a quick investigation and not safe to reflect the actual (byte-)code used. The decompiled source of java.lang.Integer made the observed difference even more mysterious.

...
public String toString()
{
  return toString(this.value);
}
...
public static String toString(int paramInt)
{
  if (paramInt == -2147483648)
    return "-2147483648";
  int i = (paramInt < 0) ? stringSize(-paramInt) + 1 : stringSize(paramInt);
  char[] arrayOfChar = new char[i];
  getChars(paramInt, i, arrayOfChar);
  return new String(arrayOfChar, true);
}
...

Ok, so the call on toString() on a new Integer object is in turn jumping to the static toString(int) method? In that case my previous measurements must have been influenced by something else than just the sourcecode itself. Most probably some effects from JIT compilation by the HotSpot JVM. And therefore the measurements were not usable until I made the effect of JIT compilation neglectable. What's the easy way of making JIT compilation a neglectable factor in measurements? Crank up the number of iterations of the code to measure. The 100k iterations in my first test ran in a mere seconds, maybe not long enough to properly warm up the JVM. But after increasing the iteration count by a factor of 1000 (taking significantly longer to run) following numbers were the result:

// Results with 100000000 invocations of each method, timed using System.nanoTime()
new Integer(int).toString()      : 6044546500
String.valueOf(int)              : 6052663051
Integer.valueOf(int).toString()  : 6287452752
Integer.toString(int)            : 5439002900

Raising the number of iterations even more did not change the relative difference between the numbers much so I think at that stage JVM and other side effects are small enough to not change the execution speed significantly. It also better fits to my expectations of the running costs when roughly brought into correlation of the execution path, logic executed and functions called of each individual conversion variant.

At that point I'm pretty confident that I now better understand the reasons for the initial Sonar warning and that the static method call is roughly 10% faster than calling toString() on newly created objects. And that's even without burdening an additional Integer object to the garbage collection which at a later stage takes some additional time to clean up.

Of course, I'm aware that this is a topic which dives deep into the micro-optimization area. On the other side it can be boiled down pretty easily to using certain methods in favour of other methods, as there is no drawback on safety or functionality and at the core the same static method will be called anyway. Furthermore, ignoring simple performance and memory optimizations may not affect you on small scale like client applications or Java applets but may be pretty relevant on larger (server) systems or even time-critical installations. For a more detailled description why this is relevant on server systems and how it affects throughput and garbage collection times see this excellent list of Java Anti-Patterns.

|

Yes, it's been a month now since my last entry. I've prepared some more but never came around finishing them because there has been some stuff going on which kept me off the blog until now. Maybe (or not) on that later, this posting is about my experiences with installing and using CyanogenMod 6 RC2 on my HTC Magic.

I tried to keep off custom hacking on my phone for as long as possible but since HTC and my provider won't be offering an update to the current version 1.6 of Android for this phone anymore, I've been looking forward to try out the custom ROM "CyanogenMod" for quite some time now. I've just been waiting for it to include the FroYo-Changes into its content because especially the Just-in-Time compiler was something which I hoped to give my phone a new boost. And now as the second release-candidate of CM6 was out I began to read the instructions how to get the whole stuff done.

It turned out that it's not really that hard to flash a custom ROM onto the HTC Magic. But it's essential to make a backup of the currently installed operating system to be able to restore it if something goes wrong or the new ROM doesn't meet the expectations.

For the flashing itself, I just followed the update instructions on the CyanogenMod Wiki to prepare the phone with the recovery image and to perform the initial backup. After that I just followed the instructions to install CM on the phone, using the latest Cyanogen and Google-Apps images. This was all done in a matter of minutes and after that I was running FroYo.

The very initial impressions were very exciting, a lean and very fast system with a load of options and settings to tweak. Then I began installing all my previously used applications one after another. This took a while because I had forgotten to check all applications for possibilities to back up their data and settings and so I had to flash back the original image and back to CM6 several times. But I didn't bother because it shouldn't be necessary anymore after I'm finished with that.

As time went by and more and more applications were installed I began more often to experience forced-closes where windows and applications just shut down immediately after I've started them. A quick connection with the adb logcat command revealed, that my phone was running extremely low on memory and that was the cause for the shutdown of many applications. Quite a turn-down. Even more so since there were many applications and services in the background, which I didn't want or never used anyway.

The solution to this memory issue was to insert a larger Class6 Micro-SD-card (set me back by 20EUR), reformat it using the corresponding option from the recovery-bootloader and re-writing it with the previously backed up data. After that I used Stevo's scripts according to the instructions for setting up swap on CM5 and enabled system swapping to the SD card.

This gave me another enormous speed boost and no closed applications anymore. Nice! :) I could continue setting up my phone and restoring the settings.

Later on I also applied the CM6 settings suggested by Vermithrax in a custom userinit.sh script (leaning on these instructions) which added a little more performance.

In conclusion, I think I'll keep this setup with CyanogenMod 6, although I'll have to re-flash it at least once more if CM6 final is released. Most of the time it's still snappy and faster to use than the original 1.6-image even if there are a ton of new features and larger applications and multithreading etc. But sometimes it still slows down to a crawl, I wasn't able to track it down to a specific cause so far. I guess it's somewhere rooted in the memory-settings. Have to play around with that a bit or even try to remove some of the pre-installed (and un-installable) applications like this strange "Amazon MP3" tool, which always crawls around in memory.

Yay!

Update 2010-08-18 The last weekend I updated to RC3. Went without a hitch, I just had to re-setup the modifications for 'bootswap20' with Stevo's scripts again and remove the Amazon MP3 tool once more. Just have to get used to the new icons and bootup logo...

|

On to the next Java Tip. Again, this time I'm staying within the boundaries of the Sun JDK.


Advice

When traversing a Map, always use the minimum necessary methods to get keys/values out.
<Map>.entrySet() vs. <Map>.keySet() vs. <Map>.values()

Code-Example

Before

...
 for (String number : phoneBook.keySet()) {
   PhoneBookEntry name = phoneBook.get(number);
   if (name != null) {
...

...
 for (String parameterKey : paramMap.keySet()) {
   Object value = paramMap.get(parameterKey);
...

After

...         
// if only values are needed
for(PhoneBookEntry name : phoneBook.values()) {
  if (name != null) {
...

...
// if key&value are needed
for(Entry<String, Object> entry : paramMap.entrySet()) {
  String parameterKey = entry.getKey();
  Object value = entry.getValue();
...

Benefit

Performance gain. Map is only searched once instead twice (and also the hashing for get() is avoided), or there is only the really required data extracted and returned from the map. Furthermore having only the required data around avoids later confusion on the original intent ("... is the key maybe used somewhere or just a leftover?...").

Remarks

None.

|

And on to the next in a series of Java Tips. While last time the performance gain was very tiny and only affected high-load scenarios, this tip may considerably speed up even simple applications where there is String-processing involved.


Advice

Use StringBuilder instead of + or += to concatenate Strings in non-linear cases (when concatenation not appears immediately one after another), ie. in loops.

Code-Example

Before

  String test = "";
  for(int i = 0; i < 50000; i++) {
     test += "abc";
  }

After

  StringBuilder test = new StringBuilder();
  for(int i = 0; i < 50000; i++) {
     test.append("abc");
  }

Benefit

Huge performance gain! The unoptimized code forces Java to create new Strings and copy the contents around all the time (because Strings are immutable in Java). The optimized code avoids this creation/copying by using StringBuilder. While the Java compiler can optimize linear concatenations, ie.

String test = "a" + "b" + "c";

into using a StringBuilder internally, it is not clever enough to apply this optimization correctly if there is more logic than just concatenation involved. Even if the concatenation is the only operation inside some loop-logic, the Java compiler falls back into creating a whole lot of String (or to be more exact: StringBuilder) objects, copying them around like crazy and causing a huge performance impact in some cases. I confirmed this example for measurement of StringBuilder performance: concatenating 50000 times "abc" in a loop takes ~11000ms, using StringBuilder keeps the time spent at near 0ms. (I tried concatenating with 500000 iterations, but stopped the execution of the first loop after ~10 minutes running unfinished, so the impact is nonlinear. Second loop finished in 15ms with 500000, for the record.)

Remarks

It is not necessary to optimize code like

String email = user + "@" + domain + ".com";

as javac is clever enough for these cases and it would reduce readability considerably. But even with the simplest loops involved the conditions change. For example, internally the first loop gets compiled by javac into following bytecode

 13  new java.lang.StringBuilder [24]
 16  dup
 17  aload_1 [test]
 18  invokestatic java.lang.String.valueOf(java.lang.Object) : java.lang.String [26]
 21  invokespecial java.lang.StringBuilder(java.lang.String) [32]
 24  ldc <String "abc"> [35]
 26  invokevirtual java.lang.StringBuilder.append(java.lang.String) : java.lang.StringBuilder [37]
 29  invokevirtual java.lang.StringBuilder.toString() : java.lang.String [41]
 32  astore_1 [test]
 33  iinc 4 1 [i]
 36  iload 4 [i]
 38  ldc <Integer 50000> [45]
 40  if_icmplt 13

where for each iteration of the loop(13-40) a new StringBuilder is instantiated and initialized with the result of the previous' loop StringBuilders value before appending the constant String just once each time. The optimized code results in this bytecode

 81  new java.lang.StringBuilder [24]
 84  dup
 85  invokespecial java.lang.StringBuilder() [62]
 88  astore 4 [builder]
 90  iconst_0
 91  istore 5 [i]
 93  goto 107
 96  aload 4 [builder]
 98  ldc <String "abc"> [35]
100  invokevirtual java.lang.StringBuilder.append(java.lang.String) : java.lang.StringBuilder [37]
103  pop
104  iinc 5 1 [i]
107  iload 5 [i]
109  ldc <Integer 50000> [45]
111  if_icmplt 96

in which the loop(96-111) just appends the constant String to the same StringBuilder each time which was created only once before the loop started. No copying around and creation of additional objects necessary, thus a huge performance-gain.

| | Comments (2)

As promised last time I'm presenting here the first in a series of Java Tips. To start easy I'll begin with one of the simplest tip to implement.


Advice

Use StringBuilder instead of StringBuffer.

Code-Example

Before

  StringBuffer str = new StringBuffer();
  str.append("foo");
  String x = str.toString();

After

  StringBuilder str = new StringBuilder();
  str.append("foo");
  String x = str.toString();

Benefit

Small performance gain. StringBuilder is a 1:1 drop-in replacement for the StringBuffer class. The difference is that the StringBuilder is not thread synchronized and therefore performs better on most implementations of Java. Even javac internally translates String x = "foo" + "bar"; into a StringBuilder operation (confirmed with Java 1.6.0_18). A small testcase

public static void main(String[] args) {
    long start = System.currentTimeMillis();
    StringBuffer buffer = new StringBuffer();
    for(int i = 0; i < 1000000; i++) {
        buffer.append("abc");
    }
    System.out.println("Time lapse using StringBuffer: " + (System.currentTimeMillis() - start) + " milliseconds");

    start = System.currentTimeMillis();
    StringBuilder builder = new StringBuilder();
    for(int i = 0; i < 1000000; i++) {
        builder.append("abc");
    }
    System.out.println("Time lapse using StringBuilder: " + (System.currentTimeMillis() - start) + " milliseconds");
}

using Java 1.6.0_18 shows that StringBuilder is roughly 100% faster than StringBuffer. Although on my machine this testcase keeps below 100ms for both with one million appends so this won't be the magical solution for most of your performance issues.

Remarks

Even if this tip can be applied in 98% of all cases one has to be sure that the String is used afterwards and the StringBuilder instance does not get passed between several threads. Since StringBuilder is not thread-safe this would be the only case where StringBuffer should be used. And of course it's not the silver performance bullet but just one slice in string-heavy applications.

|

1

Archives