Подтвердить что ты не робот

Почему проверка границ не устраняется?

Я написал простой benchmark, чтобы выяснить, можно ли исключить проверку границ, когда массив вычисляется поразрядным образом. Это в основном то, что делают почти все хэш-таблицы: они вычисляют

h & (table.length - 1)

как индекс в table, где h - это hashCode или производное значение. Результаты показывают, что проверка границ не устраняется.

Идея моего теста довольно проста: выведите два значения i и j, где оба гарантированно будут действительными индексами массива.

  • i - это счетчик циклов. Когда он используется как индекс массива, проверка границ удаляется.
  • j вычисляется как x & (table.length - 1), где x - некоторое изменение значения на каждой итерации. Когда он используется как индекс массива, проверка границ не устраняется.

Соответствующая часть выглядит следующим образом:

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

В другом эксперименте используется

    result ^= table[i] + j;

вместо этого. Разница в сроках составляет 15% (довольно последовательно в разных вариантах, которые я пробовал). Мои вопросы:

  • Существуют ли другие возможные причины для этого, кроме связанного исключения проверки?
  • Есть ли какая-то сложная причина, по которой я не вижу, почему нет ограничения на проверку для j?

Резюме ответов

Ответ МаркоТополника показывает, что все это сложнее, и устранение проверок границ не гарантируется как победа, особенно на его компьютере "нормальный" код медленнее, чем "замаскированный". Я предполагаю, что это связано с тем, что это позволяет сделать некоторую дополнительную оптимизацию, которая в этом случае оказывается на самом деле вредной (учитывая сложность текущих процессоров, компилятор даже не знает наверняка).

leventov answer ясно показывает, что проверка границ массива выполняется в "masked" и что ее устранение делает код столь же быстрым, как "normal".

Donal Fellows указывает на то, что маскирование не работает для таблицы нулевой длины, так как x & (0-1) равно x. Таким образом, лучшее, что может сделать компилятор, это заменить проверку привязки проверкой нулевой длины. Но это ИМХО все еще стоит того, так как проверка нулевой длины может быть легко удалена из цикла.

Предлагаемая оптимизация

Из-за эквивалентности a[x & (a.length - 1)] выбрасывается тогда и только тогда, когда a.length == 0, компилятор может сделать следующее:

  • Для каждого доступа к массиву проверьте, был ли вычисляемый индекс побитовым и.
  • Если да, проверьте, был ли один из операндов рассчитан как длина минус единица.
  • Если это так, замените проверку границ проверкой нулевой длины.
  • Пусть существующие оптимизации позаботятся об этом.

Такая оптимизация должна быть довольно простой и дешевой, поскольку она смотрит только на родительские узлы в графе SSA. В отличие от многих сложных оптимизаций, он никогда не может быть вредным, поскольку он заменяет только одну проверку немного более простой; поэтому нет проблем, даже если он не может быть удален из цикла.

Я отправлю это в списки рассылки hotspot-dev.

Новости

Джон Роуз подал RFE, и там уже есть "быстро и грязно" патч.
4b9b3361

ОТВЕТЫ

Ответ 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 знает, что эти плохие условия не соответствуют действительности? Он должен быть более консервативным, чем программист, поскольку программист может узнать больше о ограничениях высокого уровня в системе (например, что массив никогда не бывает пустым и всегда как целое число элементов, два).