Pages

Friday, December 31, 2010

KeySet vs EntrySet iteration

There is bug pattern in Findbugs tool that states rather obvious thing that needing both the key and value iterating over the map we should use entry set but not the key set. So in similar to the previous post way I want to measure the effect of this inefficiency.

But looking only at state of the art implementations of the equals() and hashCode() methods which are under the hood of working with HashMap (and therefore almost with every Map in practice) is just not very interesting. From the other hand if the hashCode() is well distinctive for various objects but just too long to compute the effect of its extra usage is obvious. So I'll try to bench the using in this case of the most ugly possible but still valid hashCode() method. I.e. the constant number (let it be prime though ещ not to cause the heart attack of someone accidentally looking at this code).

public class EntriesVsKeysIteratingBench {
  public static void main(String[] args) {
    Map<String, String> map = new HashMap<String, String>();
    for (int i = 0; i < 10000; i++) {
      map.put("srt" + i + "key", "str" + i + "value");
    }
    long nanoTime = System.nanoTime();
    for (String str : map.keySet()) {
      String value = map.get(str);
    }
    System.out.println((System.nanoTime() - nanoTime)
        + " with keyset (bare strings)");
    nanoTime = System.nanoTime();
    for (Entry<String, String> entry : map.entrySet()) {
      String key = entry.getKey();
      String value = entry.getValue();
    }
    System.out.println((System.nanoTime() - nanoTime)
        + " with entryset (bare strings)");

    Map<StringContainer, String> map2 = new HashMap<StringContainer, String>();
    for (int i = 0; i < 10000; i++) {
      map2.put(new StringContainer("srt" + i + "key"), "str" + i
          + "value");
    }
    nanoTime = System.nanoTime();
    for (StringContainer str : map2.keySet()) {
      String value = map2.get(str);
    }
    System.out.println((System.nanoTime() - nanoTime)
        + " with keyset (ugly string container)");
    nanoTime = System.nanoTime();
    for (Entry<StringContainer, String> entry : map2.entrySet()) {
      StringContainer key = entry.getKey();
      String value = entry.getValue();
    }
    System.out.println((System.nanoTime() - nanoTime)
        + " with entryset (ugly string container)");

  }

  private static class StringContainer {
    private String value;

    public StringContainer(String value) {
      this.value = value;
    }

    @Override
    public int hashCode() {
      // do not ever do this
      return 31;
    }

    @Override
    public boolean equals(Object obj) {
      // generated by Eclipse
      if (this == obj) {
        return true;
      }
      if (obj == null) {
        return false;
      }
      if (getClass() != obj.getClass()) {
        return false;
      }
      StringContainer other = (StringContainer) obj;
      if (value == null) {
        if (other.value != null) {
          return false;
        }
      } else if (!value.equals(other.value)) {
        return false;
      }
      return true;
    }
  }
}


* This source code was highlighted with Source Code Highlighter.

and the output of this code is:

40545520 with keyset (bare strings)
14589848 with entryset (bare strings)
653681133 with keyset (ugly string container)
1732427 with entryset (ugly string container)

So with less than three-times inefficiency on the really good hashCode() the inefficiency of most ugly possible hashCode() in this inefficient use case reaches ten thousand percent and more.

But there is also some unexpected result. Usage of entryset on the map of ugly hashCoded objects is more efficient then using it on good objects. However this effect is explained by warming up the VM. Here are the results for interchanged benchs:

632880923 with keyset (ugly string container)
6900615 with entryset (ugly string container)
4327640 with keyset (bare strings)
3176151 with entryset (bare strings)

P.S. And the last one - changing the order of iterations over key set and entry set will not change the results ;-)

Happy New Year, by the way.

Plus empty string - not the best way to ensure not nullness

In continuation of the previous post yet another silly benchmark. On Topcoder and in the code at work I have seen such a construction variable (of type String) = variable + "" to ensure that the value is not null. as it leads to creation of the StringBuilder object it is obvious that it is not very optimal. But is just pure performance or a very-very pure performance? Here is a straightforward bench. If someone see why the part without plus should be faster because of some not related to the subject stuff - please leave a comment.

import java.util.Random;

public class PlusEmptyStringBench {
  private static Random r = new Random();

  public static void main(String[] args) {
    long nanoTime = System.nanoTime();
    for (int i = 0; i < 10000000; i++) {
      doWithCheck();
    }
    System.out.println("With check: " + (System.nanoTime() - nanoTime));
    nanoTime = System.nanoTime();
    for (int i = 0; i < 10000000; i++) {
      doWithPlus();
    }
    System.out.println("With plus: " + (System.nanoTime() - nanoTime));
  }

  private static String checkNotNull(String forCheck) {
    if (forCheck == null) {
      return "null";
    } else {
      return forCheck;
    }
  }

  private static void doWithPlus() {
    if (r.nextBoolean()) {
      String local = null + "";
    } else {
      String local = String.valueOf(r.nextBoolean()) + "";
    }
  }

  private static void doWithCheck() {
    if (r.nextBoolean()) {
      String local = checkNotNull(null);
    } else {
      String local = checkNotNull(String.valueOf(r.nextBoolean()));
    }
  }
}


* This source code was highlighted with Source Code Highlighter.


The output of this code is:

With check: 297321208
With plus: 922518553

Wednesday, November 24, 2010

Specifying the size for StringBuilder

Curiously in C# simple string concatenation is faster in some cases than using the StringBuilder class. As far as I understand from the documentation and surfing the net it is not possible in Java as any string concatenation there is substituted by the StringBuilder usage. Here is a little benchmark to measure the difference in using the simple StringBuilder constructor and the constructor with the predefined proper maximum size. It is very rough as it is not even using something other than ints.

  public static void main(String[] args) {
    final int benchScale = 10;
    long[] slowTimes = new long[benchScale];
    for (int i = 0; i < benchScale; i++) {
      slowTimes[i] = slow();
    }
    long[] fastTimes = new long[benchScale];
    for (int i = 0; i < benchScale; i++) {
      fastTimes[i] = fast();
    }

    long slowAv = 0L;
    for (long i : slowTimes) {
      slowAv += i;
    }
    slowAv /= slowTimes.length;

    long fastAv = 0L;
    for (long i : fastTimes) {
      fastAv += i;
    }
    fastAv /= fastTimes.length;

    System.out.println("slow average " + slowAv);
    System.out.println("fast average " + fastAv);
  }

  private static long fast() {
    long now = System.currentTimeMillis();
    StringBuilder s = new StringBuilder(100000);
    for (int i = 0; i < 100000; i++) {
      s.append("*");
    }
    return System.currentTimeMillis() - now;
  }

  private static long slow() {
    long now = System.currentTimeMillis();
    StringBuilder s = new StringBuilder();
    for (int i = 0; i < 100000; i++) {
      s.append("*");
    }
    return System.currentTimeMillis() - now;
  }


* This source code was highlighted with Source Code Highlighter.

The output of this code may vary, but usually it is something like this:

slow average 3
fast average 2

Interestingly, if benchScale local variable is bumped to 100 or higher the output almost always will be this:

slow average 1
fast average 1

compareTo must not use mutable fields

It is a rather common knowledge, that hashcode() and equals() methods must not use mutable fields. There are plenty of examples of breaking this contract on the net here and there. From the second link it is actually clear that the iterator's remove() method (iterator from the HashSet) is based on the hashcode as well as the HashSet's own remove() method. This not a very common knowledge.

And here is another fact with not very widespread awareness of. Implementing compareTo() method from the Comparable interface is as hard as implementing the hashcode method (and if you wish to use all the functionality of TreeSet inherited from the Collection interface it is as hard as implementing the equals() method too).

So here is the rather selfexplanatory code.

  public static void main(String[] args) {

    Set<MyClass> set = new TreeSet<MyClass>();
    MyClass entity = new MyClass("boo");

    for (int i = 0; i < 10; i++) {
      if (i == 5) {
        entity = new MyClass("boo" + i);
        set.add(entity);
      } else {
        set.add(new MyClass("boo" + i));
      }
    }
    System.out.println(set.contains(entity));

    entity.setContent("boo10");

    System.out.println(set.contains(entity));
  }

  private static class MyClass implements Comparable<MyClass> {
    private String content;

    public MyClass(String content) {
      this.content = content;
    }

    public void setContent(String content) {
      this.content = content;
    }

    @Override
    public int compareTo(MyClass o) {
      return content.compareTo((o).content);
    }
  }


* This source code was highlighted with Source Code Highlighter.

Output of this code is:
true
false


P.S. From the source of the TreeSet class it is clear that failures with mutated fields may be "less frequent" than with the HashSet, as the order of elements remain unchanged. I.e. you will be able to operate fully on the mutable object in the TreeSet all the time as long there is the single element in the TreeSet. It is not possible with HashSet. But of cause this is just a curious thing and no logic should be based on that. Here is the proof though (hashcode() and equals() are generated - do not bother yourself to read them ;-)):


  public static void main(String[] args) {
    Set<MyClass> set = new HashSet<MyClass>();
    MyClass entity = new MyClass("boo");
    set.add(entity);
 
    System.out.println(set.contains(entity));

    entity.setContent("boo10");

    System.out.println(set.contains(entity));
  }

  private static class MyClass {
    private String content;

    public MyClass(String content) {
      this.content = content;
    }

    public void setContent(String content) {
      this.content = content;
    }

    @Override
    public int hashCode() {
      final int prime = 31;
      int result = 1;
      result = prime * result
          + ((content == null) ? 0 : content.hashCode());
      return result;
    }

    @Override
    public boolean equals(Object obj) {
      if (this == obj)
        return true;
      if (obj == null)
        return false;
      if (getClass() != obj.getClass())
        return false;
      MyClass other = (MyClass) obj;
      if (content == null) {
        if (other.content != null)
          return false;
      } else if (!content.equals(other.content))
        return false;
      return true;
    }
  }


* This source code was highlighted with Source Code Highlighter.



Output of this code:
true
false

Monday, November 1, 2010

By-ref and by-val passing in Java

On my last job-interview I answered wrong on this question: "Is the passing of arguments is held by value or by reference?". Here is a small example on this topic.

Actually if it is understood once, the one sentence to refresh it all is - All is passed by reference, primitives are passed by value. Of cause immutable objects could not be changed.
public static void main(String[] args) {

    int sampleInt = 1;
    doWithInt(sampleInt);
    System.out.println(sampleInt);

    int[] sampleArray = new int[3];
    for (int i = 0; i < sampleArray.length; i++) {
      sampleArray[i] = i;
    }
    printArray(sampleArray);
    doWithArray(sampleArray);
    printArray(sampleArray);

    String s = "Hello";
    doWithString(s);
    System.out.println(s);

    StringBuilder sampleStringBuilder = new StringBuilder("Hello");
    doWithStringBuilder(sampleStringBuilder);
    System.out.println(sampleStringBuilder);
  }

  private static void doWithInt(int sampleInt) {
    sampleInt++;
    System.out.println(sampleInt);

  }

  private static void doWithArray(int[] sampleArray) {
    for (int i = 0; i < sampleArray.length; i++) {
      sampleArray[i]++;
    }
    printArray(sampleArray);
  }

  private static void printArray(int[] sampleArray) {
    System.out.print("[");
    for (int i = 0; i < sampleArray.length; i++) {
      System.out.print(sampleArray[i] + ", ");
    }
    System.out.println("]");
  }

  private static void doWithString(String s) {
    s += " world!";
    System.out.println(s);
  }

  private static void doWithStringBuilder(StringBuilder sampleStringBuilder) {
    sampleStringBuilder.append(" world!");
    System.out.println(sampleStringBuilder);
  }


* This source code was highlighted with Source Code Highlighter.

Output of this code:

2
1
[0, 1, 2, ]
[1, 2, 3, ]
[1, 2, 3, ]
Hello world!
Hello
Hello world!
Hello world!

Referencing system property in Spring XML config

It have took me quite a bit of time to found this way. So I've decided to write it in some publicly available place and remembered that some time ago I've created this blog. I think it is the proper place. And also in the official documentation this is done with creating two beans - I've done it with only one.


<bean id="javaTmpDir" class="org.springframework.beans.factory.config.MethodInvokingFactoryBean" autowire-candidate="false">
  <property name="targetClass"><value>java.lang.System</value></property>
  <property name="targetMethod"><value>getProperty</value></property>
  <property name="arguments">
   <list>
    <value>java.io.tmpdir</value>
   </list>
  </property>
</bean>


* This source code was highlighted with Source Code Highlighter.

First message in blog is usually something ugly. I hope that possible future posts will be more  curious ;-)