Могу ли я использовать устройство Даффа на массиве в C?

Question

У меня есть цикл, и я хочу, чтобы он работал быстрее. Я передаю в большом массиве. Я недавно слышал об устройстве Даффа, это может быть применено к этому для цикла? есть идеи?

for (i = 0; i < dim; i++) {
    for (j = 0; j < dim; j++) {
        dst[RIDX(dim-1-j, i, dim)] = src[RIDX(i, j, dim)];
    }
}

Answer 1

Пожалуйста, пожалуйста, не используйте устройство Даффа. Тысячи программистов обслуживания будут вам благодарны. Раньше я работал в учебной компании, где кому-то показалось забавным представить устройство на первых десяти страницах курса по программированию на Си. Как преподаватель, с этим было невозможно иметь дело, если (как парень, который написал этот кусочек курса, очевидно, не сделал), вы не поверите в кодирование "kewl".

Само собой разумеется, я вычеркнул вещь из курса, КАК МОЖНО СКОРЕЕ.

Answer 2

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

Есть ли проблема с производительностью?

Если да, то вы профилировали и обнаружили, что это выполняется достаточно часто и, следовательно, стоит оптимизировать?

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

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

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

Answer 3

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

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

Answer 4

Количество циклов инструкций для реализации оператора

dst[RIDX(dim-1-j, i, dim)] = src[RIDX(i, j, dim)];

будет значительно перевешивать издержки цикла, поэтому развертывание цикла будет очень мало помощи в процентном отношении.

Answer 5

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

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

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

Может ли ваша видеокарта выполнить эту работу?

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

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

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

Answer 6

Устройство Даффа - это просто техника для раскрутки петли А поскольку любой цикл можно развернуть, вы можете использовать устройство Даффа.

Answer 7

Вероятно, до тех пор, пока dim является степенью 2 или у вас быстрый модуль на вашей целевой системе. Узнал что-то новое сегодня. Я независимо открыл эту конструкцию 5 лет назад и поместил ее в нашу подпрограмму memCopy () Кто знал:)

Answer 8

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

Answer 9

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

Потребность в оптимизации никогда не закончится. Я разговаривал с аспирантом, который сломал malloc () / free (), работая над самым большим файлом генетических данных, когда-либо предпринятых за один проход. Через некоторое время куча стала слишком фрагментированной для malloc, чтобы найти блок непрерывной оперативной памяти для выделения вызывающей функции. Он должен был переключиться на библиотеку, которая malloc выдавала блоки памяти только на границах 32 КБ. Старой библиотеке потребовалось на 160% больше памяти, она работала медленнее, но завершила работу.

Вы должны быть осторожны, используя Duff's Device и многие другие оптимизации, чтобы быть уверенным, что компилятор не оптимизирует вашу оптимизацию в скрытый битый объектный код. Когда мы войдем в среду, используя инструменты автоматического распараллеливания, это станет еще большей проблемой.

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

-gcouger

Answer 10

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