quick_sort_asm.cpp

/*
    Быстрая сортировка:    на C++ и на ассемблере.
    Ассемблер:             masm.
    Синтаксис:             AT&T.

    Набор настроек и флагов компилятора:
        Version: TDM-GCC 4.9.2 32-bit Release
        Compile with the following bit width (-mx): 32bit
        Language standard (-std): ISO C++11

    В main создается массив из 10.000.000 случайных чисел в двух экземплярах.
    Засекается время работы сортировки алгоритмом на C++
    Засекается время работы сортировки ассемблерной вставкой
    Проверяется правильность: получен ли неубывающий порядок?

    Вывод (то, ради чего работа и делалась):
        Ассемблерная вставка работает в среднем в два раза быстрее аналога на C++.

    Если использовать оптимизацию -O3 high level'a по скорости, то необходимо закомментировать строку 49: "pop %ebp;".
    При оптимизации компилятор добавит ее за нас, следовательно, нам это делать не нужно.
*/

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <ctime>
using namespace std;

void quick_sort(int * first, int * last){
    int * f = first, * l = last;
    int mid = f[(l-f)/2];
    do {
        while ( *f < mid ) f++;
        while ( *l > mid ) l--;
        if ( f <= l ) {
            int temp = *f;
            *f = *l;
            *l = temp;
            f++;
            l--;
        }
    } while (f < l);
    if ( first < l ) quick_sort(first, l);
    if ( f < last )  quick_sort(f, last);
}

void quick_sort_asm(int * first, int * last){
    asm (
            "pop %ebp;" // Уничтожаем последствия от вызова void quick_sort_asm(int * first, int * last).
        "_quick_sort:;"
            // Сохраняем используемые регистры, смещаем указатель на стек:
            "push   %ebp; push   %edi; push   %esi; push   %ebx; sub    $0x1c,  %esp;"

            "mov    0x30(%esp),     %ebp;" // 48; ebp = first
            "mov    0x34(%esp),     %esi;" // 52; esi = last

            // eax = (l-f)/2
            "mov    %esi,           %eax;"
            "sub    %ebp,           %eax;"
            "sar    $0x2,           %eax;"
            "mov    %eax,           %edx;"
            "shr    $0x1f,          %edx;"
            "add    %edx,           %eax;"
            "sar    %eax;"

            "mov    (%ebp,%eax,4),  %ecx;"  //  mid = *(f + (l-f)/2)
            "mov    %esi,           %eax;"  //  l = last
            "mov    %ebp,           %ebx;"  //  f = first

            // цикл do {...} while (f < l)
            "_before_do:;"

                // цикл while ( *f < mid ) f++;
                "_left_while_condition:;"
                    "mov    (%ebx),     %edi;"
                    "cmp    %edi,       %ecx;"
                    "jle     _after_left_while;"
                "_left_while_body:;"
                    "add    $0x4,       %ebx;"  //  f++
                    "jmp    _left_while_condition;"
                "_after_left_while:;"

                // цикл while ( *l > mid ) l--;
                "_right_while_condition:;"
                    "mov    (%eax),     %edx;"
                    "cmp    %edx,       %ecx;"
                    "jge    _after_right_while;"
                "_right_while_body:;"
                    "sub    $0x4,       %eax;"  //  l--
                    "jmp    _right_while_condition;"
                "_after_right_while:;"

                "_before_swapping:;"
                    //  проверка условия if ( f <= l ):
                    "cmp    %eax,       %ebx;"
                    "ja     _after_swapping;"
                    //  обмен *f и *l:
                    "mov    %edx,       (%ebx);"
                    "mov    %edi,       (%eax);"
                    //  смещение f вправо на sizeof(int) = 4 бита:
                    "add    $0x4,       %ebx;"      //  f++
                    //  смещение l влево на sizeof(int) = 4 бита:
                    "sub    $0x4,       %eax;"      //  l--
                "_after_swapping:;"

                // Проверка условия цикла с постусловием do {...} while (f < l):
                "cmp    %eax,       %ebx;"
                "jb     _before_do;"
            "_after_do:;"

            // Левая рекурсивная ветвь:
            "_before_left_call:;"
                // Проверка условия if ( first < l ):
                "cmp    %eax,       %ebp;"
                "jae    _after_left_call;"
                // Размещение l на стеке:
                "mov    %eax,       0x4(%esp);"
                // Передача first перед l на стеке:
                "mov    %ebp,       (%esp);"
                // Вызов функции сортировки на отрезке [first, l]:
                "call   _quick_sort;"
            "_after_left_call:;"

            // Правая рекурсивная ветвь:
            "_before_right_call:;"
                // Проверка условия if ( f < last ):
                "cmp    %ebx,       %esi;"
                "jbe    _after_right_call;"
                // Размещение last на стеке:
                "mov    %esi,       0x4(%esp);"
                // Передача f перед last на стеке:
                "mov    %ebx,       (%esp);"
                // Вызов функции сортировки на отрезке [f, last]:
                "call   _quick_sort;"
            "_after_right_call:;"

        "_end:;"
        // Возвращаем указатель на стек в его исходное состояние и восстанавливаем значения используемых регистров:
            "add    $0x1c,  %esp; pop    %ebx; pop    %esi; pop    %edi; pop    %ebp;"
        "ret;"
    );
}

int main() {
//  Создаем массив:
    const int n = 10000000;
    int * a = new int[n];
    int * b = new int[n];
    for (int i = 0; i < n; i++)
        a[i] = b[i] = rand() % n;

    int t = clock();
    quick_sort(b, b+n-1);
    double time_sec = (clock() - t ) * 1.0 / CLOCKS_PER_SEC;
    printf("standart quick sort time: %0.3fs\n", time_sec);

//  Сортируем в порядке неубывания и засекаем время:
    t = clock();
    quick_sort_asm(a, a+n-1);
    time_sec = (clock() - t ) * 1.0 / CLOCKS_PER_SEC;
    printf("assembly quick sort time: %0.3fs\n", time_sec);

//  Проверяем на правильность:
    for (int i = 1; i < n; i++)
        if ( a[i-1] > a[i] )
            printf("ERROR: a[%d] > a[%d]\n", i-1, i);

    delete[] a;
    delete[] b;
    printf("Type something and press enter for exit...\n");
    char c; cin >> c;
    return 0;
}