Замедляет ли доступ к массивам мою функцию?
У меня есть 2 функции:
unsigned long long getLineAsRow(unsigned long long board, int col) {
unsigned long long column = (board >> (7-(col - 1))) & col_mask_right;
column *= magicLineToRow;
return (column >> 56) & row_mask_bottom;
}
unsigned long long getDiagBLTR_asRow(unsigned long long board, int line, int row) {
unsigned long long result = board & diagBottomLeftToTopRightPatterns[line][row];
result = result << diagBLTR_shiftUp[line][row];
result = (result * col_mask_right) >> 56;
return result;
}
Единственное большое отличие, которое я вижу, это доступ к 2-dim-массиву. Определяется как
int diagBRTL_shiftUp[9][9] = {};
Я вызываю обе функции 10.000.000 раз:
getLineAsRow ... time used: 1.14237s
getDiagBLTR_asRow ... time used: 2.18997s
Я проверил это с помощью cl (vc ++) и g ++. Почти без разницы.
Это действительно огромная разница, есть ли у вас какие-либо советы?
Решение
На вопрос о том, что создает разницу между временами выполнения ваших двух функций, на самом деле невозможно ответить, не зная ни получившийся код ассемблера, ни то, какие глобальные переменные, к которым вы обращаетесь, фактически являются константами, которые можно скомпилировать прямо в код. Во всяком случае, анализируя ваши функции, мы видим, что
-
функция 1
- читает два аргумента из стека, возвращает одно значение
- читает три глобальных, которые могут быть или не быть константами
- выполняет шесть арифметических операций (два минуса в
7-(col-1)можно свернуть в одно вычитание)
-
функция 2
- читает три аргумента из стека, возвращает одно значение
- читает один глобальный, который может или не может быть константой
- разыменовывает два указателя (не четыре, см. ниже)
- выполняет пять арифметических операций (три, которые вы видите, две, которые производят индексы массива)
Обратите внимание, что доступ к 2D-массивам фактически сводится к одному доступу к памяти. Когда ты пишешь diagBottomLeftToTopRightPatterns[line][row]твой компилятор превращает его во что-то вроде diagBottomLeftToTopRightPatterns[line*9 + row], Это две дополнительные арифметические инструкции, но только один доступ к памяти. Более того, результат расчета line*9 + row может быть переработан для доступа ко второму 2D массиву.
Арифметические операции выполняются быстро (порядка одного цикла ЦП), чтение из памяти может занять от четырех до двадцати циклов ЦП. Итак, я предполагаю, что три глобала, к которым вы обращаетесь в функции 1, являются константами, которые ваш компилятор встроил прямо в код ассемблера. Это оставляет функции 2 больше доступа к памяти, делая ее медленнее.
Однако меня беспокоит одна вещь: если я предполагаю, что у вас нормальный процессор с тактовой частотой не менее 2 ГГц, ваше время показывает, что ваши функции потребляют более 200 или 400 циклов соответственно. Это значительно больше, чем ожидалось. Даже если ваш процессор не имеет значений в кеше, ваши функции не должны занимать более примерно 100 циклов. Поэтому я бы посоветовал еще раз взглянуть на то, как вы синхронизируете свой код, я полагаю, что в вашем цикле измерения есть еще немного кода, который портит ваши результаты.
Другие решения
Эти функции делают совершенно разные вещи, но я предполагаю, что это не имеет отношения к вопросу.
Иногда эти тесты не показывают реальная стоимость функции.
В этом случае основной ценой является доступ к массиву в памяти. После первого доступа он будет в кеше, и после этого ваша функция будет работать быстро. Таким образом, вы на самом деле не измеряете эту характеристику. Несмотря на то, что в тесте 10 000 000 итераций, вы платите цену только один раз.
Теперь, если вы выполняете эту функцию в пакете, вызывая ее много раз навалом, тогда это не проблема. Кеш будет теплым.
Если вы обращаетесь к нему спорадически, в приложении, которое имеет высокие требования к памяти и часто сбрасывает ошибки ЦП, это может быть проблемой производительности. Но это, конечно, зависит от контекста: как часто это называется и т. Д.