A DESCRIPTION OF THE REQUEST :
1.) Add shortcut if lengths are 0.
2.) Concider hashes if not 0.
3.) Add shortcut if contents are identical.
4.) Don't de/increment 3 variables in loop.
5.) Compare the chars reversely from the end of the string.
6.) Compare loop end against 0
JUSTIFICATION :
1.) Performance win, as loading several member values from memory is omitted.
2.) Performance win, if hashes differ.
Please have in mind, that repetitive equals()'s occur likely in hash maps when buckets have more than 1 entry.
In that case hashes are definitly still computed.
3.) Performance win for the rare case if strings are still backed by the same content, e.g. after subString() operations.
4.) See EXPECTED vs ACTUAL section.
5.) If chars have same length, it's very likely, that they differ not till the last characters.
E.g.: "PropertyName.minor.micro_1" - "PropertyName.minor.micro_2"
6.) See internal review ID of 1730206.
EXPECTED VERSUS ACTUAL BEHAVIOR :
EXPECTED -
Alternative 1:
for (n += o1; o1 != n; ) // avoids decrement of n
if (v1[o1++] != v2[o2++])
return false;
Loop compiles to (needs only 23 bytes of machine code):
0x00b87da7: movzwl 0xc(%edx,%esi,2),%ecx ;*caload
; - java.lang.String::equals2@82 (line 1105)
0x00b87dac: movzwl 0xc(%ebp,%esi,2),%edi ;*caload
; - java.lang.String::equals2@74 (line 1105)
0x00b87db1: cmp %ecx,%edi
0x00b87db3: jne 0x00b87e32 ;*if_icmpeq
; - java.lang.String::equals2@83 (line 1105)
0x00b87db9: inc %esi ;*iinc
; - java.lang.String::equals2@71 (line 1105)
0x00b87dba: cmp %ebx,%esi
0x00b87dbc: jl 0x00b87da7
0x00b87dbe:
Alternative 2:
while (n-- != 0) // compare against 0 is little faster; only decrement 1 register
// to benefit from CPU's complex addressing modes
if (v1[o1+n] != v2[o2+n]) // compare the chars backwards
return false;
Loop compiles to (needs only 23 bytes of machine code):
0x00b87130: movzwl 0xc(%edx,%esi,2),%ecx ;*caload
; - java.lang.String::equals1@76 (line 1087)
0x00b87135: movzwl 0xc(%ebp,%esi,2),%edi ;*caload
; - java.lang.String::equals1@69 (line 1087)
0x00b8713a: cmp %ecx,%edi
0x00b8713c: jne 0x00b871cc ;*if_icmpeq
; - java.lang.String::equals1@77 (line 1087)
0x00b87142: dec %esi ;*iinc
; - java.lang.String::equals1@56 (line 1086)
0x00b87143: cmp %ebx,%esi
0x00b87145: jg 0x00b87130
0x00b87147:
ACTUAL -
Original:
while (n-- != 0) { // needs 1 decrement
if (v1[o1++] != v2[o2++]) // + 2 increments
return false;
}
Loop compiles to (needs 33 bytes of machine code):
0x00b87738: mov %ebx,%edi
0x00b8773a: neg %edi ;*aload
; - java.lang.String::equals@63 (line 1066)
0x00b8773c: movzwl 0xc(%ebp,%edi,2),%eax ;*caload
; - java.lang.String::equals@78 (line 1066)
0x00b87741: movzwl 0xc(%edx,%edi,2),%esi ;*caload
; - java.lang.String::equals@70 (line 1066)
0x00b87746: cmp %eax,%esi
0x00b87748: jne 0x00b87802 ;*if_icmpeq
; - java.lang.String::equals@79 (line 1066)
0x00b8774e: mov %ebx,%eax
0x00b87750: dec %eax ;*iinc
; - java.lang.String::equals@57 (line 1065)
0x00b87751: cmp %ecx,%eax
0x00b87753: jle 0x00b87759
0x00b87755: mov %eax,%ebx
0x00b87757: jmp 0x00b87738
0x00b87759:
---------- BEGIN SOURCE ----------
public class Sting {
...
public boolean equals(Object anObject) {
if (this == anObject) // 1st check identitiy
return true;
if (anObject instanceof String) { // 2nd check type
String anotherString = (String)anObject;
int n = count;
if (n == anotherString.count) { // 3rd check lengths
if (n != 0) { // 4th avoid loading registers from members if length == 0
int h1 = hash, h2 = anotherString.hash;
if (h1 != 0 && h2 != 0 && h1 != h2) // 5th check the hashes
return false;
char[] v1 = value, v2 = anotherString.value;
int o1 = offset, o2 = anotherString.offset;
if (v1 != v2 || o1 != o2) // 6th don't compare the chars if identical
while (--n >= 0) // only decrement 1 register
// to benefit from CPU's complex addressing modes
if (v1[o1+n] != v2[o2+n]) // compare the chars backwards
return false;
}
return true;
}
}
return false;
}
...
}
// Alternative:
public boolean equals(Object anObject) {
if (this == anObject) // 1st check identitiy
return true;
if (anObject instanceof String) { // 2nd check type
String anotherString = (String)anObject;
int n = count;
if (n == anotherString.count) { // 3rd check lengths
int h1 = hash, h2 = anotherString.hash;
if (n >= 4 && h1 != 0 && h2 != 0 && h1 != h2) // 5th check the hashes
return false;
char[] v1 = value, v2 = anotherString.value;
int o1 = offset, o2 = anotherString.offset;
if (v1 != v2 || o1 != o2) // 6th don't compare the chars if identical
while (--n >= 0) // only decrement 1 register
// to benefit from CPU's complex addressing modes
if (v1[o1+n] != v2[o2+n]) // compare the chars backwards
return false;
return true;
}
}
return false;
}
---------- END SOURCE ----------
1.) Add shortcut if lengths are 0.
2.) Concider hashes if not 0.
3.) Add shortcut if contents are identical.
4.) Don't de/increment 3 variables in loop.
5.) Compare the chars reversely from the end of the string.
6.) Compare loop end against 0
JUSTIFICATION :
1.) Performance win, as loading several member values from memory is omitted.
2.) Performance win, if hashes differ.
Please have in mind, that repetitive equals()'s occur likely in hash maps when buckets have more than 1 entry.
In that case hashes are definitly still computed.
3.) Performance win for the rare case if strings are still backed by the same content, e.g. after subString() operations.
4.) See EXPECTED vs ACTUAL section.
5.) If chars have same length, it's very likely, that they differ not till the last characters.
E.g.: "PropertyName.minor.micro_1" - "PropertyName.minor.micro_2"
6.) See internal review ID of 1730206.
EXPECTED VERSUS ACTUAL BEHAVIOR :
EXPECTED -
Alternative 1:
for (n += o1; o1 != n; ) // avoids decrement of n
if (v1[o1++] != v2[o2++])
return false;
Loop compiles to (needs only 23 bytes of machine code):
0x00b87da7: movzwl 0xc(%edx,%esi,2),%ecx ;*caload
; - java.lang.String::equals2@82 (line 1105)
0x00b87dac: movzwl 0xc(%ebp,%esi,2),%edi ;*caload
; - java.lang.String::equals2@74 (line 1105)
0x00b87db1: cmp %ecx,%edi
0x00b87db3: jne 0x00b87e32 ;*if_icmpeq
; - java.lang.String::equals2@83 (line 1105)
0x00b87db9: inc %esi ;*iinc
; - java.lang.String::equals2@71 (line 1105)
0x00b87dba: cmp %ebx,%esi
0x00b87dbc: jl 0x00b87da7
0x00b87dbe:
Alternative 2:
while (n-- != 0) // compare against 0 is little faster; only decrement 1 register
// to benefit from CPU's complex addressing modes
if (v1[o1+n] != v2[o2+n]) // compare the chars backwards
return false;
Loop compiles to (needs only 23 bytes of machine code):
0x00b87130: movzwl 0xc(%edx,%esi,2),%ecx ;*caload
; - java.lang.String::equals1@76 (line 1087)
0x00b87135: movzwl 0xc(%ebp,%esi,2),%edi ;*caload
; - java.lang.String::equals1@69 (line 1087)
0x00b8713a: cmp %ecx,%edi
0x00b8713c: jne 0x00b871cc ;*if_icmpeq
; - java.lang.String::equals1@77 (line 1087)
0x00b87142: dec %esi ;*iinc
; - java.lang.String::equals1@56 (line 1086)
0x00b87143: cmp %ebx,%esi
0x00b87145: jg 0x00b87130
0x00b87147:
ACTUAL -
Original:
while (n-- != 0) { // needs 1 decrement
if (v1[o1++] != v2[o2++]) // + 2 increments
return false;
}
Loop compiles to (needs 33 bytes of machine code):
0x00b87738: mov %ebx,%edi
0x00b8773a: neg %edi ;*aload
; - java.lang.String::equals@63 (line 1066)
0x00b8773c: movzwl 0xc(%ebp,%edi,2),%eax ;*caload
; - java.lang.String::equals@78 (line 1066)
0x00b87741: movzwl 0xc(%edx,%edi,2),%esi ;*caload
; - java.lang.String::equals@70 (line 1066)
0x00b87746: cmp %eax,%esi
0x00b87748: jne 0x00b87802 ;*if_icmpeq
; - java.lang.String::equals@79 (line 1066)
0x00b8774e: mov %ebx,%eax
0x00b87750: dec %eax ;*iinc
; - java.lang.String::equals@57 (line 1065)
0x00b87751: cmp %ecx,%eax
0x00b87753: jle 0x00b87759
0x00b87755: mov %eax,%ebx
0x00b87757: jmp 0x00b87738
0x00b87759:
---------- BEGIN SOURCE ----------
public class Sting {
...
public boolean equals(Object anObject) {
if (this == anObject) // 1st check identitiy
return true;
if (anObject instanceof String) { // 2nd check type
String anotherString = (String)anObject;
int n = count;
if (n == anotherString.count) { // 3rd check lengths
if (n != 0) { // 4th avoid loading registers from members if length == 0
int h1 = hash, h2 = anotherString.hash;
if (h1 != 0 && h2 != 0 && h1 != h2) // 5th check the hashes
return false;
char[] v1 = value, v2 = anotherString.value;
int o1 = offset, o2 = anotherString.offset;
if (v1 != v2 || o1 != o2) // 6th don't compare the chars if identical
while (--n >= 0) // only decrement 1 register
// to benefit from CPU's complex addressing modes
if (v1[o1+n] != v2[o2+n]) // compare the chars backwards
return false;
}
return true;
}
}
return false;
}
...
}
// Alternative:
public boolean equals(Object anObject) {
if (this == anObject) // 1st check identitiy
return true;
if (anObject instanceof String) { // 2nd check type
String anotherString = (String)anObject;
int n = count;
if (n == anotherString.count) { // 3rd check lengths
int h1 = hash, h2 = anotherString.hash;
if (n >= 4 && h1 != 0 && h2 != 0 && h1 != h2) // 5th check the hashes
return false;
char[] v1 = value, v2 = anotherString.value;
int o1 = offset, o2 = anotherString.offset;
if (v1 != v2 || o1 != o2) // 6th don't compare the chars if identical
while (--n >= 0) // only decrement 1 register
// to benefit from CPU's complex addressing modes
if (v1[o1+n] != v2[o2+n]) // compare the chars backwards
return false;
return true;
}
}
return false;
}
---------- END SOURCE ----------
- duplicates
-
JDK-6912520 String#equals(Object) should benefit from hash code
-
- Closed
-
-
JDK-6992751 Optimized String.equals()
-
- Closed
-
- relates to
-
JDK-4514146 (str) String.equals is inefficient. Unrolling comparison loop makes it faster
-
- Closed
-