Подтвердить что ты не робот

Заставляя GCC выполнять переключение циклов проверки размера среды memcpy?

Есть ли какой-либо надежный способ заставить GCC (или любой компилятор) исключить проверки размера времени выполнения в memcpy() вне цикла (где этот размер не является константой времени компиляции, но константа в этом цикле), специализируясь на цикл для каждого соответствующего диапазона размеров, а не многократно проверять размер внутри него?

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

Исходный код находится в Cython, но я уменьшил его до чистого прокси C следующим образом:

void take(double * out, double * in,
          int stride_out_0, int stride_out_1,
          int stride_in_0, int stride_in_1,
          int * indexer, int n, int k)
{
    int i, idx, j, k_local;
    k_local = k; /* prevent aliasing */
    for(i = 0; i < n; ++i) {
        idx = indexer[i];
        for(j = 0; j < k_local; ++j)
            out[i * stride_out_0 + j * stride_out_1] =
            in[idx * stride_in_0 + j * stride_in_1];
    }
}

Шаги являются переменными; в общем случае массивы даже не гарантируются быть смежными (поскольку они могут быть несмежными срезами больших массивов). Однако для частного случая с-смежных массивов я оптимизировал приведенное выше следующее:

void take(double * out, double * in,
          int stride_out_0, int stride_out_1,
          int stride_in_0, int stride_in_1,
          int * indexer, int n, int k)
{
    int i, idx, k_local;
    assert(stride_out_0 == k);
    assert(stride_out_0 == stride_in_0);
    assert(stride_out_1 == 1);
    assert(stride_out_1 == stride_in_1);
    k_local = k; /* prevent aliasing */
    for(i = 0; i < n; ++i) {
        idx = indexer[i];
        memcpy(&out[i * k_local], &in[idx * k_local],
               k_local * sizeof(double));
    }
}

(Утверждений нет в исходном коде, вместо этого он проверяет смежность и вызывает оптимизированную версию, если это возможно, и неоптимизированный, если нет).

Эта версия в большинстве случаев очень хорошо оптимизируется, поскольку обычный вариант использования, если для малых n и больших k. Однако имеет место и противоположный случай использования (большой n и малый k), и это оказывается для частного случая n == 10000 и k == 4 (который нельзя исключить как представитель важной части гипотетического рабочего процесса), версия memcpy() в 3,6 раза медленнее оригинала. Это, по-видимому, главным образом из-за того, что k не является константой времени компиляции, о чем свидетельствует тот факт, что эта следующая версия выполняет (почти или точно, в зависимости от настроек оптимизации), а также оригинальную (или лучше, иногда), для частного случая k == 4:

    if (k_local == 4) {
        /* this optimizes */
        for(i = 0; i < n; ++i) {
            idx = indexer[i];
            memcpy(&out[i * k_local], &in[idx * k_local],
                   k_local * sizeof(double));
        }
    } else {
        for(i = 0; i < n; ++i) {
            idx = indexer[i];
            memcpy(&out[i * k_local], &in[idx * k_local],
                   k_local * sizeof(double));
        }
    }

Очевидно, что нецелесообразно жестко кодировать цикл для каждого конкретного значения k, поэтому я попытался сделать следующее (в качестве первой попытки, которая позже может быть обобщена, если она сработает):

    if (k_local >= 0 && k_local <= 4) {
        /* this does not not optimize */
        for(i = 0; i < n; ++i) {
            idx = indexer[i];
            memcpy(&out[i * k_local], &in[idx * k_local],
                   k_local * sizeof(double));
        }
    } else {
        for(i = 0; i < n; ++i) {
            idx = indexer[i];
            memcpy(&out[i * k_local], &in[idx * k_local],
                   k_local * sizeof(double));
        }
    }

К сожалению, эта последняя версия не быстрее оригинальной версии memcpy(), что несколько разочаровывает мою веру в возможности оптимизации GCC.

Есть ли способ дать дополнительные "подсказки" GCC (любыми способами), которые помогут ему сделать правильные вещи здесь? (И еще лучше, есть ли "подсказки", которые могли бы надежно работать с разными компиляторами? Эта библиотека скомпилирована для разных целей.)

Приведенные результаты относятся к GCC 4.6.3 на 32-разрядном Ubuntu с флагом "-O2", но я также тестировал версии GCC 4.7.2 и "-O3" с аналогичными (но не идентичными) результатами. Я отправил свой тестовый жгут в LiveWorkspace, но тайминги взяты из моей машины с помощью команды time(1) (я не знаю, насколько надежны тайм-ауты LiveWorkspace есть.)

EDIT: Я также рассмотрел возможность установки "магического номера" для некоторого минимального размера для вызова memcpy() с, и я мог бы найти такое значение при повторном тестировании, но я не знаю, насколько обобщаю мои результаты в разных компиляторах/платформах. Есть ли какое-либо эмпирическое правило, которое я мог бы использовать здесь?

ДАЛЬНЕЙШЕЕ ИЗМЕНИТЬ: Реализованные переменные k_local в этом случае бесполезны, поскольку наложение не возможно; это было уменьшено из некоторых экспериментов, в которых я работал, где это было возможно (k был глобальным), и я забыл, что я его изменил. Просто проигнорируйте эту часть.

EDIT TAG: Реализовано Я также могу использовать С++ в более новых версиях Cython, поэтому пометка как С++ в случае, если что-нибудь может помочь с С++...

ЗАКЛЮЧИТЕЛЬНЫЙ РЕДАКТ: Вместо того, чтобы сбрасываться на сборку для специализированного memcpy(), кажется лучшим эмпирическим решением для моей локальной машины:

    int i, idx, j;
    double * subout, * subin;
    assert(stride_out_1 == 1);
    assert(stride_out_1 == stride_in_1);
    if (k < 32 /* i.e. 256 bytes: magic! */) {
        for(i = 0; i < n; ++i) {
            idx = indexer[i];
            subout = &out[i * stride_out_0];
            subin = &in[idx * stride_in_0];
            for(j = 0; j < k; ++j)
                subout[j] = subin[j];
        }
    } else {
        for(i = 0; i < n; ++i) {
            idx = indexer[i];
            subout = &out[i * stride_out_0];
            subin = &in[idx * stride_in_0];
            memcpy(subout, subin, k * sizeof(double));
        }
    }

Это использует "магическое число", чтобы решить, следует ли вызывать memcpy() или нет, но все же оптимизирует случай для небольших массивов, которые, как известно, являются смежными (поэтому он быстрее, чем оригинал, в большинстве случаев, поскольку оригинал не делает такого предположения).

4b9b3361

ОТВЕТЫ

Ответ 1

В конечном счете, проблема заключается в том, чтобы попросить оптимизатора сделать предположения о поведении во время выполнения на основе нескольких переменных. Хотя можно дать оптимизатору некоторые подсказки времени компиляции с помощью объявлений 'const' и 'register' для ключевых переменных, в конечном счете, вы в зависимости от оптимизатора, чтобы сделать много предположений. Кроме того, хотя memcpy() вполне может быть внутренним, он не гарантируется и даже если/когда он есть, реализация (реализации) может варьироваться довольно широко.

Если цель заключается в достижении максимальной производительности, иногда вам просто не нужно полагаться на технологии, чтобы понять это для вас, а сделать это напрямую. Лучшим советом для этой ситуации является использование встроенного ассемблера для решения проблемы. Это позволяет вам избежать всех ошибок в "черном ящике", дополняя эвристику компилятора и оптимизатора и окончательно заявляя о своих намерениях. Ключевым преимуществом использования встроенного ассемблера является возможность избегать любых нажатий/всплывающих окон и постороннего кода "обобщения" в решении проблемы с копией памяти и возможностью прямого использования возможностей процессора для решения проблемы. Нижняя сторона - это обслуживание, но, учитывая, что вам действительно нужно только адресовать Intel и AMD для покрытия большей части рынка, это не является непреодолимым.

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

Альтернатива этому заключается в том, чтобы зависеть от компилятора/оптимизатора, чтобы сделать для вас наилучшие догадки, использовать объявления 'const' и 'register', где вы можете предложить подсказки компилятора и использовать магические числа для ветвления на основе "лучшее решение"... это, однако, будет исключительно зависимым от компилятора/системы, и ваш пробег будет широко варьироваться от одной платформы/среды к другой.

Ответ 2

SSE/AVX и выравнивание

Если вы используете, например, современный процессор Intel, тогда использование SSE или AVX-инструкций является опцией. Хотя конкретно не о GCC, см. this. Если вам интересно и флеш с кешем, я думаю, что Intel сделает версию своего компилятора для Linux, а также Windows, и я предположим, что поставляется со своим набором библиотек.

Там также этот post.

Темы (eek)

У меня была такая же проблема довольно недавно, memcpy() занимает слишком много времени. В моем случае это был один большой memcpy() (1MByte или около того), а не много меньших, как вы делаете.

У меня очень хороший пробег, написав мою собственную многопоточную memcpy(), где потоки были постоянными и получили задание с долей задания вызовом моей собственной функции pmemcpy(). Персистентные потоки означали, что накладные расходы были довольно низкими. Я получил улучшение x4 для 4 ядер.

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

Что делает толпа в реальном времени - DMA

Как и в стороне, я с удовольствием играю с довольно экзотическим оборудованием OpenVPX. В основном это куча досок в большой коробке с высокоскоростным последовательным интерфейсом RapidIO между ними. Каждая плата имеет механизм DMA, который передает данные через sRIO в другую плату.

Поставщик, к которому я пришел, довольно умен в том, как максимально использовать процессор. Умный бит заключается в том, что двигатели DMA довольно умны - они могут быть запрограммированы на то, чтобы делать вещи, такие как преобразования матриц "на лету", "добывать полосы", такие вещи, как вы пытаетесь сделать, и т.д. И поскольку это отдельная аппаратная часть процессора пока не завязывается, так что можно заняться чем-то другим.

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

В любом случае, пользу от такого рода вещей действительно делает одно желание, чтобы процессоры Intel (и другие) имели встроенные DMA-устройства, способные работать с памятью памяти, а не только с периферийной памятью. Это сделает ваши задачи очень быстрыми.

Ответ 3

Я думаю, что лучший способ - экспериментировать и найти оптимальное значение "k" для переключения между исходным алгоритмом (с циклом) и вашим оптимизированным алгоритмом с использованием memcpy. Оптимальное "k" будет варьироваться в разных CPU, но не должно быть резко отличающимся; в основном, о накладных расходах на вызов memcpy, накладных расходов в самой memcpy при выборе оптимального алгоритма (на основе размера, выравнивания и т.д.) по сравнению с "наивным" алгоритмом с циклом.

memcpy является неотъемлемой частью gcc, да, но он не делает магии. В основном это означает, что если аргумент размера известен во время компиляции и малый размер (я не знаю, что такое порог), то GCC заменит вызов функции memcpy встроенным кодом. Если аргумент размера неизвестен во время компиляции, вызов функции библиотеки memcpy всегда будет выполнен.