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 );

Let’s write a JMH benchmark:

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
29
30
31
32
33
34
35
36
37
38
@BenchmarkMode(Mode.Throughput)
@OutputTimeUnit(TimeUnit.SECONDS)
@Warmup(iterations = 5, time = 1, timeUnit = TimeUnit.SECONDS )
@Measurement(iterations = 10, time = 1, timeUnit = TimeUnit.SECONDS )
@Threads(1)
@State(Scope.Thread)
public class CallTest {
    private String m_commandName9 = "Command9";
    private String m_commandName99 = "Command99";
    private String m_commandName100 = "Command100";
    private ObjectWithCommands m_obj = new ObjectWithCommands();
    private Object m_arg = new Object();
 
    @GenerateMicroBenchmark
    public Object testEqualsIgnoreCase9()
    {
        return EqualsIgnoreCaseCaller.call(m_obj, m_commandName9, m_arg);
    }
    @GenerateMicroBenchmark
    public Object testEqualsIgnoreCase99()
    {
        return EqualsIgnoreCaseCaller.call(m_obj, m_commandName99, m_arg);
    }
    @GenerateMicroBenchmark
    public Object testEqualsIgnoreCase100()
    {
        return EqualsIgnoreCaseCaller.call(m_obj, m_commandName100, m_arg);
    }
 
    public static void main(String[] args) throws RunnerException {
        Options opt = new OptionsBuilder()
                .include(".*" + CallTest.class.getSimpleName() + ".*")
                .forks(1)
                .build();
 
        new Runner(opt).run();
    }
}
@BenchmarkMode(Mode.Throughput)
@OutputTimeUnit(TimeUnit.SECONDS)
@Warmup(iterations = 5, time = 1, timeUnit = TimeUnit.SECONDS )
@Measurement(iterations = 10, time = 1, timeUnit = TimeUnit.SECONDS )
@Threads(1)
@State(Scope.Thread)
public class CallTest {
    private String m_commandName9 = "Command9";
    private String m_commandName99 = "Command99";
    private String m_commandName100 = "Command100";
    private ObjectWithCommands m_obj = new ObjectWithCommands();
    private Object m_arg = new Object();

    @GenerateMicroBenchmark
    public Object testEqualsIgnoreCase9()
    {
        return EqualsIgnoreCaseCaller.call(m_obj, m_commandName9, m_arg);
    }
    @GenerateMicroBenchmark
    public Object testEqualsIgnoreCase99()
    {
        return EqualsIgnoreCaseCaller.call(m_obj, m_commandName99, m_arg);
    }
    @GenerateMicroBenchmark
    public Object testEqualsIgnoreCase100()
    {
        return EqualsIgnoreCaseCaller.call(m_obj, m_commandName100, m_arg);
    }

    public static void main(String[] args) throws RunnerException {
        Options opt = new OptionsBuilder()
                .include(".*" + CallTest.class.getSimpleName() + ".*")
                .forks(1)
                .build();

        new Runner(opt).run();
    }
}

Here are the test results on my ultrabook:

Benchmark                              Mode   Samples         Mean   Mean error    Units
t.CallTest.testEqualsIgnoreCase9      thrpt        10   998445.643     3518.385    ops/s
t.CallTest.testEqualsIgnoreCase99     thrpt        10    83494.967     1237.927    ops/s
t.CallTest.testEqualsIgnoreCase100    thrpt        10  3701991.457    21054.106    ops/s

Command100 was the fastest one, followed by Command9, and the Command99 was the slowest one. So, why Command100, which was the last in the chain of comparisons was ~44 times faster than Command99? Should not their performance be nearly equal?

Of course, not. Let’s take a look at String.equalsIgnoreCase source code:

1
2
3
4
5
6
public boolean equalsIgnoreCase(String anotherString) {
    return (this == anotherString) ? true
            : (anotherString != null)
            && (anotherString.value.length == value.length)
            && regionMatches(true, 0, anotherString, 0, value.length);
}
public boolean equalsIgnoreCase(String anotherString) {
    return (this == anotherString) ? true
            : (anotherString != null)
            && (anotherString.value.length == value.length)
            && regionMatches(true, 0, anotherString, 0, value.length);
}

The main optimization here is to check that both strings have equal length. This check allows Command100 to bypass the first 99 comparisons and become the fastest one. At the same time, Command99 can bypass only the first 9 comparisons due to this optimization.

Command99 will have to compare up to 89*9 characters before finding the successful match. Here comes the second optimization (which is quite useless in general case, but here it works) – the very first comparison ( (this == anotherString) ) bypasses the check if we compare a string with itself. It works in this case, because all strings in the test are literals, so they get interned. This optimization is more important in case of Command100 – it allows the comparison to succeed without a single actual comparison of string contents!

Similar logic is implemented in String.equals – identity check followed by length check followed by the actual contents check (though, equals starts from the tail of the string).

So, if we have to implement such command proxy logic, is a list of equalsIgnoreCase calls is good enough or we can do better?

Possible case insensitive “string switch” implementations

Chain of String.equalsIgnoreCase

This is the most straight forward approach. Unfortunately, it works well only if there is a single command of a given length and a list of commands is short enough.

1
2
3
4
5
if ( commandName.equalsIgnoreCase( "Command1" ) )
    return obj.Command1( arg );
if ( commandName.equalsIgnoreCase( "Command2" ) )
    return obj.Command2( arg );
...
if ( commandName.equalsIgnoreCase( "Command1" ) )
    return obj.Command1( arg );
if ( commandName.equalsIgnoreCase( "Command2" ) )
    return obj.Command2( arg );
...

Command.toLowerCase followed by a chain of String.equals

We can lowercase the command name we are looking for once and then compare it to lowercased command names. This option works better when the number of commands grows.

1
2
3
4
5
6
final String lcName = commandName.toLowerCase();
if ( lcName.equals( "command1" ) )
    return obj.Command1( arg );
if ( lcName.equals( "command2" ) )
    return obj.Command2( arg );
...
final String lcName = commandName.toLowerCase();
if ( lcName.equals( "command1" ) )
    return obj.Command1( arg );
if ( lcName.equals( "command2" ) )
    return obj.Command2( arg );
...

Java 7 String switch

From Java 7 we are allowed to use strings in switch statements. While it is logically equivalent to the previous case, the implementation is different. String switch is implemented as a map from strings into blocks of code linked to those strings.

1
2
3
4
5
6
7
8
final String lcName = commandName.toLowerCase();
switch( lcName ) {
    case "command1":
        return obj.Command1( arg );
    case "command2":
        return obj.Command2( arg );
    ...
}
final String lcName = commandName.toLowerCase();
switch( lcName ) {
    case "command1":
        return obj.Command1( arg );
    case "command2":
        return obj.Command2( arg );
    ...
}

Explicit map from names into commands (prior to Java 8)

Let’s compare the String switch performance with the explicit map from lowercased command names into commands. Each command would be implemented as an anonymous class implementing the following interface:

1
2
3
interface ICommandCaller {
    public Object call( final ObjectWithCommands obj, final Object arg );
}
interface ICommandCaller {
    public Object call( final ObjectWithCommands obj, final Object arg );
}

Prior to Java 8 and its lambdas the implementation would look like:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
private static final Map<String, ICommandCaller> CALL_MAP = new HashMap<>( 100 );
static {
    CALL_MAP.put( "command1", new ICommandCaller() {
        public Object call( final ObjectWithCommands obj, final Object arg ) {
            return obj.Command1( arg );
        }
    } );
    CALL_MAP.put( "command2", new ICommandCaller() {
        public Object call( final ObjectWithCommands obj, final Object arg ) {
            return obj.Command2( arg );
        }
    } );
    ...
}
 
public static Object call( final ObjectWithCommands obj, final String commandName, final Object arg )
{
    return CALL_MAP.get( commandName.toLowerCase() ).call( obj, arg );
}
private static final Map<String, ICommandCaller> CALL_MAP = new HashMap<>( 100 );
static {
    CALL_MAP.put( "command1", new ICommandCaller() {
        public Object call( final ObjectWithCommands obj, final Object arg ) {
            return obj.Command1( arg );
        }
    } );
    CALL_MAP.put( "command2", new ICommandCaller() {
        public Object call( final ObjectWithCommands obj, final Object arg ) {
            return obj.Command2( arg );
        }
    } );
    ...
}

public static Object call( final ObjectWithCommands obj, final String commandName, final Object arg )
{
    return CALL_MAP.get( commandName.toLowerCase() ).call( obj, arg );
}

Java 8 lambdas map

In Java 8 we can replace anonymous classes from the previous example with lambdas:

1
2
3
4
5
6
private static final Map<String, ICommandCaller> CALL_MAP = new HashMap<>( 100 );
static {
    CALL_MAP.put( "command1", ( obj, arg ) -> obj.Command1( arg ) );
    CALL_MAP.put( "command2", ( obj, arg ) -> obj.Command2( arg ) );
    ...
}
private static final Map<String, ICommandCaller> CALL_MAP = new HashMap<>( 100 );
static {
    CALL_MAP.put( "command1", ( obj, arg ) -> obj.Command1( arg ) );
    CALL_MAP.put( "command2", ( obj, arg ) -> obj.Command2( arg ) );
    ...
}

Tests

All the above mentioned classes are generated by Generator.java class, which you will be able to find at the end of this article. We will only change the set of command names (and their number) for various tests.

Corner case – no other commands of the same length

Let’s see how all these algorithms perform in the above mentioned case – 100 commands: from Command1 to Command100. We will check the access time to Command100:

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
@BenchmarkMode(Mode.Throughput)
@OutputTimeUnit(TimeUnit.SECONDS)
@Warmup(iterations = 5, time = 1, timeUnit = TimeUnit.SECONDS )
@Measurement(iterations = 10, time = 1, timeUnit = TimeUnit.SECONDS )
@Threads(1)
@State(Scope.Thread)
public class CallTest {
    private String m_commandName = "Command100";
    private ObjectWithCommands m_obj = new ObjectWithCommands();
    private Object m_arg = new Object();
 
    @GenerateMicroBenchmark
    public Object testEqualsIgnoreCase()
    {
        return EqualsIgnoreCaseCaller.call(m_obj, m_commandName, m_arg);
    }
 
    @GenerateMicroBenchmark
    public Object testEqualsLowerCase()
    {
        return EqualsCaller.call(m_obj, m_commandName, m_arg);
    }
 
    @GenerateMicroBenchmark
    public Object testSwitchCall()
    {
        return SwitchCaller.call(m_obj, m_commandName, m_arg);
    }
 
    @GenerateMicroBenchmark
    public Object testJava7Map()
    {
        return Map7Caller.call(m_obj, m_commandName, m_arg);
    }
 
    @GenerateMicroBenchmark
    public Object testJava8Map()
    {
        return Map8Caller.call(m_obj, m_commandName, m_arg);
    }
 
    public static void main(String[] args) throws RunnerException {
        Options opt = new OptionsBuilder()
                .include(".*" + CallTest.class.getSimpleName() + ".*")
                .forks(1)
                .build();
 
        new Runner(opt).run();
    }
}
@BenchmarkMode(Mode.Throughput)
@OutputTimeUnit(TimeUnit.SECONDS)
@Warmup(iterations = 5, time = 1, timeUnit = TimeUnit.SECONDS )
@Measurement(iterations = 10, time = 1, timeUnit = TimeUnit.SECONDS )
@Threads(1)
@State(Scope.Thread)
public class CallTest {
    private String m_commandName = "Command100";
    private ObjectWithCommands m_obj = new ObjectWithCommands();
    private Object m_arg = new Object();

    @GenerateMicroBenchmark
    public Object testEqualsIgnoreCase()
    {
        return EqualsIgnoreCaseCaller.call(m_obj, m_commandName, m_arg);
    }

    @GenerateMicroBenchmark
    public Object testEqualsLowerCase()
    {
        return EqualsCaller.call(m_obj, m_commandName, m_arg);
    }

    @GenerateMicroBenchmark
    public Object testSwitchCall()
    {
        return SwitchCaller.call(m_obj, m_commandName, m_arg);
    }

    @GenerateMicroBenchmark
    public Object testJava7Map()
    {
        return Map7Caller.call(m_obj, m_commandName, m_arg);
    }

    @GenerateMicroBenchmark
    public Object testJava8Map()
    {
        return Map8Caller.call(m_obj, m_commandName, m_arg);
    }

    public static void main(String[] args) throws RunnerException {
        Options opt = new OptionsBuilder()
                .include(".*" + CallTest.class.getSimpleName() + ".*")
                .forks(1)
                .build();

        new Runner(opt).run();
    }
}

Here are the test results:

Benchmark                           Mode   Samples         Mean   Mean error    Units
t.CallTest.testEqualsIgnoreCase    thrpt        10  3722062.950    96314.315    ops/s
t.CallTest.testEqualsLowerCase     thrpt        10  1399947.402    11651.113    ops/s
t.CallTest.testJava7Map            thrpt        10  2640137.150    17767.132    ops/s
t.CallTest.testJava8Map            thrpt        10  2673449.940    13438.176    ops/s
t.CallTest.testSwitchCall          thrpt        10  2653356.312    22085.341    ops/s

equalsIgnoreCase became the fastest test and equals became the slowest. Both share the same code except one detail – equals test eagerly calls toLowerCase on its argument, and it makes the difference. switch and map tests exhibit the same performance.

100 commands of the same length

Let’s change the test set – now we will have 100 commands from Command10001 to Command10100. It will test the case when you have a large number of identical length commands. We will check access time to Command10100.

Benchmark                           Mode   Samples         Mean   Mean error    Units
t.CallTest.testEqualsIgnoreCase    thrpt        10    62066.170      157.287    ops/s
t.CallTest.testEqualsLowerCase     thrpt        10   450102.165     1121.556    ops/s
t.CallTest.testJava7Map            thrpt        10  2411420.337    11454.230    ops/s
t.CallTest.testJava8Map            thrpt        10  2400935.810    54165.643    ops/s
t.CallTest.testSwitchCall          thrpt        10  2406538.563    10945.766    ops/s

500 commands of the same length

Now let’s try 500 commands: Command10001 to Command10500. We will check access time to Command10500.

Benchmark                           Mode   Samples         Mean   Mean error    Units
t.CallTest.testEqualsIgnoreCase    thrpt        10    12899.127      886.002    ops/s
t.CallTest.testEqualsLowerCase     thrpt        10    49137.482      976.380    ops/s
t.CallTest.testJava7Map            thrpt        10  2435168.660    28192.640    ops/s
t.CallTest.testJava8Map            thrpt        10  2488337.117   170484.548    ops/s
t.CallTest.testSwitchCall          thrpt        10   948982.350     2652.893    ops/s

1000 commands of the same length

Finally let’s try 1000 commands: Command10001 to Command11000. We will check access time to Command11000.

Benchmark                           Mode   Samples         Mean   Mean error    Units
t.CallTest.testEqualsIgnoreCase    thrpt        10     4338.513      153.786    ops/s
t.CallTest.testEqualsLowerCase     thrpt        10     7602.722      746.926    ops/s
t.CallTest.testJava7Map            thrpt        10  2147853.317    45741.062    ops/s
t.CallTest.testJava8Map            thrpt        10  2339853.845    10194.687    ops/s
t.CallTest.testSwitchCall          thrpt        10   896876.772     5740.585    ops/s

As you can see in all three tests, map access time is approximately the same in all test cases, while equals/equalsIgnoreCase performance plummets with the increase of number of commands to check.

String switch implementation

String switch performance is more interesting – it degrades at logarithmic speed, which means that switch is implemented as a fixed size map. Let’s try to find out the number of slots in this fixed map. We need to calculate the performance of at least 2 operations – commandName.toLowerCase() and command1.equals( command2 ). JMH will help us:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
private String m_commandName = "Command10500";
private String m_commandName2 = "Command10090";
 
@GenerateMicroBenchmark
public String testLC()
{
    return m_commandName.toLowerCase();
}
 
@GenerateMicroBenchmark
public boolean testEQ()
{
    return m_commandName.equals( m_commandName2 );
}
private String m_commandName = "Command10500";
private String m_commandName2 = "Command10090";

@GenerateMicroBenchmark
public String testLC()
{
    return m_commandName.toLowerCase();
}

@GenerateMicroBenchmark
public boolean testEQ()
{
    return m_commandName.equals( m_commandName2 );
}
Benchmark                           Mode   Samples         Mean   Mean error    Units
t.CallTest.testLC                  thrpt        10  3262501.308   610471.458    ops/s
t.CallTest.testEQ                  thrpt        10 53070517.985   232819.742    ops/s

The switch test consists of a commandName.toLowerCase() followed by a number of equals calls (the number depends on the number of strings in a given slot). So, we can calculate the number of equals calls (N) from the following equation:

        TEST_TIME = LC_TIME + N * EQ_TIME
        N = ( TEST_TIME - LC_TIME ) / EQ_TIME
    

Timings in my tests slightly varied, but I ended up with approximately 5 equals calls in case of 100 commands and 50 equals calls for 1000 commands. In both cases it means that we have approximately 20 slots in the switch map (most likely it will be a prime number close to 20, like 19 or 23).

Summary

  • String switch in Java 7 is implemented using a fixed size map with a number of slots close to 20. This means that you can freely use it in most of cases not worrying about its performance at all. As you have seen, string switch has identical performance compared to manually implemented maps when you have under 100 cases in the switch.
  • String.equals/equalsIgnoreCase perform great as a replacement for string switch while all your cases have different length (or at least the number of cases with the same string length is too low compared to the total number of cases) and the number of string cases is not too big. This property is achieved by comparing string length prior to comparing the actual contents in String.equals/equalsIgnoreCase.

Source code

Source code (with generated classes for the case of 500 commands)


Leave a Reply

Your email address will not be published. Required fields are marked *