[Ecls-list] About new_cons branch

[Juan Jose Garcia-Ripoll]

Hi,

it seems I am getting some real improvements there. As I mentioned,
creating the LIST type and moving NIL there, reduces quite
significantly the amount of checks to be done when looping over lists,
concatenating them, etc. By coding the list routines I am getting
speedups of up to 50% in some routines. Just to show this, the
following is a benchmark of current ECL (main branch, no improvements)

Name         Real(s)    Run(s)    GC(kb)    Repetitions
NCONC-2        0.488     .4783     15626        1000000
NCONC-3        .4998     .4925     31251        1000000
LIST*          0.897     .8823    156251        1000000
LIST           .8975     .8703    156251        1000000
APPEND         .8293     .8145    156251         100000
MAKE-LIST      .7632     .7528    156251         100000
COPY-LIST      0.823     .8045    156251         100000
COPY-ALIST     .8338     .8212    156251         100000
LAST-0         .4167     0.413         1        1000000
LAST-1         .4138     .4097         1        1000000
LAST-2         .4147     .4097         1        1000000

And this is what the new_cons branch produces

Name         Real(s)    Run(s)    GC(kb)    Repetitions
NCONC-2        .3175     .3117     15626        1000000
NCONC-3        .4317     .4247     31251        1000000
LIST*          .5905     .5797    156251        1000000
LIST           0.577     0.567    156251        1000000
APPEND         .4885     .4758    157814         100000
MAKE-LIST      .4892     .4778    156251         100000
COPY-LIST      .4845     .4648    156251         100000
COPY-ALIST     .5415     .5292    156251         100000
LAST-0         .2753     .2702         1        1000000
LAST-1         .2485     0.243         1        1000000
LAST-2         .2745     .2712         1        1000000

We are not yet there. I expect further improvements by turning NIL
into a fixed word, namely 0x00003, instead of reference to a global
variable. The reason is that, at least on Mac OS X, when NIL is a
global variable, a function has to be called to find its address.
However, this is an even more delicate change and will be postponed
until more functions operating with lists have been optimized / fixed.

Juanjo

P.S.: This is the code I use to benchmark the implementation.
MAKE-LIST serves as a reference, because, since it only involves
consing simple objects, a function creating lists cannot really get
much faster than that.

(defvar *forms*
  '((nconc-2	(setf x (cdr (nconc x (list 1))))		1000000)
    (nconc-3	(setf x (cddr (nconc x (list 1) (list 2))))	1000000)
    (list*	(list* 0 1 2 3 4 5 6 7 8 9 10)			1000000)
    (list	(list 0 1 2 3 4 5 6 7 8 9)			1000000)
    (append	(locally (declare (notinline append))
		  (append x '(1)))				100000)
    (make-list	(make-list 100)					100000)
    (copy-list	(copy-list x)					100000)
    (copy-alist	(copy-alist x)					100000)
    (last-0	(last x 0)					1000000)
    (last-1	(last x)					1000000)
    (last-2	(last x 2)					1000000)
))

(defun test1 (compiled-form)
  (si:gc t)
  (let* ((gc-start (si::gc-stats t))
	 (real-start (get-internal-real-time))
	 (run-start (get-internal-run-time)))
    (funcall compiled-form)
    (let* ((real-end (get-internal-real-time))
	   (run-end (get-internal-run-time))
           (gc-end (progn (si:gc t) (si::gc-stats nil))))
      (values
       (/ (- real-end real-start) internal-time-units-per-second)
       (/ (- run-end run-start) internal-time-units-per-second)
       (- gc-end gc-start)))))

(defun compile-test (record)
  (let* ((form (second record))
	 (times (third record))
	 (s-form `(lambda ()
		    (let ((x (make-list 100)))
		      (dotimes (i ,times)
			,form))))
	 (form (let ((*compile-verbose* nil)) (compile 'nil s-form))))
    (list (first record) form (third record))))

(defun test (name form times)
  (let* ((real 0)
	 (run 0)
	 (gc 0)
	 (repetitions 6))
    (dotimes (i repetitions)
      (multiple-value-bind (r rn g)
	  (test1 form)
	(incf real r)
	(incf run rn)
	(incf gc g)))
    (format t "~10A     ~5F     ~5F~10D~15D~%"
	    name (float (/ real repetitions)) (float (/ run repetitions))
	    (floor gc (* repetitions 1024))
	    times)
    (force-output *standard-output*)))

(require 'cmp)
(terpri)
(format t "~10A~@10A~@10A~@10A~@15A~%"
	"Name" "Real(s)" "Run(s)" "GC(kb)" "Repetitions")
(dolist (i (mapcar #'compile-test *forms*))
  (apply #'test i))
(quit)



-- 
Facultad de Fisicas, Universidad Complutense,
Ciudad Universitaria s/n Madrid 28040 (Spain)
http://juanjose.garciaripoll.googlepages.com