Есть ли разница в производительности между доступом к массиву жесткого кода и массивом инициализации времени выполнения?

Question

Например, я хочу создать квадратную корневую таблицу с использованием массива SQRT [i] для оптимизации игры, но я не знаю, есть ли разница в производительности между следующей инициализацией при доступе к значению SQRT [i]:

1. жёстко массив

   int SQRT[]={0,1,1,1,2,2,2,2,2,3,3,.......255,255,255} 
   

2. Сформировать значение во время выполнения

   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) 
    ... 

Я не ясно, если программа хранит или имеет доступ к массив жесткого кода по-другому, и я не знаю, если компилятор будет оптимизировать жесткий -code для ускорения времени доступа, есть ли различия в производительности между ними при доступе к массиву?

Answer 1

Во-первых, вы должны сделать жестко запрограммированный право массива:

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. Однако лучше всего задать новый вопрос.

Answer 2

Время доступа будет таким же. Когда вы жестко задаете массив, подпрограммы библиотеки C, вызываемые до начала инициализации, инициализируют его (во встроенной системе код запуска копирует данные чтения записи, т.е. жестко закодированные из ПЗУ в адрес RAM, где находится массив, если массив постоянный , то доступ к нему осуществляется непосредственно из ПЗУ).

Если цикл for используется для инициализации, тогда есть накладные расходы на вызов функции Sqrt.

Answer 3

Как говорили в комментариях:

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