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

 
+
-
edit
 

=KRoN=
Balancer

администратор
★★★★★
Тест №1. Функция Аккермана.

Функцию брал с The page cannot be found
code text
  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]


Тестирую на PIII-1200/SDRAM (124МГц). Сравниваются VC++ 7.0 и O'Caml 4.

Для начала программа на С++.
code text
  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. }
[/blue]

Компиляция: cl /Ox /O2 /F327680000 /Fa /FAsc /G6 accerman.c

Код получился классный. Даже switch разложен на
code text
  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]


Я уже молчу про то, что компилятор развернул один цикл рекурсии, как можно сократил внутренние переходы, распараллелил инструкции и проч.

В итоге имеем результат 16777216 за 4.07сек. В принципе, можно загнать в цикл и измерить точнее, что сделаю попозже.

Кстати, обращаю внимание на размер стека - 327680000. Изначально сделал 32768байт и потом дописывал нули, пока его хватило.

Теперь - O'Caml 4.
 
+
-
edit
 

=KRoN=
Balancer

администратор
★★★★★
Итак, O'Caml.

С исходным текстом мудрить не стал.

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]

Компиляция - ocamlopt.exe -S -inline 100 -o akkr.exe -ccopt /F32768000 akkr.ml

Как видим, стека хватает в 10 раз меньшего, чем на VC7.

Время работы программы - 2.23 сек! :D
При чём он даже не пытался делать внешнюю раскрутку функции.
Вот, если кому интересно, ассемблерный код функции:

[html_font size=+0]
[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

[/html_font]
 
+
-
edit
 

=KRoN=
Balancer

администратор
★★★★★
Если честно, я такого не ожидал :D
 
+
-
edit
 

Mishka

модератор
★★★

Сгрузил я O'Caml с inria и ввел программу Крона. И получил

Stack overflow during evaluation (looping recursion?). Как стек увеличить из среды?
 
+
-
edit
 

Mishka

модератор
★★★

=KRoN=>Итак, O'Caml.

=KRoN=>С исходным текстом мудрить не стал.
=KRoN=>

=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=>

[/html_font]

=KRoN=>Компиляция - ocamlopt.exe -S -inline 100 -o akkr.exe -ccopt /F32768000 akkr.ml

=KRoN=>Как видим, стека хватает в 10 раз меньшего, чем на VC7.

И этому есть объснение - смотри ниже.

=KRoN=>Время работы программы - 2.23 сек! :D
=KRoN=>При чём он даже не пытался делать внешнюю раскрутку функции.
=KRoN=>Вот, если кому интересно, ассемблерный код функции:

Вот здесь я и прокомментирую.

=KRoN=>[html_font size=+0]
[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

[/html_font]

[ слишком длинный топик - автонарезка ]
 
+
-
edit
 

Mishka

модератор
★★★

Так что ничего неожиданного - просто хорошие проекции и хорошие идеи. Ровно в 2 раза меньше вызовов (один вызов заменен на переход) и соответсвенно в 2 раза меньше работы со стеком. Да и существующая работа значительно проще, чем в С++. При передаче параметров, когда их количество не сможет лечь на регистры - может быть проблемой.

Кстати, а возможно создание у верблюда локальных переменных?
 
+
-
edit
 

=KRoN=
Balancer

администратор
★★★★★
Mishka>Stack overflow during evaluation (looping recursion?). Как стек увеличить из среды?

Из среды - не знаю, я компилил из командной строки, передавая параметр стека внешнему VC7 компилеру+линкеру:

ocamlopt.exe -S -inline 100 -o akkr.exe -ccopt /F32768000 akkr.ml

Mishka>Так что ничего неожиданного - просто хорошие проекции и хорошие идеи.

Гы. А что, есть другие пути оптимизации? :D Типа телепатического взаимодействия с процессором? :D Ну а если б он рекурсию придумал развернуть, то разница в скорости на МНОГО порядков была бы :)

Mishka>Кстати, а возможно создание у верблюда локальных переменных?

Точно не знаю, т.к. на его изучение я потратил минут 5, только чтобы написать вышеприведённую програмку :) Скорее всего - есть. Возможно даже (!) глобальные переменные есть, на правах goto в Си++ и т.п. :) Т.к. язык, в отличие от того же Хаскелла, насколько я знаю, создавался не как академический, а для реальной работы.
 
+
-
edit
 

Mishka

модератор
★★★

=KRoN=>Из среды - не знаю, я компилил из командной строки, передавая параметр стека внешнему VC7 компилеру+линкеру:

=KRoN=>ocamlopt.exe -S -inline 100 -o akkr.exe -ccopt /F32768000 akkr.ml

Да я тоже так сделал. Кстати, то, что вызовов в два раза меньше - это и экономия стека - отсюда те самые 10 раз.

Mishka>>Так что ничего неожиданного - просто хорошие проекции и хорошие идеи.

=KRoN=>Гы. А что, есть другие пути оптимизации? :D Типа телепатического взаимодействия с процессором? :D Ну а если б он рекурсию придумал развернуть, то разница в скорости на МНОГО порядков была бы :)

Насчет идей - нет. А насчет проекций - это начало. Есть еще граф исполнения программы. Я тут где-то уже говорил, что французы очень здорово здесь поработали. У них было много интересных работ по преобразования графа исполнения в эквивалентные для параллелизма. Но это же самое подходит и для обычных алгоритмов - появляются куски, которые можно двигать.

Про рекурсию - потому и сказал про Аккермана - он не выражается.

=KRoN=>Точно не знаю, т.к. на его изучение я потратил минут 5, только чтобы написать вышеприведённую програмку :) Скорее всего - есть. Возможно даже (!) глобальные переменные есть, на правах goto в Си++ и т.п. :) Т.к. язык, в отличие от того же Хаскелла, насколько я знаю, создавался не как академический, а для реальной работы.

Вроде ребята из Inria побывали там, если не ошибаюсь. Правда эта контора вроде нашей академии. Я сгрузил книжку по верблюду - на сайте и ссылка есть. Так что почитаю на досуге. Кстати, если будут локальные переменные, то раскрутить рекурсию таким образом не удасться - надо будет фрейм оформлять. На вызове можно (переход вместо вызова), а на фрейме нет.
 
+
-
edit
 

Mishka

модератор
★★★

Как все экономиться:
С++ примерно так^
push y - parameters
push x
push N
call ackerman

ackerman:
push bp - frame
mov bp, sp
sub sp,12 - local variables

....
push n
push x
push y-1
call ackerman
push n-1
push result
push x
call ackerman

mov sp,bp
ret

O'Caml:
subp sp, 8 - temp variables

l1:
...
mov ax,n
mov bx,x
mov cx,y-1
call acckerman
mov bx,ax - result as x
mov ax, n-1
mov cx,x
jmp l1

l2: ret

т.е. нет отведения 12 байт под временные переменные, а только 8 - экономия 4. Развернутая рекурсия - нет одного вызова - экономия адрес возврата. Параметры передаются через регистры, а не стек - 12 байт.

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

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

Так что по моим оценкам не в 10, а в 5-6 раз больше стека надо.

Кстати, такую развертку никто не мешал бы сделать и на других языках - у нас в Алголе 68 было понятие процедуры без базы (без стекового фрейма). И мы применяли это. Только вот по причинам иного характера не разварачивали, а вроде обсуждали.
 
+
-
edit
 

=KRoN=
Balancer

администратор
★★★★★
Кстати, на Форте я так написал:
[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

[/html_font]

Вот только на 3 9 9 дефолтового стека не хватает, а как увеличить его в SP-Forth пока не нашёл :)
 
+
-
edit
 

Mishka

модератор
★★★

Кстати, здесь сразу видны накладные расходы на чисто стековую архитектуру - нет неразрушающих операций - отсюда dup многократно. И нет специального регистра для хранения результатов операций сравнения - все кладем на стек. Я понимаю, что это все логично, но я бы добавил бы и их самих, и их помеси - для ортогональности.
 
+
-
edit
 

=KRoN=
Balancer

администратор
★★★★★
Ну, локальные переменные в ANS-94 есть, но, ИМХО, они медленнее.
 
+
-
edit
 

Mishka

модератор
★★★

Кстати говоря, Крон прав - VC 6.0 в режиме оптимизации тоже один уровень рекурсии снижает - раскрывая его как верблюд. Так что похоже накладных расходов на лишний вызов нет - остается передача параметров.

Вот полный ассемблерный код с комментариями
_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


 
+
-
edit
 

Mishka

модератор
★★★

Похоже, что у Форта тоже возникнут проблемы с пересылками на стеке :(

А еще говорят, что много регистров не надо - вот пример, когда это помогает просто дальше некуда. Поэтому и пул регистров надо делать здоровый. Вызов процедуры с 5 параметрами еще может быть ОК, а с 20 - уже через стек. Ну, вроде, если кто-то и пишет процедуры с 20 параметрами, то ему на скорость накакать.
 
+
-
edit
 

=KRoN=
Balancer

администратор
★★★★★
Сегодня нашёл у cl.exe ключик /Gr (fastcall). С ним у VC7 вышло 2.56сек. И всё равно Ocaml чуть-чуть быстрее :)

code text
  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
[/blue]
 
+
-
edit
 

=KRoN=
Balancer

администратор
★★★★★
Хотел сегодня на C# измерить, благо практически C++ по коду:

[blue]using System;

class test
{
static int a(int n, int x, int y)
{
if(n==0)
return x+1;

if(y!=0)
return a(n-1,a(n,x,y-1),x);

switch(n)
{
case 1: return x;
case 2: return 0;
case 3: return 1;
}

return 2;
}

static void Main(string[] args)
{
Console.Write(a(3,8,8));
}

}[/blue]

Но увы, стека, как обычно, не хватает, а как его увеличить нигде не нашёл :-/
 
Это сообщение редактировалось 26.07.2003 в 14:50
+
-
edit
 

=KRoN=
Balancer

администратор
★★★★★
Блин, захотел на Хаскелле (ghc) попробовать:

import System

a 0 x y = x+1
a 1 x 0 = x
a 2 x 0 = 0
a 3 x 0 = 1
a n x 0 = 2
a n x y = (a (n-1) (a n x (y-1)) x)

main = do print(a 3 8 8)


Увы, через 6 мин. работы: "ackr.exe: fatal error: Windows programs can only use 256Mb of heap; sorry!"

Это при том, что:
" -M<size> Sets the maximum heap size (default unlimited) Egs: -M256k -M1G"

Запустил сейчас с -M1G - посмотрим... :)

P.S. Нет, пофиг :(
 
+
-
edit
 

=KRoN=
Balancer

администратор
★★★★★
Есть. C# после ручного копания заголовка EXE-шника (спасибо MaxMP) дал результат 3.96сек. По-моему очень и очень неплохо! У C#, думаю, есть все шансы потеснить C++ и, тем более, Java/VB.
 
+
-
edit
 

=KRoN=
Balancer

администратор
★★★★★
Не поленился написать "лобовое" решение на Асме. На отладку ушло ~45мин :)

code 6502acme
  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


Время работы - 2.88 сек.

Кстати, среднее время работы для 10 вызовов a 3 8 8 на Ocaml оказалось 2.08 сек, а не 2.23, как было указано ранее :)
 
Это сообщение редактировалось 26.07.2003 в 14:49
+
-
edit
 

avmich

координатор

>У C#, думаю, есть все шансы потеснить C++ и, тем более, Java/VB.

Только разве что из-за маркетинга... Даже Java, не говоря уж о C++...

[ 25-11-2002: Message edited by: avmich ]
 
+
-
edit
 

=KRoN=
Balancer

администратор
★★★★★
C# компилит в нативный код, в отличие от Java. И снабжён целой кучей вкусностей, которых нет в С++ - от сборки мусора, до массивов массивов и т.п. Кроме того, на C# после C++ переучиваться практически не нужно.

Если кто-то для теста сгенерит консольный .class для функции Аккермана для 3,8,8 - я прогоню его у себя и скажу, сколько времени он будет работать :D
 
+
-
edit
 

avmich

координатор

>C# компилит в нативный код, в отличие от Java.

Ерунда. Непринципиально в данном случае.

>И снабжён целой кучей вкусностей, которых нет в С++

;)

>от сборки мусора

"Одни программисты считают, что управление памятью - это очень важная вещь, и ею должна заниматься только операционная система. Другие программисты считают, что управление памятью - жто очень важная вещь, и её никак нельзя поручить операционной системе, а нужно делать самим.

При этом и те, и другие согласны, что управление памятью - это очень важная вещь."

(с) фольклор

>до массивов массивов

Ну, формально массивы массивов есть чуть ли не везде... уж в C++ и Java точно.

>Кроме того, на C# после C++ переучиваться практически не нужно.

О, вот это действительно важное качество :) . Особенно по сравнению с Java ;) .

>Если кто-то для теста сгенерит консольный .class для функции Аккермана для 3,8,8 - я прогоню его у себя и скажу, сколько времени он будет работать :D

Лучше скажи, зачем... нет, правда, Крон... на бенчмарки тестов по реальным программам смотрел?..

Это, кстати, тоже неважно. Стоимость разработки - один из основных критериев сегодня.
 
+
-
edit
 

=KRoN=
Balancer

администратор
★★★★★
>>C# компилит в нативный код, в отличие от Java.
avmich>Ерунда. Непринципиально в данном случае.

Ну-ну... :)

avmich>При этом и те, и другие согласны, что управление памятью - это очень важная вещь."

Слава Богу, со времён этой шутки уже не одно поколение еомпиляторов сменилось, и сегодня сборка мусора мало того, что хорошо работает, иногда без неё в принципе никак. Обычно фанаты Ocaml и Haskell любят показывать древовидные структуры с циклическими ссылками, которые на классическом Си++ невозможны без утечек памяти :) По-моему, сейчас как раз очередной виток в fido7.su.softw идёт (не вчитывался) :)

>>до массивов массивов
avmich>Ну, формально массивы массивов есть чуть ли не везде... уж в C++ и Java точно.

Я с C++ сравниваю, т.к. массив указателей - это не то :)

>>Кроме того, на C# после C++ переучиваться практически не нужно.
avmich>О, вот это действительно важное качество :) . Особенно по сравнению с Java ;) .

Всё же, Java от Си++ отличается гораздо сильнее, чем C#.

avmich>Лучше скажи, зачем... нет, правда, Крон... на бенчмарки тестов по реальным программам смотрел?..

Ну, вот, например - RSDN

avmich>Это, кстати, тоже неважно. Стоимость разработки - один из основных критериев сегодня.

Вот тут у C# шансов оказывается очень много :D
 
+
-
edit
 

avmich

координатор

>Вот тут у C# шансов оказывается очень много

Не может быть :)
 
+
-
edit
 

avmich

координатор

А бенчмарки вроде как вполне мою точку зрения подтверждают.

> Первый – к любым тестам нужно относиться со здравой долей скептицизма.

> Второй – практически все компиляторы производят на свет довольно быстрый код.

> Третье – новые платформы (Java и .Net), а вместе с ними и так любимая у нас Delphi, практически не уступают C++-компиляторам по скорости производимого кода

(тут откусил часть фразы)

> Четвертое – мнение о том, что управляемые среды типа Java и .Net медленны и из-за этого не могут рассматриваться всерьез как универсальные языки, на которых можно создавать быстрое ПО, ошибочно.
 

в начало страницы | новое
 
Поиск
Настройки
Твиттер сайта
Статистика
Рейтинг@Mail.ru