Почему порядок объявления массива так сильно влияет на производительность?

Во-первых, при настройке функции частотного анализа с использованием инфраструктуры Accelerate абсолютное системное время постоянно составляло 225 мс на итерацию. Затем прошлой ночью я изменил порядок объявления двух массивов, и внезапно он снизился до 202 мс. Увеличение на 10% за счет простого изменения порядка объявления кажется безумием. Может кто-нибудь объяснить мне, почему компилятор (который настроен на оптимизацию) еще не находит это решение?

Дополнительная информация: Перед циклом есть некоторая настройка массивов, используемых в цикле, состоящая из преобразования их из целых чисел в массивы с плавающей запятой (для Accelerate) и последующего взятия sin и cos массива времени (длиной 16 строк). Все массивы с плавающей запятой (8 массивов x 1000 элементов) объявляются первыми в функции (после проверки правильности параметров). Они всегда объявляются одного и того же размера (константой), потому что в противном случае производительность страдала из-за незначительного сокращения занимаемой площади. Я пробовал сделать их глобальными, но я думаю, что компилятор уже понял это, так как производительность не изменилась. Цикл состоит из 25 строк.

---Дополнения---

Да, "-Os" - это флаг. (в любом случае по умолчанию в Xcode: самый быстрый, самый маленький)

(ниже по памяти - не пытайтесь скомпилировать его, потому что я не вставил такие вещи, как шаг (который равен 1) и т. д. Однако все вызовы Accelerate есть)

передаваемые параметры: inttimearray, intamparray, length, scale1, scale2, amp

float trigarray1[maxsize];
float trigarray2[maxsize];
float trigarray3[maxsize];
float trigarray4[maxsize];
float trigarray5[maxsize];
float temparray[maxsize];
float amparray[maxsize];    //these two make the most change
float timearray[maxsize];    //these two make the most change

vDSP_vfltu32(inttimearray,timearray,length); //convert to float array
vDSP_vflt16(intamparray,amparray,length);    //convert to float array

vDSP_vsmul(timearray,scale1,temparray,length);    //scale time and store in temp
vvcosf(temparray,trigarray3,length);     //cos of temparray
vvsinf(temparray,trigarray4,length);     //sin of temparray
vDSP_vneg(trigarray4,trigarray5,length); //negative of trigarray4

vDSP_vsmul(timearray,scale2,temparray,length); //scale time and store in temp
vvcosf(temparray,trigarray1,length);           //cos of temparray
vvsinf(temprray,trigarray2,length);            //sin of temparray

float ysum;
vDSP_sve(amparray,ysum,length);    //sum of amparray

float csum, ssum, ccsum, sssum, cssum, ycsum, yssum;

for (i = 0; i<max; i++) {

    vDSP_sve(trigarray1,csum,length);    //sum of trigarray1
    vDSP_sve(trigarray2,ssum,length);    //sum of trigarray2

    vDSP_svesq(trigarray1,ccsum,length); //sum of trigarray1^2
    vDSP_svesq(trigarray2,sssum,length); //sum of trigarray2^2

    vDSP_vmul(trigarray1,trigarray2,temparray,length); //temp = trig1*trig2
    vDSP_sve(temparray,cssum,length);                  //sum of temp array
    // 2 more sets of the above 2 lines, for the 2 remaining sums

    amp[i] = (arithmetic of sums);

    //trig identity to increase the sin/cos by a delta frequency
    //vmma is a*b+c*d=result
    vDSP_vmma (trigarray1,trigarray3,trigarray2,trigarray4,temparray,length);
    vDSP_vmma (trigarray2,trigarray3,trigarray1,trigarray5,trigarray2,length);
    memcpy(trigarray1,temparray,length*sizeof(float));
}

---Текущее решение---

Я сделал некоторые изменения следующим образом:

Все массивы объявлены выровненными и обнулены (я объясню далее), а maxsize теперь кратен 16.

__attribute__ ((align (16))) float timearray[maxsize] = {0};

Я обнулил все массивы, потому что теперь, когда длина меньше maxsize, я округляю длину до ближайшего числа, кратного 16, чтобы все зацикленные функции работали с шириной, кратной 16, не влияя на размер суммы.

Преимущества:

  • Небольшой прирост производительности
  • Скорость почти постоянна независимо от порядка объявления массивов (что теперь делается прямо перед тем, как они понадобятся, а не все в большом блоке)
  • Скорость также почти постоянна для любой длины 16 (т. е. от 241 до 256 или от 225 до 240...), тогда как раньше, если длина менялась от 256 до 255, функция теряла производительность на 3+%.

В будущем (возможно, с этим кодом, поскольку требования к анализу все еще меняются), я понимаю, что мне нужно будет больше учитывать использование стека и выравнивание/фрагменты векторов. К сожалению, для этого кода я не могу сделать эти массивы статическими или глобальными, так как эта функция может вызываться более чем одним объектом одновременно.


person Adam Jones    schedule 10.08.2012    source источник
comment
Вы можете вернуться к 225 мс, просто поменяв местами порядок объявления массива?   -  person Dan F    schedule 10.08.2012
comment
Да, с этими двумя, последовательно. И я обнаружил, что если я переключаю другие массивы, я могу получить еще худшую производительность 290+ мс или в других конфигурациях 210 мс. Сейчас все они объявлены блоком строк (по одной в строке, чтобы быстрее тестировать порядок). Тем не менее, я попытался переместить каждое объявление прямо перед тем, как оно было необходимо, и получил 290 мс.   -  person Adam Jones    schedule 10.08.2012
comment
Может код покажешь? Хотя бы по декларациям, если они все вместе.   -  person Analog File    schedule 10.08.2012
comment
Может дело в кешировании? С массивами в одном порядке, возможно, вы с большей вероятностью получите данные в одной операции, которые вам понадобятся в следующей операции.   -  person JeremyP    schedule 10.08.2012


Ответы (5)


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

__attribute__ ((align (16))) float ...[maxsize];

Или убедитесь, что maxsize кратно 16. Это определенно может привести к попаданию в 10%, если в одной конфигурации вы выровнены, а в другой нет. Векторные операции могут быть чрезвычайно чувствительны к этому.

Следующая серьезная проблема, с которой вы можете столкнуться, — это огромный стек (при условии, что maxsize довольно большой). ARM может работать с числами меньше 4 КБ гораздо эффективнее, чем с числами больше 4 КБ (поскольку он может работать только с 12-битными непосредственными значениями). Таким образом, в зависимости от того, как компилятор оптимизировал его, перемещение amparray вниз по стеку может привести к более сложной математике для доступа к нему.

Когда небольшие нелепые вещи приводят к большим изменениям производительности, я всегда рекомендую использовать сборку (Product>Generate Output>Assembly) и посмотреть, что изменилось в выводе компилятора. Я также настоятельно рекомендую тур по сборке ARM, чтобы вы начали понимать, что вы снова смотрю. (Убедитесь, что вы установили вывод «Для архивации», чтобы увидеть оптимизированный результат.)

Вы также должны сделать еще несколько вещей:

  • Попробуйте переписать эту процедуру как простой C вместо использования Accelerate. Да, я знаю, что Accelerate всегда быстрее, но это не так. Все эти вызовы функций довольно дороги, и компилятор часто может лучше векторизовать простое умножение и сложение, чем Accelerate, по моему опыту. Это особенно верно, если ваш шаг равен 1, ваши векторы не огромны, и вы используете устройство с 1-2 ядрами, такое как iPad. В тот момент, когда у вас есть код, который обрабатывает шаг (если вам не нужен шаг), он сложнее (медленнее), чем код, который вы написали бы вручную. По моему опыту, Accelerate кажется очень хорошим в линейных и трансцендентных (например, косинусах больших таблиц), но не так хорош в простой векторной и матричной математике.

  • Если этот код действительно важен для вас, я обнаружил, что написание сборки от руки определенно может опередить компилятор. Я даже не очень хорошо разбираюсь в ассемблере ARM, и мне удалось в два раза превзойти компилятор в простой матричной математике (и компилятор раздавил Accelerate). Я особенно говорю о вашем цикле, который, кажется, просто складывает и умножает. Написание сборки от руки, конечно, утомительно, и тогда вам придется поддерживать версию C для ассемблера, но когда это действительно важно, это очень быстро.

person Rob Napier    schedule 10.08.2012
comment
Недавно я изменил свои блоки анализа и теперь понимаю, что могу значительно уменьшить максимальный размер, что может сделать это упражнение бесполезным. Первоначально весь код был написан на чистом C и стал в 10 раз медленнее, чем когда я заменил его на Accelerate (vdsp_vmma и vvsinf значительно быстрее, чем C) — опять же, когда блоки были больше, а длина итерируемого массива и индекс были переменными ( ни то, ни другое не верно). Время, которое у меня есть сейчас, приемлемо, и я не уверен, что ASM стоил бы потраченного времени. Однако мне любопытно выравнивание - я пробовал этот атрибут безрезультатно. Есть мысли по этому поводу? - person Adam Jones; 10.08.2012
comment
Спасибо за заметку о vdsp_vmma. Я определенно согласен с vvsinf; не профилировал вмма. Выравнивание не всегда имеет смысл, если данные уже выровнены (что может произойти случайно или в результате оптимизации) или если конкретная функция не слишком на них полагается. Иногда они выполняют отдельную итерацию для обработки начальных невыровненных значений, пока не смогут перейти к выровненным данным. Иногда они просто не требуют выровненных данных. - person Rob Napier; 10.08.2012
comment
Спасибо. Я дам еще один шанс выровнять и поиграть с maxsize. Единственная причина, по которой я пошел в Accelerate, заключалась в том, что размер блока был огромным. И я просто тратил слишком много времени на итерацию. Теперь, когда я направился к меньшему блоку, прямой C может быть быстрее без накладных расходов. Однако я не буду его удалять сейчас, так как это делает функцию более читабельной (опять же, показан не весь мой код, но недостающие строки — это простая арифметика). - person Adam Jones; 10.08.2012

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

Я собираюсь использовать этот ответ, чтобы предложить некоторые возможности и прокомментировать некоторые вопросы, поднятые в других ответах и ​​комментариях к этому вопросу.

Во-первых, имея 7 массивов по 4 КБ каждый, вы используете почти размер кеша L1. В зависимости от того, сколько еще используется стеком и тому подобное, вы можете перегружать кеш. Это может объяснить, почему уменьшение размера блока улучшило производительность: с меньшими блоками в каждой итерации использовалось меньше памяти, и вся она помещалась в кеш, поэтому во время итерации почти ничего не выбрасывалось. Еще один способ справиться с таким переполнением кеша — это анализ полос: вместо выполнения sve, svesq, vmul, vmma и memcpy для всей длины, выполните их все для части длины (например, половины), а затем выполните все их на другой части, и повторяйте по мере необходимости, пока они не будут полностью обработаны.

trigarray5 существует только для того, чтобы вторая vmma отрицала trigarray4. Удалите trigarray5 и вызовите vmmsb (вычитание вместо добавления) с помощью trigarray4. Это также уменьшает использование памяти.

Геометрия кэша иногда приводит к перегрузке, даже если используется меньше данных, чем заполняет кэш. Кэш разбит на наборы, и каждый адрес памяти должен быть сопоставлен с определенным набором. Например, кэш с 32 768 байтами может иметь 1024 «строки» по 32 байта каждая, но он может быть организован в 256 наборов из четырех строк. Любой адрес памяти отображается в один набор, и он должен использовать одну из четырех строк в этом наборе. Если у вас есть пять массивов, которые начинаются с одного и того же адреса по модулю этой геометрии (или которые существенно перекрываются), то они будут бороться за четыре строки в каждом наборе, отбрасывая друг друга по мере продвижения. Этого можно избежать, когда массивы размещаются в памяти последовательно, как это обычно делает компилятор, когда массивы просто объявляются один за другим, но могут возникнуть сложности. Без исполняемого кода это трудно определить.

Выравнивание массивов по кратным 16 байтам нормально и может немного помочь. В определенных ситуациях очень помогает. Когда это возможно, многие подпрограммы vDSP обрабатывают несколько начальных элементов, чтобы достичь четко выровненной границы, а затем используют быстрый SIMD-код почти до конца массива, когда может потребоваться отдельная обработка еще нескольких элементов. Однако это не всегда возможно, например, когда подпрограмме, работающей с несколькими векторами, передаются векторы с разными выравниваниями. (Обработка элементов для выравнивания одного указателя приводит к смещению других указателей.) Помимо добавления атрибута align, другим способом выравнивания массивов является выделение их с помощью стандартных процедур выделения памяти, таких как malloc. В Mac OS X и iOS malloc возвращает адреса, выровненные по 16 байт.

Размер стека и тот факт, что ARM имеет ограниченные непосредственные значения, скорее всего, не проблема, вычисление векторных адресов должно быть тривиальной частью вычислений в вашем коде. (Кроме того, в ARM есть несколько интересных гибких непосредственных значений, а не просто 12-битные целые числа.)

Стоимость фактического вызова функции и самого возврата, вероятно, тривиальна. Поставляемые Apple компиляторы «не лучше векторизируют простое умножение и сложение, чем Accelerate», а вызовы функций не «довольно дороги».

Вы пропустили шаги. Если они не едины, вы, вероятно, много выиграете, переписав свой код так, чтобы данные имели единичный шаг при вызове подпрограмм vDSP.

Предсказание ветвлений здесь, скорее всего, не проблема.

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

person Eric Postpischil    schedule 11.08.2012
comment
Для будущих ссылок другим, я не использовал vmmsb, потому что это значительно медленнее, чем создание отрицательного массива и использование vmma. Я не думал делать куски за раз — это было бы хорошей идеей для огромных векторов. Из вашего ответа и других ответов я вижу, что в будущем мне нужно гораздо больше заботиться об использовании памяти, чем раньше. - person Adam Jones; 11.08.2012
comment
Производительность vmmsb и vmma должна быть одинаковой в текущих версиях iOS. (Исходный код кажется идентичным, за исключением изменений добавления и вычитания.) На Mac vmma оптимизирована, а vmmsb — нет. Это упущение; отправьте запрос на bugreport.apple.com для оптимизации vmmsb. Если вы заметили падение производительности ARM, это может быть иллюзией из-за других обсуждаемых эффектов. Если это воспроизводимо, отправьте отчет об ошибке и укажите конкретные версии программного обеспечения, в частности, версию целевой ОС и модель устройства. - person Eric Postpischil; 11.08.2012
comment
Ты прав. Я тестировал функции внутри простого приложения для Mac. Тем не менее, я только что протестировал его в голом приложении iOS как на симуляторе, так и на своем телефоне. На симуляторе я получаю замедление примерно на 40% с vmmsb (в приложении Mac это не так уж плохо), а на iPhone производительность точно такая же. Спасибо, вы сохранили мне немного памяти. - person Adam Jones; 12.08.2012

Вероятно, это связано с предсказанием ветвления и с тем, какие элементы находятся внутри ваших массивов.

См. этот пост для УДИВИТЕЛЬНОЙ справки. Ваш пост может быть похож на этот пост тем, что при объявлении ваших массивов в одном порядке данные отображаются «отсортированными», а в другом порядке - нет.

Почему быстрее обрабатывать отсортированный массив, чем несортированный массив?

person MikeS    schedule 10.08.2012
comment
В этом коде нет операторов IF. Как я понимаю, без кондиционалов нечего разветвлять. Кроме того, я протестировал добавление __property___((aligned)) для массивов Accelerate, но, похоже, компилятор уже их выровнял. - person Adam Jones; 10.08.2012
comment
У вас точно есть филиал. Это в for(). Я не говорю, что предсказание ветвлений - это ваша проблема, но, безусловно, есть условное выражение, которое вызывается max раз. - person Rob Napier; 10.08.2012
comment
Предсказание ветвления на for в этом случае, скорее всего, тривиально, потому что оно будет перегружено работой подпрограмм vDSP. Даже если ветвь для for выпадает из кеша истории ветвлений и каждый раз неверно предсказывается, это не должно сильно влиять на производительность. - person Eric Postpischil; 11.08.2012
comment
Изменение порядка массивов не влияет на сортировку элементов внутри массивов. - person Krazy Glew; 12.08.2012
comment
Конечно. Я не очень внимательно прочитал вопрос и только что прочитал ветку, на которую я ссылался, и это звучало как возможная причина. Посмотрев на код Адама, я вижу, что предсказание ветвлений не имеет к нему никакого отношения. - person MikeS; 14.08.2012

Просто предположение здесь. Выравнивание?

Эти библиотеки должны использовать SIMD-инструкции, и время их выполнения зависит от выравнивания даже в некоторых случаях, когда выравнивание не требуется.

Также выравнивание кэшлайна может играть или не играть роль.

Эти массивы размещаются в стеке, а это означает, что у вас мало контроля над выравниванием этих данных, кроме внутренней гарантии sizeof(float) и архитектурной гарантии для первого объекта (64-битное выравнивание де-факто гарантируется для первой локальной переменной, если вы компилируете в 64-битном режиме).

Вы можете попытаться проверить, каково выравнивание данных, распечатав/зарегистрировав адреса. И поиграть с временными эффектами выравнивания, определив структуру для хранения данных и используя malloc для получения памяти для них (получите больше памяти, чем вам нужно, чтобы вы могли размещать структуру по разным смещениям в блоке памяти, особенно если вы хочу поиграть с выравниванием кэшлайна).

person Analog File    schedule 10.08.2012

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

Обычными виновниками таких потерь производительности являются:

  • неправильные предсказания ветвей

  • кеш-эффекты

    • пропускная способность (просто слишком много данных, например, 1 МБ данных не помещается в кэш 32 КБ)

    • конфликты кеша (например, более 4 адресов, которые совпадают по модулю 8 КБ в 4-стороннем ассоциативном кеше 32 КБ)

  • Эффекты DRAM

    • DRAM page misses

У меня возникли проблемы с разбором того, что вы говорите: что такое MAXSIZE? Вы говорите 7 * 4 КБ... Но у вас есть 8 массивов, поэтому я сомневаюсь, что вы говорите, что MAXSIZE = 1024. Вы говорите, что MAXSIZE составляет 7 * 1024? (*4В/поплавок?)

В любом случае: если MAXSIZE для каждого отдельного массива составляет около 28 КБ, то вы приближаетесь к размеру кеша для многих систем. В этом случае я бы заподозрил эффекты страницы DRAM — я бы подозревал, что при хорошей производительности массив, к которому чаще всего обращаются, помещается на отдельную страницу DRAM.

Вы не говорите, что работает лучше, но я бы предположил:

float amparray[maxsize];    //these two make the most change
float timearray[maxsize];    //these two make the most change

глядя на ваш код, timearray кажется наиболее доступным. Если производительность лучше с timearray second, и мое предположение о MAXSIZE верно, то я бы поспорил, что это эффекты страницы DRAM.

Краткое объяснение: в DRAM есть концепции страниц и банков. Не путать со страницами ОС. Каждый чип DRAM и, следовательно, каждый модуль DIMM имеют 4 или 8 внутренних банков. Каждый банк может иметь одну открытую страницу. Если вы получаете доступ к данным с той же страницы, того же банка, это быстрее. Если вы получаете доступ к данным с уже открытой страницы в другом банке, быстро, но медленнее, чем на той же странице в том же банке. Если вам нужна другая страница в том же банке, очень медленно. Если у вас есть кеш обратной записи, записи происходят почти случайным образом, поэтому вы можете получить очень плохое поведение страницы.

Однако, если я неправильно угадал про MAXSIZE, то, вероятно, это эффект кеша.

КРАСНЫЙ ФЛАГ: вы говорите: «Я не добавил таких вещей, как шаг». Strides печально известны тем, что данные в кэше ведут себя плохо. Кэши обычно устанавливаются ассоциативно, что означает, что они имеют то, что я называю «резонансом» — адреса, которые совпадают по модулю резонанса кеша, будут отображаться в один и тот же набор. Если у вас больше таких, чем ассоциативность, вы будете лупить.

Рассчитайте резонанс как размер кэша, деленный на ассоциативность. Например. если у вас 32К 4-канальный ассоциативный кеш, ваш резонанс 8К.

В любом случае... если вы получаете доступ только к вещам на ходу, то размещение массива может иметь значение. Например. скажем, что у вас есть шаг 16. То есть доступ к элементам 0, 16, 32, 48 и т. д. Если MAXSIZE было 7 * 1024, как я догадался выше, то элементы

float trigarray1[maxsize];
float trigarray2[maxsize];
float trigarray3[maxsize];
float trigarray4[maxsize];
float trigarray5[maxsize];
float temparray[maxsize];
float amparray[maxsize];    //these two make the most change
float timearray[maxsize];    //these two make the most change

тогда следующие массивы будут конфликтовать — их пошаговые шаблоны доступа будут отображаться в одни и те же наборы:

trigarray1, trigarray5
trigarray2, temparray
trigarray3, amparray
trigarray4, timearray,

если вы поменяете местами amparray и timearray, то

   trigarray3 will conflict with timearray
and
   trigarray4 with amparray

trigarray4 и timarray кажутся наиболее часто используемыми, поэтому я предполагаю, что если у вас есть шаг, например 0, 16, 32, 348 или любой шаг, начинающийся с 0, то эти два конфликтующих массива - ваша проблема.

Однако у вас могут быть разные шаблоны шагов: 0, 16, 32, 48... в одном массиве и 1,17,33,... в другом. Тогда разные пары массивов будут конфликтовать.

--

У меня недостаточно информации, чтобы диагностировать вашу проблему здесь.

Возможно, вы сможете сделать это самостоятельно, если у вас есть доступ к хорошим инструментам повышения производительности.

Например. на процессорах Intel вы можете записать то, что я называю профилем промаха кэша, записать идеальные физические адреса памяти, вычислить, на какие наборы они сопоставляются в кэше, и сгенерировать гистограмму. Если вы видите шипы, это, вероятно, проблема. Точно так же вы можете создавать профили промахов страницы DRAM или промаха банка. Я упоминаю Intel только потому, что я разработал некоторые аппаратные средства для такого измерения производительности. То же самое должно быть доступно на ARM (если нет, может быть, я мог бы разбогатеть, продавая инструменты для этого... :-)).

Если это проблема, как вы можете это исправить?

Ну, попробовав разные места размещения, как вы объяснили выше. Это может помочь как в случае успеха (конфликты наборов кэшей), так и при проблемах со страницами DRAM.

Если проблема заключается в шагах, вы можете попробовать немного изменить размеры массива — MAXSIZE + 4, MAXSIZE 8 и т. д. Это может эффективно компенсировать шаги. (В кодах суперкомпьютеров часто встречаются массивы размером 255 или 257 по той же причине смещения шаблонов доступа с шагом, чтобы не конфликтовать.)

person Krazy Glew    schedule 11.08.2012