LINUX.ORG.RU

Кодим на ассемблере в рождество

 


1

2

С Рождеством ЛОРчик!

Что мы делаем в Рождество? Кодим на ассемблере конечно же!

В одном из программистких чатиков была предложена задача по удалению пробелов из строки. Понятно, что во многих языках для этого есть библиотечные функции. Однако здесь же предлагалось подумать над своей реализацией.

Я сначала удивился простоте задачи, минут за 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

★★★★★
Ответ на: комментарий от MOPKOBKA
#include <stdio.h>
#include <string.h>

static void remove_spaces(char *s, char *out)
{
    char *ptr = s;
    char *out_ptr = out;

    while (*ptr != '\0')
    {
        if (*ptr != ' ')
        {
            *out_ptr = *ptr;
            out_ptr++;
        }
        ptr++;
    }
    *out_ptr = '\0';
}

int main() 
{
    char buf[256];
    char *str = "String spaces remover";

    printf("%s\n", str);
    remove_spaces(str, buf);
    printf("%s\n", buf);

    return 0;
}


hibou ★★★★★
() автор топика
Ответ на: комментарий от hibou

Посмотрел твой код на асме, со счетчиком не честно %)

void delspace(const char *in, char *out) {
    for(;*in;in++) if(*in != ' ') *out++ = *in;
    *out = 0;
}
delspace:                               # @delspace
.LBB0_1:                                # =>This Inner Loop Header: Depth=1
        mov     al, byte ptr [rdi]
        cmp     al, 32
        je      .LBB0_4
        test    al, al
        je      .LBB0_5
        mov     byte ptr [rsi], al
        inc     rsi
.LBB0_4:                                #   in Loop: Header=BB0_1 Depth=1
        inc     rdi
        jmp     .LBB0_1
.LBB0_5:
        mov     byte ptr [rsi], 0
        ret

MOPKOBKA ★★★★★
()
Ответ на: комментарий от Psilocybe

Все варианты компилятся в одинаковый асм-код при -O2 (и выше). При -O1 тоже, но другой по сравнению с -O2

anonymous
()
Ответ на: комментарий от Psilocybe

Тем временем этот вариант «в лоб» самый быстрый. Быстрее в 1.3 раза «табличного», который не записывает 0 в конце и с сравнением в цикле.

anonymous
()
Вы не можете добавлять комментарии в эту тему. Тема перемещена в архив.