Почему проверка границ не устраняется?
Я написал простой бенчмарк, чтобы выяснить, можно ли устранить проверку границ, когда массив вычисляется по битам и. Это в основном то, что делают почти все хеш-таблицы: они вычисляют
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?
Краткое изложение ответов
Ответ МаркоТопольника показывает, что все гораздо сложнее, и устранение проверок границ не гарантированно является победой, особенно на его компьютере "нормальный" код работает медленнее, чем "маскируемый". Я предполагаю, что это из-за того, что он допускает некоторую дополнительную оптимизацию, которая в данном случае оказывается действительно вредной (учитывая сложность текущих процессоров, компилятор даже не знает наверняка).
Ответ Левентова ясно показывает, что проверка границ массива выполняется в "маске" и что его устранение делает код таким же быстрым, как "нормальный".
Donal Fellows указывает на тот факт, что маскирование не работает для таблицы нулевой длины, так как x & (0-1) равно x, Поэтому лучшее, что может сделать компилятор, - это заменить проверку проверки проверкой нулевой длины. Но это ИМХО все еще стоит, поскольку проверку нулевой длины можно легко вывести из цикла.
Предлагаемая оптимизация
Из-за эквивалентности a[x & (a.length - 1)] бросает если и только если a.length == 0Компилятор может сделать следующее:
- Для каждого доступа к массиву проверьте, был ли индекс вычислен с помощью побитового и.
- Если это так, проверьте, был ли какой-либо из операндов вычислен как длина минус один.
- Если это так, замените проверку границ проверкой нулевой длины.
- Пусть существующие оптимизации позаботятся об этом.
Такая оптимизация должна быть довольно простой и дешевой, поскольку она смотрит только на родительские узлы в графе SSA. В отличие от многих сложных оптимизаций, он никогда не может быть вредным, поскольку он заменяет только одну проверку на несколько более простую; так что нет проблем, даже если это нельзя вывести из цикла.
Я опубликую это в списках рассылки hotspot-dev.
Новости
3 ответа
- Нет, это, очевидно, является следствием неумелого устранения проверки границ.
Я продлил тест Марко Топольника:
@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, а не Stackru, ИМХО.
Для начала, основное различие между вашими двумя тестами, безусловно, заключается в устранении проверки границ; однако то, как это влияет на машинный код, далеко от того, что можно было бы предположить наивным.
Моя гипотеза:
Проверка границ более сильна как точка выхода из цикла, чем как дополнительный код, который вводит накладные расходы.
Точка выхода из цикла предотвращает следующую оптимизацию, которую я выбрал из выданного машинного кода:
- цикл развернут (это верно во всех случаях);
- Кроме того, выборка из этапа массива выполняется сначала для всех развернутых этапов, затем выполняется запись в аккумулятор для всех этапов.
Если цикл может разорваться на каком-либо шаге, эта подготовка приведет к выполнению работы для шагов цикла, которые фактически никогда не выполнялись.
Рассмотрим эту небольшую модификацию вашего кода:
@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
"Замаскированный индекс" отреагировал предсказуемо (сокращение накладных расходов), но "нормальный индекс" неожиданно стал намного хуже. По-видимому, это связано с плохим соответствием между дополнительным шагом оптимизации и моей конкретной моделью процессора.
Моя точка:
Модель производительности на таком детальном уровне очень нестабильна и, как свидетельствует мой процессор, даже нестабильна.
Для того, чтобы безопасно устранить эту проверку границ, необходимо доказать, что
h & (table.length - 1)
гарантированно создать действительный индекс в table, Не будет, если table.length ноль (как вы в конечном итоге & -1Эффектный-ноуп). Это также не будет полезным, если table.length не степень 2 (вы потеряете информацию; рассмотрим случай, когда table.length 17).
Как может компилятор HotSpot узнать, что эти плохие условия не соответствуют действительности? Он должен быть более консервативным, чем программист, поскольку программист может больше знать об ограничениях высокого уровня в системе (например, что массив никогда не бывает пустым и всегда является числом элементов, которое является степенью власти). два).