How to become an author
Search
Write a publication
Pull to refresh

Comments 33

Два фразы из всей статьи, который сразу показывают, о чём идёт речь:

Оригинальный код использовал высокооптимизированные ассемблерные инкантации

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

То есть вставки на ассемблере не то, что никто не попрофайлил — никто даже не заглянул в тот код, который генерирует компилятор на самом деле! О каких «высокооптимизированных ассемблерные инкантациях» может идти речь?

Вместо того, чтобы сделать несколько простых ассемблерных вставок, которые делают то, что «руками» из-за ограничений языка сделать нельзя порождена здоровенная простыня… и никто даже не удосужился посмотреть — во что она выливается после компиляции… Типичный карго-культ: ассмеблер == очень-очень быстро, думать не надо, главное — что ассемблер…

А потом делается «открытие»: надо же — и на ассемблере можно написать плохо и медленно! Это таки так… но причём тут rust???
Total votes 23: ↑14 and ↓9+5
Представьте что будет, когда они узнают что почти как 30 лет сопроцессор у всех из коробки есть, и 128 битную арифметику давно подвезли.
Total votes 13: ↑7 and ↓6+1

Расскажите поподробнее пожалуйста про 128-битную арифметику на x86

Total votes 4: ↑4 and ↓0+4
Причём тут сопроцессор?

128 битную арифметику давно подвезли.

Кому подвезли?
Total votes 2: ↑2 and ↓0+2
SSE — расширение команд сопроцессора? Так вот в SSE2 (Pentium 4) есть целочисленная SIMD арифметика, да не совсем 128, а 2x64, но это лучше чем считать на CPU.
Далее, не трогал, но знаю что есть AVX, там как раз расширение до 128 бит, 2011 год, не сказать что что то супер новое и редкое.
Total votes 6: ↑1 and ↓5-4
Какое имеет отношение SIMD к 128-битной/256-битной арифметике? Вот прямо из названия «одиночный поток команд, множественный поток данных» очевидно же, что ни о какой 128-битной/256-битной арифметике там речь не идёт, всё сводится к независимым наборами чисел! И даже понятно почему: чем более длинный у вас сумматор или мультипликатор… тем сложнее заставить его работать на высокой частоте! Потому ничего похожего на то, что требуется для обсуждаемой в статье задачи в SSE/AVX нет и быть не может. Даже всякие SSSE3 и SSE4 с их «горизонтальными» сложениями/умножениями базовый принцип «сумматоры и мультипликаторы должны быть короткими» блюдут строго… против физики не попрёшь, однако.

P.S. Тем грустные видеть кучу плюсов, которые набрал ваш комментарий… Когда-то на Хабре собиралась публика, которая подобных элементарных ошибок не допускала… Но чем дальше в лес, тем ближе уровень фишек.нет или дёрти.ру… грустно…
Total votes 7: ↑6 and ↓1+5
SIMD дает нам возможность производить некоторые операции (сложение/умножение) сразу над несколькими парами операндов. И да, есть досадное ограничение, большинство этих операции carry-less, старшую часть результата мы теряем. Но мы можем делать вычисления над числами разрядностью меньшей разрядности регистров (например для сложения/вычитания 63 бита вместо 64), тогда после операции нам надо будет довычислять эти переносы. С умножением сложнее, но принцип тот же, понижаем разрядность что бы не потерять перенос и используем на свой вкус алгоритм Штрассена или Фюрера, которое хорошо ложатся ни SIMD. Да это не прям готовая реализация в виде одной команды add/mul, но SSE/AVX дают сильное ускорение если подумать.
Да, моя ошибка выше что арифметика не 128 битная, а скажем так над 128 битами одновременно, а то и больше, давно не использовал ассемблер да и особенности технологий подзабыл за ненадобностью в повседневной работе.
Total votes 2: ↑1 and ↓10
Какое отношение алгоритм Штрассена имеет к длинной арифметике?
Total votes 1: ↑0 and ↓1-1
Прям как на экзамене )) Ok, алгоритм Шёнхаге-Штрассена
Total votes 1: ↑1 and ↓0+1
Но мы можем делать вычисления над числами разрядностью меньшей разрядности регистров (например для сложения/вычитания 63 бита вместо 64), тогда после операции нам надо будет довычислять эти переносы.
Как вы это себе представляете? В SIMD не операций для работы с 63-разрядными числами. Либо 64бита, либо 32. Если вы начинаете работать с 32 битами, то вы получаете вдвое больше операций и, соответсвенно смысла в SSE нет никакого (мы будем вместо пару 64битных чисел складывать две пары 32-битных, что явно никакого ускорения не даст). AVX вроде как может, в теории, дать какое-то ускорение, так как можно складывать 4 32-битных числа одновременно (получая 4 64-битных числа с точки зрения процессора, а практически — 33битных), но к этому добавятся инструкции перемешивания, и в результате, скорее всего, вычисления будут происходить дольше.

С умножением сложнее, но принцип тот же, понижаем разрядность что бы не потерять перенос и используем на свой вкус алгоритм Штрассена или Фюрера, которое хорошо ложатся ни SIMD.
Плохо они ложатся на SIMD, очень плохо. Дело в том, что, как я уже писал, мультипликатора 64бит на 64бита в 128бит в SIMD нету, всё что есть — это «обрезанные» мультипликаторы 32бит на 32бита в 64бит. Дальше — у нас получается в 4 раза больше операций, что, опять-таки, немедленно делает SSE бессмысленным, а AVX — почти бессмысленным (вместо одного умножения 64бит на 64бита в 128бит мы вроде как могли бы использовать 4 умножения 32бит на 32бита в 64бит — но у нас появлятся дополнительные инструкции для «разреживания» и прочего).

Да это не прям готовая реализация в виде одной команды add/mul, но SSE/AVX дают сильное ускорение если подумать.
Не в случае с арифметикой длинных чисел. Теориетически разве что AVX512 мог бы дать ускорение, но во-первых он мало где есть, а во-вторых — это использование снижает частоту процессора, так что не факт что в результате будет выигрыш.

Да, моя ошибка выше что арифметика не 128 битная, а скажем так над 128 битами одновременно, а то и больше, давно не использовал ассемблер да и особенности технологий подзабыл за ненадобностью в повседневной работе.
Если вы «подзабыли особенности технологий за ненадобностью», то откуда такая уверенность, что они, в данном конкретном случае, вообще дадут выигрыш?
Total votes 2: ↑1 and ↓10
Как вы это себе представляете? В SIMD не операций для работы с 63-разрядными числами.

Разбиваете 128 бит число на четыре 32битных (или 8x16бит, тогда далее делим разрядность на два). Расширяете их до 64 бит старшими нулевыми битами. Далее при умножении этих 64битных чисел, результат тоже будет не более 64 бит, и отсечение старшей части результат вам уже не страшно. Ну и с этим подходом используете упомянутые выше алгоритмы.
Total votes 1: ↑0 and ↓1-1
Вы вообще хоть иногда читаете комментарии, на который отвечаете? Там, вообще-то, описан и ваш «гениальнй» алгоритм и объяснено, почему толку от него — никакого (за исключением обфускации кода, но для этого есть много других способов).

Если вы не знаете как работает та или иная технология, то не стоит их тащить в дискуссию. Ну пожалйста. Хабр был одним из немногих мест в сети, где собеседники умели-таки думать и считать. Не нужно его в фишки.нет превращать…
Total votes 2: ↑1 and ↓10
Почему вы считаете, что хитрое 32х-битное умножение будет работать быстрее чем обычное 64х-битное?
This comment wasn’t rated yet0
На всякий случай напишу подробнее имею в виду. Вот у нас есть два 128-битных числа, и их надо перемножить.

Если использовать 64х-битное умножение, то методом «в лоб» будет достаточно 4х умножений и 4х сложений. Методом Карацубы число умножений удастся уменьшить до 3х, но число сложений вырастет и появятся логические операции, так что не рискну оценивать что из этого лучше.

Вы же предлагаете сделать два FFT-преобразования и параллельное умножение на SIMD-инструкциях. Будет ли это быстрее чем 4 обычных умножения и 4 сложения?
Total votes 1: ↑1 and ↓0+1
Почему вы считаете
С чего вы решили, что Ghost_nsk вообще хоть чего-то считал? Если бы он считал, то сразу понял бы, что SSE — будет только замедлять, так как там только два умножителя 32бит на 32бита в 64бит, что однозначно медленнее, чем один умножитель 64бита на 64бита в 128бит.

В случае с AVX'ом 32бит на 32бита в 64бит умножителей у нас уже 4 штуки, но что-то выиграть мы сможем только если использовать что-то типа Карацубы — а тут мы упрёмся в сложения (так как аналога скалярного ADC в AVX нету).

То есть если где-то и можно получить выигрыш — то лишь начиная с AVX512. Что, в принципе, не так плохо согласуется с тем, что нам нужна 256-битная арифметика (как раз после расширения вдвое всё влазит в один регистр). Но тут надо считать особенно тщательно, так как использование AVX512 автоматически понижает частоту ядра, так что вопрос — будет ли в итоге выигрыш… он далеко неочевиден даже для AVX512.

Но посмотрите с чего мы начали:
Представьте что будет, когда они узнают что почти как 30 лет сопроцессор у всех из коробки есть, и 128 битную арифметику давно подвезли.

Это явно было замечание не про AVX512, появившийся чуть больше года назад в Skylake-SP (то есть только на серверах), а о чём-то другом.
Total votes 1: ↑1 and ↓0+1
Я предлагаю взглянуть чуть с другой стороны.

Был код на языке высокого уровня. Прошлись профайлером, нашли узкое место: широкая арифметика. Решили переписать с использованием ассемблерных вставок. Человек переписал, получили значимое ускорение. Обрадовались, выкатили.
Компилятор языка высокого уровня обновился, появилась поддержка 128-битной арифметики. Решили проверить, на сколько её использование оправдано. Выяснили, что новая реализация быстрее той, что была с вставками. Обрадовались, выкатили.

Нашли проблему, замерили, нашли решение, замерили. Решение устроило — пользуемся и радуемся.
Изменились внешние обстоятельства, касающиеся данной задачи. Проверили новое решение, которое проще в поддержке и при этом оказалось быстрее использующегося. Задача решена.

Выводы:
0) Люди не идеальны. Что-то не знают, о чем-то забывают.
1) Во многих случаях компиляторы способны генерировать весьма хороший код.
2) Хорошо, когда в языке высокого уровня дают спуститься на низкий.
3) И да, Rust тут весьма вторичен. Хотя родная поддержка 128-битных целых мне что-то весьма не часто попадалась.
Total votes 16: ↑16 and ↓0+16

Вот дельное замечание. А позиция некоторых, дескать "автор сам дурак и нечего тут рассуждать" — неконструктивна.

Total votes 4: ↑3 and ↓1+2

Это все понятно. Но я бы не стал написанный на шаге "переписал, получили значимое ускорение" код называть "высокооптимизированным". Прилагательное "высокооптимизированный" все-таки подразумевает кучу итераций оптимизации с изучением кода на всех уровнях, чего тут сделано не было.

Total votes 4: ↑3 and ↓1+2
3) И да, Rust тут весьма вторичен. Хотя родная поддержка 128-битных целых мне что-то весьма не часто попадалась.
В gcc (и, соответственно, в clang'е) оно уже давно есть.

Или вы думали их кто-то в LLVM специально для rust'а добавил? И оптимизации сделал?

Прошлись профайлером, нашли узкое место: широкая арифметика. Решили переписать с использованием ассемблерных вставок. Человек переписал, получили значимое ускорение. Обрадовались, выкатили.
И даже не попробовали взглянуть в сгенерированный код?

Понимаете, я ж не против. «Метод тяп-ляп и в подакшн» — очень часть самый выгодный. Но когда мне заливают в уши про «highly-optimised assembly incantations from our resident cycle wizard» (переводчик перевёл это просто как «высокооптимизированные ассемблерные инкантации», чтобы не так пафосно выглядело), а потом выясняется, что его вкрутили так, что все данные через память гоняются… это даже не смешно.
Total votes 2: ↑1 and ↓10

Про реализации в gcc и llvm знаю. Я про язык. Хотя тут Rust'у с его единственной, по сути, реализацией просто говорить.


Про пафос согласен, тут они сильно перегнули и, я бы даже сказал, напросились.

This comment wasn’t rated yet0
я подумал в новом расте появилась какая-то могучая оптимизация, ан нет, просто поддержка старого доброго нового типа…
This comment wasn’t rated yet0
UFO just landed and posted this here
лицензия GPL подходит далеко не всем
Total votes 3: ↑3 and ↓0+3
UFO just landed and posted this here

Все-таки LGPL так себе сочетается со статической линковкой, которую очень любит раст. Всем просить исключение такое себе занятие.


Но при этом для желающих есть несколько готовых пакетов с привязками


This comment wasn’t rated yet0

Если нельзя использовать динамическую линковку, то можно задействовать dlopen().

This comment wasn’t rated yet0
она офигенно медленная по сравнению с кастомными решениями
Total votes 1: ↑1 and ↓0+1
Надо было еще ссылки на скомпилированный результат на play.rust-lang.org оставить. Там и IR и ассемблер можно посмотреть
Total votes 1: ↑1 and ↓0+1
В С++ 20 может быть приедут шаблонные wide_integers произвольной длины. Очень жаль, что в Rust все еще не приехали дженерики с аргументами-не типами, и аналогичную штуку не сделать :(
Total votes 2: ↑1 and ↓10
Да, я знаю; примерно раз в полгода открываю этот тред.
Грустно, что очень многих вещей, которые уже есть в С++ (или в D), ждать еще очень очень долго. Многих, подозреваю, вообще можно не дождаться, типа static if, поскольку их изначально не закладывали.
Ле вздох.
This comment wasn’t rated yet0
Sign up to leave a comment.

Articles

Show the best of all time
Change theme settings

Your account

Sections

Information

Services

Support
© 2006–2024, Habr