Ассемблерный код работает медленнее сишного!

Уважаемые программисты!
Столкнулся с такой проблемой: есть код на Си, вычисляющий факториал. Код таков:

Код (Text):

1. #include <stdio.h>
2. unsigned short array[1000000] = {1};
3. unsigned int len= 1;
4. void main()
5. {
6. unsigned int i;
7. unsigned long L;
8. unsigned long cn;
9. int N;
10.  
11. printf("Input N:");
12. scanf("%d",&N);
13.  
14. cn= 0;
15. for(L= 1; L<=N; L++)
16.  
17. {
18. i=0;
19.        do {cn+= array[i]*L;
20.         array[i]= (unsigned short)(cn%10000);
21.         cn/= 10000;} while (++i<len || cn);
22. len= i;
23. }
24. printf("%d", array[len-1]);
25.  
26. for(i= len-1; i--;)
27.         {
28.         printf("%04d", array[i]);
29.         }
30.  
31. printf("\n");
32. }

Я решил переписать его на ассемблере, получив следующее:

Код (Text):

1. format PE console
2. include 'win32axp.inc'
3. .data
4. dllka db 'msvcrt.dll',0
5. name1 db 'scanf',0
6. scanf dd ?
7. name2 db 'printf',0
8. printf dd ?
9. inp db 'Input N:',0
10. d db '%d',0
11. d4 db '%04d',0
12. crlf db 13,10,0
13. N dd ?
14. len dd 1
15.  
16. array dw 1
17.       dw 999999 dup 0
18.  
19. .code
20. puck:
21. invoke LoadLibrary,dllka
22. push eax
23. invoke GetProcAddress,eax,name1
24. mov [scanf],eax
25. pop eax
26. invoke GetProcAddress,eax,name2
27. mov [printf],eax
28. cinvoke printf,inp
29. cinvoke scanf,d,N
30.  
31. mov ebx,[N]
32. test ebx,ebx
33. jl konets
34.  
35. mov edi,[len]
36. xor esi,esi
37. inc esi
38. xor eax,eax
39. cmp ebx,esi
40. jb mtk1
41.  
42. mtk0:
43. xor ecx,ecx
44.  
45. mtk:
46. movzx edx,word [array+ecx*2]
47. imul edx,esi
48. add eax,edx
49. xor edx,edx
50. mov ebp,2710h
51. div ebp
52. mov word[array+ecx*2],dx
53. inc ecx
54. cmp ecx,edi
55. jb mtk
56. test eax,eax
57. jnz mtk
58. inc esi
59. cmp esi,ebx
60. mov edi,ecx
61. jbe mtk0
62. mov [len],edi
63.  
64. mtk1:
65. movzx eax,word [array-2+edi*2]
66. cinvoke printf,d,eax
67. mov esi,[len]
68. dec esi
69. jz konets
70.  
71. mtk2:
72. dec esi
73. movzx ecx,word[array+esi*2]
74. cinvoke printf,d4,ecx
75. test esi,esi
76. jnz mtk2
77.  
78. konets:
79. cinvoke printf,crlf
80. invoke ExitProcess,0
81. .end puck

Скомпилировав сишный исходник с помощью MS VC++ Toolkit 2003 с максимальной оптимизацией, я сравнил время его работы с ассемблерным кодом. Замерял примитивно, с помощью обычных часов
Итог: при вычислении чисел типа 150000! ассемблерный вариант секунд на 10 отстаёт от сишного! Я, конечно, понимаю, что в MS не дураки сидят и умеют писать оптимизаторы, но чтобы так... И это при том, что сишный компилятор даже не все регистры занимает!
Господа программисты! Подскажите, где теряется производительность в ассемблерном варианте и, если это возможно, подскажите пути исправления
Советовать VTune не стоит - пока я его ещё не раздобыл, да и толку - проц у меня AMD

 

ну так посмотри что сгенерил Си.
а твой код неотформатирован, коряво читается. но по-крайне мере деление можно было и не юзать.

 

укажи компилеру опцию /FA и получай код на асме.
немного подправив, его можно будет скормить масму.

 

Нда, нет слов
Adrax, зачем тебе здесь умножение? Индекс массива увеличивается линейно, на постоянную величину, так не проще ли завести указатель на массив и просто инкрементировать его?
Вообще код очень корявый, пропадает все желание в нем разбираться, но даже навскидку видно нерациональное распределение регистров(хватит и четырех) и лишние проверки ((++i<len || cn) можно свести к одной).

 

Adrax
насчёт кода. комментарии к коду не бывают лишними ;P

 

Adrax
Возможно ещё влияет выравнивание. Неоднократно наблюдал прикольную картину: добавляешь в цикл какую-нибудь бесполезную команду, и скорость существенно возрастает, хотя по идее должно бы наоборот. Ещё встечалось, что было достаточно компильнуть более новым компиллером, и тоже в несколько раз возрастала скорость. Так что флаг в руки и вперёд, анализировать сгенерённый ассемблерный листинг.

 

Жаль, leo куда-то запропастился, он бы все подробно объяснил.

 

Насчет умножения был неправ, там никак не заменишь
Посмотрел, что мне борландовский компиль выдал, и упал под стол, такой код никак не может быть быстрее, нежели представленный Adrax
Что касается оптимизации, то, не изменяя самого алгоритма, напрашивается избавление от одного условного перехода в цикле while (++i<len || cn), например:

Код (Text):

1. ; ebx - i
2. ; ecx - cn
3. ; ebp - len
4. lea eax, [ebx+1]
5. sub eax, ebp
6. inc ebx
7. or eax, ecx
8. jnz __do

Что касается использования регистров, то cn желательно хранить в eax, поскольку отпадают ненужные перестановки:

Код (Text):

1. movzx eax, [array+ebx*2]
2. imul xxx
3. mov ecx, 10000
4. xor edx, edx
5. div ecx
6. mov [array+ebx*2], dx
7. ; cn в eax

Если же нужна более эффективная оптимизация, то необходимо развернуть цикл, заменив mov [array+ebx*2], dx на mov [array+ebx*2], edx. Теоретически должно добавить скорости, хотя бы за счет сокращения обращений к памяти.
ЗЫ: Adrax, попробуй. Если не получится, тогда уж помогу.

 

Возьми AMD CodeAnalyst.

 

mov ebp,2710h
всё таки лучше вынести из цикла

 

2 t00x
Да, насчёт 2710h протупил... Спасибо!

2 AndNot
Огромное спасибо! Сейчас буду пытаться

 

Adrax, да незачто Сейчас протестил малость.

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

Код (Text):

1.         mov     esi, 1             ; esi = len
2.         mov     ecx, esi           ; ecx = L
3.         xor     edi, edi           ; edi = cn
4.         mov     ebp, 10000
5.     __loop:
6.         xor     ebx, ebx           ; ebx = i
7.     __do: ; здесь можно и упростить, но очень уж не хочется диапозон для imul ограничивать
8.         movzx   eax, [word array+ebx*2]
9.         imul    ecx
10.         add     eax, edi           ; eax = cn+array[i]*L
11.         xor     edx, edx
12.         div     ebp
13.         inc     ebx
14.         mov     edi, eax           ; edi = cn/10000
15.         mov     [word array+ebx*2-2], dx
16.         cmp     ebx, esi
17.         jb      __do
18.         or      eax, eax
19.         jnz     __do
20.  
21.         inc     ecx
22.         mov     esi, ebx           ; esi = len
23.         cmp     ecx, [N]
24.         jbe     __loop

Билдер делает почти в два раза, хотя и не оптимизирован ни грамма

PS: а вообще было бы неплохо взглянуть на код, сгенерированный VC. У кого есть возможность, выложите плиз
PPS: будет время - разверну цикл, хотя эффект будет только на больших итерациях.

 

Если факториал - это промежуточный результат (для дальнейших вычислений), то лучше считать его в хексе.
Не будет тяжёлых операций / и %.

В любом случае, лучше оперировать ulong вместо ushort (используя uint64).

 

Объясните мне, плз, почему 10000 а не 10.
-------
[+]
Понял примерно.

 

green

в каком хексе?

Чем лучше?

 

Наверное имелось в виду, что вместо 10000 лучше взять 16384, отбросив деление. Только как потом результат в десятичную систему переводить?

 

KeSqueer

в 16-ричной системе исчисления.

Быстрее будет - в 2 раза меньше итераций во внутреннем цикле.

Если факториал - это промежуточный результат, то лучше считать в hex.
Но если это вся задача - посчитать факториал и вывести его, то, наверно, надо сразу в dec(10-й) считать - выигрыш теряется из-за необходимости перевода в dec при выводе (будет то же деление на степень 10).

 

green

И как это должно выглядеть? Убей - не пойму что Вы имеете ввиду.

 

KeSqueer
Просто заменяем основание системы счисления: с 10000 на 65536.
Это, с одной стороны, значительно ускорит алгоритм за счёт избавления от деления.
Но, с другой стороны, при выводе таких чисел их наверняка придётся переводить обратно в десятичную систему, т.е. выполнять кучу длинных делений.

 

Это я уже пробовал. Выигрыш немалый, но это не то.
Единственное, что приходит в голову, это использовать, вместо 10000, более крупную степень десятки, чтобы отлавливать переполнение через флаги. Осталось только решить, какое. Наверное лучше всего перейти на 32-х разрядные.