🚀 go-pugleaf

In article <91544@netnews.upenn.edu> freeman@gradient.cis.upenn.edu (Jon Freeman) writes:

   This is not a question that I would normally ask, but unfortunately I
   need to ask it and I need answers as soon as possible...

   In the personal experience of people on the net, which widely
   available implementation of a functional language is the fastest on
   comparable programs?  I'm thinking about language-implementation pairs
   like MIT Scheme, Lucid Common Lisp, Franz Lisp, etc.

   Here's why I'm asking: I have been writing search algorithms for the
   CNF-satisfiability problem in Standard ML of New Jersey, version 0.75.
   Although I like SML very much, and I think its static type-checking is
   fantastic for program development, I'm afraid I have to admit that its
   performance on my algorithms, at least, is simply terrible.

You should do some simple benchmarks for yourself that test those
aspects of the implementation that you are interested in. NJ/SML does
not perform very well for arithmetic (in particular, floating point),
buts I believe that its garbage collector is generally faster than
that of the other languages. For non-numerical problems, I have not
noticed a big difference between NJ/SML and CommonLisp.

   First, let me illustrate this claim with a specific example.  There's
   a local search algorithm for CNF-satisfiability called GSAT.  The most
   recent paper on GSAT is available via anonymous ftp from
   research.att.com in the directory /dist/ai.  Like all local search
   algorithms, GSAT is very simple: it's essentially two nested FOR
   loops.  According to the above paper, the authors' implementation of
   GSAT (written in C) can solve the 8, 20, and 30-queens problems in
   0.1, 0.9, and 2.5 seconds, respectively.  My SML implementation of
   GSAT, on the other hand, requires an average of 3, 70, and 500 seconds
   of CPU time, respectively.  GSAT's simplicity makes these results
   particularly troubling.  My _backtracking_ search algorithms are also
   much slower than their counterparts in the literature.

One problem you may be having is that the SML code you have written
is written less efficiently. In different words, you can write more
C-style code in SML, but, unlike C, SML gives you the choice of more
convenient, but slower, constructs. In my experience, a factor of 30
sounds like too big of a difference even between a C version and an
SML version of the same algorithm to be explicable by an inefficient
implementation of the language.

One particular stylistic choice, which will most likely cost you a
factor of 2-3 in execution speed, is currying (I find that it makes
your programs not only slower, but also harder to read and debug, but
that's a different issue...). Another important difference is that C
code is unsafe, while SML code is safe. You will find that C code
becomes significantly slower once you start adding all those safety
checks.

				Thomas.

PS: Just FYI, here is a _very simple_ comparison of tupled function
calls and curried function calls in NJ/SML, and of the same program in
CMU-CL. Note that the CL version doesn't perform significantly
differently from the SML version. Also note that there are some flags
in NJ/SML analogous to "speed 3" that you can twiddle, but I didn't
bother. Type declarations in CL are, of course, a big mess...

================================================================
SML VERSION
================================================================

(* fold function "f" over the sublists of "(x::xs)" of size "n", starting
   with value "r", and appending "p" to each sublist *)

fun folds_onto([]:'a list,1,r:'b,p:'a list,f:'b * 'a list -> 'b):'b = r
  | folds_onto(x::xs,1,r,p,f) = folds_onto(xs,1,f(r,x::p),p,f)
  | folds_onto([],n,r,p,f) = r
  | folds_onto(x::xs,n,r,p,f) = folds_onto(xs,n,folds_onto(xs,n-1,r,x::p,f),p,f);
	    
fun folds_onto' ([]:'a list) 1 (r:'b) (p:'a list) (f:'b -> 'a list -> 'b):'b = r
  | folds_onto' (x::xs) 1 r p f = folds_onto' xs 1 (f r (x::p)) p f
  | folds_onto' [] n r p f = r
  | folds_onto' (x::xs) n r p f = folds_onto' xs n (folds_onto' xs (n-1) r (x::p) f) p f;
	    
val l = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20];
val n = 10;

fun doit() = folds_onto(l,n,0,[],fn (total,l) => total+length(l));

fun doit'() = folds_onto' l n 0 [] (fn total => fn l => total+length l);

================================================================    

IDIAP Standard Library - working version
eXene - working version
Concurrent ML, version 0.9.6, October 11, 1991
Standard ML of New Jersey, Version 0.84, July 5, 1992
val it = () : unit
[closing dump-elib]
val it = () : unit
- 
val folds_onto = fn : 'a list * int * 'b * 'a list * ('b * 'a list -> 'b) -> 'b
val folds_onto' = fn : 'a list -> int -> 'b -> 'a list -> ('b -> 'a list -> 'b) -> 'b
val l = [1,2,3,4,5,6,7,8,9,10,11,12,...] : int list
val n = 10 : int
val doit = fn : unit -> int
val doit' = fn : unit -> int
[closing bar.sml]
val it = () : unit


compiled as above:

- timeit(doit);
user: 4.780000  gc: 0.010000  system: 0.040000  real: 4.950240
val it = 1847560 : int
- timeit(doit');
user: 15.970000  gc: 0.010000  system: 0.030000  real: 16.148106
val it = 1847560 : int
-

compiled as a single compilation unit (without the ";"s above):

- timeit(doit);
user: 3.120000  gc: 0.020000  system: 0.0  real: 3.152852
val it = 1847560 : int
- timeit(doit');
user: 7.880000  gc: 0.020000  system: 0.0  real: 7.925187
val it = 1847560 : int
-

================================================================
COMMON LISP VERSION
================================================================

(proclaim '(optimize (speed 3) (safety 0)))

(defconstant the-l '(1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20))
(defconstant the-n 10)

(defun folds-onto (l n r p f)
  (declare (fixnum n) (type (function (t t) t) f))
  (if (null l)
      r
      (if (= n 1)
	  (folds-onto (cdr l) 1
		      (funcall f r (cons (car l) p))
		      p f)
	  (folds-onto (cdr l) n
		      (folds-onto (cdr l) (- n 1) r (cons (car l) p) f)
		      p f))))

(defun doit ()
  (folds-onto the-l the-n 0 '()
	      #'(lambda (total l)
		  (declare (fixnum total) (list l))
		  (+ total (length l)))))

================================================================

CMU Common Lisp 16d, running on arolla
Send bug reports and questions to your local CMU CL maintainer, or to
cmucl-bugs@cs.cmu.edu.
Loaded subsystems:
    Python 1.0, target SPARCstation/Sun 4
    CLOS based on PCL version:  5/1/90  May Day PCL (REV 4b)
    CLX X Library MIT R5.0
    Hemlock 3.5
* ...
* (gc)
[GC threshold exceeded with 5,043,368 bytes in use.  Commencing GC.]
[GC completed with 104,672 bytes retained and 4,938,696 bytes freed.]
[GC will next occur when at least 10,104,672 bytes are in use.]

NIL
* (time (doit))
Compiling LAMBDA NIL: 
Compiling Top-Level Form: 

Evaluation took:
  3.51 seconds of real time
  2.81 seconds of user run time
  0.67 seconds of system run time
  0 page faults and
  4933328 bytes consed.
1847560
*