Ответ 1

• Нет, это, по-видимому, является следствием устранения недостающих умных границ.

Я распространил бенчмарк Марко Топольника:

@OutputTimeUnit(TimeUnit.NANOSECONDS)
@BenchmarkMode(Mode.AverageTime)
@OperationsPerInvocation(BCElimination.N)
@Warmup(iterations = 5, time = 1)
@Measurement(iterations = 10, time = 1)
@State(Scope.Thread)
@Threads(1)
@Fork(2)
public class BCElimination {
    public static final int N = 1024;
    private static final Unsafe U;
    private static final long INT_BASE;
    private static final long INT_SCALE;
    static {
        try {
            Field f = Unsafe.class.getDeclaredField("theUnsafe");
            f.setAccessible(true);
            U = (Unsafe) f.get(null);
        } catch (Exception e) {
            throw new IllegalStateException(e);
        }

        INT_BASE = U.arrayBaseOffset(int[].class);
        INT_SCALE = U.arrayIndexScale(int[].class);
    }

    private final int[] table = new int[BCElimination.N];

    @Setup public void setUp() {
        final Random random = new Random();
        for (int i=0; i<table.length; ++i) table[i] = random.nextInt();
    }

    @GenerateMicroBenchmark public int normalIndex() {
        int result = 0;
        final int[] table = this.table;
        int x = 0;
        for (int i=0; i<=table.length-1; ++i) {
            x += i;
            final int j = x & (table.length-1);
            result ^= table[i] + j;
        }
        return result;
    }

    @GenerateMicroBenchmark public int maskedIndex() {
        int result = 0;
        final int[] table = this.table;
        int x = 0;
        for (int i=0; i<=table.length-1; ++i) {
            x += i;
            final int j = x & (table.length-1);
            result ^= i + table[j];
        }
        return result;
    }

    @GenerateMicroBenchmark public int maskedIndexUnsafe() {
        int result = 0;
        final int[] table = this.table;
        long x = 0;
        for (int i=0; i<=table.length-1; ++i) {
            x += i * INT_SCALE;
            final long j = x & ((table.length-1) * INT_SCALE);
            result ^= i + U.getInt(table, INT_BASE + j);
        }
        return result;
    }
}

Результаты:

Benchmark                                Mean   Mean error    Units
BCElimination.maskedIndex               1,235        0,004    ns/op
BCElimination.maskedIndexUnsafe         1,092        0,007    ns/op
BCElimination.normalIndex               1,071        0,008    ns/op

2. Второй вопрос касается списков рассылки hotspot-dev, а не StackOverflow, IMHO.

Ответ 2

Чтобы начать, основное различие между двумя вашими испытаниями, безусловно, связано с проверкой исключения; однако способ, которым это влияет на машинный код, далек от того, что предложили наивное ожидание.

Моя гипотеза:

Проверка границ фигурирует сильнее как точка выхода цикла, чем как дополнительный код, который вводит служебные данные.

Точка выхода петли предотвращает следующую оптимизацию, которую я отбирал из испускаемого машинного кода:

• цикл разворачивается (это верно во всех случаях);
• Дополнительно, выборка из этапа массива выполняется сначала для всех развернутых шагов, затем выполняется xoring в аккумулятор для всех этапов.

Если цикл может вырваться на любом шаге, эта процедура приведет к выполнению работы для шагов цикла, которые никогда не выполнялись.

Рассмотрим эту небольшую модификацию вашего кода:

@OutputTimeUnit(TimeUnit.NANOSECONDS)
@BenchmarkMode(Mode.AverageTime)
@OperationsPerInvocation(Measure.N)
@Warmup(iterations = 3, time = 1)
@Measurement(iterations = 5, time = 1)
@State(Scope.Thread)
@Threads(1)
@Fork(1)
 public class Measure {
  public static final int N = 1024;

  private final int[] table = new int[N];
  @Setup public void setUp() {
    final Random random = new Random();
    for (int i = 0; i < table.length; ++i) {
      final int x = random.nextInt();
      table[i] = x == 0? 1 : x;
    }
  }
  @GenerateMicroBenchmark public int normalIndex() {
    int result = 0;
    final int[] table = this.table;
    int x = 0;
    for (int i = 0; i <= table.length - 1; ++i) {
      x += i;
      final int j = x & (table.length - 1);
      final int entry = table[i];
      result ^= entry + j;
      if (entry == 0) break;
    }
    return result;
  }
  @GenerateMicroBenchmark public int maskedIndex() {
    int result = 0;
    final int[] table = this.table;
    int x = 0;
    for (int i = 0; i <= table.length - 1; ++i) {
      x += i;
      final int j = x & (table.length - 1);
      final int entry = table[j];
      result ^= i + entry;
      if (entry == 0) break;
    }
    return result;
  }
}

Есть только одно отличие: я добавил чек

if (entry == 0) break;

чтобы дать петле способ выхода преждевременно на любой шаг. (Я также представил охранник, чтобы гарантировать, что никакие записи массива на самом деле не равны 0.)

На моей машине это результат:

Benchmark                   Mode   Samples         Mean   Mean error    Units
o.s.Measure.maskedIndex     avgt         5        1.378        0.229    ns/op
o.s.Measure.normalIndex     avgt         5        0.924        0.092    ns/op

вариант "нормального индекса" значительно быстрее, как обычно ожидалось.

Однако удалим дополнительную проверку:

// if (entry == 0) break;

Теперь мои результаты таковы:

Benchmark                   Mode   Samples         Mean   Mean error    Units
o.s.Measure.maskedIndex     avgt         5        1.130        0.065    ns/op
o.s.Measure.normalIndex     avgt         5        1.229        0.053    ns/op

"Маскированный индекс" ответил предсказуемо (уменьшены накладные расходы), но "нормальный индекс" внезапно намного хуже. По-видимому, это связано с плохой совпадением между дополнительным шагом оптимизации и моей конкретной моделью процессора.

Моя точка:

Модель производительности на таком детальном уровне очень неустойчива и, как видно на моем процессоре, даже неустойчива.

Ответ 3

Чтобы безопасно устранить эту проверку границ, необходимо доказать, что

h & (table.length - 1)

гарантированно выдаст действительный индекс в table. Это не будет, если table.length равно нулю (так как вы закончите с & -1, эффективным noop). Это также не принесет пользы, если table.length не является степенью 2 (вы потеряете информацию, рассмотрите случай, когда table.length равно 17).

Как компилятор HotSpot знает, что эти плохие условия не соответствуют действительности? Он должен быть более консервативным, чем программист, поскольку программист может узнать больше о ограничениях высокого уровня в системе (например, что массив никогда не бывает пустым и всегда как целое число элементов, два).