С Рождеством ЛОРчик!
Что мы делаем в Рождество? Кодим на ассемблере конечно же!
В одном из программистких чатиков была предложена задача по удалению пробелов из строки. Понятно, что во многих языках для этого есть библиотечные функции. Однако здесь же предлагалось подумать над своей реализацией.
Я сначала удивился простоте задачи, минут за 5 набросал решение на С++ с использованием remove_if(). Потом подумал, наверное это не совсем честно, ведь нужно самостоятельное решение, а remove_if() - это вариант для ленивых, уж очень напоминает решение с библиотечной функцией. И я переделал код на свой собственный цикл в С++ стиле, на итераторах.
Замерил быстродействие. Команда time выдавала стабильные 0,005 - 0,006 секунды.
Вроде бы и все, задача решена. Я немного отдохнул, сходил попил чаю. И тут меня осенило. А смогу ли я написать то же самое на чистом Си так, чтобы оно работало быстрее?
И я попробовал. Переписал решение на Си, с адресной арифметикой во все поля. Очень старался не делать ничего лишнего, только самое необходимое и все в одном цикле. Замерил быстродействие. Оно оказалось те же 0,005 секунды. Но 0,006 уже не появлялось никогда. Т.е. может быть мы немножко выиграли, какую-нибудь половину тысячной доли секунды.
Но! Я бы не стал писать пост ради этого. Как вы понимаете, потом меня понесло! :-)
Я попил еще чаю. Поел маминого супа. И решил написать все то же самое, только на ассемблере! Мне было интересно, смогу ли я переплюнуть результаты Си-шного кода.
Вот тут пришлось серьезно постараться. Кажется, это будет мое первое приложение на ассемблере под мак.
Сколько раз мое приложение падало, наверное не сосчитать. Я убил на него полдня! Сломал себе весь мозг. Едва не навернул всю систему, особенно пока искал нужный системный вызов. Но я, таки, справился.
Короче, идея, в общем-то, проста. У нас есть некая строка в секции данных приложения. Там же мы себе оставили буфер для будущей новой строки. Ну и переписываем в этот буфер по байтам старую строчку. Если нам встречается пробел, мы его не переписываем. Для этого в ассемблере есть специальные команды, lods и stos, которые сами увеличат и уменьшат нужные заначения в регистрах. Нам для них нужно только подготовить начальные данные. Командой cmp мы сравниваем байты. Командой je (jump if equivalent) прыгаем на нужную инструкцию по результату сравнения. Регистр r10 я использовал, чтобы сохранить длину нашей новой строки. Почему r10? Не знаю, вроде он был следующий по конвенции вызовов, остальные, предыдущие мы уже использовали.
Чтобы напечать строки, дергаем системный вызов write(). Здесь я тоже надеялся немного выиграть, за счет того, что не использую библиотечные функции, а напрямую прося операционную систему печтать в stdout. Так как операционка - macos, системные вызовы у нее оказались под другими номерами, не как в Linux. Пришлось изрядно постараться, чтобы найти наконец нужный. Хорошо хоть параметры передавались в тех же регистрах, что и в Linux. Видимо соблюдалась конвенция о системных вызовах.
Другой новостью оказалсь RIP-related адресация. Может быть я забыл, но это было несколько неожиданно. Когда последний рза писал на ассемблере для Linux, вроде не сталкивался с этим. В общем, теперь мы не можем просто передавать адрес объекта внутри бинарника куда-нибудь еще. Этот адрес нужно вычислять относительно RIP - register instruction pointer. По-идее, это хорошее нововведение, потому что объекты встроенные в бинарник более не зависят от адреса загрузки этого бинарника поскольку вычисляются из адреса текущей исполняемой инструкции.
Я был очень рад, когда моя штуковина заработала. С трепетом замеряю быстродействие….
Нет, те же 0,005 тысячных долей секунды. Я не смог переплюнуть в написании кода Си-шный компилятор. Иногда, в некоторых, очень редких замерах проскакивает отметка 0,004 секунды. С натяжкой можно предположить, что мы обошли на 0,001 тысяную доли компиляторный код. Но это настолько мало, что можно списать на погрешность измерений.
ЛОР, скажи, а был ли у меня шанс обогнать компилятор? Можно ли как-то улучшить код?
Вот мой код ниже. Только номер системного вызова write стоит маковский, при компиляции под линукс, нужно будет подставить линуксовый номер. В линукс он, вроде 1 (единица).
.bss
str_out:
.space 256
.global _main
.text
# rsi: msg, rdx: len
_print:
movq $0x2000004, %rax # system call write
movq $1, %rdi # id handler 1 is stdout
syscall
ret
# rsi: from, rdi: to, rcx: count
# r10: current index
_copy:
lodsb
cmpb $32, %al
je _cpe
stosb
inc %r10
_cpe:
loop _copy
ret
_main:
movq msg@GOTPCREL(%rip), %rsi # address of string to output
movq $msg_len, %rdx # number of bytes
call _print
movq msg@GOTPCREL(%rip), %rsi
movq str_out@GOTPCREL(%rip), %rdi
movq $msg_len, %rcx
xor %r10, %r10
call _copy
movq str_out@GOTPCREL(%rip), %rsi
movq %r10, %rdx # number of bytes
call _print
ret
.cstring
msg:
.ascii "String spaces remover\n"
msg_len = . - msg
Перемещено Zhbert из linux-org-ru
