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

C2 SuperWord: implement polynomial reductions (for hashing)

XMLWordPrintable

    • Icon: Enhancement Enhancement
    • Resolution: Unresolved
    • Icon: P4 P4
    • tbd
    • 24
    • hotspot

      Examples:

              for (int i = fromIndex; i < end; i++) {
                  result = 31 * result + a[i];
              }

          @Benchmark
          public int nativeSegmentJava() {
              int result = 1;
              for (long i = 0; i < ELEM_SIZE; i++) {
                  result = 31 * result + nativeSegment.get(JAVA_BYTE, i);
              }
              return result;
          }


      Basic idea, this reformulation:

      result = result * 31^N + a[0] * 31^(N-1) + ... a[i] * 32^ (N-1-i) ... + a[N-2] * 31 + a[N-1]

      All the values can thus be calculated in parallel.

      This work would generallize the intrinsics we already have for strings:
      https://bugs.openjdk.org/browse/JDK-8282664
      https://github.com/openjdk/jdk/pull/10847

      Other previous investigation:
      https://inside.java/2021/01/27/extending-c2-autovectorization-capabilities/

      A further generalization would to vectorize prefix-sums and more generally scans:
      https://eme64.github.io/blog/2023/11/03/C2-AutoVectorizer-Improvement-Ideas.html

            epeter Emanuel Peter
            epeter Emanuel Peter
            Votes:
            0 Vote for this issue
            Watchers:
            2 Start watching this issue

              Created:
              Updated: