I have a question about the performance of Java's String.indexOf(String subString).
I've written a class to compare the performance of calling String.indexOf(String subString) compare to copying the source from inside String's source and calling the internal indexOf() using exactly the same arguments.
The performance appears to be about 4x better when calling String.indexOf() directly, despite the call stack would be 2 frames deeper.
My JVM is JDK1.7.0_40 64bit (windows hotspot). My machine is running Windows with i7-4600U CPU with 16GB ram.
Here is the code:
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.atomic.AtomicBoolean;
import java.util.concurrent.atomic.AtomicLong;
public class TestIndexOf implements Runnable {
final static String s0 = "This is my search string, it is pretty long so can test the speed of the search";
final static String s1 = "speed of the search";
final static char[] c0 = s0.toCharArray();
final static char[] c1 = s1.toCharArray();
final static byte[] b0 = s0.getBytes();
final static byte[] b1 = s1.getBytes();
static AtomicBoolean EXIT = new AtomicBoolean(false);
static AtomicLong TOTAL = new AtomicLong(0);
@Override
public void run() {
long count = 0;
try {
for (;;) {
// Case 1, search as byte[]
int idx = indexOf(b0, 0, b0.length, b1, 0, b1.length, 0);
// Case 2, search as char[]
// int idx = indexOf(c0, 0, c0.length, c1, 0, c1.length, 0);
// Case 3, search as String (using String.indexOf())
// int idx = s0.indexOf(s1);
if (idx >= 0) {
count ++;
}
if (EXIT.get()) {
break;
}
}
TOTAL.addAndGet(count);
} catch(Exception e) {
e.printStackTrace();
}
}
/* byte version of indexOf, modified from Java JDK source */
static int indexOf(byte[] source, int sourceOffset, int sourceCount,
byte[] target, int targetOffset, int targetCount,
int fromIndex) {
if (fromIndex >= sourceCount) {
return (targetCount == 0 ? sourceCount : -1);
}
if (fromIndex < 0) {
fromIndex = 0;
}
if (targetCount == 0) {
return fromIndex;
}
byte first = target[targetOffset];
int max = sourceOffset + (sourceCount - targetCount);
for (int i = sourceOffset + fromIndex; i <= max; i++) {
/* Look for first character. */
if (source[i] != first) {
while (++i <= max && source[i] != first) {
;
}
}
/* Found first character, now look at the rest of v2 */
if (i <= max) {
int j = i + 1;
int end = j + targetCount - 1;
for (int k = targetOffset + 1; j < end && source[j] ==
target[k]; j++, k++) {
;
}
if (j == end) {
/* Found whole string. */
return i - sourceOffset;
}
}
}
return -1;
}
/* char version of indexOf, directly copied from JDK's String class */
static int indexOf(char[] source, int sourceOffset, int sourceCount,
char[] target, int targetOffset, int targetCount,
int fromIndex) {
if (fromIndex >= sourceCount) {
return (targetCount == 0 ? sourceCount : -1);
}
if (fromIndex < 0) {
fromIndex = 0;
}
if (targetCount == 0) {
return fromIndex;
}
char first = target[targetOffset];
int max = sourceOffset + (sourceCount - targetCount);
for (int i = sourceOffset + fromIndex; i <= max; i++) {
/* Look for first character. */
if (source[i] != first) {
while (++i <= max && source[i] != first) {
;
}
}
/* Found first character, now look at the rest of v2 */
if (i <= max) {
int j = i + 1;
int end = j + targetCount - 1;
for (int k = targetOffset + 1; j < end && source[j] ==
target[k]; j++, k++) {
;
}
if (j == end) {
/* Found whole string. */
return i - sourceOffset;
}
}
}
return -1;
}
public static void main(String[] args) throws Exception {
int threads = 4;
ExecutorService executorService = Executors.newFixedThreadPool(threads);
for(int i=0; i<threads; i++) {
executorService.execute(new TestIndexOf());
}
Thread.sleep(10000);
EXIT.set(true);
System.out.println("STOPPED");
Thread.sleep(1000);
System.out.println("Count = " + TOTAL.get());
System.exit(0);
}
}
The results I got was: (2 samples, ran for 10 seconds, with 4 threads)
byte[] 224848726 225011695
char[] 224707442 224707442
String 898161092 897897572
What is the magic with String.indexOf()? Does this get hardware acceleration? :P
