NOTE: This patch has been committed. The version below is informational only (whitespace differences have been removed). ../ChangeLog addition: 2006-01-09 Didier Verna <didier(a)lrde.epita.fr> Add Common Lisp dedicated versions: * 2.0/src/dd/cl/u.cl: New (untyped version). * 2.0/src/dd/cl/t.cl: New (typed version). * 2.0/src/dd/cl/ts.cl: New (typed and sized version). Randomized versions of the files above: * 2.0/src/dd/cl/ui.cl: New. * 2.0/src/dd/cl/ti.cl: New. * 2.0/src/dd/cl/tsi.cl: New. GSC source patch: Diff command: svn diff --diff-cmd /usr/bin/diff -x "-u -t -b -B -w" Files affected: src/dd/cl/tsi.cl src/dd/cl/ui.cl src/dd/cl/ti.cl src/dd/cl/ts.cl src/dd/cl/u.cl src/dd/cl/t.cl Property changes on: src/dd/cl ___________________________________________________________________ Name: svn:ignore + *.x86f Index: src/dd/cl/t.cl =================================================================== --- src/dd/cl/t.cl (revision 0) +++ src/dd/cl/t.cl (revision 0) @@ -0,0 +1,103 @@ +;;; 1D Image assignation algorithm, typed version. + +(eval-when (:compile-toplevel) + (defvar *optimize* t) + (if *optimize* + (declaim (inline assign/mb assign/sb-aref assign/sb-svref) + (optimize (speed 3) + (compilation-speed 0) + (safety 0) + (debug 0))) + (declaim (optimize (speed 0) + (compilation-speed 0) + (safety 3) + (debug 0))))) + +(defvar *size* 800 + "Dimension for (square) images.") + +(defvar *nsteps* 200 + "Number of times to repeat the algorithm.") + + +;;; 1D Image, multibuffer implementation: + +(defun make-image/mb (size) + "Create a square 1D image using a 2D array." + ;; The following declaration doesn't optimize anything, since the problem is + ;; having a constant list in MAKE-ARRAY. + (declare (type fixnum size)) + (make-array (list size size) :initial-element 0 :element-type 'fixnum)) + +(defun assign/mb (image value) + "Add VALUE to every point of IMAGE (2D array implementation)." + (declare (type (simple-array fixnum) image)) + (declare (type fixnum value)) + (let ((size (array-dimension image 0))) + (dotimes (i size) + (declare (type fixnum i)) + (dotimes (j size) + ;; Surprisingly, CMU-CL requests the declaration of i to optimize, but + ;; not the following one ?? + (declare (type fixnum j)) + (setf (aref image i j) (+ (aref image i j) value)))))) + + +;;; 1D Image, singlebuffer / aref implementation: + +(defun make-image/sb-aref (size) + "Create a square 1D image using a 1D array." + (declare (type fixnum size)) + (make-array (* size size) :initial-element 0 :element-type 'fixnum)) + +(defun assign/sb-aref (image value) + "Add VALUE to every point of IMAGE (1D array implementation)." + (declare (type (simple-array fixnum) image)) + (declare (type fixnum value)) + (let ((size (array-dimension image 0))) + (dotimes (i size) + (setf (aref image i) (+ (aref image i) value))))) + + +;;; 1D Image, singlebuffer / svref implementation: + +(defun make-image/sb-svref (size) + "Create a square 1D image using a simple-vector." + (declare (type fixnum size)) + ;; Don't specify a type here. We're using the simple-vector approach. + (make-array (* size size) :initial-element 0)) + +(defun assign/sb-svref (image value) + "Add VALUE to every point of IMAGE (simple-vector implementation)." + (declare (type simple-vector image)) + (declare (type fixnum value)) + (let ((size (array-dimension image 0))) + (dotimes (i size) + (setf (the fixnum (svref image i)) + (+ (the fixnum (svref image i)) value))))) + + +;;; Entry point: + +(defun bench () + (let ((value 51)) + (format t ";;; ~Aptimized benches for ~D step(s):~&" + (if *optimize* "O" "Not o") *nsteps*) + (format t ";; Linear / Typed / Multibuffer:") + (let ((image (make-image/mb *size*))) + (time + (dotimes (i (the fixnum *nsteps*)) + (declare (type fixnum i)) + (assign/mb image value)))) + (format t ";; Linear / Typed / Singlebuffer / AREF:") + (let ((image (make-image/sb-aref *size*))) + (time + (dotimes (i (the fixnum *nsteps*)) + (declare (type fixnum i)) + (assign/sb-aref image value)))) + (format t ";; Linear / Typed / Singlebuffer / SVREF:") + (let ((image (make-image/sb-svref *size*))) + (time + (dotimes (i (the fixnum *nsteps*)) + (declare (type fixnum i)) + (assign/sb-svref image value)))))) Index: src/dd/cl/u.cl =================================================================== --- src/dd/cl/u.cl (revision 0) +++ src/dd/cl/u.cl (revision 0) @@ -0,0 +1,83 @@ +;;; 1D Image assignation algorithm, untyped version. + +(eval-when (:compile-toplevel) + (defvar *optimize* t) + (if *optimize* + (declaim (inline assign/mb assign/sb-aref assign/sb-svref) + (optimize (speed 3) + (compilation-speed 0) + (safety 0) + (debug 0))) + (declaim (optimize (speed 0) + (compilation-speed 0) + (safety 3) + (debug 0))))) + +(defvar *size* 800 + "Dimension for (square) images.") +(defvar *nsteps* 200 + "Number of times to repeat the algorithm.") + + +;;; 1D Image, multibuffer implementation: + +(defun make-image/mb (size) + "Create a square 1D image using a 2D array." + (make-array (list size size) :initial-element 0)) + +(defun assign/mb (image value) + "Add VALUE to every point of IMAGE (2D array implementation)." + (let ((size (array-dimension image 0))) + (dotimes (i size) + (dotimes (j size) + (setf (aref image i j) (+ (aref image i j) value)))))) + + +;;; 1D Image, singlebuffer / aref implementation: + +(defun make-image/sb-aref (size) + "Create a square 1D image using a 1D array." + (make-array (* size size) :initial-element 0)) + +(defun assign/sb-aref (image value) + "Add VALUE to every point of IMAGE (1D array implementation)." + (let ((size (array-dimension image 0))) + (dotimes (i size) + (setf (aref image i) (+ (aref image i) value))))) + + +;;; 1D Image, singlebuffer / svref implementation: + +(defun make-image/sb-svref (size) + "Create a square 1D image using a simple-vector." + (make-array (* size size) :initial-element 0)) + +(defun assign/sb-svref (image value) + "Add VALUE to every point of IMAGE (simple-vector implementation)." + (let ((size (array-dimension image 0))) + (dotimes (i size) + (setf (svref image i) (+ (svref image i) value))))) + + +;;; Entry point: + +(defun bench () + "Perform benchmarks on all implementations." + (let ((value 51)) + (format t ";;; ~Aptimized benches for ~D step(s):~&" + (if *optimize* "O" "Not o") *nsteps*) + (format t ";; Linear / Untyped / Multibuffer:") + (let ((image (make-image/mb *size*))) + (time + (dotimes (i *nsteps*) + (assign/mb image value)))) + (format t ";; Linear / Untyped / Singlebuffer / AREF:") + (let ((image (make-image/sb-aref *size*))) + (time + (dotimes (i *nsteps*) + (assign/sb-aref image value)))) + (format t ";; Linear / Untyped / Singlebuffer / SVREF:") + (let ((image (make-image/sb-svref *size*))) + (time + (dotimes (i *nsteps*) + (assign/sb-svref image value)))))) Index: src/dd/cl/ts.cl =================================================================== --- src/dd/cl/ts.cl (revision 0) +++ src/dd/cl/ts.cl (revision 0) @@ -0,0 +1,99 @@ +;;; 1D Image assignation algorithm, typed and sized version. + +(eval-when (:compile-toplevel) + (defvar *optimize* t) + (if *optimize* + (declaim (optimize (speed 3) + (compilation-speed 0) + (safety 0) + (debug 0))) + (declaim (optimize (speed 0) + (compilation-speed 0) + (safety 3) + (debug 0))))) + +(eval-when (:compile-toplevel :load-toplevel :execute) + (defvar *size* 800 + "Dimension for (square) images.")) + +(defvar *nsteps* 200 + "Number of times to repeat the algorithm.") + + +;;; 1D Image, multibuffer implementation: + +(defmacro make-image/mb (size) + "Create a square 1D image using a 2D array." + (let ((size-list (eval `(list ,size ,size)))) + `(make-array ',size-list :initial-element 0 :element-type 'fixnum))) + +(defmacro assign/mb (image value) + "Add VALUE to every point of IMAGE (2D array implementation)." + `(let ((size (array-dimension ,image 0))) + (dotimes (i size) + (declare (type fixnum i)) + (dotimes (j size) + ;; Surprisingly, CMU-CL requests the declaration of i to optimize, but + ;; not the following one ?? + (declare (type fixnum j)) + (setf (aref ,image i j) (+ (aref ,image i j) ,value)))))) + +;;; 1D Image, singlebuffer / aref implementation: + +(defmacro make-image/sb-aref (size) + "Create a square 1D image using a 1D array." + ;; Or, we could have used (the fixnum ,size) directly in MAKE-ARRAY. + `(let ((size ,size)) + (declare (type fixnum size)) + (make-array (* size size) :initial-element 0 :element-type 'fixnum))) + +(defmacro assign/sb-aref (image value) + "Add VALUE to every point of IMAGE (1D array implementation)." + `(let ((size (array-dimension ,image 0))) + (dotimes (i size) + (setf (aref ,image i) (+ (aref ,image i) ,value))))) + + +;;; 1D Image, singlebuffer / svref implementation: + +(defmacro make-image/sb-svref (size) + "Create a square 1D image using a simple-vector." + ;; Or, we could have used (the fixnum ,size) directly in MAKE-ARRAY. + `(let ((size ,size)) + (declare (type fixnum size)) + (make-array (* size size) :initial-element 0))) + +(defmacro assign/sb-svref (image value) + "Add VALUE to every point of IMAGE (simple-vector implementation)." + `(let ((size (array-dimension ,image 0))) + (dotimes (i size) + (setf (the fixnum (svref ,image i)) + (+ (the fixnum (svref ,image i)) ,value))))) + + +;;; Entry point: + +(defun bench () + "Perform benchmark on all implementations." + (let ((value 51)) + (declare (type fixnum value)) + (format t ";;; ~Aptimized benches for ~D step(s):~&" + (if *optimize* "O" "Not o") *nsteps*) + (format t ";; Linear / Typed / Sized / Multibuffer:") + (let ((image (make-image/mb *size*))) + (time + (dotimes (i (the fixnum *nsteps*)) + (declare (type fixnum i)) + (assign/mb image value)))) + (format t ";; Linear / Typed / Sized / Singlebuffer / AREF:") + (let ((image (make-image/sb-aref *size*))) + (time + (dotimes (i (the fixnum *nsteps*)) + (declare (type fixnum i)) + (assign/sb-aref image value)))) + (format t ";; Linear / Typed / Sized / Singlebuffer / SVREF:") + (let ((image (make-image/sb-svref *size*))) + (time + (dotimes (i (the fixnum *nsteps*)) + (declare (type fixnum i)) + (assign/sb-svref image value)))))) Index: src/dd/cl/ti.cl =================================================================== --- src/dd/cl/ti.cl (revision 0) +++ src/dd/cl/ti.cl (revision 0) @@ -0,0 +1,128 @@ +;;; 1D Image assignation algorithm, randomized and typed version. + +(eval-when (:compile-toplevel) + (defvar *optimize* t) + (if *optimize* + (declaim (inline assign/mb assign/sb-aref assign/sb-svref) + (optimize (speed 3) + (compilation-speed 0) + (safety 0) + (debug 0))) + (declaim (optimize (speed 0) + (compilation-speed 0) + (safety 3) + (debug 0))))) + +;; This prime number is chosen as the biggest one for which the offsets +;; increments in assign/* stay representable as a fixnum +(defconstant +offset+ 509 + "Prime number to randomize memory access.") + +(defvar *size* 800 + "Dimension for (square) images.") + +(defvar *nsteps* 200 + "Number of times to repeat the algorithm.") + + +;;; 1D Image, multibuffer implementation: + +(defun make-image/mb (size) + "Create a square 1D image using a 2D array." + ;; The following declaration doesn't optimize anything, since the problem is + ;; having a constant list in MAKE-ARRAY. + (declare (type fixnum size)) + (make-array (list size size) :initial-element 0 :element-type 'fixnum)) + +(defun assign/mb (image value) + "Add VALUE to every point of IMAGE (2D array implementation)." + (declare (type (simple-array fixnum) image)) + (declare (type fixnum value)) + (let ((size (array-dimension image 0)) + (offset-i 0) + (offset-j 0) + pos-i pos-j) + (declare (type fixnum offset-i)) + (declare (type fixnum offset-j)) + (dotimes (j size) + (declare (type fixnum j)) + (setf offset-i 0 + offset-j (+ offset-j +offset+) + pos-j (rem offset-j size)) + (dotimes (i size) + ;; Surprisingly, CMU-CL requests the declaration of i to optimize, but + ;; not the following one ?? + (declare (type fixnum i)) + (setf offset-i (+ offset-i +offset+) + pos-i (rem offset-i size) + (aref image pos-i pos-j) (+ (aref image pos-i pos-j) value)))))) + + +;;; 1D Image, singlebuffer / aref implementation: + +(defun make-image/sb-aref (size) + "Create a square 1D image using a 1D array." + (declare (type fixnum size)) + (make-array (* size size) :initial-element 0 :element-type 'fixnum)) + +(defun assign/sb-aref (image value) + "Add VALUE to every point of IMAGE (1D array implementation)." + (declare (type (simple-array fixnum) image)) + (declare (type fixnum value)) + (let ((size (array-dimension image 0)) + (offset 0) + pos) + (declare (type fixnum offset)) + (dotimes (i size) + (setf offset (+ offset +offset+) + pos (rem offset size) + (aref image pos) (+ (aref image pos) value))))) + + +;;; 1D Image, singlebuffer / svref implementation: + +(defun make-image/sb-svref (size) + "Create a square 1D image using a simple-vector." + (declare (type fixnum size)) + ;; Don't specify a type here. We're using the simple-vector approach. + (make-array (* size size) :initial-element 0)) + +(defun assign/sb-svref (image value) + "Add VALUE to every point of IMAGE (simple-vector implementation)." + (declare (type simple-vector image)) + (declare (type fixnum value)) + (let ((size (array-dimension image 0)) + (offset 0) + pos) + (declare (type fixnum offset)) + (dotimes (i size) + (setf offset (+ offset +offset+) + pos (rem offset size) + (the fixnum (svref image pos)) + (+ (the fixnum (svref image pos)) value))))) + + +;;; Entry point: + +(defun bench () + (let ((value 51)) + (format t ";;; ~Aptimized benches for ~D step(s):~&" + (if *optimize* "O" "Not o") *nsteps*) + (format t ";; Randomized / Typed / Multibuffer:") + (let ((image (make-image/mb *size*))) + (time + (dotimes (i (the fixnum *nsteps*)) + (declare (type fixnum i)) + (assign/mb image value)))) + (format t ";; Randomized / Typed / Singlebuffer / AREF:") + (let ((image (make-image/sb-aref *size*))) + (time + (dotimes (i (the fixnum *nsteps*)) + (declare (type fixnum i)) + (assign/sb-aref image value)))) + (format t ";; Randomized / Typed / Singlebuffer / SVREF:") + (let ((image (make-image/sb-svref *size*))) + (time + (dotimes (i (the fixnum *nsteps*)) + (declare (type fixnum i)) + (assign/sb-svref image value)))))) Index: src/dd/cl/ui.cl =================================================================== --- src/dd/cl/ui.cl (revision 0) +++ src/dd/cl/ui.cl (revision 0) @@ -0,0 +1,104 @@ +;;; 1D Image assignation algorithm, randomized and untyped version. + +(eval-when (:compile-toplevel) + (defvar *optimize* t) + (if *optimize* + (declaim (inline assign/mb assign/sb-aref assign/sb-svref) + (optimize (speed 3) + (compilation-speed 0) + (safety 0) + (debug 0))) + (declaim (optimize (speed 0) + (compilation-speed 0) + (safety 3) + (debug 0))))) + +;; See comment in ti.cl about this prime number +(defconstant +offset+ 509 + "Prime number to randomize memory access.") + +(defvar *size* 800 + "Dimension for (square) images.") + +(defvar *nsteps* 200 + "Number of times to repeat the algorithm.") + + +;;; 1D Image, multibuffer implementation: + +(defun make-image/mb (size) + "Create a square 1D image using a 2D array." + (make-array (list size size) :initial-element 0)) + +(defun assign/mb (image value) + "Add VALUE to every point of IMAGE (2D array implementation)." + (let ((size (array-dimension image 0)) + offset-i + (offset-j 0) + pos-i pos-j) + (dotimes (j size) + (setf offset-i 0 + offset-j (+ offset-j +offset+) + pos-j (rem offset-j size)) + (dotimes (i size) + (setf offset-i (+ offset-i +offset+) + pos-i (rem offset-i size) + (aref image pos-i pos-j) (+ (aref image pos-i pos-j) value)))))) + + +;;; 1D Image, singlebuffer / aref implementation: + +(defun make-image/sb-aref (size) + "Create a square 1D image using a 1D array." + (make-array (* size size) :initial-element 0)) + +(defun assign/sb-aref (image value) + "Add VALUE to every point of IMAGE (1D array implementation)." + (let ((size (array-dimension image 0)) + (offset 0) + pos) + (dotimes (i size) + (setf offset (+ offset +offset+) + pos (rem offset size) + (aref image pos) (+ (aref image pos) value))))) + + +;;; 1D Image, singlebuffer / svref implementation: + +(defun make-image/sb-svref (size) + "Create a square 1D image using a simple-vector." + (make-array (* size size) :initial-element 0)) + +(defun assign/sb-svref (image value) + "Add VALUE to every point of IMAGE (simple-vector implementation)." + (let ((size (array-dimension image 0)) + (offset 0) + pos) + (dotimes (i size) + (setf offset (+ offset +offset+) + pos (rem offset size) + (svref image pos) (+ (svref image pos) value))))) + + +;;; Entry point: + +(defun bench () + "Perform benchmarks on all implementations." + (let ((value 51)) + (format t ";;; ~Aptimized benches for ~D step(s):~&" + (if *optimize* "O" "Not o") *nsteps*) + (format t ";; Randomized / Untyped / Multibuffer:") + (let ((image (make-image/mb *size*))) + (time + (dotimes (i *nsteps*) + (assign/mb image value)))) + (format t ";; Randomized / Untyped / Singlebuffer / AREF:") + (let ((image (make-image/sb-aref *size*))) + (time + (dotimes (i *nsteps*) + (assign/sb-aref image value)))) + (format t ";; Randomized / Untyped / Singlebuffer / SVREF:") + (let ((image (make-image/sb-svref *size*))) + (time + (dotimes (i *nsteps*) + (assign/sb-svref image value)))))) Index: src/dd/cl/tsi.cl =================================================================== --- src/dd/cl/tsi.cl (revision 0) +++ src/dd/cl/tsi.cl (revision 0) @@ -0,0 +1,124 @@ +;;; 1D Image assignation algorithm, randomized, typed and sized version. + +(eval-when (:compile-toplevel) + (defvar *optimize* t) + (if *optimize* + (declaim (optimize (speed 3) + (compilation-speed 0) + (safety 0) + (debug 0))) + (declaim (optimize (speed 0) + (compilation-speed 0) + (safety 3) + (debug 0))))) + +;; See comment in ti.cl about this prime number +(defconstant +offset+ 509 + "Prime number to randomize memory access.") + +(eval-when (:compile-toplevel :load-toplevel :execute) + (defvar *size* 1024 + "Dimension for (square) images.")) + +(defvar *nsteps* 100 + "Number of times to repeat the algorithm.") + + +;;; 1D Image, multibuffer implementation: + +(defmacro make-image/mb (size) + "Create a square 1D image using a 2D array." + (let ((size-list (eval `(list ,size ,size)))) + `(make-array ',size-list :initial-element 0 :element-type 'fixnum))) + +(defmacro assign/mb (image value) + "Add VALUE to every point of IMAGE (2D array implementation)." + `(let ((size (array-dimension ,image 0)) + (offset-i 0) + (offset-j 0) + pos-i pos-j) + (declare (type fixnum offset-i)) + (declare (type fixnum offset-j)) + (dotimes (j size) + (declare (type fixnum j)) + (setf offset-i 0 + offset-j (+ offset-j +offset+) + pos-j (rem offset-j size)) + (dotimes (i size) + ;; Surprisingly, CMU-CL requests the declaration of i to optimize, but + ;; not the following one ?? + (declare (type fixnum i)) + (setf offset-i (+ offset-i +offset+) + pos-i (rem offset-i size) + (aref ,image pos-i pos-j) (+ (aref ,image pos-i pos-j) + ,value)))))) + +;;; 1D Image, singlebuffer / aref implementation: + +(defmacro make-image/sb-aref (size) + "Create a square 1D image using a 1D array." + ;; Or, we could have used (the fixnum ,size) directly in MAKE-ARRAY. + `(let ((size ,size)) + (declare (type fixnum size)) + (make-array (* size size) :initial-element 0 :element-type 'fixnum))) + +(defmacro assign/sb-aref (image value) + "Add VALUE to every point of IMAGE (1D array implementation)." + `(let ((size (array-dimension ,image 0)) + (offset 0) + pos) + (declare (type fixnum offset)) + (dotimes (i size) + (setf offset (+ offset +offset+) + pos (rem offset size) + (aref ,image pos) (+ (aref ,image pos) ,value))))) + + +;;; 1D Image, singlebuffer / svref implementation: + +(defmacro make-image/sb-svref (size) + "Create a square 1D image using a simple-vector." + ;; Or, we could have used (the fixnum ,size) directly in MAKE-ARRAY. + `(let ((size ,size)) + (declare (type fixnum size)) + (make-array (* size size) :initial-element 0))) + +(defmacro assign/sb-svref (image value) + "Add VALUE to every point of IMAGE (simple-vector implementation)." + `(let ((size (array-dimension ,image 0)) + (offset 0) + pos) + (declare (type fixnum offset)) + (dotimes (i size) + (setf offset (+ offset +offset+) + pos (rem offset size) + (the fixnum (svref ,image pos)) (+ (the fixnum (svref ,image pos)) + ,value))))) + + +;;; Entry point: + +(defun bench () + "Perform benchmark on all implementations." + (let ((value 51)) + (declare (type fixnum value)) + (format t ";;; ~Aptimized benches for ~D step(s):~&" + (if *optimize* "O" "Not o") *nsteps*) + (format t ";; Randomized / Typed / Sized / Multibuffer:") + (let ((image (make-image/mb *size*))) + (time + (dotimes (i (the fixnum *nsteps*)) + (declare (type fixnum i)) + (assign/mb image value)))) + (format t ";; Randomized / Typed / Sized / Singlebuffer / AREF:") + (let ((image (make-image/sb-aref *size*))) + (time + (dotimes (i (the fixnum *nsteps*)) + (declare (type fixnum i)) + (assign/sb-aref image value)))) + (format t ";; Randomized / Typed / Sized / Singlebuffer / SVREF:") + (let ((image (make-image/sb-svref *size*))) + (time + (dotimes (i (the fixnum *nsteps*)) + (declare (type fixnum i)) + (assign/sb-svref image value)))))) -- Didier Verna, didier(a)lrde.epita.fr, http://www.lrde.epita.fr/~didier EPITA / LRDE, 14-16 rue Voltaire Tel.+33 (1) 44 08 01 85 94276 Le Kremlin-Bicêtre, France Fax.+33 (1) 53 14 59 22 didier(a)xemacs.org