Comments 99
Статья хорошая и полезная, но некоторые утверждения меня смущают.
> «Часто будет выгоднее обратиться 100'000 раз к оперативной памяти, чем 1 раз к диску.»
Но ведь 100.000 обращений к оперативной памяти делается операциями, которые сами по себе займут 100.000 * x тактов? Как часто можно встретить ситуацию, когда 100.000 раз обращений к оперативки выгоднее, чем одно обращение к диску, особенно учитывая существование SSD и PCI-SSD?
> Скорость обращения к удаленному серверу «1'000'000'000 тактов»
Как можно скорость отклика (ping) мерять тактами? Тем более, что сетевой сокет в гигабитной локалке, может быть быстрее, чем обращение к диску. Я могу расшарить на соседнем компе виртуальный ram-диск, и по гигабитной сети это будет совсем не 1.000.000.000 тактов.
> «Часто будет выгоднее обратиться 100'000 раз к оперативной памяти, чем 1 раз к диску.»
Но ведь 100.000 обращений к оперативной памяти делается операциями, которые сами по себе займут 100.000 * x тактов? Как часто можно встретить ситуацию, когда 100.000 раз обращений к оперативки выгоднее, чем одно обращение к диску, особенно учитывая существование SSD и PCI-SSD?
> Скорость обращения к удаленному серверу «1'000'000'000 тактов»
Как можно скорость отклика (ping) мерять тактами? Тем более, что сетевой сокет в гигабитной локалке, может быть быстрее, чем обращение к диску. Я могу расшарить на соседнем компе виртуальный ram-диск, и по гигабитной сети это будет совсем не 1.000.000.000 тактов.
Учитывается, что оперативная память хорошо кэшируется. 100'000 раз считать из L1 кэша займёт 0.4М тактов, а раз считать с диска 10М тактов.
то есть прокрутить цикл на 100.000 итераций быстрее, чем один раз обратиться к диску?
Мы же не считаем непосредственно доступ к памяти, а учитываем количество обращений со всем прилагаемым — сами операции обращения?
Вот ниже картинка
прочитать 1.000.000 байт из памяти — 6000 нс
прочитать 1.000.000 байт с диска — 1.000.000 нс
Итого, разница в 166 раз, но никак не в миллион.
Мы же не считаем непосредственно доступ к памяти, а учитываем количество обращений со всем прилагаемым — сами операции обращения?
Вот ниже картинка
прочитать 1.000.000 байт из памяти — 6000 нс
прочитать 1.000.000 байт с диска — 1.000.000 нс
Итого, разница в 166 раз, но никак не в миллион.
Применив некоторые оптимизации, можно прокрутить этот цикл и за 100,000 тактов. Читайте мою стать на тему оптимизации для процессора.
Там помимо 1 мс на чтение еще 3 мс нужно затратить на поиск этих данных на диске.
Кроме того Ваш оппонент говорил о кэше L1, который на два порядка быстрее чем память DRAM о которой говорите Вы. Правда мегабайт туда не влезет, но он влезет в L3 который все равно на порядок быстрее.
Кроме того Ваш оппонент говорил о кэше L1, который на два порядка быстрее чем память DRAM о которой говорите Вы. Правда мегабайт туда не влезет, но он влезет в L3 который все равно на порядок быстрее.
Чтение с диска и запись на диск тоже могут кэшироваться оперативной памятью (и естественно кэшами L1,L2..), а не только буфером диска. Какой режим работы подразумевается установившийся или нет? И как там с ассинхронностью в 2016 для диска? Слишком уж загнули с 100 000 тактов обращения к диску.
Не надо передергивать.
В статье многобукафф, но не заметил инфы про ассоциативность. Есть размер кэша, да, но есть еще другого рода ограничение. Если обрабатывать в разных частях памяти блоки, то для конкретного процессора не более K штук таких блоков одновременно эффективно кэшируются (проверял лично).
Не надо передергивать.
В статье многобукафф, но не заметил инфы про ассоциативность. Есть размер кэша, да, но есть еще другого рода ограничение. Если обрабатывать в разных частях памяти блоки, то для конкретного процессора не более K штук таких блоков одновременно эффективно кэшируются (проверял лично).
А по поводу чтения из сети, это же всё приблизительно. Это общая картина.
Я могу расшарить на соседнем компе виртуальный ram-диск
С трудом верится, ибо гигабитная сеть, она про трупут. А цифры из статьи про лэйтенси.
Хотя, мне даже интересно, какое время отклика было бы у такой связки, но нет физически близкой машины такой под рукой :)
Если речь про вычислительные кластеры, то там есть IB, он про latency в том числе.
Не знаком с темой — что такое IB? Гуглится что-то странное.
Это 10g сетевухи от melanox и myricom?
Это InfiniBand, обычно 10+Gb/s (оно с агрегацией) и субмикросекундными latency.
> Но ведь 100.000 обращений к оперативной памяти делается операциями, которые сами по себе займут 100.000 * x тактов?
64 чтения из областей, не входящих в одну выровненную 64-байтную область (как строка кэша), займут ~64*250 тактов. 64 чтения подряд из одной такой области займут, по описанной таблице, 64*4 такта. Достаточно просить prefetch на одну такую строку в начале чтения предыдущей, чтобы последовательное чтение не задерживало процессор. В реальности ситуацию ещё больше улучшают микросхемы памяти с несколькими одновременно открытыми строками и многоканальные контроллеры памяти.
> Как часто можно встретить ситуацию, когда 100.000 раз обращений к оперативки выгоднее, чем одно обращение к диску, особенно учитывая существование SSD и PCI-SSD?
При хоть сколь-нибудь продуманном доступе к памяти — считаем, практически всегда.
> Тем более, что сетевой сокет в гигабитной локалке, может быть быстрее, чем обращение к диску.
Гигабитный — по сравнению с SATA даже 1-м — уже нет :) Вот 10GB, или Infiniband'овские скорости — да, уже стоит упоминать.
64 чтения из областей, не входящих в одну выровненную 64-байтную область (как строка кэша), займут ~64*250 тактов. 64 чтения подряд из одной такой области займут, по описанной таблице, 64*4 такта. Достаточно просить prefetch на одну такую строку в начале чтения предыдущей, чтобы последовательное чтение не задерживало процессор. В реальности ситуацию ещё больше улучшают микросхемы памяти с несколькими одновременно открытыми строками и многоканальные контроллеры памяти.
> Как часто можно встретить ситуацию, когда 100.000 раз обращений к оперативки выгоднее, чем одно обращение к диску, особенно учитывая существование SSD и PCI-SSD?
При хоть сколь-нибудь продуманном доступе к памяти — считаем, практически всегда.
> Тем более, что сетевой сокет в гигабитной локалке, может быть быстрее, чем обращение к диску.
Гигабитный — по сравнению с SATA даже 1-м — уже нет :) Вот 10GB, или Infiniband'овские скорости — да, уже стоит упоминать.
Гигабитный — по сравнению с SATA даже 1-м — уже нет :) Вот 10GB, или Infiniband'овские скорости — да, уже стоит упоминать.
Не важно гигабит или 10. Проблема не в пропускной способности, а в сетевых задержках.
> Проблема не в пропускной способности, а в сетевых задержках.
Я рассматривал в контексте передачи сравнимого с от «100,000 обращениями к оперативной памяти» и до «1,000,000,000 тактов» объёма передачи, там задержки уровня одного пакета уже не столь существенны, а скорость значительно больше влияет на общую задержку. В контексте коротких передач — да, безусловно, суммарные задержки важнее, и пример «512 байт из iRAM по сети vs. HDD локально, которому надо ещё переместить головки на полный диапазон» — отличная иллюстрация.
Я рассматривал в контексте передачи сравнимого с от «100,000 обращениями к оперативной памяти» и до «1,000,000,000 тактов» объёма передачи, там задержки уровня одного пакета уже не столь существенны, а скорость значительно больше влияет на общую задержку. В контексте коротких передач — да, безусловно, суммарные задержки важнее, и пример «512 байт из iRAM по сети vs. HDD локально, которому надо ещё переместить головки на полный диапазон» — отличная иллюстрация.
Одна кликабельная картинка лучше тысячи слов!
Если честно, такая ужасная картинка хуже тысячи слов.
На вкус и цвет фломастеры разные, но я очень рекомендую сходить по ссылке и подвигать слайдер. Заодно, к истории компьютеров в очередной раз приобщитесь, на прогноз посмотрите.
Аргументирую — вашу «таблица» ужасна с точки зрения дизайна. Ее просто невозможно прочитать, не решив попутно пару головоломок. Пустота в первом ряду третьего и четвертого столбцах — это глюк? Почему 100 ns — это один синий квадрат, а 125 ns — это пустота? А, это оттого что в третьем столбце уже все в зеленых квадратах… Который равен чему? А, нужно посмотреть в конец синего столбца… Это какая-то головоломка, а не дизайн, который призван разложить все по-полочкам.
Прогноз тоже не впечатляет, через 5 лет практически ничего не поменяется, а дальше неизвестность.
Прогноз тоже не впечатляет, через 5 лет практически ничего не поменяется, а дальше неизвестность.
Согласен.
Я, просто, не видел ничего нагляднее.
А тут ведь ещё бонусом «интерактив» и чуть-чуть истории.
Upd: автор этой странички не я. Я только заскриншотил, «мопед не мой. Но мопед хороший, годный!!!»
Я, просто, не видел ничего нагляднее.
А тут ведь ещё бонусом «интерактив» и чуть-чуть истории.
Upd: автор этой странички не я. Я только заскриншотил, «мопед не мой. Но мопед хороший, годный!!!»
Есть ещё вот такая аналогия, текстовая:
1 CPU cycle: 0.3 ns => to human scale 1s
L1 cache access: 0.9ns => 3s
L2 cache access: 2.8ns => 9s
L3 cache access: 12.9ns => 43s
Main memory access: 120ns => 6 min
SSD Disk: 50-150 us => 2-6 days
Rotational Disk: 1-10ms => 1-12months
Internet: San Francisco to New york: 40ms => 4 years
И вот такая вот инфографика.
Вообще — тема довольно избитая :)
зато подёргав ручку можно оказаться в будущем или прошлом. sarcasm Удобно
Зато понятно, в чем разница между аукционными серваками на hеtzner или low cost от kimsufi и более свежим железом
На вскидку, модуль памяти с tRCmin < 50нс.
В данном графике, скорость памяти зависла на отметке в 100 нс, и меняется только скорость SSD, что наталкивает на заказной характер графика со стороны производителей SSD.
Кроме того на скорость работы памяти (кроме непосредственно характеристик модуля памяти) влияет количество каналов памяти в системе, и оптимизации структур хранения данных под канальность.
В данном графике, скорость памяти зависла на отметке в 100 нс, и меняется только скорость SSD, что наталкивает на заказной характер графика со стороны производителей SSD.
Кроме того на скорость работы памяти (кроме непосредственно характеристик модуля памяти) влияет количество каналов памяти в системе, и оптимизации структур хранения данных под канальность.
http://www.anandtech.com/show/10435/assessing-ibms-power8-part-1/8
Пусть будет 50. Добавьте к этому время кеш-миссов L1-L2-L3
Пусть будет 50. Добавьте к этому время кеш-миссов L1-L2-L3
Там все хитрее, получить данные если блок модуля свободен в данный момент можно через 15-25 нс (включая передачу данных из RAM в кэш). Оперативная память на текущий момент оптимально заточена под последовательное чтение, чуть более менее начинается рандом, начинаются сильные задержки на доступ к данным. Насколько помню у интела есть префиксы обращения к памяти мимо кэша. Есть команды предварительного чтения данных в кэш. Если подойти комплексно то можно сильно оптимизировать, но нужно либо довериться компилятору, либо изучать/вспоминать машинные коды, ну и хорошо понимать как работает аппаратная платформа.
Хорошая попытка, именно за такими интерактивными презентациями будущее.
Но конкретно эта — полностью провалена =(
Тут даже с текстом не сразу разобрать что имел в виду автор.
Двигаем ползунок по года и лишь видим, как скорость доступа к данным ускорялась со временем. Для этого лучше бы простой график сделали, и то было бы нагляднее.
Но конкретно эта — полностью провалена =(
Тут даже с текстом не сразу разобрать что имел в виду автор.
Двигаем ползунок по года и лишь видим, как скорость доступа к данным ускорялась со временем. Для этого лучше бы простой график сделали, и то было бы нагляднее.
Мне больше эта картинка нравится
Картинка
/>
Еще есть хорошая книга по оптимизации кода для разных платформ: «Structured Parallel Programming: Patterns for Efficient Computation».
Как программист, вы должны понимать иерархию памяти, потому что она сильно влияет на производительность ваших программ. Если вы понимаете как система перемещает данные вверх и вниз по иерархии, вы можете писать такие программы, которые размещают свои данные выше в иерархии, так что процессор может получить к ним доступ быстрее.Как программист, я не должен! Это компилятор должен оптимизировать мой код, и часто у современных компиляторов это не плохо получается. Но как программист имею право отказаться от решений компилятора и попробовать сделать код быстрее. В этом случае статья может помочь, но таких случаев небольшой процент от всех решаемых задач.
У компиляторов это получается на уровне переменных. Но компилятор не сможет выбрать направление обхода матрицы.
А Вы уверены, что для другого компилятора на другой платформе выбранное направление обхода будет оптимальным. Как быть с переносимостью, если речь не о программах-однодневках?
Первая функция читала элементы матрицы построчно и двигалась по памяти последовательно, будто обходила один большой одномерный массив.Это убедительно. Но ведь это тривиальный случай.
Это довольно частый случай.
Зависит от круга решаемых задач. Может быть для какого-то типа задач этот случай очень частый, но и там, наверное, далеко не всегда этот участок кода оказывается критичным по скорости. Для разреженных матриц и для параллельных вычислений, наверное, нужны другие приемы и т.д. Впрочем я не настаиваю, просто высказал небольшое сомнение в практической полезности. Существует очень много рекомендаций по оптимизации кода, но, к сожалению, очень часто в этих рекомендациях приводят слишком искусственные примеры. Но, как сказал выше, думаю что в некоторых случаях
статья может помочь.
UFO just landed and posted this here
Ok. А теперь сравним, автор статьи написал:
А Вы написали:
Видите разницу? Я только об этом. Если моя программа работает недостаточно быстро, то мне нужно подумать, как ее ускорить. А если быстро, то не стоит тратить время на ненужное ускорение. Иногда авторы используют неподходящую форму и слова, получая нежелательный для автора эффект.
Как программист, вы должны
А Вы написали:
Если вам нужна максимальная производительность
Видите разницу? Я только об этом. Если моя программа работает недостаточно быстро, то мне нужно подумать, как ее ускорить. А если быстро, то не стоит тратить время на ненужное ускорение. Иногда авторы используют неподходящую форму и слова, получая нежелательный для автора эффект.
Если моя программа работает недостаточно быстро, то мне нужно подумать, как ее ускорить.
Совершенно верно. И это входит в обязанности программиста.
Да. Входит. Только такое бывает нечасто. В моей практике 90% программ ускорять не нужно, а 9% заметному ускорению не поддаются — такие переборные алгоритмы. Остается 1%, где ускоряем.
UFO just landed and posted this here
И ускоряете весь код или только критические участки? Широко известны утверждения типа:
«обычно 90% кода тратят 10% общего времени работы программы». Для Ваших задач это утверждение справедливо? Если справедливо, то должен ли программист думать об иерархии памяти, когда работает над некритическим участком?
«обычно 90% кода тратят 10% общего времени работы программы». Для Ваших задач это утверждение справедливо? Если справедливо, то должен ли программист думать об иерархии памяти, когда работает над некритическим участком?
UFO just landed and posted this here
И параллелится плохо — на CUDA не сделать? Тогда понятно. Спасибо за ответ.
UFO just landed and posted this here
Вообще-то написание эффективного программного кода требует затрат времени, иногда — очень больших затрат.
Поставить индексы в правильном порядке, сгруппировать данные, поставить parallel.for — эти действия практически не увеличивают время написания программы, зато сильно уввеличивают скорость выполнения. Поэтому программист должен уметь всем этим пользоваться, чтобы в случае, когда придётся писать критический участок, действия были доведены до автоматизма.
А вот выжать максимум — задействовать AVX, переписать код на CUDA может увеличить время разработки в несколько раз, что сведёт на нет выгоду от быстрого выполнения вычислительного кода. Я, например, вычислительные алгоритмы вообще пишу на C#, потому что так быстрее. Когда возникает необходимость ускорить — переписываю на C++ с использованием AVX. CUDA — тяжёлая артиллерия, когда CPU уже мало.
Поставить индексы в правильном порядке, сгруппировать данные, поставить parallel.for — эти действия практически не увеличивают время написания программы, зато сильно уввеличивают скорость выполнения. Поэтому программист должен уметь всем этим пользоваться, чтобы в случае, когда придётся писать критический участок, действия были доведены до автоматизма.
А вот выжать максимум — задействовать AVX, переписать код на CUDA может увеличить время разработки в несколько раз, что сведёт на нет выгоду от быстрого выполнения вычислительного кода. Я, например, вычислительные алгоритмы вообще пишу на C#, потому что так быстрее. Когда возникает необходимость ускорить — переписываю на C++ с использованием AVX. CUDA — тяжёлая артиллерия, когда CPU уже мало.
сейчас пишу свою вычислительную балалайку (мкэ, мдтт) и есть всего 2 критических участка. 1 — итерационное решение разреженной СЛАУ с предобуславливанием и 2 — вычисление элементов матрицы СЛАУ, где много вещественных операций, от которых никуда не деться. Первый участок сжирает ~93% времени и второй сжирает ~5% времени (для больших матриц). И самое узкое место — умножение матрицы на вектор — 91% всех вычислений — занимает 23 строки:
// A*x -> y (x !=y !!!!)
void Slau::amulx(const double *x, double *y)
{
int i, j, t;
// y = 0
for (i = 0; i < N; i++)
y[i] = 0;
// вне диагонали
for (j = 0; j < N; j++) // строка номер j
{
for (t = ind[j]; t < ind[j + 1]; t++) // t — индекс элемента j-й строки
{
i = ai[t]; // столбец номер i
// a[t] — элемент A(j, i)
y[j] += a[t] * x[i];// нижний треугольник
y[i] += a[t] * x[j];// верхний треугольник
//printf(«A(%d, %d) = %lf\n», j, i, a[t]);
}
}
// диагональ
for (i = 0; i < N; i++)
y[i] += d[i] * x[i];
}
Скопировал как есть, написано года ~3 назад.
А это <1% кода. Только сейчас задумался, как можно это оптимизировать. В boost строчно-столбцового формата для симметричных матриц вроде бы нет (за бугром его не юзают почти), а на ассемблер лома переписывать и ассемблер — это временное решение.
// A*x -> y (x !=y !!!!)
void Slau::amulx(const double *x, double *y)
{
int i, j, t;
// y = 0
for (i = 0; i < N; i++)
y[i] = 0;
// вне диагонали
for (j = 0; j < N; j++) // строка номер j
{
for (t = ind[j]; t < ind[j + 1]; t++) // t — индекс элемента j-й строки
{
i = ai[t]; // столбец номер i
// a[t] — элемент A(j, i)
y[j] += a[t] * x[i];// нижний треугольник
y[i] += a[t] * x[j];// верхний треугольник
//printf(«A(%d, %d) = %lf\n», j, i, a[t]);
}
}
// диагональ
for (i = 0; i < N; i++)
y[i] += d[i] * x[i];
}
Скопировал как есть, написано года ~3 назад.
А это <1% кода. Только сейчас задумался, как можно это оптимизировать. В boost строчно-столбцового формата для симметричных матриц вроде бы нет (за бугром его не юзают почти), а на ассемблер лома переписывать и ассемблер — это временное решение.
У вас очень много заблуждений.
1. Переписывание на ассмеблере может дать эффект только если вы программируете под компьютеры 25-летней давной. С современными компиляторами и инструкциями процессоров, скорее всего, сделаете только хуже.
2. Использование свойства симметричности матрицы снижает потребление памяти, но ухудшает производительность. Храните матрицу в общем виде, не используя этого свойства.
3. Попробуйте использовать специализированные оптимизированные библиотеки для решения поставленной задачи (например, Intel MKL), если самостоятельная реализация алгоритмов линейной алгебры не является
1. Переписывание на ассмеблере может дать эффект только если вы программируете под компьютеры 25-летней давной. С современными компиляторами и инструкциями процессоров, скорее всего, сделаете только хуже.
2. Использование свойства симметричности матрицы снижает потребление памяти, но ухудшает производительность. Храните матрицу в общем виде, не используя этого свойства.
3. Попробуйте использовать специализированные оптимизированные библиотеки для решения поставленной задачи (например, Intel MKL), если самостоятельная реализация алгоритмов линейной алгебры не является
Переписывание на ассмеблере может дать эффект только если вы программируете под компьютеры 25-летней давной. С современными компиляторами и инструкциями процессоров, скорее всего, сделаете только хуже.И я того же мнения, но всего несколько месяцев прошло как в другой теме меня хором уверяли:
А критические участки реализуют на ассемблере по сей день, и если что — я и мои знакомые можем делать на ассемблере код более быстрый, чем на языке высокого уровня :)Какие противоположные мнения существуют.
Про MKL. Не всегда помогает. У меня был случай, когда надо было решать очень много небольших (в десяток неизвестных) СЛУ. Мой код на языке высокого уровня оказался для такого случая быстрее, чем MKL. Спрашивал разработчиков — подтвердили, что это так для моего специального случая.
Я тоже сначала думал, что от переписывания критических участков на ассемблере есть смысл. И действительно получал ускорение примерно в 2 раза по сравнению с высокоуровневым кодом с использованием intrinsics, плюясь от необходимости писать отдельно 32-битный и 64-битный код. Но когда я сменил компилятор (MSVC на Intel), оказалось, что компилятор от Intel генерирует код даже более быстрый, чем вручную написанный на ассемблере. С тех пор в написание на ассемблере не лезу совсем, только периодически поглядываю на сгенерированный код.
Что касается MKL. Ну да, за универсальность тоже стоит платить. Например, собственная реализация Parallel.For имеет существенно меньший оверхед, чем реализация в Intel TBB, что позволяет вообще не думать о гранулярности параллелизма в задачах обработки изображений.
Что касается MKL. Ну да, за универсальность тоже стоит платить. Например, собственная реализация Parallel.For имеет существенно меньший оверхед, чем реализация в Intel TBB, что позволяет вообще не думать о гранулярности параллелизма в задачах обработки изображений.
Да. Это плата за универсальность. Но плата, похоже, меньшая, чем у TBB. Про TBB в Intel отмечали, что там сознательный упор на универсальность, а не на скорость. В MKL же скорости изначально уделяют большое внимание, и действительно, насколько мне известно, MKL в большинстве случаев (кроме специальных, как был у меня) очень хорошо помогает.
У меня был не особо удачный опыт с MKL. Для тех задач которые в MKL непосредственно реализованы все да, работает быстро. Но вот попытка набрать свой алгоритм из отдельных простых BLAS-функций предоставляемых MKL (типа перемножения матрицы на вектор) работала довольно грустно. С библиотекой Eigen все работало значительно быстрее.
Тот пост был написан к тому, что в вычислительных программах узкие места тоже могут занимать малую часть кода, а не для разбора моих заблуждений.
оффтоп
1. Переписывание на ассемблер в теории (в идеале) даст максимальную производительность, для конкретного множества процессоров, то есть временно, поэтому да, толку от этого мало.
2. Использование свойства симметричности наоборот улучшает производительность, это очевидно из приведенного кэш-френдли кода.
3. Таки да, придется использовать обычное строчное представление CSR и PARDISO (Intel MKL) / Eigen, за неимением лучшего.
оффтоп
1. Переписывание на ассемблер в теории (в идеале) даст максимальную производительность, для конкретного множества процессоров, то есть временно, поэтому да, толку от этого мало.
2. Использование свойства симметричности наоборот улучшает производительность, это очевидно из приведенного кэш-френдли кода.
3. Таки да, придется использовать обычное строчное представление CSR и PARDISO (Intel MKL) / Eigen, за неимением лучшего.
Если в вашей практике 90% программ ускорять не нужно, вы можете просто не читать статью.
На моем прошлом проекте (embedded), мы дрались буквально за каждый такт.
На моем прошлом проекте (embedded), мы дрались буквально за каждый такт.
Как, как… ifdef-ы, ifdef-ы, тридцать пять тысяч одних ifdef-ов. Под каждую платформу, архитектуру и компилятор, до которых руки дотянулись, вручную прописывается оптимизированное решение. Загляните как-нибудь на досуге в опенсорсную библиотеку, выполняющую много вычислений (линейная алгебра, обработка изображений, видео, вот это вот всё), ужаснитесь сами. Компилятор должен, но не может, как правило.
Направление вряд ли поменяет, но может переставить циклы или сделать блокинг: https://software.intel.com/en-us/articles/performance-tools-for-software-developers-loop-blocking
Направление обхода могут поменять и ICC и GCC и CLang, но в целом да, их возможности сильно ограничены
Отдельная история состоит в том что для FP-вычислений оптимизация может менять результат вычислений, поэтому многие оптимизации подобного рода по умолчанию заблокированы. Интел по-моему единственный кто их по умолчанию включает (и у меня в проекте он дооптимизировал подобным образом один кусок legacy-кода до segfault :) )
Отдельная история состоит в том что для FP-вычислений оптимизация может менять результат вычислений, поэтому многие оптимизации подобного рода по умолчанию заблокированы. Интел по-моему единственный кто их по умолчанию включает (и у меня в проекте он дооптимизировал подобным образом один кусок legacy-кода до segfault :) )
UFO just landed and posted this here
У меня было забавно
Безобидный код, правда? И из него совершенно очевидно что frac >= 0. Так собственно всю жизнь и было, пока не пришел Интел и не сказал
Черт его знает зачем компилятору vfmsub213sd в код захотелось вставить, но из-за того что FMA хранит результат умножения с большей точностью чем регистр то в некоторых случаях получилось что frac < 0 и это крэшило код дальше который предполагал что отрицательного числа в frac никогда не будет.
double mul = x * y;
double frac = mul - floor(mul);
Безобидный код, правда? И из него совершенно очевидно что frac >= 0. Так собственно всю жизнь и было, пока не пришел Интел и не сказал
r1 = load(x)
r2 = load(y)
r3 = mul(r1,r2)
r4 = floor(r3) // r4 = floor(x*y)
r5 = fmsub(r1, r2, r4) // r5 = x*y - r4
frac = store(r5)
Черт его знает зачем компилятору vfmsub213sd в код захотелось вставить, но из-за того что FMA хранит результат умножения с большей точностью чем регистр то в некоторых случаях получилось что frac < 0 и это крэшило код дальше который предполагал что отрицательного числа в frac никогда не будет.
Во сколько минусов отгреб! А за что? Кто бы объяснил: кому я тут задолжал? У кого 5 рублей до получки занял? :) ИМХО в большинстве случаев не должен программист задумываться о незаметных ускорениях кода, иначе это очень отрицательно скажется на продуктивности работы этого программиста. Но при этом согласен, что бывают не очень частые случаи, когда нужно сделать код быстрее. Автор и согласные с ним видимо считают, что программист всегда в любом случае должен думать про иерархию памяти. Т.к. автор первый это сказал, то пусть он (или кто с ним в этом согласен) приведет подтверждающую статистику. Тогда и только тогда мне придется согласится с тем, что и я должен это делать. Или у меня задачи такие специфические, никак у всех?
незаметных ускорениях кода
А вы читали статью?
Читал. Представьте себе. И даже не придрался, что в графе обычно ребра, а не грани. Грань — это скорее из геометрии. Википедию бы посмотрели:
Объекты представляются как вершины, или узлы графа, а связи — как дуги, или рёбраСовсем дикие?
Поставили минусы за поправку терминологии? Интересно и за следующую правку минусы получу?
В квадратной матрице две диагонали. Речь здесь идет о главной диагонали. В литературе по матричной алгебре не пишут, что матрицу нужно представлять визуально, а просто пишут, что матрица симметричная.
если представить матрицу визуально, то элементы (i, j) и (j, i) являются симметричными относительно диагонали.
В квадратной матрице две диагонали. Речь здесь идет о главной диагонали. В литературе по матричной алгебре не пишут, что матрицу нужно представлять визуально, а просто пишут, что матрица симметричная.
В литературе по матричной алгебре нет плоской одномерной оперативной памяти.
В квадратной матрице есть только одна диагональ, потому что вторая не имеет математического смысла.
См. статью и ссылку там: Weisstein, Eric W. Main diagonal (англ.) на сайте Wolfram MathWorld. А еще можно любой учебник по «линейке» открыть.
А вам кто задолжал? Почему это все должны бросаться вам что-то доказывать, искать какую-то статистику?
Вы, если программист, можете убеждать недовольное быстродействием вашей программы начальство или клиентов в том, что обеспечить быстродействие программы — это не ваша обязанность, а обязанность компилятора. С некоторыми людьми такое может даже сработать.
Вы, если программист, можете убеждать недовольное быстродействием вашей программы начальство или клиентов в том, что обеспечить быстродействие программы — это не ваша обязанность, а обязанность компилятора. С некоторыми людьми такое может даже сработать.
Потому, что аксиома, что автор должен обосновать то, о чем он пишет. Т.о. задолжал автор — т.к. не доказал. Кто сказал, что клиенты недовольны моими прогами? Срабатывает за десятую секунды, убыстрить на 20% — никто не заметит. Вы читать умеете — впечатление что писать научились, а читать еще нет. М.б. у Вас все задачи экспоненциальной сложности и других не знаете — тогда сочувствую, но описанные в статье методы Вам с экспонентой не помогут.
UFO just landed and posted this here
Вы, мне кажется, не очень понимаете, про какую оптимизацию идет речь и про какие программы. На плюсах пишется очень много научного и вычислительного кода, которые может работать несколько часов, дней или недель. Получив, скажем, 10% выигрыш в производительности на ядро, коих может использоваться сотня — это офигеть какой прирост в решении задачи.
Чтобы все работало быстро, на плюсах нужно знать довольно много нюансов, начиная от передачи тяжелый объектов по ссылке, move-семантики и префиксного инкремента, и заканчивая специфичными оптимизациями компилятора типа __builtin_expect. К слову, последнее на уже давно написанном и оптимизированным коде выдало 20% прирост производительности на x86 и (sic!) двукратный прирост на VLIW архитектуре.
Наряду с этими оптимизациями, надо еще писать эффективный параллельный код, то есть знать, что переключение контекста процессора — это ОЧЕНЬ плохо и дорого, что нужно использовать барьеры памяти, RW-локеры, атомарные операции, lock-free структуры и кучу другой магии. А еще нужно знать структуры данных, алгоритмы, оценивать сложность разработанных алгоритмов и т.д. Совокупный кругозор по всем этим тематикам делает из конкретного программиста крутого спеца, за которого готовы платить очень серьезные деньги такие компании, как Яндекс, Интел, Гугл, Майкрософт и далее по списку.
Естественно, это нужно не всем. Естественно, не нужно оптимизировать цикл, если он состоит плюс-минус из 5 элементов. Но есть ряд задач, где все эти хаки и знания приносят ощутимую выгоду.
Чтобы все работало быстро, на плюсах нужно знать довольно много нюансов, начиная от передачи тяжелый объектов по ссылке, move-семантики и префиксного инкремента, и заканчивая специфичными оптимизациями компилятора типа __builtin_expect. К слову, последнее на уже давно написанном и оптимизированным коде выдало 20% прирост производительности на x86 и (sic!) двукратный прирост на VLIW архитектуре.
Наряду с этими оптимизациями, надо еще писать эффективный параллельный код, то есть знать, что переключение контекста процессора — это ОЧЕНЬ плохо и дорого, что нужно использовать барьеры памяти, RW-локеры, атомарные операции, lock-free структуры и кучу другой магии. А еще нужно знать структуры данных, алгоритмы, оценивать сложность разработанных алгоритмов и т.д. Совокупный кругозор по всем этим тематикам делает из конкретного программиста крутого спеца, за которого готовы платить очень серьезные деньги такие компании, как Яндекс, Интел, Гугл, Майкрософт и далее по списку.
Естественно, это нужно не всем. Естественно, не нужно оптимизировать цикл, если он состоит плюс-минус из 5 элементов. Но есть ряд задач, где все эти хаки и знания приносят ощутимую выгоду.
Раз уж пошла такая пьянка, то может быть кто-то знает ответ на мой вопрос:
http://stackoverflow.com/q/39947921/253146
Коротко: почему выделение памяти операционной системой для процесса занимает в 2 раза больше времени, чем очищение страниц в оперативной памяти + очищение страниц в L3 кеше процессора.
Вы очищаете память два раза. Первый раз вам ее чистит система, перед тем как вернуть чистую страницу — второй раз вы сами чистите ее memset. Отсюда и просадка производительности.
На больших блоках malloc/free начинают запрашивать память напрямую у системы — и так же возвращать обратно.
Вы очищаете память два раза.
Да, об этом там написано
На больших блоках malloc/free начинают запрашивать память напрямую у системы
Да, об этом там написано
Отсюда и просадка производительности.
Нет, не отсюда. Производительность при выделении памяти у системы все равно в 2 раза хуже, чем очищение памяти не влезающей в кеш процессора + очищение памяти, влезающей в кеш.
А в чем вопрос-то?
Вы понимаете что память возвращаемая в ОС чистится. Это 2x потеря производительности
Вы понимаете что память полученная от ОСи не замаплена изначально в физическую. Это означает получение PAGE FAULT на каждые 4 Кб памяти и соответствующее прерывание — это отжирает еще приличный кусок производительности.
Вы, по идее, понимаете что выделение блока адресного пространства и каждой из страниц физической памяти требует от операционки поиска свободного пространства / страниц, исправления таблиц трансляции и обновления их в TLB. Это все операции подразумевающие довольно обширные прогулки по памяти и потому — сравнительно медленные и подъедающие еще ощутимый кусок от производительности.
Я правильно понимаю что судя по последнему абзацу SO вопрос, в общем-то, сводится к тому «а почему это все не сделано быстрее»? Потому что ответ на него очень простой: универсального решения в любом случае не существует и создатели операционки просто перекладывают его на разработчика программ. Если Вам внезапно почему-то нужно постоянно аллоцировать и освобождать крупные блоки памяти, то Вы должны использовать подходящий под эту задачу менеджер памяти, а не надеяться что операционка угадает какой именно из (разных возможных) сценариев использования памяти оптимальным образом подойдет к Вашему приложению. Дефолтная реализация в операционке консервативна, экономит физическую память и написана максимально безопасным способом.
Вы понимаете что память возвращаемая в ОС чистится. Это 2x потеря производительности
Вы понимаете что память полученная от ОСи не замаплена изначально в физическую. Это означает получение PAGE FAULT на каждые 4 Кб памяти и соответствующее прерывание — это отжирает еще приличный кусок производительности.
Вы, по идее, понимаете что выделение блока адресного пространства и каждой из страниц физической памяти требует от операционки поиска свободного пространства / страниц, исправления таблиц трансляции и обновления их в TLB. Это все операции подразумевающие довольно обширные прогулки по памяти и потому — сравнительно медленные и подъедающие еще ощутимый кусок от производительности.
Я правильно понимаю что судя по последнему абзацу SO вопрос, в общем-то, сводится к тому «а почему это все не сделано быстрее»? Потому что ответ на него очень простой: универсального решения в любом случае не существует и создатели операционки просто перекладывают его на разработчика программ. Если Вам внезапно почему-то нужно постоянно аллоцировать и освобождать крупные блоки памяти, то Вы должны использовать подходящий под эту задачу менеджер памяти, а не надеяться что операционка угадает какой именно из (разных возможных) сценариев использования памяти оптимальным образом подойдет к Вашему приложению. Дефолтная реализация в операционке консервативна, экономит физическую память и написана максимально безопасным способом.
PAGE FAULT на каждые 4 Кб памяти и соответствующее прерывание
поиска свободного пространства / страниц
Спасибо, это уже похоже на возможное объяснение.
«а почему это все не сделано быстрее»
Это такой теоретический подвопрос. Цель у меня сугубо практическая. Мне действительно иногда нужно выделать по 40-100 мегабайт памяти за раз и я хочу знать, можно ли с этим что-то сделать, кроме как тупо не отдавать память обратно. Мне бы сгодилась даже какая-нибудь настройка ядра Линукса, которая магическим образом делала бы все небезопасным но быстрым.
Я не сталкивался с подобными задачами но думаю что encyclopedist предлагает отличную идею в лице mmap + комбинации флагов. MAP_PRIVATE + MAP_ANONYMOUS + MAP_POPULATE выглядят разумным началом, а дальше я бы попробовал поэкспериментировать с MAP_UNINITIALIZED и MAP_HUGETLB. Но вообще как правило правильное решение — это менеджер памяти. Ибо верно одно из двух: либо Вы делаете подобные операции постоянно (и тогда разумно не возвращать часть памяти), либо занимаетесь экономией на спичках (если эти операции спорадические)
Я полагаю, это оверхед от переключения контекста между приложением и ядром при pagefault-ах. Можно попробовать использовать mmap c разными флагами (MAP_POPULATE например).
Интересно! Столько программистов написали восторженные отзывы на эту статью, но никто (может пропустил — поправьте, пожалуйста) не написал: эта статья помогла исправить провальный проект. У меня куча ссылок, статей и книг по оптимизации кода — коллекция аж с того века. Думаю: вдруг пригодится, но пригождается очень мало. Оптимизация — большое искусство, где очень трудно что-то новое и полезное предложить.
Потому что от момента когда статья была прочитана до момента, когда она пригодилась, может пройти довольно много времени. Мне вот не раз пригождались статьи в интернете — но каждый раз я к тому моменту забывал где я это все прочитал.
Именно эта статья — нет, но аналогичные — да. Cетевой транспорт некоторого специфического протокола (средняя длина сообщения около 200 байт); внутреннее представление сообщения — или разложение в таблицу пар имя=значение, или как две строки (std::string, заголовок и тело) с манипуляцией над строкой с массовыми перемещениями частей при вставлении или удалении тегов. Без проблем медленной RAM — работа с разложенным представлением была бы в разы быстрее, но с учётом медленной памяти и кэширования — работа с цельными строками в ~2 раза быстрее. Ещё процентов 30 получается за счёт предаллокации строк на предполагаемую длину, вместо того, чтобы позволять рантайму несколько раз делать realloc.
UFO just landed and posted this here
У меня была такая задача: вычислить среднее значения модуля производной изображения по блоку 3х3.
Варианта написания тут два:
1. Подход наивный — для каждого пикселя 9 раз вычислять производные, не переиспользуя значения.
2. Подход с наименьшим количеством операций — это сначала посчитать модуль производной в каждом пикселей, затем усреднить по столбцам, затем по строкам. Т.е. 3 прохода по изображению с кэш-френдли доступом.
В однопоточном режиме без AVX производительность первого подхода была немного ниже, чем второго. Но когда я переписал код с использованием AVX и параллельности, сразу упёрся в скорость памяти. Второй способ оказался в ~2.5 раза медленнее первого.
Выжать максимум же можно, преобразовав второй метод в однопроходный, используя конвейер. Ну и немного позаморачиваться при параллелизации. Я, правда, не стал заморачиваться, т.к. это привело бы к ускорению максимум на 10%, зато сильно усложнило бы код.
Варианта написания тут два:
1. Подход наивный — для каждого пикселя 9 раз вычислять производные, не переиспользуя значения.
2. Подход с наименьшим количеством операций — это сначала посчитать модуль производной в каждом пикселей, затем усреднить по столбцам, затем по строкам. Т.е. 3 прохода по изображению с кэш-френдли доступом.
В однопоточном режиме без AVX производительность первого подхода была немного ниже, чем второго. Но когда я переписал код с использованием AVX и параллельности, сразу упёрся в скорость памяти. Второй способ оказался в ~2.5 раза медленнее первого.
Выжать максимум же можно, преобразовав второй метод в однопроходный, используя конвейер. Ну и немного позаморачиваться при параллелизации. Я, правда, не стал заморачиваться, т.к. это привело бы к ускорению максимум на 10%, зато сильно усложнило бы код.
В примере void matrixmult2() массив C нужно предварительно очистить. Сдается мне, что дополнительный цикл записи по C нивелирует выигрыш
Этот проход по массиву C никак не займёт больше времени чем занимает основной цикл. А ускорение из-за эффектов локальности получилось в 12 раз.
Кэш оптимизирует чтение. Оптимизирует ли он запись?
А это не важно. Цикл уже ускорен в 12 раз, а добавление нового никак не замедлит более чем в два раза (и это очень грубая оценка).
Конечно.
Кеш для записи позволяет оптимизировать ее двумя основными способами.
1) передача операции записи на другое устройство/другой поток, которое выполнит эту запись по возможности, чтобы основной поток продолжил выполнение основной задачи сразу.
2) объединение нескольких мелких операций записи в одну большую, что уменьшает работу более медленных устройств.
Кеш для записи позволяет оптимизировать ее двумя основными способами.
1) передача операции записи на другое устройство/другой поток, которое выполнит эту запись по возможности, чтобы основной поток продолжил выполнение основной задачи сразу.
2) объединение нескольких мелких операций записи в одну большую, что уменьшает работу более медленных устройств.
Sign up to leave a comment.
Оптимизация кода: память