Есть ли разница в производительности между доступом к массиву жесткого кода и массиву инициализации во время выполнения?
Например, я хочу создать таблицу с квадратным корнем, используя массив SQRT [i] для оптимизации игры, но я не знаю, есть ли разница в производительности между следующей инициализацией при доступе к значению SQRT [i]:
-
Массив жестких кодов
int SQRT[]={0,1,1,1,2,2,2,2,2,3,3,.......255,255,255} -
Создать значение во время выполнения
int SQRT[65536]; int main(){ for(int i=0;i<65536;i++){ SQRT[i]=sqrt(i); } //other code return 0; }
Некоторые примеры доступа к ним:
if(SQRT[a*a+b*b]>something)
...
Я не уверен, что программа сохраняет или получает доступ к массиву жесткого кода другим способом, также я не знаю, оптимизировал ли бы компилятор массив жесткого кода для ускорения времени доступа, есть ли различия между ними при доступе к массиву?
Решение
Во-первых, вы должны сделать правильно закодированный массив:
static const int SQRT[]={0,1,1,1,2,2,2,2,2,3,3,.......255,255,255};
(также используя uint8_t вместо int вероятно, лучше, чтобы уменьшить размер массива и сделать его более удобным для кэширования)
Это имеет одно большое преимущество перед альтернативой: компилятор может легко проверить, что содержимое массива не может быть изменено.
Без этого компилятор должен быть параноиком — каждый вызов функции может изменить содержимое SQRTи каждый указатель потенциально может указывать на SQRT и, таким образом, любая запись через int* или же char* может быть изменение массива. Если компилятор не может доказать, что этого не происходит, это накладывает ограничения на виды оптимизации, которые он может выполнять, что в некоторых случаях может привести к снижению производительности.
Еще одним потенциальным преимуществом является способность разрешать вещи с участием констант во время компиляции.
При необходимости вы можете помочь компилятору разобраться с умным использованием __restrict__,
В современном C ++ вы можете получить лучшее из обоих миров; это должно быть возможно (и в разумный способ) написать код, который будет работать на время компиляции инициализировать SQRT как constexpr, Хотя лучше задать новый вопрос.
Другие решения
Как люди сказали в комментариях:
if(SQRT[a*a+b*b]>something)
это ужасный пример использования. Если это все, что вам нужно для SQRT, просто квадрат something,
Пока вы можете сказать компилятору, что SQRT ничего не псевдоним, тогда цикл выполнения сделает ваш исполняемый файл меньше, и только при загрузке добавит лишь небольшую нагрузку на процессор. Обязательно используйте uint8_tне int, Загрузка 32-битной временной памяти из 8-битной ячейки памяти не медленнее, чем из 32-битной ячейки памяти, заполненной нулями. (Дополнительный movsx Инструкция на x86 вместо использования операнда памяти более чем окупит себя в уменьшенном загрязнении кэша. Машины RISC обычно не допускают операнды памяти, так что вам всегда нужна инструкция для загрузки значения в регистр.)
Также, sqrt задержка цикла 10-21 на Sandybridge. Если вам это не нужно часто, цепочка int-> double, sqrt, double-> int не намного хуже, чем попадание в кэш L2. И лучше, чем переход на L3 или основную память. Если вам нужно много sqrtтогда обязательно сделайте LUT. Пропускная способность будет намного лучше, даже если вы подпрыгиваете в таблице и пропускаете L1.
Вы могли бы оптимизировать инициализацию, возводя в квадрат вместо sqrting, что-то вроде
uint8_t sqrt_lookup[65536];
void init_sqrt (void)
{
int idx = 0;
for (int i=0 ; i < 256 ; i++) {
// TODO: check that there isn't an off-by-one here
int iplus1_sqr = (i+1)*(i+1);
memset(sqrt_lookup+idx, i, iplus1_sqr-idx);
idx = iplus1_sqr;
}
}
Вы все еще можете получить выгоду от sqrt_lookup являющийся const (компилятор знает, что он не может иметь псевдоним). Либо использовать restrictили лгите компилятору, чтобы пользователи таблицы видели const массив, но вы на самом деле писать в него.
Это может включать ложь компилятору, объявив его extern const в большинстве мест, но не в файле, который его инициализирует. Вы должны убедиться, что это действительно работает и не создает код, ссылающийся на два разных символа. Если вы просто выбросили const в функции, которая его инициализирует, вы можете получить segfault, если компилятор поместил его в rodata (или только для чтения bss память, если она не инициализирована, если это возможно на некоторых платформах?)
Может быть, мы можем избежать лжи компилятору с помощью:
uint8_t restrict private_sqrt_table[65536]; // not sure about this use of restrict, maybe that will do it?
const uint8_t *const sqrt_lookup = private_sqrt_table;
На самом деле, это просто const указатель на const данные, а не гарантия того, что то, на что они указывают, не может быть изменено другой ссылкой.
Время доступа будет таким же. Когда вы жестко кодируете массив, процедуры библиотеки C, вызываемые до того, как main инициализирует его (во встроенной системе стартовый код копирует данные чтения и записи, то есть жестко кодируется из ПЗУ в адрес ОЗУ, где расположен массив, если массив постоянный , то к нему обращаются напрямую из ПЗУ).
Если для инициализации используется цикл for, то возникает необходимость вызова функции Sqrt.