Здравствуйте, кубик, Вы писали: К>да, вижу. Я пробовал с O2, а оно появляется при O3. Думаю что оптимизатору мало хинтов что б сделать красиво. К>Я тебе послал файлик. Более чем в 2 раза быстрее на выровненых данных.
Хм. Прогнал бенчмарк у себя.
Вот результат:
BenchmarkDotNet=v0.12.1, OS=Windows 10.0.18363.1139 (1909/November2018Update/19H2)
Intel Core i7-6600U CPU 2.60GHz (Skylake), 1 CPU, 4 logical and 2 physical cores
.NET Core SDK=5.0.100-rc.1.20452.10
[Host] : .NET Core 3.1.9 (CoreCLR 4.700.20.47201, CoreFX 4.700.20.47203), X64 RyuJIT
Job=InProcess Toolchain=InProcessEmitToolchain
| Method | FileName | Mean | Error | StdDev | Ratio | RatioSD |
|------------------- |-------------- |----------:|---------:|---------:|------:|--------:|
| LinqC4VectorCached | p00743.bmp.gz | 92.71 ms | 1.770 ms | 3.100 ms | 0.71 | 0.03 |
| AsmC4 | p00743.bmp.gz | 101.15 ms | 0.626 ms | 1.765 ms | 0.76 | 0.01 | <-------
| LinqC4 | p00743.bmp.gz | 109.08 ms | 1.707 ms | 1.513 ms | 0.81 | 0.02 |
| CppC4 | p00743.bmp.gz | 120.49 ms | 1.959 ms | 2.332 ms | 0.90 | 0.02 |
| UnsafeC4 | p00743.bmp.gz | 133.97 ms | 2.669 ms | 2.497 ms | 1.00 | 0.00 |
| NaturalC4 | p00743.bmp.gz | 271.44 ms | 5.193 ms | 4.857 ms | 2.03 | 0.05 |
Т.е. рукопашный ассемблерный код незначительно проигрывает Linq2d. И выигрывает у С++ компилятора MSVC, с включёнными настройками векторизации и максимальной производительности.
вот простынка, которую порождает Microsoft (R) Optimizing Compiler Version 19.27.29112.0
Здравствуйте, Sinclair, Вы писали: S>Здравствуйте, кубик, Вы писали: К>>да, вижу. Я пробовал с O2, а оно появляется при O3. Думаю что оптимизатору мало хинтов что б сделать красиво. К>>Я тебе послал файлик. Более чем в 2 раза быстрее на выровненых данных. S>Хм. Прогнал бенчмарк у себя. S>Вот результат: S>
S>BenchmarkDotNet=v0.12.1, OS=Windows 10.0.18363.1139 (1909/November2018Update/19H2)
S>Intel Core i7-6600U CPU 2.60GHz (Skylake), 1 CPU, 4 logical and 2 physical cores
S>.NET Core SDK=5.0.100-rc.1.20452.10
S>[Host] : .NET Core 3.1.9 (CoreCLR 4.700.20.47201, CoreFX 4.700.20.47203), X64 RyuJIT
S>Job=InProcess Toolchain=InProcessEmitToolchain
S>| Method | FileName | Mean | Error | StdDev | Ratio | RatioSD |
S>|------------------- |-------------- |----------:|---------:|---------:|------:|--------:|
S>| LinqC4VectorCached | p00743.bmp.gz | 92.71 ms | 1.770 ms | 3.100 ms | 0.71 | 0.03 |
S>| AsmC4 | p00743.bmp.gz | 101.15 ms | 0.626 ms | 1.765 ms | 0.76 | 0.01 | <-------
S>| LinqC4 | p00743.bmp.gz | 109.08 ms | 1.707 ms | 1.513 ms | 0.81 | 0.02 |
S>| CppC4 | p00743.bmp.gz | 120.49 ms | 1.959 ms | 2.332 ms | 0.90 | 0.02 |
S>| UnsafeC4 | p00743.bmp.gz | 133.97 ms | 2.669 ms | 2.497 ms | 1.00 | 0.00 |
S>| NaturalC4 | p00743.bmp.gz | 271.44 ms | 5.193 ms | 4.857 ms | 2.03 | 0.05 |
S>
S>Т.е. рукопашный ассемблерный код незначительно проигрывает Linq2d. И выигрывает у С++ компилятора MSVC, с включёнными настройками векторизации и максимальной производительности.
А вот примерно то, что порождает дотнетовый JIT в x64 режиме
Выделенный кусок меня смущает: почему-то вместо vpsrld ymm0, ymm0, 2 с immediate 2 третьим аргументом (VEX.256.66.0F.WIG 72), JIT вкручивает конверсию в 128-бит регистр при помощи двух лишних операций.
Похоже, он тупо не понимает, что ему в аргументах передали константу, и порождает универсальный код, готовый взять r12d откуда угодно.
Надо разобраться, как он это делает, и запилить pull request
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Re[17]: Производительность .Net на вычислительных задачах
Здравствуйте, Sinclair, Вы писали:
V>>Стек аудио-эффектов для гитары, например. S>А нельзя композицию эффектов свести к композитному эффекту?
До какой-то степени можно, конечно.
Это как минимизация выражений, распространение констант и т.д.
В общем, всё то, что входит в стадию бета-редукции у современных оптимизирующих компиляторов, с учётом предметной области вычислений.
И я одно время "пилил" именно подобное, но так и не допилил (всё надёюсь, что когда-нибудь будет чуть больше времени), бо именно эта область за вечер на коленке не взлетает, почему-то... ))
(в отличие от реализаций независимых эффектов и их простой композиции)
(и мне всё менее кажется, что "оно", действительно, надо, все эти "символьные вычисления" в операторной области)
V>>- с этой модели снимается итоговая импульсная характеристика; V>>- в реалтайме затем происходит свёртка входного сигнала с импульсной характеристикой. S>Хм. Это должно работать только с линейными фильтрами.
Разумеется, передаточная ф-ия by design служит для описания линейных (в операторной области) систем.
А IR — это представление передаточной ф-ии во временной области.
Т.е., этот подход работает для любой комбинации линейных операторов:
— линии задержки;
— интегрирование/дифференцирование;
— умножение и сложение отсчётов с константами;
— сумматоры сигналов, в т.ч. когда в аргументах идут обратные связи от других линейных вычислений этого же "блока".
V>>Суть в том, что "точная модель" оперирует большой разрядностью и кратной передискетизацией унутре, поэтому эта модель не работает в реалтайм, она используется один раз при вычислении IR. S>Как-то это сложно. Непонятно, зачем вообще вся эта суперпередискретизация
Для эффектов навроде эха/реверберации/фленжеров/фейзеров и прочих эффектов на основе обратной связи с задержкой (особенно с переменной задержкой) почти всегда применяют всякие трюки для повышения кач-ва. Иначе эффект начинает иметь "металлические нотки" в звучании, вот как роботы говорят в старых фильмах — это накопление ошибок округления, которые при обратной связи многократно набегают друг на друга, что порождает гармоники обрабатываемого сигнала, которые, в свою очередь, интерферируют с частотой дискретизации.
Вариантов борьбы с этим хватает. Например, есть еще вариант вместо суровой передискретизации применять интерполяцию на линиях задержки, т.е. допустим мгновенная задержка на некоей линии задержки 0.0678345 сек (от балды), надо вычислить некий отсчёт. Вместо наивного нахождения индекса отсчёта в массиве как округления до целого умноженой частоты дискретизации на вещественное время, целевой отсчёт ищется по некоторому закону как интерполированный сигнал. В простейшем случае делается передискретизация всего лишь вдвое, затем неокруглённый отсчёт ищется через линейную интерполяцию по двум точкам. В более сложном виде пропускают через оператор передаточной ф-ии простейшего ФНЧ во временной области — это операция нахождения определённого интеграла, оно неплохо работает, когда в небольших пределах.
Понятное дело, что для наколенного "показать принцип" оно не требуется, но речь идёт о реальных боевых эффектах, где в последний десяток-другой лет кач-во электронной музыки (.е. электронных эффектов) вышло на весьма высокий уровень. "Наколенности" давно нет даже в бесплатных эффектах (любопытные могут поискать по "VST plugin").
Опять же, принцип "подсчитали в оффлайн сколь-угодно сложный эффект, а в онлайн используем IR" — он резко развязывает руки. Это примерно то же самое, что "память не ресурс", т.е. можно сурово передискретизировать сигнал, делать все вычисления в double64 или даже в double128, зато не париться с накоплением ошибок округления и интерферированием гармоник с частотой дискретизации (это всё будет в конце отфильтровано ФНЧ при обратной передискретизации). Оно позволяет использовать более простые алгоритмы, в т.ч. при передискретизации начинают хорошо работать сугубо численные методы, например, методы численного интегрирования и дифференцирования.
Численные методы просты, но неплохо работают при передискретизации на частоты, которые в несколько десятков раз, а лучше в сотню-другую выше максимально-интересующей обрабатываемой частоты, т.е. будет тебе не 48 кГц, а 4.8 Мгц, соответственно мантисса должна удлиниться примерно на 10 разрядов, плюс берём кол-во операций на один отсчёт, на каждую тысячу операций — опять плюс 10 разрядов мантиссы (для прикидки, простейший фильтр второго порядка — это 5-6 слагаемых многочлена) и т.д. и т.п.
S>если мы всё равно пропускаем через эту модель единичный сигнал, а на выход записываем коэффициенты в "финальной" дискретизации и разрядности.
Этот единичный сигнал будет затухать некоторое время.
Затухание получается на линиях задержки и на обратной связи и т.д. что выше описано.
Да и, сами рекурсивные фильтры являются свеобразной линией задержки.
Иногда для компенсации фазовой задержки вводят отрицательную задержку в сигнал, т.е. как бы входной сигнал берется из "будущего", а управляющее вычисленное воздействие (например, мгновенная амплитуда, управляющая АЧХ фильтра) — применяется к сигналу из "настоящего".
А да, самое главное.
Коэффициенты IR имеют понятный для любого хоббиста физический смысл — это просто отсчёты выходного сигнала.
(т.е., "планка входа" в тему минимальная)
Единичный сигнал пропускают через некую систему, на выходе имеем, грубо, WAV-файл, это и есть IR.
Теперь делаем свёртку входного сигнала с IR и ву-а-ля.
Свертка тоже понятна любому хоббисту — мы проигрываем WAV-файл IR с громкостью текущего отсчёта аудио, на следующем шаге к проигрываемому прибавляем опять этот же WAV файл с громкостью, равной следующему отсчёту и т.д., т.е. как бы в параллель "играет" столько "проигрывателей" WAV-файла IR, какова его длина.
V>>Нелинейщина обычно проще. Это разного рода пороговые ф-ии, типа sqrt, log и т.д. и они часто реализованы через табличную аппроксимацию, т.е. практически бесплатны. S>Ну, по сравнению с арифметикой даже они гораздо дороже. Как сделать табличную аппроксимацию в SIMD?
Через a*x+b
V>>Компилятор Intel С++ разворачивает циклы именно при работе с SIMD в N=16, 32, ..., 128 раз. S>В примерах, которые видел я, развёртки SIMD циклов от ICC ~ 2, от GCC — ~4. И это при простейшем коде цикла, где вроде бы и нагрузки на CPU на итерацию мало, и до пределов кэша коду ещё далеко.
В 2 раза развёртки циклов я не видел ни разу в ассемблерном виде в релизе.
От 16 до 128 с шагом в степень двойки видел.
V>>Кеш данных 1-го уровня имеет в точности быстродействие файла регистров (и там и там косвенная адресация из-за ассоциативности, для кеша данных — с данными, для файла регистров — из-за переименований регистров, где внутренний файл регистров в несколько раз больше "публичного" его отображения). S>Ну... хз. Всё равно юнитов исполнительных в одном ядре не очень много; даже если я разверну цикл 128 раз, никто мне не будет 128 пар сложений одновременно выполнять.
Это не тот разворот, это ты имел ввиду в параллель когда вычисления.
Тут да, особо не разбежишься.
О чём говорил я — циклы разворачивают для экономии на обслуживании переменной цикла и соотв. ветвления.
S>Вот то же предсказание переходов: по идее, проверка выхода за диапазон вообще не должна влиять на массивах размером в 33мегапиксела. Там же ровно всегда один и тот же бранч выбирается.
От алгоритма ж зависит.
Если в алгоритме смещение x +/- 100, то на 100 точках в начале и в конце строки будет выход за границы изображения.
Но это применительно к 2D.
С 1D любопытней — выходов за границы быть не может.
Такая адресация делается на циклической линии задержки, длина которой не может быть меньше макс. амплитуды смещения по индексу, и тогда индекс любого отсчёта при смещении назад находится как (cursor + length — offset) % length. Например, было бы прикольно эту операцию сразу выполнить как "встроенный кирпичик" системы. На пальцах (для линейной аппроксимации) 3.5 отсчёта назад — это x[cursor-3]*0.5+x[cursor-4]*0.5, 4.3 отсчёта назад — это x[cursor-4]*0.7+x[cursor-5]*0.3, где индекс условного cursor-offset вычисляется на циклической линии задержки как показал выше.
Странно.... если я вставлю ymm регистры, то все очень замедляется. Написанная с ними C4 работала в несколько раз медленнее просто С++.
Надо попробовать другой комп.
Re[18]: Производительность .Net на вычислительных задачах
Здравствуйте, vdimas, Вы писали: V>До какой-то степени можно, конечно. V>Это как минимизация выражений, распространение констант и т.д. V>В общем, всё то, что входит в стадию бета-редукции у современных оптимизирующих компиляторов, с учётом предметной области вычислений.
Если мы уже перешли к линейным фильтрам, то они компонуемы просто по определению. Любая комбинация линейных фильтров является линейным фильтром.
V>Для эффектов навроде эха/реверберации/фленжеров/фейзеров и прочих эффектов на основе обратной связи с задержкой (особенно с переменной задержкой) почти всегда применяют всякие трюки для повышения кач-ва. Иначе эффект начинает иметь "металлические нотки" в звучании, вот как роботы говорят в старых фильмах — это накопление ошибок округления, которые при обратной связи многократно набегают друг на друга, что порождает гармоники обрабатываемого сигнала, которые, в свою очередь, интерферируют с частотой дискретизации.
Ок, я понял. Это если честно считать модель преобразования с начала и до конца.
S>>если мы всё равно пропускаем через эту модель единичный сигнал, а на выход записываем коэффициенты в "финальной" дискретизации и разрядности.
V>Коэффициенты IR имеют понятный для любого хоббиста физический смысл — это просто отсчёты выходного сигнала. V>(т.е., "планка входа" в тему минимальная)
Это как раз понятно.
S>>Ну, по сравнению с арифметикой даже они гораздо дороже. Как сделать табличную аппроксимацию в SIMD? V>Через a*x+b
Не-не-не-не-не, Дэвид Блейн. ax+b — это линейное преобразование. Таблица — это когда у меня значения выхода произвольные.
То есть я беру, скажем, логарифм по некоторому основанию от x, и рассчитываю его для всех 65536 возможных значений x, складывая в таблицу.
А потом вычисляю logtable[x] для каждого x.
Вот как развлекались любители математики 12 лет тому: http://jrfonseca.blogspot.com/2008/09/fast-sse2-pow-tables-or-polynomials.html
Сейчас, вроде бы, можно использовать gather инструкции из AVX2; но я с ними не разобрался — непонятно, как там задаётся базовый адрес и масштаб. И там есть ограничения на типы данных — можно тащить либо 32, либо 64 бита.
То есть работать с 16-битным звуком напрямую через них не выйдет.
V>В 2 раза развёртки циклов я не видел ни разу в ассемблерном виде в релизе. V>От 16 до 128 с шагом в степень двойки видел.
А чего далеко ходить? Вот, берём простейший код поэлементного сложения массивов. Максимально дружественный к векторизации.
Гляньте — какой имеем loop unroll factor: https://godbolt.org/z/919Mf9 ?
Покажите мне код, который разворачивается в SIMD с фактором хотя бы в 16, не говоря уже о 128.
V>О чём говорил я — циклы разворачивают для экономии на обслуживании переменной цикла и соотв. ветвления.
На фоне SIMD-операций экономия на обслуживании ветвления незначительна. Ну, по крайней мере, выглядит таковой с точки зрения компилятора.
То есть у нас и так бранч занимает, скажем, x% от стоимости вычислительной части цикла. Развёртка вдвое позволяет снизить расход до x/2 %. В 16 раз — до x/16.
Разница между 1/4 и 1/16 = 3/16, или чуть меньше 20%. Если исходный x был равен 20%, то общий выигрыш в производительности при переходе от unroll=4 к 16 будет 4%. И при этом он вообще будет заметен только в тех случаях, когда длина входных данных у нас значительно больше 16ти размера SIMD-вектора. Таким образом, unroll в 128 может быть полезен только при очень, очень дешёвом теле цикла.
V>От алгоритма ж зависит. V>Если в алгоритме смещение x +/- 100, то на 100 точках в начале и в конце строки будет выход за границы изображения.
В корректном алгоритме мы никогда не обращаемся за пределы массива. Если есть смещение — то, значит, перед обращением к a[i,j] выполняется какой-то код по коррекции индексов.
Возьмём алгоритм без смещения. Тупой цикл for(var i=0;i<a.Height;i++) for(var j=0;j<a.Width;j++) s+=a[i,j]. Тут четыре бранч-инструкции, из которых две — пользовательские, и две — в проверке диапазона.
Статистика вот такая:
1. Выход из цикла по i проверяется h раз, и только в 1 случае берётся другая ветка.
2. Выход из цикла по j проверяется h*w раз, и только в h случаев берётся другая ветка
3. Проверка диапазона по i выполняется h*w раз, и никогда не срабатывает
4. Проверка диапазона по j выполняется h*w раз, и никогда не срабатывает
Казалось бы — 3 и 4 вообще не должны давать вклад в производительность; к моменту, когда дело доходит до них, очередной элемент массива уже в регистре и прибавляется к сумме. Проверка очевидного не должна занимать больше времени, чем ожидание памяти. 1 и 2 на массиве размером 1000*1000 должны давать сбой предсказания в 0.1% случаев каждая; так что тоже должны давать пренебрежимо мало вклада.
Ан нет — устранение проверок диапазона из этого цикла даст чуть ли не 25% ускорения; развёртка цикла даёт ещё бонус.
Из этого делаем вывод — оптимизатор внутри процессора есть, но он недостаточно умный, чтобы скомпенсировать даже простейшие недостатки скормленного ему кода.
V>Такая адресация делается на циклической линии задержки, длина которой не может быть меньше макс. амплитуды смещения по индексу, и тогда индекс любого отсчёта при смещении назад находится как (cursor + length — offset) % length. Например, было бы прикольно эту операцию сразу выполнить как "встроенный кирпичик" системы. На пальцах (для линейной аппроксимации) 3.5 отсчёта назад — это x[cursor-3]*0.5+x[cursor-4]*0.5, 4.3 отсчёта назад — это x[cursor-4]*0.7+x[cursor-5]*0.3, где индекс условного cursor-offset вычисляется на циклической линии задержки как показал выше.
А зачем нам нецелые смещения?
Выражение 0.2*x[-3.5]+0.1*x[-4.3] сводится к 0.1*x[-3]+0.17*x[-4]+0.03*x[-5], и у нас опять всё целое.
Если нас интересует период эха, то как бы 44кГц уже дают точность в 22.6 микросекунд — вряд ли слушатель заметит, что эхо приходит не ровно через 2.5 секунды, а через 2.500023.
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Re[13]: Производительность .Net на вычислительных задачах
Здравствуйте, кубик, Вы писали:
К>Странно.... если я вставлю ymm регистры, то все очень замедляется. Написанная с ними C4 работала в несколько раз медленнее просто С++. К>Надо попробовать другой комп.
У тебя винда?
Можешь собрать проект (я там выложил новую версию) и запустить
Linq2d.Benchmarks.exe -f C4Benchmark
?
(Сборка на линуксе пока что сломана; надо разобраться, как заставить gcc корректно компилировать .asm файл)
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Re[14]: Производительность .Net на вычислительных задачах
Здравствуйте, Sinclair, Вы писали:
S>Здравствуйте, кубик, Вы писали:
К>>Странно.... если я вставлю ymm регистры, то все очень замедляется. Написанная с ними C4 работала в несколько раз медленнее просто С++. К>>Надо попробовать другой комп. S>У тебя винда? S>Можешь собрать проект (я там выложил новую версию) и запустить
У меня винда, но старая студия 2008. А у тебя 2016.
Я еще не понимаю как твоя таблица показывает что asm проигрывает ?
Как он может проигрывать если там все только по делу. Значит LinqC4VectorCached не всё считатает, или что-то посчитал заранее, и это время ты не учёл.
JIT генерит SSE код лучше чем gcc.
Re[15]: Производительность .Net на вычислительных задачах
Здравствуйте, кубик, Вы писали: К>У меня винда, но старая студия 2008. А у тебя 2016.
У меня 2019 Community Edition. Она бесплатная. К>Я еще не понимаю как твоя таблица показывает что asm проигрывает ?
Ну, вот так. К>Как он может проигрывать если там все только по делу. Значит LinqC4VectorCached не всё считатает, или что-то посчитал заранее, и это время ты не учёл.
Порождаются более эффективные инструкции. Нет, считается строго всё то же самое (результат сверяется в Linq2d.Tests), только не падает на невыровненных данных. К>JIT генерит SSE код лучше чем gcc.
В моих замерах JIT порождал код AVX2. У тебя — SSE. Скорее всего, разница именно в этом.
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
К>>Я еще не понимаю как твоя таблица показывает что asm проигрывает ? S>Ну, вот так.
Смотри, ты видишь что я вощем то интересуюсь не праздно, мне действительно интересно.
На моем тесте с asm более чем 2 раза быстее С++. Вызываю 10 раз подряд c4filter на рандомном массиве размером 10,000 x 10,000 и беру разницу GetTickCount64. Выделение памяти и иниц. массива не входят в измерения.
А в таблице ты делаешь вывод что он чуть чуть обгоняет. Мне не понятно методика теста и в какую колонку смотреть. Я не математик.
Re[17]: Производительность .Net на вычислительных задачах
Здравствуйте, кубик, Вы писали: К>На моем тесте с asm более чем 2 раза быстее С++. Вызываю 10 раз подряд c4filter на рандомном массиве размером 10,000 x 10,000 и беру разницу GetTickCount64. Выделение памяти и иниц. массива не входят в измерения. К>А в таблице ты делаешь вывод что он чуть чуть обгоняет. Мне не понятно методика теста и в какую колонку смотреть. Я не математик.
Методика теста очень простая: берём grayscale изображение размером 33 мегапиксела и скармливаем его в разные варианты кода, вычисляя для него фильтр C4.
Во всех вариантах исходный массив уже выделен; выделение массива результата (размером в ~130 мегабайт) в замер времени входит, но выполняется для всех измерений на стороне дотнета.
Замеры делаются при помощи benchmarkdotnet.org — он вызывает каждого из кандидатов столько раз, сколько нужно для уверенной оценки.
Точнее, делается так: замеряется время работы m вызовов подряд (m подбирается в зависимости от времени работы однократного вызова; для таких тяжёлых операций, как у нас, оно в диапазоне от 2 до 6), и замер повторяется многократно.
Из замеренного времени вычитается время прогона такого же цикла, только с вызовом пустого метода.
Перед началом измерений выполняется несколько прогревочных прогонов, не входящих в результат — чтобы прогреть все кэши и проинициализировать всякие оптимизационные структуры, и замерять производительность "стабильного" случая.
Загрузка изображения с диска делается один раз, до начала серии замеров, и в замеры не входит.
Во все вызовы передаётся физически один и тот же массив в качестве входного; выходной массив — каждый раз разный.
Смотреть надо в колонки Mean и Ratio.
Mean — это среднее время работы каждого из вариантов. Ratio — это отношение Mean к так называемой baseline реализации — в нашем случае это рукопашный скалярный unsafe код на C#.
Error — это погрешность измерения, линейно связана со среднеквадратичным измерением.
Вот, смотрим: С++ окучивает 33 мегабайта в среднем за 120.5 миллисекунд. Это 90% от времени работы скалярного unsafe-кода на шарпе. До того, как я смог включить в нём векторизацию, справлялся за ~140 миллисекунд.
Твой ассемблерный вариант окучивает тот же массив за 101 миллисекунду. А linq2d справляется за 93.
Вообще, BDN отдаёт больше результатов — в том числе и отброшенные экстремальные значения, и признаки мультимодальности (обычно мультимодальность означает, что есть какой-то скрытый параметр, и часть исполнений идёт по одному пути, а часть — по другому. Например, сборка мусора может случиться, а может не случиться во время исполнения кода). Но главный результат — вот в виде такой таблички.
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Re[19]: Производительность .Net на вычислительных задачах
Здравствуйте, Sinclair, Вы писали:
V>>До какой-то степени можно, конечно. V>>Это как минимизация выражений, распространение констант и т.д. V>>В общем, всё то, что входит в стадию бета-редукции у современных оптимизирующих компиляторов, с учётом предметной области вычислений. S>Если мы уже перешли к линейным фильтрам, то они компонуемы просто по определению. Любая комбинация линейных фильтров является линейным фильтром.
Это в теории непрерывных вычислений.
А как на практике сложить дискретные (цифровые) рекурсивный и нерекурсивный фильтры в один? ))
(линия задержки — это тоже нерекурсивный фильтр с коэфициентами 0, 0, ..., 1)
У них принципиально разный отклик, не выражаемый в общем случае один из другого (при разумной длине нерекурсивного фильтра).
Но так-то ты говоришь верно, просто у тебя недостаточно информации.
Например, такой, что рекурсивные фильтры высоких порядков часто реализуют как каскадное или параллельное подключение фильтров 2-го порядка, зависит от расположения полюсов по квандрантам.
Это предпочтительней, чем прямая реализация единого многополюсного фильтра, т.к. чем выше порядок фильтра, тем меньше его устойчивость — цифровые рекурсивные фильтры высоких порядков склонны к возбуждению из-за погрешностей округления при вычислении, т.е. это надо относительно широкое представление вещественного числа брать, которое на сегодня зачастую исключительно эмулируемое в софте.
В общем, основная идея в том, что можно найти минимальное представление линейной такой комбинированной системы, т.е. свести к минимальному кол-ву линий задержек (нерекурсивные фильтры самые дорогие) из исходного их кол-ва и произвольных связей.
Над каждой линией задержки будет более одной обратной связи с разной "дистанцией", в т.ч. с небольшой, достаточной для рекурсивных фильтров, для параллельной и последовательной их реализаций.
S>>>Ну, по сравнению с арифметикой даже они гораздо дороже. Как сделать табличную аппроксимацию в SIMD? V>>Через a*x+b S>Не-не-не-не-не, Дэвид Блейн. ax+b — это линейное преобразование. Таблица — это когда у меня значения выхода произвольные.
Не понял возражения.
Для линейной интерполяции по таблице у нас есть прямая и точка на этой прямой.
Индекс значений i (a[i], b[i]) — целая часть значения (после масштабирования на размер таблицы), x — дробная часть.
Это классический вариант табличной линейной интерполяции.
Или ты имел ввиду "сырой" вариант табличной апроксимации, когда таблица будет содержать в ячейках таблицы непосредственные значения выходной ф-ии вместо коэф. {a,b}? Тогда искомую прямую придётся строить каждый раз заново по двум точкам {a[i], a[i+1]}: a[i]*(1-x)+a[i+1]*x, где i — опять целая часть, x — дробная.
По "сырому" методу операций больше на одно умножение и три сложения.
S>То есть я беру, скажем, логарифм по некоторому основанию от x, и рассчитываю его для всех 65536 возможных значений x, складывая в таблицу. S>А потом вычисляю logtable[x] для каждого x. S>Вот как развлекались любители математики 12 лет тому: http://jrfonseca.blogspot.com/2008/09/fast-sse2-pow-tables-or-polynomials.html
А в чем там "математичность"?
Что использовали формулу суммы степеней exp(a+b)=exp(a)*exp(b)?
На олимпиадах для 7-8-х классов подобные задачи дают.
А меня, как программиста-профика, интересуют вещи куда как более скучные, см. выделенное:
/* index = EXP2_TABLE_OFFSET + (int)(fpart * EXP2_TABLE_SCALE) */
— никакой интерполяции не происходит, даже линейной, именно поэтому по ссылке баловство.
Кто-то дорвался "немного попрограммировать".
S>То есть работать с 16-битным звуком напрямую через них не выйдет.
На HD Audio идёт туда-обратно обычно int32.
AC'97 в живых, наверно, уже и не осталось.
Но стандарты цифрового софта давно сошлись на потоке IO float32.
Как остроумно объяснил один аудиофил другому:
32 bit floating is a 24 bit recording with 8 extra bits for volume.
))
Сейчас стандарт float32 потихоньку пролазит в железо, например, в USB-аудио-девайсы.
Фишка в том, что АЦП/ЦАП на 32 честных бита задешево — давно реальность, и даже начинают превышать 32 бита в проф.аппаратуре (значит, в обозримом будущем доедет и до ширпотреба).
И не потому что нужна такая точность, а потому что из-за динамического диапазона.
Например, для тихого сигнала при разрядности 16 бит реальная разрядность была пару бит всего, а то и 1.
Вот и получается, что для настраиваемого динамического диапазона 24 бита за глаза хватает, а для ненастраиваемого и 32 бита так себе.
V>>В 2 раза развёртки циклов я не видел ни разу в ассемблерном виде в релизе. V>>От 16 до 128 с шагом в степень двойки видел. S>А чего далеко ходить? Вот, берём простейший код поэлементного сложения массивов. Максимально дружественный к векторизации. S>Гляньте — какой имеем loop unroll factor: https://godbolt.org/z/919Mf9 ?
S>Покажите мне код, который разворачивается в SIMD с фактором хотя бы в 16, не говоря уже о 128.
Давай ты мне просто поверишь на слово или забьёшься на спор, оформив чётко своё возражение?
S>А зачем нам нецелые смещения?
Чтобы обеспечить кач-во.
S>Выражение 0.2*x[-3.5]+0.1*x[-4.3] сводится к 0.1*x[-3]+0.17*x[-4]+0.03*x[-5], и у нас опять всё целое.
Навряд ли сводится именно таким образом.
Если по 3-м точкам, то искомая точка будет на параболле.
S>Если нас интересует период эха, то как бы 44кГц уже дают точность в 22.6 микросекунд — вряд ли слушатель заметит, что эхо приходит не ровно через 2.5 секунды, а через 2.500023.
Здравствуйте, vdimas, Вы писали:
V>Здравствуйте, Sinclair, Вы писали:
V>>>До какой-то степени можно, конечно. V>>>Это как минимизация выражений, распространение констант и т.д. V>>>В общем, всё то, что входит в стадию бета-редукции у современных оптимизирующих компиляторов, с учётом предметной области вычислений. S>>Если мы уже перешли к линейным фильтрам, то они компонуемы просто по определению. Любая комбинация линейных фильтров является линейным фильтром.
V>Это в теории непрерывных вычислений. V>А как на практике сложить дискретные (цифровые) рекурсивный и нерекурсивный фильтры в один? )) V>(линия задержки — это тоже нерекурсивный фильтр с коэфициентами 0, 0, ..., 1) V>У них принципиально разный отклик, не выражаемый в общем случае один из другого (при разумной длине нерекурсивного фильтра).
V>Но так-то ты говоришь верно, просто у тебя недостаточно информации. V>Например, такой, что рекурсивные фильтры высоких порядков часто реализуют как каскадное или параллельное подключение фильтров 2-го порядка, зависит от расположения полюсов по квандранту. V>Это предпочтительней, чем прямая реализация единого многополюсного фильтра, т.к. чем выше порядок фильтра, тем меньше его устойчивость — цифровые рекурсивные фильтры высоких порядков склонны к возбуждению из-за погрешностей округления при вычислении, т.е. это надо относительно широкое представление вещественного числа брать, которое на сегодня зачастую исключительно эмулируемое в софте.
V>В общем, основная идея в том, что можно найти минимальное представление линейной такой комбинированной системы, т.е. свести к минимальному кол-ву линий задержек (нерекурсивные фильтры самые дорогие) из исходного их кол-ва и произвольных связей. V>Над каждой линией задержки будет более одной обратной связи с разной "дистанцией", в т.ч. с небольшой, достаточной для рекурсивных фильтров, для параллельной и последовательной их реализаций.
V>Не понял возражения. V>Для линейной интерполяции по таблице у нас есть прямая и точка на этой прямой. V>Индекс значений i (a[i], b[i]) — целая часть значения (после масштабирования на размер таблицы), x — дробная часть. V>Это классический вариант табличной линейной интерполяции. V>Или ты имел ввиду "сырой" вариант табличной апроксимации, когда таблица будет содержать в ячейках таблицы непосредственные значения выходной ф-ии вместо коэф. {a,b}? Тогда искомую прямую придётся строить каждый раз заново по двум точкам {a[i], a[i+1]}: a[i]*(1-x)+a[i+1]*x, где i — опять целая часть, x — дробная. V>По "сырому" методу операций больше на одно умножение и три сложения.
А, то есть предлагается сделать
VBROADCASTSS ymm1, $tableLength
VMULPS ymm2, ymm1, [$data+i]
VCVTPS2DQ ymm3, ymm2
VSUBPS ymm4, ymm2, ymm3
а потом два gather по индексам из ymm3 в ymm5 и ymm6, c последующим
VFMADD132PS ymm4, ymm5, ymm6
? Ну... можно попробовать, хотя я пока не понимаю, как работают gather-инструкции, и нет ли там промежуточного сохранения индексов в память, что убьёт всю идею. V>А в чем там "математичность"?
В том, что пытались сделать SIMD-версию функции возведения в степень. Пришли к выводу, что интерполяция полиномом эффективнее.
V>А меня, как программиста-профика, интересуют вещи куда как более скучные, см. выделенное: V>
V>/* index = EXP2_TABLE_OFFSET + (int)(fpart * EXP2_TABLE_SCALE) */
V>
V>- никакой интерполяции не происходит, даже линейной, именно поэтому по ссылке баловство. V>Кто-то дорвался "немного попрограммировать".
Ну, как смогли — так и сделали. Можно попробовать улучшить. V>На HD Audio идёт туда-обратно обычно int32. V>AC'97 в живых, наверно, уже и не осталось.
Ну, ок, 32 так 32. Всё равно мне пока непонятно, как эффективно делать табличные интерполяции с таким сигналом. С честным int16 мы могли бы просто строить полную таблицу безо всяких умножений и сложений — просто 128 килобайт lookup, описывающий любую потребную нам функцию без потери точности. А с флоатом мы сможем работать только в предположении, что он нормализован в каком-то узком диапазоне. Иначе у нас таблица окажется очень "неравномерной".
V>Сейчас стандарт float32 потихоньку пролазит в железо, например, в USB-аудио-девайсы. V>Фишка в том, что АЦП/ЦАП на 32 честных бита задешево — давно реальность, и даже начинают превышать 32 бита в проф.аппаратуре (значит, в обозримом будущем доедет и до ширпотреба).
Фишка в том, что непонятно, откуда брать источник с таким соотношением сигнал/шум. Сколько бит из этих 32 — мусор?
V>Нулевой: V>
Точнее, единичный. S>>Покажите мне код, который разворачивается в SIMD с фактором хотя бы в 16, не говоря уже о 128. V>Давай ты мне просто поверишь на слово или забьёшься на спор, оформив чётко своё возражение?
Ну ок, поверю. Смысла спорить нет — я всё равно даже пробовать не буду разворачивать SIMD 128 раз.
V>Чтобы обеспечить кач-во.
Качество чего?
S>>Выражение 0.2*x[-3.5]+0.1*x[-4.3] сводится к 0.1*x[-3]+0.17*x[-4]+0.03*x[-5], и у нас опять всё целое. V>Навряд ли сводится именно таким образом.
По твоей же формуле сводится именно таким. S>>Если нас интересует период эха, то как бы 44кГц уже дают точность в 22.6 микросекунд — вряд ли слушатель заметит, что эхо приходит не ровно через 2.5 секунды, а через 2.500023. V>Это если эхо статичное.
А если нет, то что?
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Re[21]: Производительность .Net на вычислительных задачах
Здравствуйте, Sinclair, Вы писали:
S>Ну, ок, 32 так 32. Всё равно мне пока непонятно, как эффективно делать табличные интерполяции с таким сигналом. С честным int16 мы могли бы просто строить полную таблицу безо всяких умножений и сложений — просто 128 килобайт lookup, описывающий любую потребную нам функцию без потери точности.
Это слишком большая таблица, она будет охлаждать кеш.
Для нелинейных преобразований достаточно 8-10 разрядов + линейной интерполяции по таблице.
S>А с флоатом мы сможем работать только в предположении, что он нормализован в каком-то узком диапазоне. Иначе у нас таблица окажется очень "неравномерной".
1. Ты прав, различные стандарты цифрового аудио-потока регламентируют т.н. "нормальный сигнал", например, -127.0 ... +127.0, -1.0 .. +1.0 (второй вариант мне кажется более естественным)
2. Но это важно только для кастомного какого-нить, т.е. заданного по точкам нелинейного искажения.
Если же брать основные нелинейные ф-ии, используемые для искажения сигнала, то все они являются хорошо масштабируемыми.
Это ф-ии:
— log, exp
— atan, acotan
— x^2/sqrt, x^4/sqrt4, ...
Например, вид log/exp не зависит от амлитуды входного сигнала (с точностью до линейных преобразований графика).
Аналогично с x^2 и обратным sqrt.
Здравствуйте, vdimas, Вы писали: S>>А с флоатом мы сможем работать только в предположении, что он нормализован в каком-то узком диапазоне. Иначе у нас таблица окажется очень "неравномерной". V>1. Ты прав, различные стандарты цифрового аудио-потока регламентируют т.н. "нормальный сигнал", например, -127.0 ... +127.0, -1.0 .. +1.0 (второй вариант мне кажется более естественным)
V>2. Но это важно только кастомного какого-нить, т.е. заданного по точкам нелинейного искажения. V>Если же брать основные нелинейные ф-ии, используемые для искажения сигнала, то все они являются хорошо масштабируемыми. V>Это ф-ии: V>- log, exp V>- atan, acotan V>- x^2/sqrt, x^4/sqrt4, ...
Ну, возведение в степень 2^p для целых p эффективно делается в SIMD безо всяких аппроксимаций. Достаточно умножения и sqrt. V>Например, вид log/exp не зависит от амлитуды входного сигнала (с точностью до линейных преобразований графика).
Вот это я не вполне понимаю. Нам нужен индекс в таблицу — а как мы его определим, если не знаем верхний предел?
Или имеется в виду, что мы сначала подавим мантиссу при помощи операции & 0x00FFFFFF, посчитаем значение для fraction по таблице, а потом отмасштабируем соответствующим образом?
В общем, пока неясно, как это должно работать.
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Re: Производительность .Net на вычислительных задачах
Друзья,
Новости оптимизации:
У меня староватый Xeon архитектуры broadwell. На нём такие результаты в "попугаях" на Ф-ции c4filter
C++: 1720
SSE: 830
AVX2: 830
Здравствуйте, кубик, Вы писали:
К>C++: 1330 К>SSE: 440 К>AVX2: 375 К>Может у кого есть посовременнее проц ? Запустите прожку, всего 10 кб: http://files.rsdn.org/6532/testcpu2exe.zip К>Я думаю AVX2 должен еще убыстрится.
Наоборот, дал меньший относительный профит:
C++: 906
SSE: 360
AVX2: 343
Сравни
1330/375 = ~3.55
440/375 = ~1.17
906/343 = ~2.64
360/343 = ~1.05
Re[6]: Производительность .Net на вычислительных задачах
Здравствуйте, Sinclair, Вы писали:
S>Мой доклад успешно прошёл. Запись я обещал не выкладывать до середины ноября, да и не особо там чего смотреть.
Тем не менее, вот она запись: https://youtu.be/IidqxJ2Mb0s.
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
Re[2]: Производительность .Net на вычислительных задачах
Здравствуйте, Sinclair, Вы писали:
S>Здравствуйте, Sinclair, Вы писали:
S>>Мой доклад успешно прошёл. Запись я обещал не выкладывать до середины ноября, да и не особо там чего смотреть. S>Тем не менее, вот она запись: https://youtu.be/IidqxJ2Mb0s.
Помню тебя где то а районе 2004 года на конференции MS ты приезжал делал доклад.
Да изменился. Тогда был совсем молодой!
Спасибо! Посмотрю.
и солнце б утром не вставало, когда бы не было меня
Re[3]: Производительность .Net на вычислительных задачах
Здравствуйте, Serginio1, Вы писали: S> Помню тебя где то а районе 2004 года на конференции MS ты приезжал делал доклад. S>Да изменился. Тогда был совсем молодой!
Да? А в зеркале — та же рожа. Вот только фотки в старых альбомах постепенно молодеют.
Недавно откопали фотки с Алтая примерно 2000го года — я себя опознал только по куртке с логотипом.
Уйдемте отсюда, Румата! У вас слишком богатые погреба.
