Details

      Description

      String.hashCode is the primary example of polynomial hash code. Current code does:

          int h = 0;
          for (char c : value) {
              h = h * 31 + c;
          }

      ...to iteratively compute the hash code. It was illustrated [1] that hand-unrolling the loop, and
      computing the hashcode in strides can be beneficial for performance. It is better, however,
      to make compiler to optimize the loops like these automatically. Other use cases include
      Arrays.hashCode, and any other user-written loop doing the same.

      It seems plausible to implode the operations within an unrolled loop into more efficient code.
      E.g., given:

        <loop by 2> {
           t1 = K*t0 + a0;
           t2 = K*t1 + a1;
        }

      ...inline t1 into t2, and

        <loop by 2> {
           // t1 is dead here
           t2 = K*(K*t0 + a0) + a1;
        }

      ...and then fold:

        <loop by 2> {
           // t1 is dead here
           t2 = K*K*t0 + K*a0 + a1;
        }

      Performance benchmarks, perfasm outputs are available here:
        http://cr.openjdk.java.net/~shade/8059113/

      There, you can see the hand-unrolled versions run up to 1.6x faster.
      Multiplying by 31 has additional strength reduction, and partially eliminating that, we have a bit more boosts.

      [1] http://mail.openjdk.java.net/pipermail/core-libs-dev/2014-September/028898.html

        Issue Links

          Activity

          shade Aleksey Shipilev created issue -
          shade Aleksey Shipilev made changes -
          Field Original Value New Value
          Description String.hashCode is the primary example of polynomial hash code. Current code does:

              int h = 0;
              for (char c : value) {
                  h = h * 31 + c;
              }

          ...to iteratively compute the hash code. It was illustrated [1] that hand-unrolling the loop, and
          computing the hashcode in strides can be beneficial for performance. It is better, however,
          to make compiler to optimize the loops like these automatically. Other use cases include
          Arrays.hashCode, and any other user-written loop doing the same.

          It seems plausible to implode the operations within an unrolled loop into more efficient code.
          E.g., given:

            <loop by 2> {
               t1 = K*t0 + a0;
               t2 = K*t1 + a1;
            }

          ...inline t1 into t2, and

            <loop by 2> {
               // t1 is dead here
               t2 = K*(K*t0 + a0) + a1;
            }

          ...and then fold:

            <loop by 2> {
               // t1 is dead here
               t2 = K*K*t0 + K*a0 + a1;
            }


          [1] http://mail.openjdk.java.net/pipermail/core-libs-dev/2014-September/028898.html
          String.hashCode is the primary example of polynomial hash code. Current code does:

              int h = 0;
              for (char c : value) {
                  h = h * 31 + c;
              }

          ...to iteratively compute the hash code. It was illustrated [1] that hand-unrolling the loop, and
          computing the hashcode in strides can be beneficial for performance. It is better, however,
          to make compiler to optimize the loops like these automatically. Other use cases include
          Arrays.hashCode, and any other user-written loop doing the same.

          It seems plausible to implode the operations within an unrolled loop into more efficient code.
          E.g., given:

            <loop by 2> {
               t1 = K*t0 + a0;
               t2 = K*t1 + a1;
            }

          ...inline t1 into t2, and

            <loop by 2> {
               // t1 is dead here
               t2 = K*(K*t0 + a0) + a1;
            }

          ...and then fold:

            <loop by 2> {
               // t1 is dead here
               t2 = K*K*t0 + K*a0 + a1;
            }

          Performance benchmarks, perfasm outputs are available here:
            http://cr.openjdk.java.net/~shade/8059113/

          There, you can see the hand-unrolled versions run up to 1.6x faster.
          Multiplying by 31 has additional strength reduction, and partially eliminating that, we have a bit more boosts.

          [1] http://mail.openjdk.java.net/pipermail/core-libs-dev/2014-September/028898.html
          thartmann Tobias Hartmann made changes -
          Affects Version/s 9 [ 14949 ]
          Affects Version/s 10 [ 16302 ]
          thartmann Tobias Hartmann made changes -
          Labels performance c2 community-candidate performance
          thartmann Tobias Hartmann made changes -
          Status New [ 10000 ] Open [ 1 ]
          thartmann Tobias Hartmann made changes -
          Labels c2 community-candidate performance c2 c2-loopopts community-candidate performance
          thartmann Tobias Hartmann made changes -
          Fix Version/s 13 [ 19031 ]
          thartmann Tobias Hartmann made changes -
          Labels c2 c2-loopopts community-candidate performance c2 c2-loopopts community-candidate comp-backlog performance
          shade Aleksey Shipilev made changes -
          Link This issue relates to JDK-8186203 [ JDK-8186203 ]
          kvn Vladimir Kozlov made changes -
          Link This issue duplicates JDK-8186203 [ JDK-8186203 ]
          Hide
          kvn Vladimir Kozlov added a comment - - edited
          Richard Startin points the same issue - hand-unrolled hash code loop is better than auto-unroll:

            https://richardstartin.com/2017/07/23/still-true-in-java-9-handwritten-hash-codes-are-faster/
          Show
          kvn Vladimir Kozlov added a comment - - edited Richard Startin points the same issue - hand-unrolled hash code loop is better than auto-unroll:    https://richardstartin.com/2017/07/23/still-true-in-java-9-handwritten-hash-codes-are-faster/
          kvn Vladimir Kozlov made changes -
          Assignee Vladimir Kozlov [ kvn ]
          kvn Vladimir Kozlov made changes -
          Link This issue relates to JDK-8186203 [ JDK-8186203 ]

            People

            • Assignee:
              kvn Vladimir Kozlov
              Reporter:
              shade Aleksey Shipilev
            • Votes:
              0 Vote for this issue
              Watchers:
              5 Start watching this issue

              Dates

              • Created:
                Updated: