Uploaded image for project: 'JDK'
  1. JDK
  2. JDK-6932808

(str) Tune equals() of String

XMLWordPrintable

    • Icon: Enhancement Enhancement
    • Resolution: Unresolved
    • Icon: P5 P5
    • None
    • 7
    • core-libs
    • Cause Known
    • x86
    • windows_xp

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

            Unassigned Unassigned
            ndcosta Nelson Dcosta (Inactive)
            Votes:
            0 Vote for this issue
            Watchers:
            1 Start watching this issue

              Created:
              Updated:
              Imported:
              Indexed: