Комментарии 19
Даже, казалось бы, чтения из участков памяти для sse — операция более медленная, чем работа с регистрами, а получается всё равно быстрее.
У Зубкова в культовой книге «Ассемблер для DOS, Windows и UNIX» был еще такой вариант, с командой das:
Известный пример необычного использования этой команды — самый компактный вариант преобразования шестнадцатеричной цифры в ASCII-код соответствующего символа (более длинный и очевидный вариант этого преобразования рассматривался в описании команды XLAT):
cmp al,10
sbb al,96h
das
А не могли бы вы сравнить быстродействие ваших вариантов с табличным поиском?
А то 20 SSE-команд возможно будут медленнее, чем 2 lookup-а таблицы на 65536 значений, а может, даже, и чем 4 lookup-а в таблице на 256 значений.
Также не увидел других вариантов табличных поисков (особенно параллелизуемых).
Если уж сравнивать, то все возможные варианты, согласны?
А то 20 SSE-команд возможно будут медленнее, чем 2 lookup-а таблицы на 65536 значений, а может, даже, и чем 4 lookup-а в таблице на 256 значений.
Также не увидел других вариантов табличных поисков (особенно параллелизуемых).
Если уж сравнивать, то все возможные варианты, согласны?
Lookup-ы должны быть быстрее. Если не считать время на создание таблицы, особенно большой. И время на промахи кэша, что очень дорого. Да и тратить более 128К байт памяти на такую задачу, на мой взгляд, несколько расточительно.
Все варианты еще придумать нужно. :)
Все варианты еще придумать нужно. :)
Может, всё-таки попробуете сравнить хотя бы с lookup-ами? Например, на 128-битных числах, если не уверены в превосходстве своего последнего решения на 64-битных.
А то мне тоже примеры из жизни типа комментария ниже ( habrahabr.ru/post/239375/#comment_8061201 ) вспоминаются…
Особенно один случай, как у моего товарища С-шный компилятор сгенерировал более эффективный код, чем он сам написал после всех оптимизаций и долгого изучения мануалов по ассемблеру: на одну инструкцию короче и примерно на 20% быстрее.
Какой смысл рассматривать абстрактное новое решение в вакууме? Нужно попробовать найти наиболее эффективное, раз уж вы упоминаете в посте о скорости, а иначе можно и на первом варианте остановиться.
А у вас в вариантах с циклами возможны промахи предсказания ветвлений, а в остальных — сложности конвейеризации. Так что всё тоже не так однозначно.
Таблица большая, но если операция делается один раз, то оптимизировать её не имеет смысла, значит, вы будете гонять её очень много раз, логично?
В общем, прошу вас написать новый пост с альтернативными вариантами, если вы не возражаете :)
А то мне тоже примеры из жизни типа комментария ниже ( habrahabr.ru/post/239375/#comment_8061201 ) вспоминаются…
Особенно один случай, как у моего товарища С-шный компилятор сгенерировал более эффективный код, чем он сам написал после всех оптимизаций и долгого изучения мануалов по ассемблеру: на одну инструкцию короче и примерно на 20% быстрее.
Какой смысл рассматривать абстрактное новое решение в вакууме? Нужно попробовать найти наиболее эффективное, раз уж вы упоминаете в посте о скорости, а иначе можно и на первом варианте остановиться.
И время на промахи кэша, что очень дорого.
А у вас в вариантах с циклами возможны промахи предсказания ветвлений, а в остальных — сложности конвейеризации. Так что всё тоже не так однозначно.
Таблица большая, но если операция делается один раз, то оптимизировать её не имеет смысла, значит, вы будете гонять её очень много раз, логично?
В общем, прошу вас написать новый пост с альтернативными вариантами, если вы не возражаете :)
У меня сложилось впечатление, что мы друг друга недопонимаем.
Хочу уточнить, что Вы имеете ввиду под понятием lookup? Правильно ли я догадался.
Насколько я понимаю, компилятор не улавливает нюансов пожелания программиста. Да и большинству просто не приходит в голову, что нужно изобретать велосипед для какого-то частного случая. «Ведь компилятор прекрасно сгенерирует более эффективный код.» А если мне нужно отдельное решение для вывода исключительно шестнадцатеричных чисел? Интересно, что даст компилятор.
Эээ… Собственно я хотел показать как раз неэффективность первых решений на старых технологиях, против новых способов решения той же задачи на SSE. Даже, так сказать, показать развитие шахматной идеи от старых добрых восьмибитных версий до современных SIMD заморочек.
По табличному варианту немного подумал. Можно обрабатывать по байту (2 знака) за раз. Потребуется табличка размером 256 16-ти битных слов. Обрабатывать по два байта тоже можно, но табличка нужна будет уже 65536 четырехбайтных слов, что громоздко. Заполнять ее вручную я рехнусь, а писать код для этого — лень.
Навскидку, 512 байтная таблица даст выигрыш максимум раза в 3, по сравнению с xlatb. Табличный код, безусловно, компактен и быстр, параллельное исполнение на разных ядрах тоже возможно. А вот внутренний параллелизм, концепция SIMD в нем слаба, в отличие от SSE.
Хочу уточнить, что Вы имеете ввиду под понятием lookup? Правильно ли я догадался.
Особенно один случай, как у моего товарища С-шный компилятор сгенерировал более эффективный код, чем он сам написал после всех оптимизаций и долгого изучения мануалов по ассемблеру: на одну инструкцию короче и примерно на 20% быстрее.
Насколько я понимаю, компилятор не улавливает нюансов пожелания программиста. Да и большинству просто не приходит в голову, что нужно изобретать велосипед для какого-то частного случая. «Ведь компилятор прекрасно сгенерирует более эффективный код.» А если мне нужно отдельное решение для вывода исключительно шестнадцатеричных чисел? Интересно, что даст компилятор.
А у вас в вариантах с циклами возможны промахи предсказания ветвлений, а в остальных — сложности конвейеризации. Так что всё тоже не так однозначно.
Эээ… Собственно я хотел показать как раз неэффективность первых решений на старых технологиях, против новых способов решения той же задачи на SSE. Даже, так сказать, показать развитие шахматной идеи от старых добрых восьмибитных версий до современных SIMD заморочек.
Таблица большая, но если операция делается один раз, то оптимизировать её не имеет смысла, значит, вы будете гонять её очень много раз, логично?
По табличному варианту немного подумал. Можно обрабатывать по байту (2 знака) за раз. Потребуется табличка размером 256 16-ти битных слов. Обрабатывать по два байта тоже можно, но табличка нужна будет уже 65536 четырехбайтных слов, что громоздко. Заполнять ее вручную я рехнусь, а писать код для этого — лень.
Навскидку, 512 байтная таблица даст выигрыш максимум раза в 3, по сравнению с xlatb. Табличный код, безусловно, компактен и быстр, параллельное исполнение на разных ядрах тоже возможно. А вот внутренний параллелизм, концепция SIMD в нем слаба, в отличие от SSE.
Хм, странно. Берёте блок памяти, берёте ваш любой другой алгоритм, пробегаетесь по таблице — получаете эту самую таблицу в заполненном виде.
Или вам в виде констант её обязательно нужно генерировать?
Вообще, в своё время для синусов таблицы же делали — вообще было нормальной практикой.
>Насколько я понимаю, компилятор не улавливает нюансов пожелания программиста.
Да, но у него есть список оптимизаций, выстраданных программистами, часть из которых умнее, чем мы с вами :)
И loop unrolling, и ускорение доступа к памяти, и оптимизация размещения в регистрах, и некоторые частные случаи умножения на константу.
В общем, мне кажется, нужно попробовать. Если, говорите, в 3 раза ускорение можно получить, то на старых компьютерах типа Amd C-60 это решение всех заборет, если я правильно понимаю вашу табличку.
Или вам в виде констант её обязательно нужно генерировать?
Вообще, в своё время для синусов таблицы же делали — вообще было нормальной практикой.
>Насколько я понимаю, компилятор не улавливает нюансов пожелания программиста.
Да, но у него есть список оптимизаций, выстраданных программистами, часть из которых умнее, чем мы с вами :)
И loop unrolling, и ускорение доступа к памяти, и оптимизация размещения в регистрах, и некоторые частные случаи умножения на константу.
В общем, мне кажется, нужно попробовать. Если, говорите, в 3 раза ускорение можно получить, то на старых компьютерах типа Amd C-60 это решение всех заборет, если я правильно понимаю вашу табличку.
Надеюсь вечером будет время, попробую.
У меня сильное подозрение что у АМД какие-то неправильные, нелинейные попугаи. По-хорошему, измерять надо бы реальное время, а с этим свои сложности.
Кстати, с разворачиванием циклов получается не все так однозначно. АМД явно как-то оптимизирует их выполнение
У меня сильное подозрение что у АМД какие-то неправильные, нелинейные попугаи. По-хорошему, измерять надо бы реальное время, а с этим свои сложности.
Кстати, с разворачиванием циклов получается не все так однозначно. АМД явно как-то оптимизирует их выполнение
byte lookup 128 bit
mov rsi, timep +15
mov rdi,msgh
mov rcx,16
mi8:
xor rax,rax
std
lodsb
mov rax,[rax*2+convertt]
cld
stosw
loop mi8
ret
convertt:
dw '00','01','02','03','04','05','06','07','08','09','0A','0B','0C','0D','0E','0f'
...
Итого: Интел — 1050, AMD — 450 в среднем. У Интела результат стабильный и процентов на 5 лучше чем у варианта xlatb 128 bit. У AMD результат очень сильно скачет. От 250 до 600.
Хорошая статья и очень хороший пример для демонстрации того, что стоит оптимизировать распараллеливанием с привязкой к «камню». Лет 15 назад искал такую же задачу. Остановился на игре Жизнь (Conway's Game of Life). Тогда в наличии был только MMX. Распараллеливанием удалось примерно в сто раз увеличить скорость для разрешения 320х200. Параллельно обрабатывалось по 16 клеток. Я был в восторге. Ассемблер лучший язык в мире! Для меня не было ничего интереснее оптимизации на машинном уровне. Спустя немного времени я случайно нашел бинарник который летал с не меньшей скоростью но уже на неограниченном поле. Причем автор ничего особо не оптимизировал, просто вместо думать как быстро просчитывать все поле, просчитывал только список живых клеток. Вот тут то мой мозг и взорвался. С тех пор я программирую на с++ и изучаю алгоритмы.
На Z80 в свое время была такая магия:
; вход — в A число от 0 до 15
ADD A,90h
DAA
ADC A,40h
DAA
; выход — в A код символов '0'-'9', 'A'-'F'
пожалуй, это единственное применение команды DAA за все время моей работы на ассемблере.
; вход — в A число от 0 до 15
ADD A,90h
DAA
ADC A,40h
DAA
; выход — в A код символов '0'-'9', 'A'-'F'
пожалуй, это единственное применение команды DAA за все время моей работы на ассемблере.
В играх (фирменных) DAA применялась для подсчёта очков. Они не хотели писать перевод из двоичной системы в десятичную, а вместо этого всё считали сразу в двоично-десятичной.
С переводом в десятичную систему с появлением сопроцессора стало все совсем просто. 18 знаков парой команд плюс код для распаковки упакованного двоично-десятичного числа.
Воистину, дедам ещё есть чему нас научить!
В самом деле, перевод из двоичной в десятичную систему — это весьма дорогая операция. И, если расчёт числа очков (или любой другой величины) по затратам процессорного времени сопоставим с преобразованием двоичного числа в десятичное — то тут сам доктор прописал использовать двоично-десятичное представление. Возьму на вооружение, спасибо!
В самом деле, перевод из двоичной в десятичную систему — это весьма дорогая операция. И, если расчёт числа очков (или любой другой величины) по затратам процессорного времени сопоставим с преобразованием двоичного числа в десятичное — то тут сам доктор прописал использовать двоично-десятичное представление. Возьму на вооружение, спасибо!
Другой вариант, с одним DAA (можно найти на Z80 bits):
or #f0; вместо маскирования разряда
daa
add a,#a0
adc a,#40
or #f0; вместо маскирования разряда
daa
add a,#a0
adc a,#40
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Публикации
Новые решения старой задачи