Оптимизация кода

Помогите, пожалуйста, оптимизировать этот код (заполнение массива случайными неповторяющимися числами):

Код (Text):

1.                mov ecx, 63             // Кол-во блоков массива по 4 байта
2.                mov edi, OFFSET list            // edi = адрес массива
3.                xor eax, eax                    //
4.                mov [edi], eax                  // list[0] = 0
5.     @@loop:                            // *
6.        mov [edi+ecx*4], eax            // * Заполнение
7.        dec ecx                         // * list[1..255] нулями
8.        jnz @@loop                      // *
9.     @@L1:
10.        cmp cx, 256                  // for (i=0; i<=255; i++)
11.        je @@exit                       // {
12.        call RealRandom         //   *
13.        fimul freeCount                 //   *
14.        fld1                            //   * skip = (unsigned short int)(freeCount*
15.        fadd st(0), st(1)               //   *        RealRandom()+1)
16.        fistp WORD PTR [skip]           //   *
17.     @@L1a:
18.        cmp skip, 0                     // while (skip>0)
19.        jz @@L2                         // {
20.        xor eax, eax                    //    *
21.        mov al, location                //    *
22.        ror ax, 8                       //    * location = location%256+1
23.        xor al, al                      //    *
24.        rol ax, 8                           //    *
25.        inc ax                         //    *
26.        mov location, al               //    *
27.        cmp BYTE PTR [edi+eax-1], 0  //    if (list[location-1] == 0) then
28.        jnz @@L1a                      //       --skip
29.        dec skip                    
30.        jmp @@L1a                     //  }
31.     @@L2:
32.        mov BYTE PTR [edi+eax-1], cl //  list[location-1] = i
33.        dec freeCount                 //  --freeCount
34.        inc cx                            //
35.        jmp @@L1                    
36.     @@exit:                           //  }

Интересует оптимизация по скорости. Всем спасибо за внимание!

 

1. Заменяй однобайтовые inc/dec на add. Выполняются адды быстрее.
2.

Код (Text):

1. ror ax, 8    //    * location = location%256+1
2. xor al, al    //    *
3. rol ax, 8    //    *

А чем and не устраивает?
and eax, 0x00FFFFFF


3.

256 = 0x100 = 0000 ... 0001 0000 0000 (bin)

юзай комманду bt
проверяй 9й бит на 1цу


Так вроде все. leo спец в этих вопросах. Ждем его комментов.

 

Тут можно ммх2 заюзать. Сразу по 128 бит занулять.

 

они долго грузятся, лучше развёртка цикла (не лучший пример):

Код (Text):

1. @@loop:                            // *
2.        mov [edi+ecx*4], eax      
3.        mov [edi+ecx*4-4], eax  
4.        sub ecx, 2
5.        mov [edi+ecx*4], eax            // * Заполнение
6.        dec ecx                         // * list[1..255] нулями
7.        jnz @@loop                      // *

P.S. получше написал )

 

могу конечно тупить, но rep stosd вместо кода выше точно преимуществ не даст?

 

Код (Text):

1. fimul freeCount
2. fld1
3. fadd st(0), st(1)    
4. fistp WORD PTR [skip]
5. @@L1a:
6. cmp skip, 0

сделой чтото типа

Код (Text):

1. fimul freeCount
2. fistp WORD PTR [skip]
3. mov bx,[skip]
4. inc bx

с регистром операции быстрее чем с памятью

 

по скорости не даст.
AssemblerIA64
на какой процессор оптимизация?

 

Большое всем спасибо!

На Core 2 Duo.

Код (Text):

1. могу конечно тупить, но  rep stosd вместо кода выше точно преимуществ не даст?

До скорости даёт преемущество только до i80386-го процессора.

 

Действительно, SSE2 никакого прироста скорости не дали.

 

Вот что получилось:

Код (Text):

1. mov edi, OFFSET list
2.        xor eax, eax
3.        mov ebx, 63
4.        mov [edi], eax
5.     @@loop:
6.        mov [edi+ebx*4], eax         // *
7.        mov [edi+ebx*4-4], eax       // *
8.        mov [edi+ebx*4-8], eax       // * Заполнение
9.        sub ebx, 3           // * list[1..255] нулями
10.        jnz @@loop           //*
11.     @@L1:
12.        bt bx, 8             // for (i=0; i<=255; i++)
13.        jc @@exit                                 // {
14.        call RealRandom          //  *
15.        fimul freeCount                           //     *
16.        fistp WORD PTR [skip]                     //     * skip = (unsigned short int)(freeCount*
17.        mov cx, skip             //  *        RealRandom()+1)
18.        add cx, 1            //  *
19.     @@L1a:
20.        jecxz @@L2           //  while (skip>0)
21.        and ax, 0x00FF           //  {
22.        add ax, 1                                    //   * location = location%256+1
23.        cmp BYTE PTR [edi+eax-1], 0         //    if (list[location-1] == 0) then
24.        jnz @@L1a                                  //       --skip
25.        sub ecx, 1                                   //
26.        jmp @@L1a             //  }
27.     @@L2:
28.        mov BYTE PTR [edi+eax-1], bl          //  list[location-1] = i
29.        sub freeCount, 1                            //  --freeCount
30.        add bx, 1                                     //
31.        jmp @@L1                                    //
32.     @@exit:                                          //  }

 

AssemblerIA64
оригинал покажите?

P.S.

Код (Text):

1. mov edi, OFFSET list
2.        xor eax, eax
3.        mov ebx, 63
4.        mov [edi], eax
5.     @@loop:
6.        mov [edi+ebx*4], eax         // *
7.        mov [edi+ebx*4-4], eax       // *
8.        mov [edi+ebx*4-8], eax       // * Заполнение
9.        sub ebx, 3           // * list[1..255] нулями
10.        jnz @@loop           //*

получше переписал

Код (Text):

1.            mov ecx, 64
2.            xor eax, eax
3.            lea edi, [ecx*4+list]
4.            neg ecx
5.         @@loop:
6.            mov [edi+ecx*4], eax        ;  // *
7.            mov [edi+ecx*4+4], eax      ;  // *
8.            mov [edi+ecx*4+8], eax      ;  // *
9.            mov [edi+ecx*4+12], eax     ;  // * Заполнение
10.            add ecx, 4                  ;  // * list[0..255] нулями
11.            jnz @@loop                  ;  //*

 

t00x,
Оригинал вверху темы. Вообще-то я взял код из книги и переписал его на ассемблере.

Код (Text):

1. получше переписал

Спасибо! Завтра поэкспериментирую.

 

AssemblerIA64
угу. из книги надо было выкладывать.

 

Комментарии к коду и есть псевдокод алгоритма, взятого из книги.

 

Тестирую версии алгоритма при помощи небезызвестной инструкции RDTSC.
Прогоняю алгоритм несколько раз, суммирую результаты, делю на кол-во итераций.
Самое интересное в том, что в зависимости от того, в каком порядке тестируются коды получаются разные результаты! Всегда быстрее тот код, скорость которого замеряется последней.
Интересно, почему так?
P.S. В диспетчере задач стоит приоритет реального времени.

 

Перед тем, как тестировать нагрузил процессор.
Теперь результаты нормальные.

 

Реализация алгоритма Бута для знаковых целых чисел (под архитектуру AMD64):

Код (Text):

1.     mov rax, [Y]        ; rax = Y - величина R
2.     xor rsi, rsi        ; rsi = 0 - величина L
3.     mov [R], rax        ; R = Y
4.     mov [L], rsi        ; L = 0
5.     xor rdx, rdx        ; rdx = 0 - бит (n-1)-ый числа R
6.     mov r8b, 64         ; Кол-во итераций
7.   .0:
8.     and rax, 0x1        ; n-ый бит числа R (самый младший бит)
9.     mov rcx, rax
10.     xor rax, rdx        ; Биты n и (n-1) различаются?
11.     jz  .2      ; Если нет, то на .2
12.     test    rcx, rcx        ; Бит n равен 0?
13.     jne .1b     ; Если нет, то на .1b
14.   .1a:
15.     add rsi, [X]        ; L = L + X
16.     jmp .2
17.   .1b:
18.     sub rsi, [X]        ; L = L - X
19.   .2:
20.     mov rax, [R]        ; | Арифметический сдвиг
21.     shrd    rax, rsi, 1     ; | связки <L:R>
22.     sar rsi, 1      ; | на 1 разряд
23.     mov [R], rax        ; | вправо
24.     mov rdx, rcx        ; (n-1)-ый бит = n-ый бит
25.     sub r8b, 1
26.     jnz .0
27.     mov [L], rsi

Код (Text):

1.              X             dq   xxxxxxx               ; Множимое
2.              Y             dq   xxxxxxx               ; Множитель
3.              R             dq   ?                        ; Младшая часть результата
4.              L             dq   ?                        ; Старшая часть результата

Можно ли что-нибудь убыстрить?

 

в целях оптимизации кода по скорости, можно например, использовать оставшиеся регистры для хранения переменных и избавиться от переходов .1a и .1b как-нибудь так

Код (Text):

1. ...
2.     mov r8b, 64         ; Кол-во итераций
3.     mov r6, [X]
4.   .0:
5.     mov r5, r6      ;
6.     neg r5               ; или not?
7.     and rax, 0x1        ; n-ый бит числа R (самый младший бит)
8.     mov rcx, rax
9.     cmovz   r5, r6
10.     xor rax, rdx        ; Биты n и (n-1) различаются?
11.     jz  .2      ; Если нет, то на .2
12. ;   test    rcx, rcx        ; Бит n равен 0?
13. ;   jne .1b     ; Если нет, то на .1b
14. ;  .1a:
15. ;   add rsi, [X]        ; L = L + X
16. ;   jmp .2
17. ;  .1b:
18. ;   sub rsi, [X]        ; L = L - X
19.     add rsi, r5
20.   .2:
21.     mov rax, [R]        ; | Арифметический сдвиг

 

На основе Ваших советов + переделав кое-что сам, составил:

Код (Text):

1.  
2.     mov rax, [Y]        ; rax = Y
3.     xor rsi, rsi        ; rsi = 0 - величина L
4.     mov r11, rax        ; r11 = Y - величина R
5.     mov r10, [X]        ; r10 = X - множимое
6.     xor rdx, rdx        ; rdx = 0 - бит (n-1)-ый числа R
7.     mov r8b, 64         ; Кол-во итераций
8.   .0:
9.     mov r9, r10
10.     neg r9      ; r9 = -r10
11.     and rax, 0x1        ; n-ый бит числа R (самый младший бит)
12.     mov rcx, rax
13.     cmovz   r9, r10
14.     xor rax, rdx        ; Биты n и (n-1) различаются?
15.     jz  .2      ; Если нет, то на .2
16.     add rsi, r9         ; L = L + X или L = L - X (взависимости от n-ого бита)
17.   .2:
18.     shrd    r11, rsi, 1     ; | Арифметический сдвиг
19.     sar rsi, 1      ; | связки <L:R> на
20.     mov rax, r11        ; | 1 разряд вправо
21.     mov rdx, rcx        ; (n-1)-ый бит = n-ый бит
22.     sub r8b, 1
23.     jnz .0
24.     mov [L], rsi
25.     mov [R], r11

Кстати, регистров r5, r6 нет, есть регистры r8-r15 (см. 79-ю страницу http://download.intel.com/design/processor/manuals/253665.pdf).

 

слова "убыстрить" кстати тоже

Код (Text):

1. ...
2.     mov cl, 64      ; Кол-во итераций
3.     xor r12, r12        ; const r12=0
4.     mov r9, r10
5.     neg r9      ; r9 = -r10
6.   .0:
7.     mov r15, r10
8.     and rax, 0x1        ; n-ый бит числа R (самый младший бит)
9. ;   mov rcx, rax
10.     cmovz   r15, r10
11.     xor rax, rdx        ; Биты n и (n-1) различаются?
12.     cmovz   r15, r12
13. ;   jz  .2      ; Если нет, то на .2
14.     add rsi, r15        ; L = L + X или L = L - X (взависимости от n-ого бита)
15. ;  .2:
16.     shrd    r11, rsi, 1     ; | Арифметический сдвиг
17. ...
18.     sub cl, 1
19.     jnz .0

в качестве счётчика цикла лучше использовать cl, и кол-во итераций можно посчитать заранее.

P.S. изменение быстродействия не измеряли?