Мерянье пи... э... попугаями. Быстродействие языков.

1. [blue]
2.               + X+1,                 если N=0
3.               | X,                   если N=1,  Y=0,
4.               | 0,                   если N=2,  Y=0,
5.     A(N,X,Y)= | 1,                   если N=3,  Y=0,
6.               | 2,                   если N=>4, Y=0,
7.               + A(N-1,A(N,X,Y-1),X), если N#0,  Y#0;
8.  
9.      где N,X,Y - целые неотрицательные числа.
10. [/blue]

1. [blue]
2. #include <stdio.h>
3.  
4. void main(void)
5. {  
6.     printf("%dn",a(3,8,8));
7. }
8.  
9. int a(int n, int x, int y)
10. {  
11.     if(!n)
12.         return x+1;
13.  
14.     if(y)
15.         return a(n-1,a(n,x,y-1),x);
16.    
17.     switch(n)
18.     {  
19.         case 1:  return x;
20.         case 2:  return 0;
21.         case 3:  return 1;
22.     }
23.  
24.     return 2;
25. }

1. [blue]
2. ; 16   :    
3. ; 17   :     switch(n)
4. ; 18   :     {  
5.  
6.   0002d 4e       dec     esi
7.   0002e 74 18        je  SHORT $L861
8.   00030 4e       dec     esi
9.   00031 74 13        je  SHORT $L869
10.   00033 4e       dec     esi
11.   00034 74 08        je  SHORT $L870
12.   00036 5f       pop     edi
13.  
14. ; 22   :     }
15. [/blue]

let rec a n x y =
    match (n, y) with
        (0, y) -> x+1
      | (1, 0) -> x
      | (2, 0) -> 0
      | (3, 0) -> 1
      | (n, 0) -> 2
      | (n, y) -> (a (n-1) (a n x (y-1)) x)
    ;;


print_int(a 3 8 8);
print_newline();;

[html_font color=blue]
_Akkr_a_49:
    sub esp, 8
L106:
    cmp eax, 7
    ja  L101
    mov edx, eax
    sar edx, 1
    jmp [edx * 4 + L107]
    .DATA
L107    DWORD   L105
    DWORD   L104
    DWORD   L103
    DWORD   L102
    .CODE
L105:
    add ebx, 2
    mov eax, ebx
    add    esp, 8
    ret
L104:
    cmp ecx, 1
    jne L101
    mov eax, ebx
    add    esp, 8
    ret
L103:
    cmp ecx, 1
    jne L101
    mov eax, 1
    add    esp, 8
    ret
L102:
    cmp ecx, 1
    jne L101
    mov eax, 3
    add    esp, 8
    ret
L101:
    cmp ecx, 1
    je  L100
    mov DWORD PTR 0[esp], eax
    mov DWORD PTR 4[esp], ebx
    add ecx, -2
    call    _Akkr_a_49
L108:
    mov ebx, eax
    mov eax, DWORD PTR 0[esp]
    add eax, -2
    mov ecx, DWORD PTR 4[esp]
    jmp L106
L100:
    mov eax, 5
    add    esp, 8
    ret

=KRoN=>let rec a n x y =
=KRoN=>    match (n, y) with
=KRoN=>        (0, y) -> x+1
=KRoN=>      | (1, 0) -> x
=KRoN=>      | (2, 0) -> 0
=KRoN=>      | (3, 0) -> 1
=KRoN=>      | (n, 0) -> 2
=KRoN=>      | (n, y) -> (a (n-1) (a n x (y-1)) x)
=KRoN=>    ;;


=KRoN=>print_int(a 3 8 8);
=KRoN=>print_newline();;
=KRoN=>

=KRoN=>Время работы программы - 2.23 сек!

[html_font color=blue]
=KRoN=>_Akkr_a_49:
=KRoN=>    sub esp, 8 - налицо отсутствие оформления фрэйма 
                        стэка - в спорах на этом форуме я не
                        раз упоминал, что в современных языках
                        вызов процедуры одно из самых дорогих
                        удовольствий - фрэйм для локальных
                        переменных, передача параметров 
                        через стек и т.д. Здесь произведена
                        резервация под две временные
                        переменные. Надо еще сказать, что
                        параметры передаются через регистры -
                        n - eax, x - ebx, y - ecx. Результат
                        возвращается на eax.
      
=KRoN=>L106:             Запомните эту метку!!!!
=KRoN=>    cmp eax, 7    Все константы и вычисления сдвинуты
                         по формуле 2*n+1 иниыми словами это
                         сравнение  cmp eax,3
=KRoN=>    ja  L101      есла n больше 3, то это общий случай
=KRoN=>    mov edx, eax  иначе преобразуем это в индекс для
                         косвенного перехода - таким образом
                         закодирована первая часть match
=KRoN=>    sar edx, 1
=KRoN=>    jmp [edx * 4 + L107]
=KRoN=>    .DATA
                              Это собственно таблица 
                              косвенной адресации
=KRoN=>L107    DWORD   L105   n == 0
=KRoN=>    DWORD   L104       n == 1 
=KRoN=>    DWORD   L103       n == 2
=KRoN=>    DWORD   L102       n == 3
=KRoN=>    .CODE
=KRoN=>L105:
=KRoN=>    add ebx, 2           x + 1
=KRoN=>    mov eax, ebx         вернуть на eax
=KRoN=>    add    esp, 8        подровнять стек
=KRoN=>    ret
=KRoN=>L104:
=KRoN=>    cmp ecx, 1           сравнение y == 0
=KRoN=>    jne L10
=KRoN=>    mov eax, ebx         x
=KRoN=>    add    esp, 8
=KRoN=>    ret
=KRoN=>L103:
=KRoN=>    cmp ecx, 1              y == 0
=KRoN=>    jne L101
=KRoN=>    mov eax, 1               вернуть 0
=KRoN=>    add    esp, 8
=KRoN=>    ret
=KRoN=>L102:
=KRoN=>    cmp ecx, 1           y == 0
=KRoN=>    jne L101
=KRoN=>    mov eax, 3           вернуть 1
=KRoN=>    add    esp, 8
=KRoN=>    ret
=KRoN=>L101:                     общий случай
=KRoN=>    cmp ecx, 1            y == 0
=KRoN=>    je  L100
=KRoN=>    mov DWORD PTR 0[esp], eax  внимание, сохраним n
=KRoN=>    mov DWORD PTR 4[esp], ebx  и х во временные 
                                      переменные
=KRoN=>    add ecx, -2           y - 1
=KRoN=>    call    _Akkr_a_49    вызовем функцию для вычисления
                                 a n x ( y - 1 ) - внутренний
                                 вызов.
=KRoN=>L108:                  
                                А вот здесь начинается второе
                                место, где объектный верблюд
                                выигрывает. ВНИМАНИЕ.
                                Вместо вызова функции еще раз
                                верблюд подготовил параметры
                                на регистрах и перешел на ту
                                метку, которую я вам советовал
                                завпомнить - сразу после 
                                sub esp,8 - тем самым экономия
                                сразу в двух местах - нет
                                операции вызова - она заменена
                                переходом (нет работы со стеком
                                и т.д.) и еще - переиспользова-
                                ние временных переменных без их
                                дополнительного переразмещнния
                                на стеке!
=KRoN=>    mov ebx, eax         результат на eax - поместим 
                                его вторым параметром - как x  
=KRoN=>    mov eax, DWORD PTR 0[esp] востановим n
=KRoN=>    add eax, -2                и отнимем 1 - т.е. мы
                                      имеем n - 1 первым 
                                      параметром   
=KRoN=>    mov ecx, DWORD PTR 4[esp] а бывший x передадим пос-
                                      ледним
=KRoN=>    jmp L106                А вот и тот самый переход
                                   вместо вызова!!!!!
=KRoN=>L100:
=KRoN=>    mov eax, 5               здесь возратим 2
=KRoN=>    add    esp, 8
=KRoN=>    ret

С++                           Верблюд
2*12 - параметры              0
2*12 - временные переменные   1*8 
2*4 - адрес возврата          1*4 - развернули один уровень
2*4 - оформление фрейма       0
2 возврата/вызова             один вызов, один переход
(двойная операция со стеком)

Итого
64 байта на вызов             12 байтов

[html_font color=blue]
: AA  ( x y n — an )
    ?DUP 0= IF DROP 1+ EXIT THEN
    ( x y n )
    SWAP ?DUP IF  ( x n y!=0 )
        >R 2DUP R> 1- ( x n x n y-1 ) SWAP RECURSE ( x n a )
        -ROT 1- RECURSE
        EXIT
    THEN
    ( x n )
    DUP 1 = IF DROP ( x ) EXIT THEN
    DUP 2 = IF 2DROP    0 EXIT THEN
        3 = IF 2DROP    1 EXIT THEN
    DROP 2
;        

    
: A  ( n x y — an )  ROT AA ;

3 3 3 A . CR
BYE

_TEXT	SEGMENT
_n$ = 8               смещения до параметров на стеке
_x$ = 12              относительно esp
_y$ = 16
?a@@YAHHHH@Z PROC NEAR					; a, COMDAT
; File D:Testsackermanackerman.cpp
; Line 12
	push	esi    фрейм не оформляем - нет локальных переменных
; Line 14
	mov	esi, DWORD PTR _n$[esp]  загрузили n - потеря у верблюда уже на регистре
	test	esi, esi                 сравнили
	push	edi                      сохранили регистр - потеря
	je	SHORT $L768
	mov	ecx, DWORD PTR _y$[esp+4] теперь достаем y&x - потеря
	mov	eax, DWORD PTR _x$[esp+4]
$L764:
; Line 17
	test	ecx, ecx
	je	SHORT $L723
; Line 18
	dec	ecx          готовимся к внутреннему вызову - и 
                             edi еще пихаем - а потом восстанавливаем
	mov	edi, eax
	push	ecx          Подготовка параметров
	push	eax
	push	esi
	call	?a@@YAHHHH@Z				; a
	add	esp, 12					; 0000000cH выравнивание стека
	dec	esi
	mov	ecx, edi
	jne	SHORT $L764   вот она замена рекурсии!!!!
	pop	edi
	inc	eax
	pop	esi
; Line 27
	ret	0
$L768:
; Line 14
	mov	eax, DWORD PTR _x$[esp+4]
	pop	edi
; Line 15
	inc	eax
	pop	esi
; Line 27
	ret	0
$L723:
; Line 21
	dec	esi
	je	SHORT $L721
	dec	esi
	je	SHORT $L729
	dec	esi
	je	SHORT $L730
	pop	edi
; Line 26
	mov	eax, 2
	pop	esi
; Line 27
	ret	0
$L730:
	pop	edi
; Line 24
	mov	eax, 1
	pop	esi
; Line 27
	ret	0
$L729:
; Line 23
	xor	eax, eax
$L721:
	pop	edi
	pop	esi
; Line 27
	ret	0
?a@@YAHHHH@Z ENDP					; a
_TEXT	ENDS

1. [blue]
2. PUBLIC  @ackr@12
3. _y$ = 8
4. @ackr@12 PROC NEAR                  ; COMDAT
5. ; _n$ = ecx
6. ; _x$ = edx
7.  
8. ; 9    : {  
9.  
10.   00000 56       push    esi
11.   00001 8b f1        mov     esi, ecx
12.  
13. ; 10   :     if(!n)
14.  
15.   00003 85 f6        test    esi, esi
16.   00005 57       push    edi
17.   00006 8b c2        mov     eax, edx
18.   00008 74 1c        je  SHORT $L884
19.   0000a 8b 4c 24 0c  mov     ecx, DWORD PTR _y$[esp+4]
20.  
21. ; 23   : }
22.  
23.   0000e 8b ff        npad    2
24. $L882:
25.  
26. ; 12   :
27. ; 13   :     if(y)
28.  
29.   00010 85 c9        test    ecx, ecx
30.   00012 74 18        je  SHORT $L864
31.  
32. ; 14   :         return ackr(n-1,ackr(n,x,y-1),x);
33.  
34.   00014 49       dec     ecx
35.   00015 51       push    ecx
36.   00016 8b d0        mov     edx, eax
37.   00018 8b ce        mov     ecx, esi
38.   0001a 8b f8        mov     edi, eax
39.   0001c e8 00 00 00 00   call    @ackr@12
40.   00021 4e       dec     esi
41.   00022 8b cf        mov     ecx, edi
42.   00024 75 ea        jne     SHORT $L882
43. $L884:
44.   00026 5f       pop     edi
45.  
46. ; 11   :         return x+1;
47.  
48.   00027 40       inc     eax
49.   00028 5e       pop     esi
50.  
51. ; 23   : }
52.  
53.   00029 c2 04 00     ret     4
54. $L864:
55.  
56. ; 15   :    
57. ; 16   :     switch(n)
58. ; 17   :     {  
59.  
60.   0002c 4e       dec     esi
61.   0002d 74 1c        je  SHORT $L862
62.   0002f 4e       dec     esi
63.   00030 74 17        je  SHORT $L870
64.   00032 4e       dec     esi
65.   00033 74 0a        je  SHORT $L871
66.   00035 5f       pop     edi
67.  
68. ; 21   :     }
69. ; 22   :     return 2;
70.  
71.   00036 b8 02 00 00 00   mov     eax, 2
72.   0003b 5e       pop     esi
73.  
74. ; 23   : }
75.  
76.   0003c c2 04 00     ret     4
77. $L871:
78.   0003f 5f       pop     edi
79.  
80. ; 20   :         case 3: return 1;
81.  
82.   00040 b8 01 00 00 00   mov     eax, 1
83.   00045 5e       pop     esi
84.  
85. ; 23   : }
86.  
87.   00046 c2 04 00     ret     4
88. $L870:
89.  
90. ; 18   :         case 1: return x;
91. ; 19   :         case 2: return 0;
92.  
93.   00049 33 c0        xor     eax, eax
94. $L862:
95.   0004b 5f       pop     edi
96.   0004c 5e       pop     esi
97.  
98. ; 23   : }
99.  
100.   0004d c2 04 00     ret     4
101. @ackr@12 ENDP
102.  
103. PUBLIC  _main
104. _main   PROC NEAR                   ; COMDAT
105.  
106. ; 5    :     printf("%dn",ackr(3,8,8));
107.  
108.   00000 6a 08        push    8
109.   00002 6a 07        push    7
110.   00004 ba 08 00 00 00   mov     edx, 8
111.   00009 b9 03 00 00 00   mov     ecx, 3
112.   0000e e8 00 00 00 00   call    @ackr@12
113.   00013 8b d0        mov     edx, eax
114.   00015 b9 02 00 00 00   mov     ecx, 2
115.   0001a e8 00 00 00 00   call    @ackr@12
116.   0001f 50       push    eax
117.   00020 68 00 00 00 00   push    OFFSET FLAT:??_C@_03PMGGPEJJ@?$CFd?6?$AA@
118.   00025 e8 00 00 00 00   call    _printf
119.   0002a 83 c4 08     add     esp, 8
120.  
121. ; 6    : }
122.  
123.   0002d 33 c0        xor     eax, eax
124.   0002f c3       ret     0
125. _main   ENDP

1.       iackr: ; ebx = n, ecx = x, edx = y -> eax = ackr(n,x,y)
2.         test ebx, ebx
3.         jnz iackr_1
4.         lea eax, [ecx+1]
5.         ret
6.       iackr_1:
7.         test edx, edx
8.         jz iackr_2
9.         push ebx
10.         push ecx
11.         push edx
12.         dec edx
13.         call iackr
14.         mov edx, ecx
15.         mov ecx, eax
16.         dec ebx
17.         call iackr
18.         pop edx
19.         pop ecx
20.         pop ebx
21.         ret
22.       iackr_2:
23.         push ebx
24.         dec ebx
25.         jnz iackr_3
26.         mov eax, ecx ;1
27.         pop ebx
28.         ret
29.       iackr_3:
30.         dec ebx
31.         jnz iackr_4
32.         xor eax, eax ;2
33.         pop ebx
34.         ret
35.       iackr_4:
36.         dec ebx
37.         jnz iackr_5
38.         mov eax, 1 ;3
39.         pop ebx
40.         ret
41.       iackr_5:
42.         mov eax, 2
43.         pop ebx
44.         ret