Какой тип организации данных, использующий массивы C, создает самый быстрый код и почему?

Question

Учитывая следующие данные, каков наилучший способ организовать массив элементов так, чтобы был возможен самый быстрый произвольный доступ?

Каждый элемент имеет некоторый int, имя из 3 символов с '\ 0' в конце и значение с плавающей запятой .

Я вижу два возможных способа организации и доступа к такому массиву:

Первый:

typedef struct { int num; char name[4]; float val; } t_Element;
t_Element array[900000000];
//random access:
num = array[i].num;
name = array[i].name;
val = array[i].val;
//sequential access:
some_cycle:
  num = array[i].num
  i++;

Второе:

#define NUMS 0
#define NAMES 1
#define VALS 2
#define SIZE (VALS+1)
int array[SIZE][900000000];
//random access:
num = array[NUMS][i];
name = (char*) array[NAMES][i];
val = (float) array[VALS][i];
//sequential access:
p_array_nums = &array[NUMS][i];
some_cycle:
  num = *p_array_nums;
  p_array_nums++;  

Мой вопрос: какой метод быстрее и почему? Моей первой мыслью было, что второй метод создает самый быстрый код и позволяет максимально быстро копировать блок, но я сомневаюсь, что он экономит какое-либо чувствительное количество инструкций процессора по сравнению с первым методом?

Answer 1

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

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

Я должен сказать, однако, что ваш подход к реализации параллельных массивов оставляет желать лучшего. Вы должны просто объявить три массива вместо того, чтобы стать «умными» с двумерными массивами и приведением:

int nums[900000000];
char names[900000000][4];
float vals[900000000];

Answer 2

Невозможно сказать.Как и в случае любого теста, связанного с производительностью, ответ может варьироваться в зависимости от одной или нескольких ваших ОС, вашего процессора, памяти, вашего компилятора и т. Д.

Так что вам нужно проверить себя.Установите целевые показатели производительности, измерьте, оптимизируйте, повторите.

Answer 3

Первый, вероятно, быстрее, так как задержка доступа к памяти будет доминирующим фактором в производительности.В идеале вы должны обращаться к памяти последовательно и последовательно, чтобы наилучшим образом использовать загруженные строки кэша и уменьшить количество ошибок кэширования.

Конечно, схема доступа является критической в ​​любом таком обсуждении, поэтому иногда лучше использовать SoAструктура массивов) и другие периоды времени AoS (массив структур), по крайней мере, когда производительность критическая