Выполнение операций с памятью на iPhone

Question

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

const unsigned int height = 1536; 
const unsigned int width = 2048; 

uint32_t* buffer1 = (uint32_t*)malloc(width * height * BPP); 
uint32_t* buffer2 = (uint32_t*)malloc(width * height * BPP); 

int i = 0; 
for (int x = 0; x < width; x++) 
    for (int y = 0; y < height; y++) 
     buffer1[x+y*width] = buffer2[i++]; 

Может кто-нибудь объяснить, почему используя следующее назначение:

buffer1[i++] = buffer2[x+y*width]; 

вместо одного в мой код занимает в два раза больше времени?

Answer 1

Вероятно, до поведения кэша процессора (на 12 МБ ваши изображения намного превышают кеш-память L2 256 КБ в ARM Cortex A8, находящемся в iphone3gs).

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

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

Рекомендуется прочитать статью Ульриха Дреппера What Every Programmer Should Know About Memory, если вы хотите узнать больше об этом.

Обратите внимание, что если у вас есть эта операция завернутой в функцию, то вам поможет оптимизатору генерировать лучший код, если вы используете restrict спецификатора на ваших аргументах указателей, например:

void reorder(uint32_t restrict *buffer1, uint32_t restrict *buffer2) 
{ 
    int i = 0; 
    for (int x = 0; x < width; x++) 
     for (int y = 0; y < height; y++) 
      buffer1[x+y*width] = buffer2[i++]; 
} 

(The restrict дает обещание компилятору, что данные, на которые указывают два указателя, не перекрываются, что в этом случае необходимо, чтобы функция имела смысл в любом случае).

Answer 2

Каждый доступ к пикселям в первом имеет линейный locality of reference, второй - ваш кеш на каждом считывании, который должен иметь основную память для каждого.

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