Выполнение операций с памятью на 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).

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

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

Статья Ульриха Дреппера Что каждый программист должен знать о памяти рекомендуется прочитать, если вы хотите узнать больше о подобных вещах.

Обратите внимание, что если эта операция заключена в функцию, вы поможете оптимизатору сгенерировать лучший код, если будете использовать квалификатор 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++];
}

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

Answer 2

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

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