Tag Archives: Java 8

String deduplication feature (from Java 8 update 20)

by Mikhail Vorontsov

This article will provide you a short overview of a string deduplication feature added into Java 8 update 20.

String objects consume a large amount of memory in an average application. Some of these strings may be duplicated – there exist several distinct instances of the same String (a != b, but a.equals(b)). In practice, a lot of Strings could be duplicated due to various reasons.

Originally, JDK offered String.intern() method to deal with the string duplication. The disadvantage of this method is that you have to find which strings should be interned. This generally requires a heap analysis tool with a duplicate string lookup ability, like YourKit profiler. Nevertheless, if used properly, string interning is a powerful memory saving tool – it allows you to reuse the whole String objects (each of whose is adding 24 bytes overhead to the underlying char[]).

Starting from Java 7 update 6, each String object has its own private underlying char[]. This allows JVM to make an automatic optimization – if an underlying char[] is never exposed to the client, then JVM can find 2 strings with the same contents, and replace the underlying char[] of one string with an underlying char[] of another string.

That’s done by the string deduplication feature added into Java 8 update 20. How it works:

Continue reading

String switch performance

by Mikhail Vorontsov

Suppose we have a large number of commands. For simplicity of writing this article, they all would be implemented as methods of one class. We should be able to call any of these commands by a string name. We will allow case-insensitive calls. Our “class with commands” would look like:

1
2
3
4
5
6
7
8
9
10
public class ObjectWithCommands {
    public Object Command1( final Object arg ) { return arg; }
    public Object Command2( final Object arg ) { return arg; }
    ...
    public Object Command9( final Object arg ) { return arg; }
    public Object Command10( final Object arg ) { return arg; }
    ...
    public Object Command99( final Object arg ) { return arg; }
    public Object Command100( final Object arg ) { return arg; }
}
public class ObjectWithCommands {
    public Object Command1( final Object arg ) { return arg; }
    public Object Command2( final Object arg ) { return arg; }
    ...
    public Object Command9( final Object arg ) { return arg; }
    public Object Command10( final Object arg ) { return arg; }
    ...
    public Object Command99( final Object arg ) { return arg; }
    public Object Command100( final Object arg ) { return arg; }
}

This article will check the performance of various ways of calling these commands.

But first of all, a quiz 🙂 Suppose you are going to call your commands using the following class:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class EqualsIgnoreCaseCaller {
    public static Object call( final ObjectWithCommands obj, final String commandName, final Object arg )
    {
        if ( commandName.equalsIgnoreCase( "Command1" ) )
            return obj.Command1( arg );
        if ( commandName.equalsIgnoreCase( "Command2" ) )
            return obj.Command2( arg );
        ...
        if ( commandName.equalsIgnoreCase( "Command99" ) )
            return obj.Command99( arg );
        if ( commandName.equalsIgnoreCase( "Command100" ) )
            return obj.Command100( arg );
    }
}
public class EqualsIgnoreCaseCaller {
    public static Object call( final ObjectWithCommands obj, final String commandName, final Object arg )
    {
        if ( commandName.equalsIgnoreCase( "Command1" ) )
            return obj.Command1( arg );
        if ( commandName.equalsIgnoreCase( "Command2" ) )
            return obj.Command2( arg );
        ...
        if ( commandName.equalsIgnoreCase( "Command99" ) )
            return obj.Command99( arg );
        if ( commandName.equalsIgnoreCase( "Command100" ) )
            return obj.Command100( arg );
    }
}

Which of the following method calls will be the fastest (after warmup)?

  1. EqualsIgnoreCaseCaller.call( obj, "Command9", arg );
  2. EqualsIgnoreCaseCaller.call( obj, "Command99", arg );
  3. EqualsIgnoreCaseCaller.call( obj, "Command100", arg );

Continue reading

Charset encoding and decoding in Java 7/8

by Mikhail Vorontsov

We will take a look at Charset encoder and decoder performance in Java 7/8. We will check the performance of the 2 following String methods with various charsets:

1
2
3
4
5
/* String to byte[] */
public byte[] getBytes(Charset charset);
/* byte[] to String */
public String(byte bytes[], Charset charset);
    
/* String to byte[] */
public byte[] getBytes(Charset charset);
/* byte[] to String */
public String(byte bytes[], Charset charset);
    

I have translated phrase “Develop with pleasure” into German, Russian, Japanese and traditional Chinese using Google Translate. We will build chunks of given size from these phrases by concatenating them using “\n” as a separator until we reach the required length (in most cases the result will be slightly longer). After that we will convert 100 million characters of such data to byte[] and back to String (100M is the total data length in Java chars). We will convert data 10 times in order to make results more reliable (as a result, times in the following table are the times to convert 1 billion chars).

We will use 2 chunk sizes: 100 chars to test the performance of short string conversion and 100M chars to test the raw conversion performance. You can find the source code at the end of this article. We will compare encoding into a “national” charset (US-ASCII for English; ISO-8859-1 for German; windows-1251 for Russian; Shift_JIS for Japanese; GB18030 for Traditional Chinese) with UTF-8 encoding, which could be used as a universal encoding (at a possible price of a longer binary representation). We will also compare Java 7u51 with Java 8 (original release). All tests were run on my Xeon-2650 (2.8Ghz) workstation with -Xmx32G setting (to avoid GC).

Here are the test results. Each cell has two times: Java7_time (Java8_time). “UTF-8” line, which follows every “national” charset line contains conversion times for the data from the previous line (for example, the last line contains times to encode/decode a string in the traditional Chinese into UTF-8).

Continue reading

Base64 encoding and decoding performance

by Mikhail Vorontsov

02 Apr 2014 update: added Guava implementation and byte[] < -> byte[] section.

21 Mar 2014 update: major rewrite + added javax.xml.bind.DatatypeConverter class description.

21 Feb 2014 update: added MiGBase64 class description.

25 Dec 2013 update: added Java 8 java.util.Base64 class description.

We will discuss what is Base64 algorithm and what is the performance of several different well-known libraries implementing Base64 encoding/decoding.

Base64 is an algorithm mapping all 256 byte values to 64 printable byte values (printable means that those bytes are printed in US-ASCII encoding). This is done by packing 3 input bytes to 4 output bytes. Base64 is generally used in text-based data exchange protocols when there is still a need to transfer some binary data. The best known example is encoding of e-mail attachments.

JDK Base64 implementations

Surprisingly, there was no Base64 implementation in the core JDK classes before Java 6. Some web forums advise to use two non-public sun.* classes which are present in all Sun/Oracle JDK: sun.misc.BASE64Encoder and sun.misc.BASE64Decoder. The advantage of using them is that you don’t need to ship any other libraries with your application. The disadvantage is that those classes are not supposed to be used from outside JDK classes (and, of course, they can be removed from JDK implementation… in theory, at least).

Sun has added another Base64 implementation in Java 6 (thanks to Thomas Darimont for his remainder!): it was hidden in javax.xml.bind package and was unknown to many developers. javax.xml.bind.DatatypeConverter class has 2 static methods – parseBase64Binary and printBase64Binary, which are used for Base64 encoding and decoding.

Java 8 has finally added a Base64 implementation in the java. namespace – java.util.Base64. This static factory class provides you with the basic/MIME/URL and filename safe encoder and decoder implementations.

Surprisingly (or may be not), all these implementations do not share any logic even in Java 8.

Third party Base64 implementations

I will also mention 4 quite well known Base64 third party implementations.

  • The first one is present in the Apache Commons Codec library and called org.apache.commons.codec.binary.Base64.
  • The next one is present in the Google Guava library and accessible via com.google.common.io.BaseEncoding.base64() static method.
  • Another one was written by Robert Harder and available from his website: http://iharder.net/base64. This is a single class which you will have to add to your project.
  • The last one was written by Mikael Grev nearly 10 years ago. It is available from http://migbase64.sourceforge.net/. This is also a single class you have to add into your project. This implementation claims to be the fastest Base64 implementation, but unfortunately this is not true any longer. Besides, it has a strictest limit on the maximal length of byte[] to decode (see below).

Continue reading

JSR 310 – Java 8 Date/Time library performance (as well as Joda Time 2.3 and j.u.Calendar)

by Mikhail Vorontsov

Introduction

This is the third date/time article in this blog. I advice you to look at the other two as well: java.util.Date, java.util.Calendar and java.text.SimpleDateFormat and Joda Time library performance.

This article is a short overview of the new Java 8 date/time implementation also known as JSR-310. I will compare JSR-310 implementation and performance with their counterparts from Joda Time library as well as with the good old java.util.GregorianCalendar. This review was written and tested on Java 8 ea b121.

All new Java 8 classes are implemented around the human time concept – separate fields for years, months, days, hours, minutes, seconds, and, in line with the current fashion, nanoseconds. Their counterpart is a machine time – number of milliseconds since epoch, which you may obtain, for example, via System.currentTimeMillis() call. In order to convert time between 2 these systems you will need to know which timezone to use. A timezone defines the offset from UTC used in conversions. Offset calculation may require the use of transition table or transition rules defining when the daylight savings changes happen. Sometime it may become a performance bottleneck.

JSR-310 implementation was inspired by a Joda Time library – both libraries have the similar interface, but their implementations differ greatly – Java 8 classes are built around the human time, but Joda Time is using machine time inside. As a result, if you are looking for the fastest implementation, I would recommend you to use Java 8 classes except the situations when:

  • You can’t use Java 8 (yeah, not many people can use it before the first official release…)
  • You work strictly with the machine time inside a few day range (in this case manual long/int based implementation will be faster).
  • You have to parse timestamps including offset/zone id.

Continue reading

String.intern in Java 7 and 8 – part 3

by Mikhail Vorontsov

I want to return to String.intern method I have discussed earlier ( part 1, part 2 ). During the last couple of months I have used interning heavily in my pet project in order to see the pros and cons of using String.intern for every non-temporary string in my application (non-temporary – the one which is expected to live longer than for a few seconds and most likely get into the GC old generation).

As I have written before, the advantages of String.intern in Java 7 and 8 are:

  • Rather fast execution, nearly no performance loss in the multithreaded mode (still using the global string pool).
  • Saving memory, thus allowing your dataset to shrink, which will let your application to run faster (in general).

The main disadvantages of this method (as I have noticed before) are:

  • The requirement to set -XX:StringTableSize=N JVM parameter in advance and dealing with its fixed value (needs JVM restart in order to expand the JVM string pool).
  • Adding calls to String.intern in a lot of places globally (probably via your own wrapper) – which has linear code maintenance cost.

After a couple of months of using String.intern in my project, I think that its usage should be limited to the fields having a limited domain of distinct values (like person first names or state/province names). We should not try to intern anything with a low probability of a repeating value – it would be a waste of CPU time.

Continue reading

A possible memory leak in the manual MultiMap implementation

by Mikhail Vorontsov

Pure Java 6 and 7

In this short article I will describe a junior level memory leak I have recently seen in a pure JDK application (no 3rd party libs were allowed).

Suppose you have a map from String identifiers to some Collections, for example a set of String properties of such identifiers: Map<String, Set<String>>. The actual type of the inner collection does not matter for this article – it should just be a Collection. Such collections are generally called multimaps.

The following method was initially written to obtain the inner set by its identifier:

1
2
3
4
5
6
7
8
9
10
11
12
private final Map<String, Set<String>> m_ids = new HashMap<String, Set<String>>( 4 );
 
private Set<String> getSetByNameFaulty( final String id )
{
    Set<String> res = m_ids.get( id );
    if ( res == null )
    {
        res = new HashSet<String>( 1 );
        m_ids.put( id, res );
    }
    return res;
}
private final Map<String, Set<String>> m_ids = new HashMap<String, Set<String>>( 4 );

private Set<String> getSetByNameFaulty( final String id )
{
    Set<String> res = m_ids.get( id );
    if ( res == null )
    {
        res = new HashSet<String>( 1 );
        m_ids.put( id, res );
    }
    return res;
}

This method checks if an identifier is already present in the map and either returns the corresponding Set or allocates a new one and adds it into the map. This method is useful for populating our map:

1
2
3
4
5
6
7
private void populateJava67()
{
    getSetByNameFaulty( "id1" ).add( "property1" );
    getSetByNameFaulty( "id1" ).add( "property2" );
    getSetByNameFaulty( "id1" ).add( "property3" );
    getSetByNameFaulty( "id2" ).add( "property1" );
}
private void populateJava67()
{
    getSetByNameFaulty( "id1" ).add( "property1" );
    getSetByNameFaulty( "id1" ).add( "property2" );
    getSetByNameFaulty( "id1" ).add( "property3" );
    getSetByNameFaulty( "id2" ).add( "property1" );
}

The next step while writing a program would be to add some accessors to our map, like the following one:

1
2
3
4
private boolean hasPropertyFaulty( final String id, final String property )
{
    return getSetByNameFaulty( id ).contains( property );
}
private boolean hasPropertyFaulty( final String id, final String property )
{
    return getSetByNameFaulty( id ).contains( property );
}

This method looks good and is unlikely to be caught by any code quality tools. Unfortunately, it has a major flaw: if you will query properties of unknown identifier, a new empty set will be allocated in our map inside getSetByNameFaulty method. This is definitely a not wanted side effect. Instead we should let our new getSetByName method know if we want to write something to the returned set:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
private Set<String> getSetByName( final String id, final boolean isWrite )
{
    Set<String> res = m_ids.get( id );
    if ( res == null )
    {
        if ( isWrite )
        {
            res = new HashSet<String>( 1 );
            m_ids.put( id, res );
        }
        else
            res = Collections.emptySet();
    }
    return res;
}
 
private boolean hasProperty( final String id, final String property )
{
    return getSetByName( id, false ).contains( property );
}
 
private void populateJava67Better()
{
    getSetByName( "id1", true ).add( "property1" );
    getSetByName( "id1", true ).add( "property2" );
    getSetByName( "id1", true ).add( "property3" );
    getSetByName( "id2", true ).add( "property1" );
}
private Set<String> getSetByName( final String id, final boolean isWrite )
{
    Set<String> res = m_ids.get( id );
    if ( res == null )
    {
        if ( isWrite )
        {
            res = new HashSet<String>( 1 );
            m_ids.put( id, res );
        }
        else
            res = Collections.emptySet();
    }
    return res;
}

private boolean hasProperty( final String id, final String property )
{
    return getSetByName( id, false ).contains( property );
}

private void populateJava67Better()
{
    getSetByName( "id1", true ).add( "property1" );
    getSetByName( "id1", true ).add( "property2" );
    getSetByName( "id1", true ).add( "property3" );
    getSetByName( "id2", true ).add( "property1" );
}

Continue reading

String.intern in Java 6, 7 and 8 – multithreaded access

by Mikhail Vorontsov

This article follows the initial String.intern in Java 6, 7 and 8 – string pooling article describing the implementation and benefits of using String.intern() method in Java 7 and 8. The original article was already getting too long, so I had to write this article in order to describe the performance characteristics of the multithreaded access to the String.intern.

The tests we will perform today are calling String.intern() from the multiple threads. They will emulate the behavior of a lot of modern server applications (for example, specialized web crawlers). For tests I will use my new workstation with Intel Xeon E5-2650 CPU (8 physical, 16 virtual cores @ 2 Ghz) and 128 Gb RAM. It will allow us to test the rather high contention scenarios. In this article we will create 8 threads in order to utilize all physical cores.

There will be 4 tests:

  1. The benchmark one – a single thread calling String.intern() using testLongLoop method from the previous article. It will show us how fast this configuration is without any contention.
  2. All 8 threads are calling String.intern() with unique values – an own prefix will be added by each thread to the interned string. This test will show us the synchronization overhead of String.intern(). It should be the theoretical worst case: it is highly unlikely that the only thing the actual application would do is calling String.intern in a loop from many threads.
  3. Initially we start the first thread interning the set of strings. After 2 seconds delay we will start a second thread interning the same set of strings. We expect that the following assumptions will be true: str.intern()==str for the first thread; str.intern()!=str for the second thread. It will allow us to prove that there are no thread local JVM string pools.
  4. All 8 threads will intern the same set of values. This scenario will be closer to the real situation – it will provide us the rather likely mix of adding strings to the JVM pool and querying the strings from it. Nevertheless, such a high read contention on the JVM string pool is still an unlikely event.

Continue reading

String.intern in Java 6, 7 and 8 – string pooling

by Mikhail Vorontsov

This article will describe how String.intern method was implemented in Java 6 and what changes were made in it in Java 7 and Java 8.

First of all I want to thank Yannis Bres for inspiring me to write this article.

07 June 2014 update: added 60013 as a default string pool size since Java 7u40 (instead of Java 8), added -XX:+PrintFlagsFinal and -XX:+PrintStringTableStatistics JVM parameter references, cleaned up a few typos.

This is an updated version of this article including -XX:StringTableSize=N JVM parameter description. This article is followed by String.intern in Java 6, 7 and 8 – multithreaded access article describing the performance characteristics of the multithreaded access to String.intern().

String pooling

String pooling (aka string canonicalisation) is a process of replacing several String objects with equal value but different identity with a single shared String object. You can achieve this goal by keeping your own Map<String, String> (with possibly soft or weak references depending on your requirements) and using map values as canonicalised values. Or you can use String.intern() method which is provided to you by JDK.

At times of Java 6 using String.intern() was forbidden by many standards due to a high possibility to get an OutOfMemoryException if pooling went out of control. Oracle Java 7 implementation of string pooling was changed considerably. You can look for details in http://bugs.sun.com/view_bug.do?bug_id=6962931 and http://bugs.sun.com/view_bug.do?bug_id=6962930.

String.intern() in Java 6

In those good old days all interned strings were stored in the PermGen – the fixed size part of heap mainly used for storing loaded classes and string pool. Besides explicitly interned strings, PermGen string pool also contained all literal strings earlier used in your program (the important word here is used – if a class or method was never loaded/called, any constants defined in it will not be loaded).

The biggest issue with such string pool in Java 6 was its location – the PermGen. PermGen has a fixed size and can not be expanded at runtime. You can set it using -XX:MaxPermSize=N option. As far as I know, the default PermGen size varies between 32M and 96M depending on the platform. You can increase its size, but its size will still be fixed. Such limitation required very careful usage of String.intern – you’d better not intern any uncontrolled user input using this method. That’s why string pooling at times of Java 6 was mostly implemented in the manually managed maps.

String.intern() in Java 7

Oracle engineers made an extremely important change to the string pooling logic in Java 7 – the string pool was relocated to the heap. It means that you are no longer limited by a separate fixed size memory area. All strings are now located in the heap, as most of other ordinary objects, which allows you to manage only the heap size while tuning your application. Technically, this alone could be a sufficient reason to reconsider using String.intern() in your Java 7 programs. But there are other reasons.

Continue reading