Да я вроде этому и посвятил пол статьи. Но всё-таки это не всегда так и надо отслеживать когда I/O bound а когда CPU. AoS vs SoA это частные случае data oriented design, минимизация обращений к памяти через дизайн структуры часто очень не простая задача
Очень сильно не согласен. Во-первых, SSE, AVX2 и AVX512 различаются не только длиной регистра, но и доступными инструкциями (вики и список интринсиков). Во-вторых, в зависимости от задачи ботлнек может быть по памяти, а может и по вычислениям, в последнем случае имеет значение сколько и каких SIMD юнитов имеет процессор. У меня есть пример где ботлнек по арифметике и как раз использование GFNI из AVX-512 ускоряет в два раза универсальный алгоритм на AVX2 https://github.com/Malkovsky/galois?tab=readme-ov-file#vector-operations (понятно, что оба варианта еще можно соптимизировать и разница возможно будет меньше, но суть от этого не меняется)
*dst=*src работает быстрее, чем dst[i]=src[j]. Массивы с указателем data[i] внутри (ассемблер) не смотрел
не совсем понял о чем речь
Включил кеши и MMU. Вместо ожидаемых 10...20 крат прироста скорости, получились все 40
Почему ожидали 10..20?
Вот тут я начал сомневаться, а что если процессор берет данные не из ячеек памяти, где они актуальные, а из кеша и помещает также, где гарантия, что они - валидны. Тут есть вариант либо чтения несколько раз, пока не считается нужное, либо надо ставить барьер в памяти. И то, и другое -лишние циклы. А если несколько ядер, у каждого свои кеши - как они могул знать, что у кого в "мозгаз" пока не попадут в RAM.
Как-будто вы описываете общую проблему валидности памяти кэш систем с разделенными L1/L2. Отсюда кстати и false sharing вырастает
Мне кажется, что посыл как раз в том, что сейчас мы можем посмотреть на все это безобразие и осознать, что многого из этого можно было избежать. Мы видим "прекрасные" наглядные примеры того, к чему приводят кривоватости в фундаменте и как сложно его потом менять. Понятно, что ничего из перечисленного в баше не изменится, но смотря на это можно хотя бы не допускать подобного для новых технологий
Разумеется, на него тоже «есть управа» в виде алгоритма Берлекэмпа-Мэсси, модификаций критерия интервалов на выборках в десятки петабайт и особо хитрых настройках критерия промежутков между днями рождения
Если честно, выглядит так, как будто пример взят не из практики, а придуман. Про то, что пройтись по списку дольше, чем по массиву из-за кэш промахов да, понятно. Как это связано с исходным тезисом про хеш-таблицы и бинарный поиск? Может пример какой-нибудь? Полагаю, что не будет, потому что как раз на практике у бинарного бинарного поиска хуже паттерн обращений к памяти, чем у хеш-таблицы.
Если нужен реальный пример грамотной работы с кэшем -- замена бинарного дерева поиска на B-дерево, в котором размер узла может быть выставлен в соответствие размеру кэш линии.
Typest попробовал, клевая вещь, рендерит быстрее. Но пока не понял почему нужно на него перейти. Слишком много всего надо будет менять и переадаптироваться
Вот если бы он просто быстро рендерил латех, то я скорее всего сидел бы на нём
Еще такой глобальный вопрос: из статьи кажется, что вы хотите учебник и в печатном, и в электронном варианте. Многие вспомогательные штуки в печатном варианте невозможны, что делает сложным иметь один вариант для обоих случаев. Если все-таки предполагается электронный вариант, разве нет каких-нибудь хороших альтернатив latex? Я лично смотрю в сторону jupyter book и подобного, сам использую quarto, по сути они все представлют собой jupyter страницы в разных вариациях, преимущество которых перед техом в том, что большую часть текста можно верстать в markdown, тех поддерживается на достаточном уровне чтобы сверстать IEEE статью и при этом есть возможность исполняемые вставлять фрагменты кода и компилировать не только в пдф.
Отдельно отмечу, что лично я latex перестал работать c чистым latex в основном из-за отсутствия адекватного UX, например в overleaf я не вижу визуально изменения мгновенно, а в MD вижу. Тут еще стоит отметить typst, но с ним я почти не знаком.
Мне кажется, что это статья гораздо лучше большинства нейрослопа, которым сейчас переполнен Хабр и не только. Несмотря на это не могу не согласиться с соседними комментариями о низком уровне материала, от себя добавлю про техническую часть, касающуюся математических вычислений:
Вы сравниваете свои реализацию метода №1 и метода №2, полезные для широкого круга инженеров выводы можно было бы делать, если бы ваши рутины были хорошо оптимизированы или использовались известные библиотеки. А так можно легко получиться, что когда вы соптимизируете обе реализации, то результаты поменяются. На хабре есть например отличная статья про то, как умножать матрицы на CPU и что реализации одной и той же математической формулы может различаться по производительности в 1000 раз https://habr.com/ru/articles/359272/
На практике если вы хотите обращать матрицу с помощью LU декомпозиции (или какой-либо другой декомпозиции), то в большинстве случаев нет смысла вычислять обратную матрицу в явной форме, вместо этого вы храните матрицы декомпозиции и используете backward/forward propagation вместо умножения. Для LU (или LDU) декомпозиции при этом всю декомпозицию можно уместить в одной матрице, причем это можно сделать без дополнительной памяти если исходная матрица не нужна, соответствующий код есть на википедии https://en.wikipedia.org/wiki/LU_decomposition#C_code_example
КДПВ -- "картинка для привлечения внимания", т.е. титульная. Статья (и пакет qr-verbose) не про то, чтобы генерировать QR коды, а про то помочь разобраться как они устроены, основной посыл, что данные в нижнем коде уложены уже не так просто, как в верхнем, в других статьях-туториалах на хабре вы такого не найдёте (смотрите самую последнюю картинку в статье). В любом случае, спасибо, что проверили!
По поводу сканируемости: оба сканируются с андроида -- да, так и должно быть. По поводу сбербанка, сам им не пользуюсь, но судя по тому, что вы написали, это видимо сканнер платежа, полагаю что он ожидает какой-то идентификатор платежа, а не просто какую-то произвольную информацию. Думаю, что в Озоне тоже самое
Текст и код усеяны юникодом, который для меня в большинстве случаев признак нейрообработки (и мне кажется не только для меня). Готов поверить, что вы это делаете сами -- в этом случае снимаю шляпу! Если же это всё-таки обработка LLM, то ... просто напишите что и где используете, люди поймут. Мне вот тоже иногда нейрослоп приписывают, думаю перестать тратить время на ручную замену "--" -> "—"
Отличная статья, определенно в закреп! Некоторые отдельные тезисы хотелось бы обсудить
Профилируйте Release билд с debug symbols (-O2 -g), не Debug!
Вопрос, насколько отличается -O2 и -O3? По моему опыту например SIMD clang/gcc поагрессивней в SIMD оптимизациях при -O3, но реально я не никогда особо не замерял, так как для критической части кода SIMDы писал вручную.
1. Меньше кода = быстрее
Категорически не согласен, причем вы сами приводите пример #10 когда это не так -- как-будто хочется уточнения. Ну и касательно примера 10 тоже хочется отметить, что это должно сворачиваться в SIMD.
Деление - дорого
Бессмертная классик, я бы всё-таки дополнил, что деление на константу сильно дешевле деления на переменную.
Ну и отдельно хотелось бы отметить что у вас в кучу смешаны оптимизации разных типов, хотел бы от вас комментарий по опыту. Лично я при оптимизации стараюсь придерживаться приоритета кэш промахи -> ветвление -> арифметика, сам не до конца уверен что это универсальный подход. А какого подхода придерживаетесь вы?
Хмм, я мне говорили, что он это делает, потому что первые релизы плавили процессор.
Да я вроде этому и посвятил пол статьи. Но всё-таки это не всегда так и надо отслеживать когда I/O bound а когда CPU. AoS vs SoA это частные случае data oriented design, минимизация обращений к памяти через дизайн структуры часто очень не простая задача
Очень сильно не согласен. Во-первых, SSE, AVX2 и AVX512 различаются не только длиной регистра, но и доступными инструкциями (вики и список интринсиков). Во-вторых, в зависимости от задачи ботлнек может быть по памяти, а может и по вычислениям, в последнем случае имеет значение сколько и каких SIMD юнитов имеет процессор. У меня есть пример где ботлнек по арифметике и как раз использование GFNI из AVX-512 ускоряет в два раза универсальный алгоритм на AVX2
https://github.com/Malkovsky/galois?tab=readme-ov-file#vector-operations
(понятно, что оба варианта еще можно соптимизировать и разница возможно будет меньше, но суть от этого не меняется)
"Если можешь не писать -- не пиши" Л. Н. Толстой.
Почему такая мелочь как "засмеют и фамилию не спросят" вас останавливает?
не совсем понял о чем речь
Почему ожидали 10..20?
Как-будто вы описываете общую проблему валидности памяти кэш систем с разделенными L1/L2. Отсюда кстати и false sharing вырастает
Спецификация at, [] есть в стандарте, в статье есть ссылка на недавнее выступление с cppcon про матричное умножение, ну или вот есть статья на хабре.
Ну, чем богаты.
Неправильно вы в гиперпространство входите! Правильно вот так:
Мне кажется, что посыл как раз в том, что сейчас мы можем посмотреть на все это безобразие и осознать, что многого из этого можно было избежать. Мы видим "прекрасные" наглядные примеры того, к чему приводят кривоватости в фундаменте и как сложно его потом менять. Понятно, что ничего из перечисленного в баше не изменится, но смотря на это можно хотя бы не допускать подобного для новых технологий
Что это значит?
Если честно, выглядит так, как будто пример взят не из практики, а придуман. Про то, что пройтись по списку дольше, чем по массиву из-за кэш промахов да, понятно. Как это связано с исходным тезисом про хеш-таблицы и бинарный поиск? Может пример какой-нибудь? Полагаю, что не будет, потому что как раз на практике у бинарного бинарного поиска хуже паттерн обращений к памяти, чем у хеш-таблицы.
Если нужен реальный пример грамотной работы с кэшем -- замена бинарного дерева поиска на B-дерево, в котором размер узла может быть выставлен в соответствие размеру кэш линии.
Вот если бы он просто быстро рендерил латех, то я скорее всего сидел бы на нём
Еще такой глобальный вопрос: из статьи кажется, что вы хотите учебник и в печатном, и в электронном варианте. Многие вспомогательные штуки в печатном варианте невозможны, что делает сложным иметь один вариант для обоих случаев. Если все-таки предполагается электронный вариант, разве нет каких-нибудь хороших альтернатив latex? Я лично смотрю в сторону jupyter book и подобного, сам использую quarto, по сути они все представлют собой jupyter страницы в разных вариациях, преимущество которых перед техом в том, что большую часть текста можно верстать в markdown, тех поддерживается на достаточном уровне чтобы сверстать IEEE статью и при этом есть возможность исполняемые вставлять фрагменты кода и компилировать не только в пдф.
Отдельно отмечу, что лично я latex перестал работать c чистым latex в основном из-за отсутствия адекватного UX, например в overleaf я не вижу визуально изменения мгновенно, а в MD вижу. Тут еще стоит отметить typst, но с ним я почти не знаком.
Есть предзаказ?
Мне кажется, что это статья гораздо лучше большинства нейрослопа, которым сейчас переполнен Хабр и не только. Несмотря на это не могу не согласиться с соседними комментариями о низком уровне материала, от себя добавлю про техническую часть, касающуюся математических вычислений:
Вы сравниваете свои реализацию метода №1 и метода №2, полезные для широкого круга инженеров выводы можно было бы делать, если бы ваши рутины были хорошо оптимизированы или использовались известные библиотеки. А так можно легко получиться, что когда вы соптимизируете обе реализации, то результаты поменяются. На хабре есть например отличная статья про то, как умножать матрицы на CPU и что реализации одной и той же математической формулы может различаться по производительности в 1000 раз https://habr.com/ru/articles/359272/
На практике если вы хотите обращать матрицу с помощью LU декомпозиции (или какой-либо другой декомпозиции), то в большинстве случаев нет смысла вычислять обратную матрицу в явной форме, вместо этого вы храните матрицы декомпозиции и используете backward/forward propagation вместо умножения. Для LU (или LDU) декомпозиции при этом всю декомпозицию можно уместить в одной матрице, причем это можно сделать без дополнительной памяти если исходная матрица не нужна, соответствующий код есть на википедии https://en.wikipedia.org/wiki/LU_decomposition#C_code_example
30% кода можно закрыть на любой версии при выставленном уровне коррекции ошибок H и в статье об этом написано.
КДПВ -- "картинка для привлечения внимания", т.е. титульная. Статья (и пакет
qr-verbose) не про то, чтобы генерировать QR коды, а про то помочь разобраться как они устроены, основной посыл, что данные в нижнем коде уложены уже не так просто, как в верхнем, в других статьях-туториалах на хабре вы такого не найдёте (смотрите самую последнюю картинку в статье). В любом случае, спасибо, что проверили!По поводу сканируемости: оба сканируются с андроида -- да, так и должно быть. По поводу сбербанка, сам им не пользуюсь, но судя по тому, что вы написали, это видимо сканнер платежа, полагаю что он ожидает какой-то идентификатор платежа, а не просто какую-то произвольную информацию. Думаю, что в Озоне тоже самое
https://yandex.ru/video/preview/3518178718487329809
https://habr.com/ru/articles/950774/
Да, а еще можно греческий алфавит, значок кубического корня и прочие прелести, но нет, спасибо, я пожалуй всё-таки лучше в
Текст и код усеяны юникодом, который для меня в большинстве случаев признак нейрообработки (и мне кажется не только для меня). Готов поверить, что вы это делаете сами -- в этом случае снимаю шляпу! Если же это всё-таки обработка LLM, то ... просто напишите что и где используете, люди поймут. Мне вот тоже иногда нейрослоп приписывают, думаю перестать тратить время на ручную замену "--" -> "—"
Отличная статья, определенно в закреп! Некоторые отдельные тезисы хотелось бы обсудить
Вопрос, насколько отличается -O2 и -O3? По моему опыту например SIMD clang/gcc поагрессивней в SIMD оптимизациях при -O3, но реально я не никогда особо не замерял, так как для критической части кода SIMDы писал вручную.
Категорически не согласен, причем вы сами приводите пример #10 когда это не так -- как-будто хочется уточнения. Ну и касательно примера 10 тоже хочется отметить, что это должно сворачиваться в SIMD.
Бессмертная классик, я бы всё-таки дополнил, что деление на константу сильно дешевле деления на переменную.
Ну и отдельно хотелось бы отметить что у вас в кучу смешаны оптимизации разных типов, хотел бы от вас комментарий по опыту. Лично я при оптимизации стараюсь придерживаться приоритета кэш промахи -> ветвление -> арифметика, сам не до конца уверен что это универсальный подход. А какого подхода придерживаетесь вы?