Why does Java's String.equals() method use two counting variables?

Question

I was just looking through the implementation of Java's String class and the following struck me as odd:

public boolean equals(Object anObject) {
    if (this == anObject) {
        return true;
    }
    if (anObject instanceof String) {
        String anotherString = (String)anObject;
        int n = value.length;
        if (n == anotherString.value.length) {
            char v1[] = value;
            char v2[] = anotherString.value;
            int i = 0;
            while (n-- != 0) {               // Here n is being decremented...
                if (v1[i] != v2[i])
                    return false;
                i++;                         // while i is being incremented
            }
            return true;
        }
    }
    return false;
}

This could easily be implemented with just one counting variable while n would be effectively final, like this:

while (i != n) {
    if (v1[i] != v2[i])
        return false;
    i++;
}

Theres also this, which gets rid of the i entirely:

while (n-- != 0) {
    if (v1[n] != v2[n])
        return false;
}

Does it have to do with comparison to 0 being (a miniscule bit) cheaper than to another variable or is there any other particular reason as to why it is implemented that way?

Answer 1

I think it has to to with the substring implementation prior to JDK 7.

At the time, the underlying character array size was not necessarily the string size. There were two fields, offset & count (i an j respectively) that were showing where is this string in the underlying array, so the method was :

public boolean equals(Object anObject) {
    if (this == anObject) {
        return true;
    }
    if (anObject instanceof String) {
        String anotherString = (String)anObject;
        int n = count;
        if (n == anotherString.count) {
            char v1[] = value;
            char v2[] = anotherString.value;
            int i = offset;
            int j = anotherString.offset;
            while (n-- != 0) {
                if (v1[i++] != v2[j++])
                    return false;
            }
            return true;
        }
    }
    return false;
}

After the change mentioned above, this method had to be also changed, so they just fixed n to be now the array length:

int n = value.length;

and got rid of j (because there's no offset anymore):

int i = 0;

Now because i has to be incremented after 2 usages, it is incremented in a separate statement :

if (v1[i] != v2[i])
    return false;
i++;

I think that's it, there's a more concise implementation which is evident if it's to write it from scratch but given that it was a change pushed by another change ... Oracle people are ordinary people just like us :)

Benchmarking

As for benchmarking String#equals vs Arrays#equals(char[], char[]) I think we have to compare apples with apples, so I've put the two approaches for comparing 2 character arrays together :

public static void main(String[] args) {
    final Random random = new Random();
    final int arrays = 10000;
    final int chars = 1000;
    // generate the arrays
    char[][] array = new char[arrays][chars];
    for (int i = 0; i < arrays; i++) {
        for (int j = 0; j < chars; j++) {
            array[i][j] = (char)(random.nextInt(94) + 33);
        }
    }
    // compare using Arrays equals
    long before = System.nanoTime();
    for (int i = 0; i < arrays; i++) {
        for (int j = 0; j < chars; j++) {
            equals_Arrays(array[i], array[j]);
        }
    }
    System.out.println(System.nanoTime() - before);
    // compare using String equals
    before = System.nanoTime();
    for (int i = 0; i < arrays; i++) {
        for (int j = 0; j < chars; j++) {
            equals_String(array[i], array[j]);
        }
    }
    System.out.println(System.nanoTime() - before);
}

private static boolean equals_Arrays(char[] a, char[] a2) {
    if (a == a2)
        return true;
    if (a == null || a2 == null)
        return false;

    int length = a.length;
    if (a2.length != length)
        return false;

    for (int i = 0; i < length; i++)
        if (a[i] != a2[i])
            return false;

    return true;
}

private static boolean equals_String(char[] v1, char[] v2) {
    if (v1 == v2)
        return true;
    if (v1 == null || v2 == null)
        return false;

    int length = v1.length;
    if (length == v2.length) {
        int i = 0;
        while (length-- != 0) {
            if (v1[i] != v2[i])
                return false;
            i++;
        }
        return true;
    }
    return false;
}

On my box I see no notable difference.

Answer 2

It is not real code for most of real Java VM with HotSpot. String.equals is very important method and it is implemented through intrinsic. It has platform specific native implementation. You can find full list here src/share/vm/classfile/vmSymbols.hpp (see do_intrinsic)

Answer 3

This is NOT AN ANSWER, justa pseudo banchmark:

public class CompString {

    public static void main(String[] args) {

        DecimalFormat df = new DecimalFormat("0.#################");
        int count = 1000000;
        int length = 20;
        int runs = 10;

        String[] strings = new String[count];
        String[] copiedStrings = new String[count];
        char[][] chars = new char[count][];
        char[][] copiedChars = new char[count][];

        for (int i = 0; i < count; i++) {
            String str = RandomStringUtils.random(length);

            strings[i] = new String(str);
            copiedStrings[i] = new String(str);

            chars[i] = Arrays.copyOf(str.toCharArray(), str.length());
            copiedChars[i] = Arrays.copyOf(chars[i], chars[i].length);
        }

        System.out.println("Lets banchmark that !!");
        int loop = 0;
        while (loop++ < runs) {
            System.out.println("Run #" + loop);
            long t = 0;
            long t0 = System.currentTimeMillis();
            for (int i = 0; i < count; i++) {
                strings[i].equals(copiedStrings[i]);
            }
            long t1 = System.currentTimeMillis();
            t = t1 - t0;

            System.out.println("Avg String.equals() duration: " + df.format(t / (double) count));

            t0 = System.currentTimeMillis();
            for (int i = 0; i < count; i++) {
                Arrays.equals(chars[i], copiedChars[i]);
            }
            t1 = System.currentTimeMillis();
            t = t1 - t0;

            System.out.println("Avg Arrays.equals(char[] char[]) duration: " + df.format(t / (double) count));
            System.out.println();
        }
    }
}

And here are the results:

Run #1
Avg String.equals() duration: 0,000017
Avg Arrays.equals(char[] char[]) duration: 0,000013

Run #2
Avg String.equals() duration: 0,000037
Avg Arrays.equals(char[] char[]) duration: 0

Run #3
Avg String.equals() duration: 0,000002
Avg Arrays.equals(char[] char[]) duration: 0

Run #4
Avg String.equals() duration: 0,000003
Avg Arrays.equals(char[] char[]) duration: 0

Run #5
Avg String.equals() duration: 0,000002
Avg Arrays.equals(char[] char[]) duration: 0

Run #6
Avg String.equals() duration: 0,000003
Avg Arrays.equals(char[] char[]) duration: 0

Run #7
Avg String.equals() duration: 0,000003
Avg Arrays.equals(char[] char[]) duration: 0

Run #8
Avg String.equals() duration: 0,000003
Avg Arrays.equals(char[] char[]) duration: 0

Run #9
Avg String.equals() duration: 0,000002
Avg Arrays.equals(char[] char[]) duration: 0

Run #10
Avg String.equals() duration: 0,000002
Avg Arrays.equals(char[] char[]) duration: 0

So because String.equals takes more time then comparing underlying arrays (with single iterator variable) we can rule out some magic JVM optimization issues here (but could it be in the past?).