Path: news.daimi.aau.dk!jacobse From: jacobse@daimi.aau.dk (Jacob Seligmann) Newsgroups: comp.lang.beta,comp.lang.lisp Subject: Re: Comparison: Beta - Lisp Date: 13 Sep 1994 18:13:27 GMT Organization: DAIMI, Computer Science Dept. at Aarhus University Lines: 298 Message-ID: <354q47$60i@belfort.daimi.aau.dk> References: <34n2qe$d74@nz12.rz.uni-karlsruhe.de> <34pfea$6ee@belfort.daimi.aau.dk> NNTP-Posting-Host: clematis.daimi.aau.dk Xref: news.daimi.aau.dk comp.lang.beta:35 comp.lang.lisp:13258 Jacob Seligmann (jacobse@daimi.aau.dk) wrote: > Lenny Gray (lenngray@netcom.com) wrote: > > > Bruno Haible (haible@ma2s2.mathematik.uni-karlsruhe.de) wrote: > > > > > some integer array hacking > > > C 4.2 sec > > > Mjolner 111 sec > > > GCL 288 sec > > > CLISP 415 sec > > > Are these numbers right? I've seriously used GCL and CLISP myself and > > had some arguments with a "true believer Lisper" who thought "Lisp _does_ > > compete reasonably with C for numeric stuff", but I never bothered to do > > the timing tests, and always assumed it wasn't this bad. Is it, really? > > I don't know what Bruno's "some integer array hacking" program does [...] Mr. Bruno Haible was friendly enough to send me the C and LISP programs used. Unfortunately, he had deleted the BETA program, so I had to do the port from scratch. All three programs are listed at the end of this post. The benchmark is the program run with n=9. [As you can see below, the C implementation uses a lot of tricks I did not care or was unable to use in the BETA port: in-lining (#define's), hard-wired variable liveliness information (loads of blocks with local variables, making the code very hard to read), code generation hints (register ...), array pointers (*d++ = *s++), unstructured gotos, etc.] Here's my results (486/66; BETA compiler v5.0(2); gcc v2.5.8): gcc -O6 -fomit-frame-pointer 2.08 BETA -no-range-check 11.00 [Actually, the compiler currently do not have a -no-range-check option. The BETA figure was obtained by removing all boundl-instructions from the code by hand, and reassembling; this is the only way I could achieve a fair comparison.] As you can see, the ratio between state-of-the-art optimized C and BETA was 5.3, not 26.4 as above. > > Also, I was interested in Beta until one minute ago, because of this. > > Are there intrinsic reasons for this that will prevent it from ever > > improving? I looked at the generated code, and it seems that the increase in execution time can be attributed to two factors: (1) The BETA code allocates its variables on the heap, while the C code uses registers almost exclusively. (2) The BETA code performs a regular lookup calculation at each array access, while the C code simply increases a dedicated register during the linear sweep. With a little bit of effort, there is absolutely no reason why the BETA compiler should not be able to perform the variable liveliness analysis itself (although currently it does not, and therefore pays the heavy price of using heap space instead of registers). Also, the linear array sweeps are simple enough that the compiler could recognize them and avoid the index calculations (again, it currently does not, and therefore pays the price at each lookup). "Some integer array hacking"-type programs are *exactly* what highly sophisticated C compilers excel at, but there are no intrinsic reasons why the BETA compiler should not to be able to produce comparable code. We're constantly working on it... Sincerely, /Jacob Seligmann ------------------------------------------------------------------------ Mjolner Informatics ApS Phone: (+45) 86 20 20 00 ext. 2754 Science Park Aarhus Direct: (+45) 86 20 20 11 - 2754 Gustav Wieds Vej 10 Fax: (+45) 86 20 12 22 DK-8000 Aarhus C, Denmark Email: jacobse@mjolner.dk ------------------------------------------------------------------------ BETA is better ------------------------------------------------------------------------ ============================== fannkuch.c ============================== /* Programm zur Simulation des Pfannkuchenspiels */ /* Bruno Haible 10.06.1990 */ #include #define PermLength 100 #define PermCopy(Source,Dest,n) \ {register int h = n; register int *s = Source; register int *d = Dest; \ while (h) {*d++ = *s++; h--;}; \ } void main() { int n; int Perm[PermLength]; int Perm1[PermLength]; int Zaehl[PermLength]; int PermMax[PermLength]; int BishMax; /* bisheriges Maximum aller Spiegelungsanzahlen */ printf("n = ?"); scanf("%d",&n); if (!((n>0)&&(n<=PermLength))) goto Ende; BishMax=-1; /* Erzeugung aller Permutationen */ /* Erzeuge die Permutationen nach dem Algorithmus: PERM1[0..n-1] := (0,...,n-1] t:=n # if t=1 then standardroutine, goto $ Z_hl[t-1]:=t t:=t-1, goto # $ if t0 then goto # t:=t+1, goto $ */ { register int i; for (i=0; iBishMax) {BishMax=Spiegelungsanzahl; PermCopy(Perm1,PermMax,n);}; } goto Dollar; } Fertig: printf("Das Maximum betrug %d.\n bei ",BishMax); {register unsigned int i; printf("("); for (i=0; i0) printf(" "); printf("%d",PermMax[i]+1); }; printf(")"); }; printf("\n"); Ende: ; } ============================= fannkuch.lsp ============================= (defun fannkuch (&optional (n (progn (format *query-io* "n = ?") (parse-integer (read-line *query-io*)) ) ) ) (unless (and (> n 0) (<= n 100)) (return-from fannkuch)) (let ((n n)) (declare (fixnum n)) (let ((perm (make-array n :element-type 'fixnum)) (perm1 (make-array n :element-type 'fixnum)) (zaehl (make-array n :element-type 'fixnum)) (permmax (make-array n :element-type 'fixnum)) (bishmax -1)) (declare (type (simple-array fixnum (*)) perm perm1 zaehl permmax)) (declare (fixnum bishmax)) (dotimes (i n) (setf (svref perm1 i) i)) (prog ((\t n)) (declare (fixnum \t)) Kreuz (when (= \t 1) (go standardroutine)) (setf (svref zaehl (- \t 1)) \t) (decf \t) (go Kreuz) Dollar (when (= \t n) (go fertig)) (let ((perm0 (svref perm1 0))) (dotimes (i \t) (setf (svref perm1 i) (svref perm1 (+ i 1)))) (setf (svref perm1 \t) perm0) ) (when (plusp (decf (svref zaehl \t))) (go Kreuz)) (incf \t) (go Dollar) standardroutine (dotimes (i n) (setf (svref perm i) (svref perm1 i))) (let ((Spiegelungsanzahl 0) (k 0)) (declare (fixnum Spiegelungsanzahl k)) (loop (when (= (setq k (svref perm 0)) 0) (return)) (let ((k2 (ceiling k 2))) (declare (fixnum k2)) (dotimes (i k2) (rotatef (svref perm i) (svref perm (- k i)))) ) (incf Spiegelungsanzahl) ) (when (> Spiegelungsanzahl bishmax) (setq bishmax Spiegelungsanzahl) (dotimes (i n) (setf (svref permmax i) (svref perm1 i))) ) ) (go Dollar) fertig ) (format t "Das Maximum betrug ~D.~% bei " bishmax) (format t "(") (dotimes (i n) (when (> i 0) (format t " ")) (format t "~D" (+ (svref permmax i) 1)) ) (format t ")") (terpri) (values) ) ) ) ============================= fannkuch.bet ============================= ORIGIN '~beta/basiclib/v1.4/betaenv' --program:descriptor-- (# PermLength: (# exit 100 #); Perm, Perm1, PermMax, Zaehl: [PermLength]@integer; h, i, k, n, t, up, down, BishMax, Spiegelungsanzahl: @integer; do 'n = ?' -> putText; getInt -> n; (if (n < 1) or (n > PermLength) then stop if); -1 -> BishMax; (for i:n repeat i-1 -> Perm1[i] for); n -> t; again: (# do (for i:t repeat i -> Zaehl[i] for); 1 -> t; (for i:n repeat Perm1[i] -> Perm[i] for); 0 -> Spiegelungsanzahl; while1: (# do (if Perm[1]->k // 0 then leave while1 if); 1 -> up; k+1 -> down; down/2 -> i; while2: (# do (if i // 0 then leave while2 if); Perm[up] -> h; Perm[down] -> Perm[up]; h -> Perm[down]; up+1 -> up; down-1 -> down; i-1 -> i; restart while2; #); Spiegelungsanzahl+1 -> Spiegelungsanzahl; restart while1; #); (if Spiegelungsanzahl > BishMax then Spiegelungsanzahl -> BishMax; (for i:n repeat Perm1[i] -> PermMax[i] for) if); while3: (# do (if t // n then leave while3 if); Perm1[1] -> h; (for i:t repeat Perm1[i+1] -> Perm1[i] for); h -> Perm1[t+1]; (if (Zaehl[t+1]-1 -> Zaehl[t+1]) <> 0 then restart again if); t+1 -> t; restart while3; #); #); 'Das Maximum betrug ' -> putText; BishMax -> putInt; '.\n bei (' -> putText; (for i:n repeat (if i > 1 then ' ' -> put if); PermMax[i]+1 -> putInt; for); ')' -> putLine; #) ========================================================================