String Switching Benchmark

aaronweiss · Jul 14, 2012

Test 1: Constant Sample Set

Results:

Code:

string: strswitch bench: 1028 ms 1027517000 ns
string: enumswitch bench: 902 ms 901389000 ns
string: strequals bench: 935 ms 935431000 ns
string: strequalsic bench: 1116 ms 1115405000 ns

N.b. nanosecond times are simply estimates, they are not necessarily precise.

How was this conducted?

A set of 16 strings, all with a length of 6, is prepared. Each is added into a collection of strings, and the collection then shuffles itself randomly. The first string after shuffling it is then compared to using the desired means. The collection is then reshuffled, and the process begins again. This process is iterated over 1,000,000 times.

Code:

package benchmarking;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;

/**
 * A tool for benchmarking different ways of comparing strings.
 * @author Aaron Weiss
 * @version 1.0
 */
public class StringBenchmark {
	private static final int ITERATIONS = 1000000;
	private static Scanner in;

	/**
	 * @param args None
	 */
	public static void main(String[] args) {
		ArrayList<String> strings = new ArrayList<String>();
		for (Strings s : Strings.values()) {
			strings.add(s.name());
		}
		Collections.shuffle(strings);
		in = new Scanner(System.in);
		System.out.print("Press return to begin.");
		in.nextLine();
		in.close();

		{
			// System.out.println("string: strswitch bench: start");
			long startNano = System.nanoTime();
			long start = System.currentTimeMillis();
			for (int i = 0; i < ITERATIONS; i++) {
				Collections.shuffle(strings);
				switch (strings.get(0)) {
					case "FLIGHT":
					case "TREATS":
					case "TEASES":
					case "BASTES":
					case "TASTES":
					case "WASTES":
					case "TATERS":
					case "HATERS":
					case "HEATER":
					case "READER":
					case "FASTER":
					case "HASTES":
					case "FASTED":
					case "PASTED":
					case "PASTER":
					case "BASTED":
						break;
				}
				Collections.shuffle(strings);
			}
			long end = System.currentTimeMillis();
			long endNano = System.nanoTime();
			// System.out.println("string: strswitch bench: end");
			System.out.println("string: strswitch bench: " + (end - start) + " ms " + (endNano - startNano) + " ns");
		}
		{
			// System.out.println("string: enumswitch bench: start");
			long startNano = System.nanoTime();
			long start = System.currentTimeMillis();
			for (int i = 0; i < ITERATIONS; i++) {
				Collections.shuffle(strings);
				Strings s = Strings.valueOf(strings.get(0));
				switch (s) {
					case FLIGHT:
					case TREATS:
					case TEASES:
					case BASTES:
					case TASTES:
					case WASTES:
					case TATERS:
					case HATERS:
					case HEATER:
					case READER:
					case FASTER:
					case HASTES:
					case FASTED:
					case PASTED:
					case PASTER:
					case BASTED:
						break;
				}
				Collections.shuffle(strings);
			}
			long end = System.currentTimeMillis();
			long endNano = System.nanoTime();
			// System.out.println("string: enumswitch bench: end");
			System.out.println("string: enumswitch bench: " + (end - start) + " ms " + (endNano - startNano) + " ns");
		}
		{
			// System.out.println("string: strequals bench: start");
			long startNano = System.nanoTime();
			long start = System.currentTimeMillis();
			for (int i = 0; i < ITERATIONS; i++) {
				Collections.shuffle(strings);
				String compare = strings.get(0);
				if (compare.equals("FLIGHT")) {
					// pass
				} else if (compare.equals("TREATS")) {
					// pass
				} else if (compare.equals("TEASES")) {
					// pass
				} else if (compare.equals("BASTES")) {
					// pass
				} else if (compare.equals("TASTES")) {
					// pass
				} else if (compare.equals("WASTES")) {
					// pass
				} else if (compare.equals("TATERS")) {
					// pass
				} else if (compare.equals("HATERS")) {
					// pass
				} else if (compare.equals("HEATER")) {
					// pass
				} else if (compare.equals("READER")) {
					// pass
				} else if (compare.equals("FASTER")) {
					// pass
				} else if (compare.equals("HASTES")) {
					// pass
				} else if (compare.equals("FASTED")) {
					// pass
				} else if (compare.equals("PASTED")) {
					// pass
				} else if (compare.equals("PASTER")) {
					// pass
				} else if (compare.equals("BASTED")) {
					// pass
				}
				Collections.shuffle(strings);
			}
			long end = System.currentTimeMillis();
			long endNano = System.nanoTime();
			// System.out.println("string: strequals bench: end");
			System.out.println("string: strequals bench: " + (end - start) + " ms " + (endNano - startNano) + " ns");
		}
		{
			// System.out.println("string: strequalsic bench: start");
			long startNano = System.nanoTime();
			long start = System.currentTimeMillis();
			for (int i = 0; i < ITERATIONS; i++) {
				Collections.shuffle(strings);
				String compare = strings.get(0);
				if (compare.equals("FLIGHT")) {
					// pass
				} else if (compare.equalsIgnoreCase("TREATS")) {
					// pass
				} else if (compare.equalsIgnoreCase("TEASES")) {
					// pass
				} else if (compare.equalsIgnoreCase("BASTES")) {
					// pass
				} else if (compare.equalsIgnoreCase("TASTES")) {
					// pass
				} else if (compare.equalsIgnoreCase("WASTES")) {
					// pass
				} else if (compare.equalsIgnoreCase("TATERS")) {
					// pass
				} else if (compare.equalsIgnoreCase("HATERS")) {
					// pass
				} else if (compare.equalsIgnoreCase("HEATER")) {
					// pass
				} else if (compare.equalsIgnoreCase("READER")) {
					// pass
				} else if (compare.equalsIgnoreCase("FASTER")) {
					// pass
				} else if (compare.equalsIgnoreCase("HASTES")) {
					// pass
				} else if (compare.equalsIgnoreCase("FASTED")) {
					// pass
				} else if (compare.equalsIgnoreCase("PASTED")) {
					// pass
				} else if (compare.equalsIgnoreCase("PASTER")) {
					// pass
				} else if (compare.equalsIgnoreCase("BASTED")) {
					// pass
				}
				Collections.shuffle(strings);
			}
			long end = System.currentTimeMillis();
			long endNano = System.nanoTime();
			// System.out.println("string: strequalsic bench: end");
			System.out.println("string: strequalsic bench: " + (end - start) + " ms " + (endNano - startNano) + " ns");
		}
	}
	
	private enum Strings {
		FLIGHT,
		TREATS,
		TEASES,
		BASTES,
		TASTES,
		WASTES,
		TATERS,
		HATERS,
		HEATER,
		READER,
		FASTER,
		HASTES,
		FASTED,
		PASTED,
		PASTER,
		BASTED,
	};
}

Test 2: Constant Sample Set Improved

Results:

Code:

string: strswitch bench: 163 ms 163141000 ns
string: enumswitch bench: 134 ms 134133000 ns
string: strequals bench: 118 ms 118052000 ns
string: strequalsic bench: 259 ms 259730000 ns

N.b. nanosecond times are simply estimates, they are not necessarily precise.

How was this conducted?

A set of 16 strings, all with a length of 6, is prepared. Each is added into a collection of strings. A random string from the list is then compared to using the desired means. Afterward, the process begins again. This process is iterated over 1,000,000 times.

Code:

package benchmarking;

import java.util.ArrayList;
import java.util.Random;
import java.util.Scanner;

/**
 * A tool for benchmarking different ways of comparing strings.
 * @author Aaron Weiss
 * @version 2.0
 */
public class StringBenchmark {
	private static final int ITERATIONS = 1000000;
	private static Random randomizer;
	private static Scanner in;

	/**
	 * @param args None
	 */
	public static void main(String[] args) {
		randomizer = new Random();
		ArrayList<String> strings = new ArrayList<String>();
		for (Strings s : Strings.values()) {
			strings.add(s.name());
		}
		in = new Scanner(System.in);
		System.out.print("Press return to begin.");
		in.nextLine();
		in.close();
		{
			// System.out.println("string: strswitch bench: start");
			long startNano = System.nanoTime();
			long start = System.currentTimeMillis();
			for (int i = 0; i < ITERATIONS; i++) {
				switch (strings.get(randomizer.nextInt(Integer.MAX_VALUE) % strings.size())) {
					case "FLIGHT":
					case "TREATS":
					case "TEASES":
					case "BASTES":
					case "TASTES":
					case "WASTES":
					case "TATERS":
					case "HATERS":
					case "HEATER":
					case "READER":
					case "FASTER":
					case "HASTES":
					case "FASTED":
					case "PASTED":
					case "PASTER":
					case "BASTED":
						break;
				}
			}
			long end = System.currentTimeMillis();
			long endNano = System.nanoTime();
			// System.out.println("string: strswitch bench: end");
			System.out.println("string: strswitch bench: " + (end - start) + " ms " + (endNano - startNano) + " ns");
		}
		{
			// System.out.println("string: enumswitch bench: start");
			long startNano = System.nanoTime();
			long start = System.currentTimeMillis();
			for (int i = 0; i < ITERATIONS; i++) {
				Strings s = Strings.valueOf(strings.get(randomizer.nextInt(Integer.MAX_VALUE) % strings.size()));
				switch (s) {
					case FLIGHT:
					case TREATS:
					case TEASES:
					case BASTES:
					case TASTES:
					case WASTES:
					case TATERS:
					case HATERS:
					case HEATER:
					case READER:
					case FASTER:
					case HASTES:
					case FASTED:
					case PASTED:
					case PASTER:
					case BASTED:
						break;
				}
			}
			long end = System.currentTimeMillis();
			long endNano = System.nanoTime();
			// System.out.println("string: enumswitch bench: end");
			System.out.println("string: enumswitch bench: " + (end - start) + " ms " + (endNano - startNano) + " ns");
		}
		{
			// System.out.println("string: strequals bench: start");
			long startNano = System.nanoTime();
			long start = System.currentTimeMillis();
			for (int i = 0; i < ITERATIONS; i++) {
				String compare = strings.get(randomizer.nextInt(Integer.MAX_VALUE) % strings.size());
				if (compare.equals("FLIGHT")) {
					// pass
				} else if (compare.equals("TREATS")) {
					// pass
				} else if (compare.equals("TEASES")) {
					// pass
				} else if (compare.equals("BASTES")) {
					// pass
				} else if (compare.equals("TASTES")) {
					// pass
				} else if (compare.equals("WASTES")) {
					// pass
				} else if (compare.equals("TATERS")) {
					// pass
				} else if (compare.equals("HATERS")) {
					// pass
				} else if (compare.equals("HEATER")) {
					// pass
				} else if (compare.equals("READER")) {
					// pass
				} else if (compare.equals("FASTER")) {
					// pass
				} else if (compare.equals("HASTES")) {
					// pass
				} else if (compare.equals("FASTED")) {
					// pass
				} else if (compare.equals("PASTED")) {
					// pass
				} else if (compare.equals("PASTER")) {
					// pass
				} else if (compare.equals("BASTED")) {
					// pass
				}
			}
			long end = System.currentTimeMillis();
			long endNano = System.nanoTime();
			// System.out.println("string: strequals bench: end");
			System.out.println("string: strequals bench: " + (end - start) + " ms " + (endNano - startNano) + " ns");
		}
		{
			// System.out.println("string: strequalsic bench: start");
			long startNano = System.nanoTime();
			long start = System.currentTimeMillis();
			for (int i = 0; i < ITERATIONS; i++) {
				String compare = strings.get(randomizer.nextInt(Integer.MAX_VALUE) % strings.size());
				if (compare.equals("FLIGHT")) {
					// pass
				} else if (compare.equalsIgnoreCase("TREATS")) {
					// pass
				} else if (compare.equalsIgnoreCase("TEASES")) {
					// pass
				} else if (compare.equalsIgnoreCase("BASTES")) {
					// pass
				} else if (compare.equalsIgnoreCase("TASTES")) {
					// pass
				} else if (compare.equalsIgnoreCase("WASTES")) {
					// pass
				} else if (compare.equalsIgnoreCase("TATERS")) {
					// pass
				} else if (compare.equalsIgnoreCase("HATERS")) {
					// pass
				} else if (compare.equalsIgnoreCase("HEATER")) {
					// pass
				} else if (compare.equalsIgnoreCase("READER")) {
					// pass
				} else if (compare.equalsIgnoreCase("FASTER")) {
					// pass
				} else if (compare.equalsIgnoreCase("HASTES")) {
					// pass
				} else if (compare.equalsIgnoreCase("FASTED")) {
					// pass
				} else if (compare.equalsIgnoreCase("PASTED")) {
					// pass
				} else if (compare.equalsIgnoreCase("PASTER")) {
					// pass
				} else if (compare.equalsIgnoreCase("BASTED")) {
					// pass
				}
			}
			long end = System.currentTimeMillis();
			long endNano = System.nanoTime();
			// System.out.println("string: strequalsic bench: end");
			System.out.println("string: strequalsic bench: " + (end - start) + " ms " + (endNano - startNano) + " ns");
		}
	}
	
	private enum Strings {
		FLIGHT,
		TREATS,
		TEASES,
		BASTES,
		TASTES,
		WASTES,
		TATERS,
		HATERS,
		HEATER,
		READER,
		FASTER,
		HASTES,
		FASTED,
		PASTED,
		PASTER,
		BASTED,
	};
}

I may add more tests in the future, as this one only deals with constant sets of data, of constant size.
N.b. these tests are implementation-dependent, and are really just suggestions, more than they are statements of fact.

Ignorant? Going to comment something stupid? Have some bunnies instead.

aaronweiss - String Switching Benchmark - RaGEZONE Forums

retep998 · Jul 14, 2012

I too have decided to benchmark string switching, but in C++!
Unfortunately, C++ does not have any sort of way to switch on strings, so instead I simply used set and unordered_set to determine their performance, as well as a simple int switch.
Basically, first I generate an array of size random strings each of len length and populate the set and unordered_set with the strings. I also generate iter random numbers from 0 to len. Then for the benchmark itself, I iterate through each random number, get that string from the array, and then find it in the set or unordered_set. For the int switch, I simply take the random number and switch on it.
Using the same constants as Aaron did, here are my results:

Code:

Preparing data: 18ms
Hash: 61ms
Tree: 72ms
Switch: 10ms

Here is my code:

Code:

##include <iostream>
#include <string>
#include <chrono>
#include <array>
#include <random>
#include <set>
#include <unordered_set>
using namespace std;

chrono::high_resolution_clock timer;
template <typename T>
void test(T f, string s) {
    auto begin = timer.now();
    f();
    auto end = timer.now();
    cout << s << ": " << chrono::duration_cast<chrono::milliseconds>(end-begin).count() << "ms" << endl;
}

const int size = 16;
const int len = 6;
const int iter = 1000000;

array<string, size> strlist;
set<string> strtree;
unordered_set<string> strhash;
array<int, iter> numbers;
mt19937_64 engine;

void prep() {
    {
        uniform_int_distribution<char> dist;
        string s(len, '\0');
        for (int i = 0; i < size; ++i) {
            for (int j = 0; j < len; ++j) {
                s[j] = dist(engine);
            }
            strlist[i] = s;
            strtree.insert(s);
            strhash.insert(s);
        }
    }
    {
        uniform_int_distribution<int> dist(0, size-1);
        for (int i = 0; i < iter; ++i) {
            numbers[i] = dist(engine);
        }
    }
}

void findhash() {
    for (int i = 0; i < iter; ++i) {
        volatile auto it = strhash.find(strlist[numbers[i]]);
    }
}

void findtree() {
    for (int i = 0; i < iter; ++i) {
        volatile auto it = strtree.find(strlist[numbers[i]]);
    }
}

void findswitch() {
    for (int i = 0; i < iter; ++i) {
        volatile int n;
        switch(numbers[i]) {
        case 0: n = 0; break;
        case 1: n = 1; break;
        case 2: n = 1; break;
        case 3: n = 2; break;
        case 4: n = 3; break;
        case 5: n = 5; break;
        case 6: n = 8; break;
        case 7: n = 13; break;
        case 8: n = 21; break;
        case 9: n = 34; break;
        case 10: n = 55; break;
        case 11: n = 89; break;
        case 12: n = 144; break;
        case 13: n = 233; break;
        case 14: n = 377; break;
        case 15: n = 610; break;
        }
    }
}

int main() {
    test(prep, "Preparing data");
    test(findhash, "Hash");
    test(findtree, "Tree");
    test(findswitch, "Switch");
}

SuPeR SoNiC · Jul 14, 2012

Thanks for posting this. I was wondering for a long time why is string switching considered slower.
But tbh, for the specific topic of a MapleStory server, do you think it could make such a big difference?

aaronweiss · Jul 15, 2012

SuPeR SoNiC said:
Thanks for posting this. I was wondering for a long time why is string switching considered slower.
But tbh, for the specific topic of a MapleStory server, do you think it could make such a big difference?

Say you have about one thousand users on your server, and about twenty five player commands available to these players. You never know how many requests you'll get for commands, so you'll want to process them as quickly as possible. Otherwise, you'll risk getting backed up. It's not necessarily that it's guaranteed to make a difference, but when the amount of work required is minuscule, why not work to optimize for speed where you can?

Zygon · Jul 21, 2012

For a ~100 ms throughput difference? If there is this "trend" regarding the decreasing of throughput based upon the size of the switch, then you need more data to convince anyone not to use string-switch.

aaronweiss said:
Say you have about one thousand users on your server, and about twenty five player commands available to these players. You never know how many requests you'll get for commands, so you'll want to process them as quickly as possible. Otherwise, you'll risk getting backed up. It's not necessarily that it's guaranteed to make a difference, but when the amount of work required is minuscule, why not work to optimize for speed where you can?

Why not have the compiler do micro-optimization instead of the programmer?

aaronweiss · Jul 21, 2012

Zygon said:
For a ~100 ms throughput difference? If there is this "trend" regarding the decreasing of throughput based upon the size of the switch, then you need more data to convince anyone not to use string-switch.

Why not have the compiler do micro-optimization instead of the programmer?

Because aside from the speed difference, you're abandoning any reverse compatibility with older versions of Java. There's absolutely no reason to completely disregard Java 6 as it is still highly prominent, especially when you're only taking advantage of one of the slower features of Java 7. If you wanted to do all of the networking using Java 7's true async NIO, good for you, more power to you, but if your entire codebase is Java 6 with string switches, that's a tad shameful.

Zygon · Jul 21, 2012

aaronweiss said:
Because aside from the speed difference, you're abandoning any reverse compatibility with older versions of Java. There's absolutely no reason to completely disregard Java 6 as it is still highly prominent, especially when you're only taking advantage of one of the slower features of Java 7. If you wanted to do all of the networking using Java 7's true async NIO, good for you, more power to you, but if your entire codebase is Java 6 with string switches, that's a tad shameful.

Backwards compatibility* first off. Second off, this thread is not about version, it is about performance throughput with string switching compared to other options - regardless of whether or not this is on 1.7 platform, it should be assumed that everyone using our software uses this version to begin with.

Why you brought version up is beyond me; not to mention if I wanted people to be able to use my software with 1.6 then I would build it for 1.6. I am just simply stating that the ~100 ms difference is so small it really matters not, and the fact that there is this 100 ms difference means that Oracle should fix that problem (hopefully being resolved in future builds). That 100 ms difference is so small in terms of overall CPU time it really seems pointless to me making that optimization, me saying this does not imply that I use string switches regularly (in fact, I have only used it once or twice for very small portions of my code if not at all). I personally think there is way too many variables to consider benchmarking viable in terms of micro-portions of code to begin with.

Something to further express my point:

You must be registered to see links

aaronweiss · Jul 22, 2012

Why I brought it up is the whole reason I even bothered to do this, and that would be because I think it's stupid for people to abandon Java 6 just so that they can use string switching when it's actually not even an improvement in performance. There's no reason to use it, and quite frankly, no, you're just wrong. Not everyone should have it. Java 7 is currently a very early release, and is actually not standardly available on certain other platforms, for example some ARM versions of linux distributions, as well as Mac OS X. There are ways of attaining them (i.e. using poorly written alternative platform implementations for POSIX systems such as Oracle's implementation), but they often perform much worse than other better optimized implementations (such as Apple's JVM or OpenJDK). I'd like to also make it known that Apple actually abandoned working on their JVM and so it will not receive an update to Java 7. They contributed their work towards OpenJDK, adding many great improvements to it, and its certainly a better implementation than Oracle's.

retep998 · Jul 22, 2012

It doesn't matter what language you use or what version of Java you are building for, switching on a string is ALWAYS slower than switching on an enum. In most decent languages, switching on an enum is constant time: add a few million values and it still only takes a couple instructions to get to the right spot. String switching is always slow, at best it is implemented using a binary tree or hash map so that access is only logarithmic, and at worst, which is much more common than you imagine, it is implemented using linear iteration which gets proportionally slow as you add strings.
Because it can be agreed that enum switching is always faster than string switching, there is no reason not to switch on enums. Premature optimization can often be a bad thing, but when you have such a clear cut case like this, refusing to use the faster method is blatantly idiotic.
Also, aaronweiss, your enum benchmark is flawed. Look at this line:

Code:

Strings s = Strings.valueOf(strings.get(randomizer.nextInt(Integer.MAX_VALUE) % strings.size()));

Each iteration you are taking a string and getting the enum value. If you instead generated random enum values instead of string values, you would see a MUCH higher performance difference.

Welcome!

String Switching Benchmark

aaronweiss

Skilled Illusionist

retep998

PeterRabbit

SuPeR SoNiC

Have Fun!

aaronweiss

Skilled Illusionist

Zygon

Yuki

aaronweiss

Skilled Illusionist

Zygon

Yuki

aaronweiss

Skilled Illusionist

retep998

PeterRabbit

About Us

Online statistics

Forum statistics

RaGEZONE Sponsor