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

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.

Новости

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