manejo - ¿Por qué el método String.equals() de Java usa dos variables de conteo?

string en java

Question

Estaba mirando a través de la implementación de la clase String de Java y lo siguiente me pareció extraño:

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

Esto podría implementarse fácilmente con una sola variable de conteo, mientras que n sería efectivamente final, como esto:

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

También hay esto, que se deshace de la i completo:

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

¿Tiene que ver con que la comparación con 0 sea (un bit minúsculo) más barata que con otra variable o hay alguna otra razón en particular para explicar por qué se implementa de esa manera?

Answer 1

Creo que tiene que ver con la implementación de substring antes de JDK 7.

En ese momento, el tamaño de la matriz de caracteres subyacente no era necesariamente el tamaño de la cadena. Hubo dos campos, offset y count ( i y j respectivamente) que mostraban dónde está this cadena en la matriz subyacente, por lo que el método era:

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

Después del cambio mencionado anteriormente, este método también tuvo que cambiarse, por lo que simplemente arreglaron n para que sea ahora la longitud del arreglo:

int n = value.length;

y se deshizo de j (porque ya no hay compensación):

int i = 0;

Ahora, debido a que tengo que aumentar después de 2 usos, se incrementa en una declaración por separado:

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

Creo que eso es todo, hay una implementación más concisa que es evidente si es para escribirlo desde cero, pero dado que fue un cambio impulsado por otro cambio ... Las personas de Oracle son personas comunes como nosotros :)

Benchmarking

En cuanto a la evaluación comparativa, String#equals Arrays#equals(char[], char[] ) Creo que tenemos que comparar manzanas con manzanas, por lo que he puesto los dos enfoques para comparar matrices de 2 caracteres juntos:

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

En mi caja no veo diferencia notable.

Answer 2

Esto NO ES UNA RESPUESTA, 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();
        }
    }
}

Y aquí están los resultados:

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

Entonces, debido a que String.equals toma más tiempo que la comparación de matrices subyacentes (con una sola variable de iterador), podemos descartar algunos problemas de optimización de JVM mágicos aquí (¿pero podría estar en el pasado?).

Answer 3

No es un código real para la mayoría de las máquinas virtuales Java reales con HotSpot. String.equals es un método muy importante y se implementa a través de intrínseco. Tiene plataforma de implementación nativa específica. Puede encontrar la lista completa aquí src/share/vm/classfile/vmSymbols.hpp (vea do_intrinsic)