VPF::Помогите упростить код - Форум программистов

ChihPih

Дата 10.1.2009, 23:05 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 532
Регистрация: 3.12.2006

Репутация: нет
Всего: 22

Привет всем.
Реализовал на асм алгоритм последовательной сортировки - получилось. Потом реализовал на Borland C++. Решил сравнить, что быстрее - мой код или сгенерированный код borland'овским компилятором. Оказалось, что мой медленее почти на 3 сек. Мерил, сортровкой массива из 100000 элементов целого типа.

Вот код на асм:

Код


void __stdcall SortAsm(int mas[], int count)
{
  asm {
    xor ecx, ecx                  // ecx - счетчик
    mov edx, dword ptr [mas]      // Получаем адрес начала mas
    jmp _sort
    _mod:                         // Нашли новый минимальный элемент (min = j)
        mov ebx, ecx
        jmp _sort_j_end
    _sort:                        // Начало сортировки
        push ecx                  // Теперь ecx - счетчик для цикла _sort_j
        mov ebx, ecx              // ebx - индекс минимального элемениа
    _sort_j:                      // Поиск минимального элемента
        mov eax, dword ptr [edx + 4*ebx]    // Получение mas[min]
        cmp eax, dword ptr [edx + 4*ecx]    // Сравниваем mas[min] с mas[j]
        jg _mod
    _sort_j_end:
        inc ecx
        cmp ecx, count
        jne _sort_j
    _sort_i_continue:             // Меняем местами элементы
        pop ecx                   // Восстанавливаем предыдущий индекс
        push dword ptr [edx + 4*ecx]        // Запоменаем mas[ecx]
        push dword ptr [edx + 4*ebx]        // Запоминаем mas[ebx]
        pop dword ptr [edx + 4*ecx]         // Извлекаем mas[ebx] из стека
        pop dword ptr [edx + 4*ebx]         // Извлекаем mas[eсx] из стека

        inc ecx
        cmp ecx, count
        jne _sort
    _quit:
  }
}

Вот код на C++:

Код


void __stdcall Sort(int mas[], int count)
{
  int min = 0, buf = 0;
  for (int i = 0; i < count; i++){
      min = i;
      for (int j = i; j < count; j++){
          if (mas[min] > mas[j]){ min = j; }
      }
      buf = mas[i];
      mas[i] = mas[min];
      mas[min] = buf;
  }
}

Подскажите, пожалуйста, как можно еще код на асме оптимизировать?

--------------------

www.info-x.org - информационный ресурс о ОС FreeBSD. Форум.

Mikl_

Дата 11.1.2009, 04:40 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 537
Регистрация: 9.11.2007

Репутация: 8
Всего: 14

Цитата(ChihPih)

Подскажите, пожалуйста, как можно еще код на асме оптимизировать?

пропусти Borland' овский код через дизассемблер и упрости его smile

ksili

Дата 11.1.2009, 06:53 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 2069
Регистрация: 3.11.2005
Где: Красноярск

Репутация: 1
Всего: 17

Что-то у тебя много условных переходов в ассемблерной проге, в то время как в сишной проге только один if.
Попробуй на асме чисто повторить сишную программу

Добавлено через 2 минуты и 27 секунд
А не, вроде с переходами все нормально

Добавлено через 9 минут и 24 секунды
Мож ещё edx использовать не под хранение ук-ля на массив, а для хранения минимального эл-та
Тогда

Код


    _sort_j:                      // Поиск минимального элемента
        mov eax, dword ptr [edx + 4*ebx]    // Получение mas[min]
        cmp eax, dword ptr [edx + 4*ecx]    // Сравниваем mas[min] с mas[j]
        jg _mod

упростится до

Код


    _sort_j:                      // Поиск минимального элемента
        cmp edx, mas[ecx]    // Сравниваем mas[min] с mas[j]
        jg _mod

Ну или как-то так

--------------------

Ничто так не развивает аналитическое мышление, как отладка сложной программы без возможности пошагового выполнения (с)

Mikl_

Дата 11.1.2009, 08:30 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 537
Регистрация: 9.11.2007

Репутация: 8
Всего: 14

ChihPih, а для чего оптимизировать алгоритм пузырьковой сортировки? Есть сортировки и более быстрые -- разберись с ними smile

ksili

Дата 11.1.2009, 08:43 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 2069
Регистрация: 3.11.2005
Где: Красноярск

Репутация: 1
Всего: 17

Человек наверно учится, решил начать с простого. В принципе и тут есть что пооптимизировать.

--------------------

Mikl_

Дата 11.1.2009, 09:02 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 537
Регистрация: 9.11.2007

Репутация: 8
Всего: 14

ksili, все уже до нас украдено (Операция "Ы" и другие приключения Шурика) смотрите здесь
(fasm) Подскажите алго сортировки unicode строк

ksili

Дата 11.1.2009, 09:20 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 2069
Регистрация: 3.11.2005
Где: Красноярск

Репутация: 1
Всего: 17

Там конечно топикстартеру будет интересно почитать. Но здесь он ещё догадался сделать прогу в Билдере для сравнения, что было очень полезно. По ссылке я таких сравнений не заметил.

Жаль нету хороших бесплатных профайлеров. Так бы я ему посоветовал

--------------------

W4FhLF

Дата 11.1.2009, 09:30 (ссылка)

(нет голосов)

Загрузка ...

found myself

Профиль
Группа: Участник Клуба
Сообщений: 2831
Регистрация: 2.12.2006

Репутация: 1
Всего: 121

Код


pop ecx                   // Восстанавливаем предыдущий индекс
push dword ptr [edx + 4*ecx]        // Запоменаем mas[ecx]
push dword ptr [edx + 4*ebx]        // Запоминаем mas[ebx]
pop dword ptr [edx + 4*ecx]         // Извлекаем mas[ebx] из стека
pop dword ptr [edx + 4*ebx]         // Извлекаем mas[eсx] из стека

Обмен значений через стек операция медленная и неэффективная. Особенно, если стек не в кэше.

Код


cmp ecx, count

Ещё одно лишнее обращение к памяти. Храни счётчик в отдельном регистре. У тебя как минимум свободны ещё 3 регистра, почему их не задейстсовать?

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

--------------------

"Бог умер" © Ницше
"Ницше умер" © Бог

airyashov

Дата 11.1.2009, 14:59 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 284
Регистрация: 1.7.2008

Репутация: 2
Всего: 6

del

Это сообщение отредактировал(а) airyashov - 26.1.2009, 08:35

--------------------

icq:3(один)7748666
mail:airyashov( а )inbox.ru

ksili

Дата 12.1.2009, 05:51 (ссылка)

(нет голосов)

Загрузка ...

Эксперт

Профиль
Группа: Завсегдатай
Сообщений: 2069
Регистрация: 3.11.2005
Где: Красноярск

Репутация: 1
Всего: 17

ChihPih, может ты сначала сортируешь массив на асме, а потом тот же уже отсортированный массив сортируешь на С?
Или у тебя два разных массива или вообще две разных программы?

--------------------

ChihPih

Дата 12.1.2009, 17:52 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 532
Регистрация: 3.12.2006

Репутация: нет
Всего: 22

Цитата(Mikl_)

ChihPih, а для чего оптимизировать алгоритм пузырьковой сортировки? Есть сортировки и более быстрые -- разберись с ними

1. Ведь не с проста я поднял тему в этом разделе!
2. Даже более быстрый алгоритм можно сделать медленным smile

Цитата(W4FhLF)

...
Обмен значений через стек операция медленная и неэффективная. Особенно, если стек не в кэше.
...

Поправил, вот, что получилось(теперь на 2 секунды отстает):

Код


void __stdcall SortAsm(int mas[], int count)
{
  asm {
    xor ecx, ecx                            // ecx - счетчик
    mov edx, dword ptr [ebp+8]              // Получаем адрес начала mas
    jmp _sort
    _mod:                                   // Нашли новый минимальный элемент (min = j)
        lea ebx, [ecx]
        jmp _sort_j_end
    _sort:                                  // Начало сортировки
        push ecx                            // Теперь ecx - счетчик для цикла _sort_j
        lea ebx, [ecx]                      // ebx - индекс минимального элемениа
    _sort_j:                                // Поиск минимального элемента
        mov eax, dword ptr [edx + 4*ebx]    // Получение mas[min]
        cmp eax, dword ptr [edx + 4*ecx]    // Сравниваем mas[min] с mas[j]
        jg _mod
    _sort_j_end:
        inc ecx
        cmp ecx, dword ptr [ebp+12]
        jne _sort_j
    _sort_i_continue:                       // Меняем местами элементы
        pop ecx
        mov eax, dword ptr [edx + 4*ecx]    // eax = mas[ecx]
        xchg eax, dword ptr [edx + 4*ebx]   // eax <=> mas[ebx]
        mov dword ptr [edx + 4*ecx], eax    // mas[min] = eax

        inc ecx
        cmp ecx, dword ptr [ebp+12]
        jne _sort
    _quit:
  }
}

Цитата(W4FhLF)

...
Ещё одно лишнее обращение к памяти. Храни счётчик в отдельном регистре. У тебя как минимум свободны ещё 3 регистра, почему их не задейстсовать?
...

Пробовал в esi помещать count, но получалось еще медленней?!

Цитата(airyashov)

не знаю на 6 борланде, процедуры без изменения, массив рандомом
asm duration = 6.593 sec
c++ duration = 21.141 sec

Вот как я сравнивал(тоже на 6 борланде):

Код


#define max_size 100000

void __fastcall TForm1::Button1Click(TObject *Sender)
{
  int mas[max_size];
  for (int i = max_size - 1; i >= 0; i--){
      mas[i] = max_size - i;
  }
  Label3->Caption = "";
  Memo1->Clear();
  double start = GetTickCount();
  Sort(mas, max_size);
  double stop = GetTickCount();
  for (int i = 0; i < 10; i++){
      Memo1->Lines->Add(IntToStr(mas[i]));
  }
  Label3->Caption = FloatToStr((stop - start)/1000.0);
}

void __fastcall TForm1::Button2Click(TObject *Sender)
{
  int mas[max_size];
  for (int i = max_size - 1; i >= 0; i--){
      mas[i] = max_size - i;
  }
  Label4->Caption = "";
  Memo1->Clear();
  double start = GetTickCount();
  SortAsm(mas, max_size);
  double stop = GetTickCount();
  Memo1->Clear();
  for (int i = 0; i < 10; i++){
      Memo1->Lines->Add(IntToStr(mas[i]));
  }
  Label4->Caption = FloatToStr((stop - start)/1000.0);
}

И, кстати, может вы забыли в опциях проекта release поставить(нажать)?

Еще пару вопросов появилось:
1. Насколько я знаю eax, ebx, ecx и edx - регистры общего назначения. А esi, edi, ebp, esp - служебные, то есть
через ebp+esp по стеку "погулять". А вот esi и edi для чего, я так и не понял.
2. Можно ли esi, edi, ebp, esp использовать так же как и eax .. edx, то есть записывать в них, что угодно и т.д. и т.п.?

--------------------

www.info-x.org - информационный ресурс о ОС FreeBSD. Форум.

ChihPih

Дата 13.1.2009, 21:17 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 532
Регистрация: 3.12.2006

Репутация: нет
Всего: 22

Цитата

Еще пару вопросов появилось:
1. Насколько я знаю eax, ebx, ecx и edx - регистры общего назначения. А esi, edi, ebp, esp - служебные, то есть
через ebp+esp по стеку "погулять". А вот esi и edi для чего, я так и не понял.
2. Можно ли esi, edi, ebp, esp использовать так же как и eax .. edx, то есть записывать в них, что угодно и т.д. и т.п.?

Сам разобрался.

--------------------

www.info-x.org - информационный ресурс о ОС FreeBSD. Форум.

ChihPih

Дата 13.1.2009, 23:00 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 532
Регистрация: 3.12.2006

Репутация: нет
Всего: 22

Вот поправил код, получилось довольно не плохо! Отставание сократилось до долей секунды.

Код


void __stdcall SortAsm(int mas[], int count)
{
  asm {
    xor ecx, ecx                            // ecx - счетчик
    mov edx, dword ptr [ebp+8]              // Получаем адрес начала mas
    mov esi, dword ptr [ebp+12]             // Количество элементов
    _loop:                                  // Начало сортировки
        push ecx                            // Теперь ecx - счетчик для цикла _sort_j
        mov ebx, ecx                        // ebx - индекс минимального элемениа
    _sort:                                  // Поиск минимального элемента
        mov eax, dword ptr [edx + 4*ebx]    // Получение mas[min]
        cmp eax, dword ptr [edx + 4*ecx]    // Сравниваем mas[min] с mas[j]
        jle _sort_continue                  // Если меньше или равно, то идем на _sort_continue
        mov ebx, ecx                        // Нашли новый минимальный элемент
    _sort_continue:
        inc ecx
        cmp ecx, esi
        jne _sort
    _loop_continue:                         // Меняем местами элементы
        pop ecx
        mov edi, dword ptr [edx + 4*ecx]    // edi = mas[ecx]
        mov eax, dword ptr [edx + 4*ebx]    // eax = mas[min]
        mov dword ptr [edx + 4*ebx], edi    // mas[min] = edi
        mov dword ptr [edx + 4*ecx], eax    // mas[ecx] = eax

        inc ecx
        cmp ecx, esi
        jne _loop
    _quit:
  }
}

Спасибо всем за помощь!

Это сообщение отредактировал(а) ChihPih - 13.1.2009, 23:20

--------------------

www.info-x.org - информационный ресурс о ОС FreeBSD. Форум.

Mikl_

Дата 14.1.2009, 04:23 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 537
Регистрация: 9.11.2007

Репутация: 8
Всего: 14

ChihPih, в ассемблере обычно разворачивают for-цикл
т.е. вместо

Код

xor ecx, ecx                            ;ecx - счетчик
_loop:      . . .
    inc ecx
     cmp ecx,count
     jne _loop

используют

Код

mov ecx,count
_loop:  . . .
    dec ecx
    jnz _loop

экономят время и код на операции cmp ecx,count

ChihPih

Дата 14.1.2009, 19:16 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 532
Регистрация: 3.12.2006

Репутация: нет
Всего: 22

Спасибо за совет, учту на будущее.

--------------------

www.info-x.org - информационный ресурс о ОС FreeBSD. Форум.

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| Asm для начинающих \| Следующая тема »