Re: [Gcl-devel] question about the reduce function

[Camm Maguire]

Greetings!

Please try gclcvs, available as a Debian package.  reduce is quite
competitive against clisp and cmu:

(Please also note that GCL does not compile top level forms by default
-- often (though not in this case), significant performance gains can
be had by doing so.

address@hidden:/fix/t1/camm/cvs/foo/ansi-tests$ GCL_ANSI=t gclcvs
GCL (GNU Common Lisp)  2.7.0 ANSI    Dec 18 2007 12:57:22
Source License: LGPL(gcl,gmp,pargcl), GPL(unexec,bfd,xgcl)
Binary License:  GPL due to GPL'ed components: (XGCL READLINE BFD UNEXEC)
Modifications of this banner must retain notice of a compatible license
Dedicated to the memory of W. Schelter

Use (help) to get some basic information on how to use GCL.

Temporary directory for compiler files set to /tmp/

>(defun range (start end) (loop for i from start below end collect i))

RANGE

>(compile 'range)

;; Compiling /tmp/gazonk_5491_0.lsp.
;; End of Pass 1.  
;; End of Pass 2.  
;; OPTIMIZE levels: Safety=0 (No runtime error checking), Space=0, Speed=3, 
(Debug quality ignored)
;; Finished compiling /tmp/gazonk_5491_0.o.
;; Loading /tmp/gazonk_5491_0.o
 ;; start address -T 0xc944c0 ;; Finished loading /tmp/gazonk_5491_0.o
#<compiled-function RANGE>
NIL
NIL

>(progn (setf *foo* (range 0 200000)) (length *foo*))

200000

>(time (reduce '+ *foo*))

real time       :      0.180 secs
run-gbc time    :      0.020 secs
child run time  :      0.000 secs
gbc time        :      0.070 secs
19999900000

>(time (reduce '+ *foo*))

real time       :      0.050 secs
run-gbc time    :      0.030 secs
child run time  :      0.000 secs
gbc time        :      0.000 secs
19999900000

>(time (reduce '+ *foo*))

real time       :      0.130 secs
run-gbc time    :      0.030 secs
child run time  :      0.000 secs
gbc time        :      0.040 secs
19999900000

>(time (reduce '+ *foo*))

real time       :      0.030 secs
run-gbc time    :      0.010 secs
child run time  :      0.000 secs
gbc time        :      0.000 secs
19999900000

>(time (reduce '+ *foo*))

real time       :      0.030 secs
run-gbc time    :      0.030 secs
child run time  :      0.000 secs
gbc time        :      0.000 secs
19999900000

>(time (reduce '+ *foo*))

real time       :      0.120 secs
run-gbc time    :      0.030 secs
child run time  :      0.000 secs
gbc time        :      0.050 secs
19999900000

>(time (reduce '+ *foo*))

real time       :      0.030 secs
run-gbc time    :      0.020 secs
child run time  :      0.000 secs
gbc time        :      0.000 secs
19999900000

>(setq a (compile nil '(lambda nil (reduce '+ *foo*))))

;; Compiling /tmp/gazonk_5491_0.lsp.
; (DEFUN COMPILER::CMP-ANON ...) is being compiled.
;; Warning: ;; The variable *FOO* is undefined.
;; The compiler will assume this variable is a global.

;; End of Pass 1.  
;; End of Pass 2.  
;; OPTIMIZE levels: Safety=0 (No runtime error checking), Space=0, Speed=3, 
(Debug quality ignored)
;; Finished compiling /tmp/gazonk_5491_0.o.
;; Loading /tmp/gazonk_5491_0.o
 ;; start address -T 0xb154b0 ;; Finished loading /tmp/gazonk_5491_0.o
#<compiled-function COMPILER::CMP-ANON>

>(time (funcall a))

real time       :      0.100 secs
run-gbc time    :      0.020 secs
child run time  :      0.000 secs
gbc time        :      0.040 secs
19999900000

>(time (funcall a))

real time       :      0.010 secs
run-gbc time    :      0.020 secs
child run time  :      0.000 secs
gbc time        :      0.000 secs
19999900000

>(time (funcall a))

real time       :      0.020 secs
run-gbc time    :      0.020 secs
child run time  :      0.000 secs
gbc time        :      0.000 secs
19999900000

>(time (funcall a))

real time       :      0.090 secs
run-gbc time    :      0.010 secs
child run time  :      0.000 secs
gbc time        :      0.060 secs
19999900000

>(time (funcall a))

real time       :      0.020 secs
run-gbc time    :      0.010 secs
child run time  :      0.000 secs
gbc time        :      0.000 secs
19999900000

>(time (funcall a))

real time       :      0.010 secs
run-gbc time    :      0.020 secs
child run time  :      0.000 secs
gbc time        :      0.000 secs
19999900000

>(time (funcall a))

real time       :      0.020 secs
run-gbc time    :      0.020 secs
child run time  :      0.000 secs
gbc time        :      0.000 secs
19999900000

>(time (funcall a))

real time       :      0.090 secs
run-gbc time    :      0.020 secs
child run time  :      0.000 secs
gbc time        :      0.040 secs
19999900000

>(time (funcall a))

real time       :      0.010 secs
run-gbc time    :      0.020 secs
child run time  :      0.000 secs
gbc time        :      0.000 secs
19999900000

>
address@hidden:/fix/t1/camm/cvs/foo/ansi-tests$ 
address@hidden:/fix/t1/camm/cvs/foo/ansi-tests$ clisp
  i i i i i i i       ooooo    o        ooooooo   ooooo   ooooo
  I I I I I I I      8     8   8           8     8     o  8    8
  I  \ `+' /  I      8         8           8     8        8    8
   \  `-+-'  /       8         8           8      ooooo   8oooo
    `-__|__-'        8         8           8           8  8
        |            8     o   8           8     o     8  8
  ------+------       ooooo    8oooooo  ooo8ooo   ooooo   8

Copyright (c) Bruno Haible, Michael Stoll 1992, 1993
Copyright (c) Bruno Haible, Marcus Daniels 1994-1997
Copyright (c) Bruno Haible, Pierpaolo Bernardi, Sam Steingold 1998
Copyright (c) Bruno Haible, Sam Steingold 1999-2000
Copyright (c) Sam Steingold, Bruno Haible 2001-2006

[1]> (defun range (start end) (loop for i from start below end collect i))
RANGE
[2]> (compile *)
RANGE ;
NIL ;
NIL
[3]> (progn (setf *foo* (range 0 200000)) (length *foo*))
200000
[4]> (time (reduce '+ *foo*))
Real time: 0.041738 sec.
Run time: 0.040003 sec.
Space: 3107312 Bytes
GC: 2, GC time: 0.008 sec.
19999900000
[5]> (time (reduce '+ *foo*))
Real time: 0.038692 sec.
Run time: 0.036001 sec.
Space: 3107312 Bytes
GC: 3, GC time: 0.016001 sec.
19999900000
[6]> (time (reduce '+ *foo*))
Real time: 0.031871 sec.
Run time: 0.032002 sec.
Space: 3107312 Bytes
GC: 3, GC time: 0.004 sec.
19999900000
[7]> (time (reduce '+ *foo*))
Real time: 0.05605 sec.
Run time: 0.036003 sec.
Space: 3107312 Bytes
GC: 3, GC time: 0.012 sec.
19999900000
[8]> (time (reduce '+ *foo*))
Real time: 0.038674 sec.
Run time: 0.040002 sec.
Space: 3107312 Bytes
GC: 3, GC time: 0.004 sec.
19999900000
[9]> (time (reduce '+ *foo*))
Real time: 0.052683 sec.
Run time: 0.032002 sec.
Space: 3107312 Bytes
GC: 3, GC time: 0.004 sec.
19999900000
[10]> (time (reduce '+ *foo*))
Real time: 0.041969 sec.
Run time: 0.040002 sec.
Space: 3107312 Bytes
GC: 3, GC time: 0.008 sec.
19999900000
[11]> (setq a (compile nil '(lambda nil (reduce '+ *foo*))))
WARNING :
*FOO* is neither declared nor bound,
it will be treated as if it were declared SPECIAL.
#<COMPILED-FUNCTION NIL>
[12]> (time (funcall a))
Real time: 0.050151 sec.
Run time: 0.040002 sec.
Space: 3107312 Bytes
GC: 3, GC time: 0.004001 sec.
19999900000
[13]> (time (funcall a))
Real time: 0.064543 sec.
Run time: 0.032002 sec.
Space: 3107312 Bytes
GC: 3, GC time: 0.008001 sec.
19999900000
[14]> (time (funcall a))
Real time: 0.058717 sec.
Run time: 0.036003 sec.
Space: 3107312 Bytes
GC: 2, GC time: 0.004001 sec.
19999900000
[15]> (time (funcall a))
Real time: 0.050054 sec.
Run time: 0.036003 sec.
Space: 3107312 Bytes
GC: 3, GC time: 0.008001 sec.
19999900000
[16]> (time (funcall a))
Real time: 0.056186 sec.
Run time: 0.040003 sec.
Space: 3107312 Bytes
GC: 3, GC time: 0.008 sec.
19999900000
[17]> (time (funcall a))
Real time: 0.057125 sec.
Run time: 0.040002 sec.
Space: 3107312 Bytes
GC: 3, GC time: 0.004 sec.
19999900000
[18]> (quit)
Bye.
address@hidden:/fix/t1/camm/cvs/foo/ansi-tests$ lisp
CMU Common Lisp CVS 19d 19d-release (19D), running on intech30
With core: /usr/lib/cmucl/lisp.core
Dumped on: Tue, 2007-10-23 18:07:27-04:00 on intech30
For support see http://www.cons.org/cmucl/support.html Send bug reports to the 
debian BTS.
or to address@hidden
type (help) for help, (quit) to exit, and (demo) to see the demos

Loaded subsystems:
    Python 1.1, target Intel x86
    CLOS based on Gerd's PCL 2004/04/14 03:32:47
* (defun range (start end) (loop for i from start below end collect i))

RANGE
* (compile *)
; Compiling LAMBDA (START END): 
; Compiling Top-Level Form: 

RANGE
NIL
NIL
* (progn (setf *foo* (range 0 200000)) (length *foo*))
Warning:  Declaring *FOO* special.

200000
* (time (reduce '+ *foo*))
; Compiling LAMBDA NIL: 
; Compiling Top-Level Form: 

; Evaluation took:
;   0.05 seconds of real time
;   0.044003 seconds of user run time
;   0.0 seconds of system run time
;   159,535,377 CPU cycles
;   0 page faults and
;   7,213,536 bytes consed.
; 
19999900000
* (time (reduce '+ *foo*))
; Compiling LAMBDA NIL: 
; Compiling Top-Level Form: 
; [GC threshold exceeded with 12,015,456 bytes in use.  Commencing GC.]
; [GC completed with 1,741,976 bytes retained and 10,273,480 bytes freed.]
; [GC will next occur when at least 13,741,976 bytes are in use.]

; Evaluation took:
;   0.09 seconds of real time
;   0.068005 seconds of user run time
;   0.004 seconds of system run time
;   278,739,765 CPU cycles
;   [Run times include 0.02 seconds GC run time]
;   0 page faults and
;   7,216,408 bytes consed.
; 
19999900000
* (time (reduce '+ *foo*))
; Compiling LAMBDA NIL: 
; Compiling Top-Level Form: 

; Evaluation took:
;   0.05 seconds of real time
;   0.032002 seconds of user run time
;   0.012001 seconds of system run time
;   133,138,746 CPU cycles
;   0 page faults and
;   7,213,536 bytes consed.
; 
19999900000
* (time (reduce '+ *foo*))
; Compiling LAMBDA NIL: 
; Compiling Top-Level Form: 
; [GC threshold exceeded with 13,753,248 bytes in use.  Commencing GC.]
; [GC completed with 1,737,064 bytes retained and 12,016,184 bytes freed.]
; [GC will next occur when at least 13,737,064 bytes are in use.]

; Evaluation took:
;   0.08 seconds of real time
;   0.064004 seconds of user run time
;   0.004 seconds of system run time
;   258,668,523 CPU cycles
;   [Run times include 0.02 seconds GC run time]
;   0 page faults and
;   7,216,408 bytes consed.
; 
19999900000
* (time (reduce '+ *foo*))
; Compiling LAMBDA NIL: 
; Compiling Top-Level Form: 
; [GC threshold exceeded with 13,751,520 bytes in use.  Commencing GC.]
; [GC completed with 1,808,120 bytes retained and 11,943,400 bytes freed.]
; [GC will next occur when at least 13,808,120 bytes are in use.]

; Evaluation took:
;   0.08 seconds of real time
;   0.056003 seconds of user run time
;   0.0 seconds of system run time
;   243,833,310 CPU cycles
;   [Run times include 0.01 seconds GC run time]
;   0 page faults and
;   7,216,408 bytes consed.
; 
19999900000
* (time (reduce '+ *foo*))
; Compiling LAMBDA NIL: 
; Compiling Top-Level Form: 

; Evaluation took:
;   0.05 seconds of real time
;   0.036002 seconds of user run time
;   0.008001 seconds of system run time
;   144,268,488 CPU cycles
;   0 page faults and
;   7,213,536 bytes consed.
; 
19999900000
* (time (reduce '+ *foo*))
; Compiling LAMBDA NIL: 
; Compiling Top-Level Form: 
; [GC threshold exceeded with 13,820,488 bytes in use.  Commencing GC.]
; [GC completed with 1,829,104 bytes retained and 11,991,384 bytes freed.]
; [GC will next occur when at least 13,829,104 bytes are in use.]

; Evaluation took:
;   0.1 seconds of real time
;   0.060004 seconds of user run time
;   0.004 seconds of system run time
;   269,535,780 CPU cycles
;   [Run times include 0.01 seconds GC run time]
;   0 page faults and
;   7,216,408 bytes consed.
; 
19999900000
* (time (reduce '+ *foo*))
; Compiling LAMBDA NIL: 
; Compiling Top-Level Form: 
; [GC threshold exceeded with 13,843,344 bytes in use.  Commencing GC.]
; [GC completed with 1,903,640 bytes retained and 11,939,704 bytes freed.]
; [GC will next occur when at least 13,903,640 bytes are in use.]

; Evaluation took:
;   0.09 seconds of real time
;   0.052003 seconds of user run time
;   0.0 seconds of system run time
;   263,615,661 CPU cycles
;   [Run times include 0.02 seconds GC run time]
;   0 page faults and
;   7,216,408 bytes consed.
; 
19999900000
* (setq a (compile nil '(lambda nil (reduce '+ *foo*))))
Warning:  Declaring A special.
; Compiling LAMBDA NIL: 
; Compiling Top-Level Form: 

#<Function "LAMBDA NIL" {58140309}>
* (time (funcall a))
; Compiling LAMBDA NIL: 
; Compiling Top-Level Form: 

; Evaluation took:
;   0.08 seconds of real time
;   0.048003 seconds of user run time
;   0.004 seconds of system run time
;   248,951,484 CPU cycles
;   0 page faults and
;   7,213,536 bytes consed.
; 
19999900000
* (time (funcall a))
; Compiling LAMBDA NIL: 
; Compiling Top-Level Form: 
; [GC threshold exceeded with 13,919,960 bytes in use.  Commencing GC.]
; [GC completed with 1,930,216 bytes retained and 11,989,744 bytes freed.]
; [GC will next occur when at least 13,930,216 bytes are in use.]

; Evaluation took:
;   0.08 seconds of real time
;   0.048003 seconds of user run time
;   0.004 seconds of system run time
;   239,660,514 CPU cycles
;   0 page faults and
;   7,216,408 bytes consed.
; 
19999900000
* (time (funcall a))
; Compiling LAMBDA NIL: 
; Compiling Top-Level Form: 

; Evaluation took:
;   0.09 seconds of real time
;   0.048003 seconds of user run time
;   0.004001 seconds of system run time
;   284,850,324 CPU cycles
;   0 page faults and
;   7,213,536 bytes consed.
; 
19999900000
* (time (funcall a))
; Compiling LAMBDA NIL: 
; Compiling Top-Level Form: 
; [GC threshold exceeded with 13,944,752 bytes in use.  Commencing GC.]
; [GC completed with 2,032,000 bytes retained and 11,912,752 bytes freed.]
; [GC will next occur when at least 14,032,000 bytes are in use.]

; Evaluation took:
;   0.1 seconds of real time
;   0.052004 seconds of user run time
;   0.004 seconds of system run time
;   304,011,729 CPU cycles
;   [Run times include 0.01 seconds GC run time]
;   0 page faults and
;   7,216,408 bytes consed.
; 
19999900000
* (time (funcall a))
; Compiling LAMBDA NIL: 
; Compiling Top-Level Form: 
; [GC threshold exceeded with 14,042,344 bytes in use.  Commencing GC.]
; [GC completed with 1,778,304 bytes retained and 12,264,040 bytes freed.]
; [GC will next occur when at least 13,778,304 bytes are in use.]

; Evaluation took:
;   0.14 seconds of real time
;   0.072004 seconds of user run time
;   0.004 seconds of system run time
;   398,411,901 CPU cycles
;   [Run times include 0.03 seconds GC run time]
;   0 page faults and
;   7,216,408 bytes consed.
; 
19999900000
* (time (funcall a))
; Compiling LAMBDA NIL: 
; Compiling Top-Level Form: 

; Evaluation took:
;   0.08 seconds of real time
;   0.040003 seconds of user run time
;   0.004 seconds of system run time
;   253,180,719 CPU cycles
;   0 page faults and
;   7,213,536 bytes consed.
; 
19999900000
* (time (funcall a))
; Compiling LAMBDA NIL: 
; Compiling Top-Level Form: 
; [GC threshold exceeded with 13,792,720 bytes in use.  Commencing GC.]
; [GC completed with 1,869,144 bytes retained and 11,923,576 bytes freed.]
; [GC will next occur when at least 13,869,144 bytes are in use.]

; Evaluation took:
;   0.09 seconds of real time
;   0.052003 seconds of user run time
;   0.004001 seconds of system run time
;   269,008,416 CPU cycles
;   0 page faults and
;   7,216,408 bytes consed.
; 
19999900000
* (time (funcall a))
; Compiling LAMBDA NIL: 
; Compiling Top-Level Form: 

; Evaluation took:
;   0.08 seconds of real time
;   0.040003 seconds of user run time
;   0.0 seconds of system run time
;   236,768,031 CPU cycles
;   0 page faults and
;   7,213,536 bytes consed.
; 
19999900000
* (quit)
address@hidden:/fix/t1/camm/cvs/foo/ansi-tests$ 

Take care, 

"Bill Six" <address@hidden> writes:

> Hi,
> I'm relatively new to Common Lisp.  GCL has been my preferred CL platform 
> (over CMUCL and CLisp) because it generates portable C code and then
> calls a compiler.  I recently was trying to sum a large list of numbers using 
> reduce, and GCL took a very long time to compute the result. 
> I'm trying to understand why.
> In GCL, it takes ~852 seconds to sum 200000 integers:
>      >(defun range (start end)
>              (loop for i from start below end collect i))
>      RANGE
>      >(progn
>         (setf *foo* (range 0 200000))
>         (length *foo*))
>      200000
>      (time (reduce #'+ *foo*))
>      real time       :    852.200 secs
>      run-gbc time    :    839.160 secs
>      child run time  :      0.000 secs
>      gbc time        :      0.100 secs
>      19999900000
> In CLisp, the computation took less than a second:
>      [1]> (defun range (start end)
>              (loop for i from start below end collect i))
>      RANGE
>      [2]> (progn
>         (setf *foo* (range 0 200000))
>         (length *foo*))
>      200000
>      [3]> (time (reduce #'+ *foo*))
>      Real time: 0.109255 sec.
>      Run time: 0.108007 sec.
>      Space: 3107312 Bytes
>      GC: 3, GC time: 0.048003 sec.
>      19999900000
> Why is this?  (I'm running GCL (GNU Common Lisp)  2.6.8 ANSI    Aug  2 2007 
> 17:12:54 on Ubuntu Gutsy).  How would I go about finding out the
> bottleneck in gcl_seqlib.lsp?
> Any advice would be much appreciated. 
> Thanks,
> Bill Six
> 
> _______________________________________________
> Gcl-devel mailing list
> address@hidden
> http://lists.gnu.org/mailman/listinfo/gcl-devel

-- 
Camm Maguire                                            address@hidden
==========================================================================
"The earth is but one country, and mankind its citizens."  --  Baha'u'llah