X-Git-Url: http://repo.macrolet.net/gitweb/?a=blobdiff_plain;f=src%2Fcode%2Farray.lisp;h=b1239ca8a2e56ea4663a94b148bd4246fc24be6d;hb=4191783c20fc6f86afe4b3fe73e79b075a08cc43;hp=9b8088a9e09c9b9767ca9c301c60b95f47e251b3;hpb=4898ef32c639b1c7f4ee13a5ba566ce6debd03e6;p=sbcl.git diff --git a/src/code/array.lisp b/src/code/array.lisp index 9b8088a..b1239ca 100644 --- a/src/code/array.lisp +++ b/src/code/array.lisp @@ -46,8 +46,11 @@ (fixnum index)) (%check-bound array bound index)) +(defun %with-array-data/fp (array start end) + (%with-array-data-macro array start end :check-bounds t :check-fill-pointer t)) + (defun %with-array-data (array start end) - (%with-array-data-macro array start end :fail-inline? t)) + (%with-array-data-macro array start end :check-bounds t :check-fill-pointer nil)) (defun %data-vector-and-index (array index) (if (array-header-p array) @@ -55,14 +58,6 @@ (%with-array-data array index nil) (values vector index)) (values array index))) - -;;; It'd waste space to expand copies of error handling in every -;;; inline %WITH-ARRAY-DATA, so we have them call this function -;;; instead. This is just a wrapper which is known never to return. -(defun failed-%with-array-data (array start end) - (declare (notinline %with-array-data)) - (%with-array-data array start end) - (bug "called FAILED-%WITH-ARRAY-DATA with valid array parameters?")) ;;;; MAKE-ARRAY (eval-when (:compile-toplevel :execute) @@ -149,6 +144,11 @@ (declare (fixnum array-rank)) (when (and displaced-index-offset (null displaced-to)) (error "can't specify :DISPLACED-INDEX-OFFSET without :DISPLACED-TO")) + (when (and displaced-to + (arrayp displaced-to) + (not (equal (array-element-type displaced-to) + (upgraded-array-element-type element-type)))) + (error "Array element type of :DISPLACED-TO array does not match specified element type")) (if (and simple (= array-rank 1)) ;; it's a (SIMPLE-ARRAY * (*)) (multiple-value-bind (type n-bits) @@ -306,49 +306,166 @@ of specialized arrays is supported." (fill-data-vector data dimensions initial-contents))) data)) -(defun fill-data-vector (vector dimensions initial-contents) - (let ((index 0)) - (labels ((frob (axis dims contents) - (cond ((null dims) - (setf (aref vector index) contents) - (incf index)) - (t - (unless (typep contents 'sequence) - (error "malformed :INITIAL-CONTENTS: ~S is not a ~ - sequence, but ~W more layer~:P needed." - contents - (- (length dimensions) axis))) - (unless (= (length contents) (car dims)) - (error "malformed :INITIAL-CONTENTS: Dimension of ~ - axis ~W is ~W, but ~S is ~W long." - axis (car dims) contents (length contents))) - (if (listp contents) - (dolist (content contents) - (frob (1+ axis) (cdr dims) content)) - (dotimes (i (length contents)) - (frob (1+ axis) (cdr dims) (aref contents i)))))))) - (frob 0 dimensions initial-contents)))) - (defun vector (&rest objects) #!+sb-doc "Construct a SIMPLE-VECTOR from the given objects." (coerce (the list objects) 'simple-vector)) + ;;;; accessor/setter functions -(defun hairy-data-vector-ref (array index) - (with-array-data ((vector array) (index index) (end)) - (declare (ignore end)) - (etypecase vector . - #.(map 'list - (lambda (saetp) - (let* ((type (sb!vm:saetp-specifier saetp)) - (atype `(simple-array ,type (*)))) - `(,atype - (data-vector-ref (the ,atype vector) index)))) - (sort - (copy-seq - sb!vm:*specialized-array-element-type-properties*) - #'> :key #'sb!vm:saetp-importance))))) + +;;; Dispatch to an optimized routine the data vector accessors for +;;; each different specialized vector type. Do dispatching by looking +;;; up the widetag in the array rather than with the typecases, which +;;; as of 1.0.5 compiles to a naive sequence of linear TYPEPs. Also +;;; provide separate versions where bounds checking has been moved +;;; from the callee to the caller, since it's much cheaper to do once +;;; the type information is available. Finally, for each of these +;;; routines also provide a slow path, taken for arrays that are not +;;; vectors or not simple. +(macrolet ((def (name table-name) + `(progn + (defvar ,table-name) + (defmacro ,name (array-var) + `(the function + (let ((tag 0) + (offset + #.(ecase sb!c:*backend-byte-order* + (:little-endian + (- sb!vm:other-pointer-lowtag)) + (:big-endian + (- (1- sb!vm:n-word-bytes) sb!vm:other-pointer-lowtag))))) + ;; WIDETAG-OF needs extra code to handle LIST and + ;; FUNCTION lowtags. We're only dispatching on + ;; other pointers, so let's do the lowtag + ;; extraction manually. + (when (sb!vm::%other-pointer-p ,array-var) + (setf tag + (sb!sys:sap-ref-8 (int-sap (get-lisp-obj-address ,array-var)) + offset))) + ;; SYMBOL-GLOBAL-VALUE is a performance hack + ;; for threaded builds. + (svref (sb!vm::symbol-global-value ',',table-name) tag))))))) + (def !find-data-vector-setter *data-vector-setters*) + (def !find-data-vector-setter/check-bounds *data-vector-setters/check-bounds*) + (def !find-data-vector-reffer *data-vector-reffers*) + (def !find-data-vector-reffer/check-bounds *data-vector-reffers/check-bounds*)) + +(macrolet ((%ref (accessor-getter extra-params) + `(funcall (,accessor-getter array) array index ,@extra-params)) + (define (accessor-name slow-accessor-name accessor-getter + extra-params check-bounds) + `(progn + (defun ,accessor-name (array index ,@extra-params) + (declare (optimize speed + ;; (SAFETY 0) is ok. All calls to + ;; these functions are generated by + ;; the compiler, so argument count + ;; checking isn't needed. Type checking + ;; is done implicitly via the widetag + ;; dispatch. + (safety 0))) + (%ref ,accessor-getter ,extra-params)) + (defun ,slow-accessor-name (array index ,@extra-params) + (declare (optimize speed (safety 0))) + (if (not (%array-displaced-p array)) + ;; The reasonably quick path of non-displaced complex + ;; arrays. + (let ((array (%array-data-vector array))) + (%ref ,accessor-getter ,extra-params)) + ;; The real slow path. + (with-array-data + ((vector array) + (index (locally + (declare (optimize (speed 1) (safety 1))) + (,@check-bounds index))) + (end) + :force-inline t) + (declare (ignore end)) + (,accessor-name vector index ,@extra-params))))))) + (define hairy-data-vector-ref slow-hairy-data-vector-ref + !find-data-vector-reffer + nil (progn)) + (define hairy-data-vector-set slow-hairy-data-vector-set + !find-data-vector-setter + (new-value) (progn)) + (define hairy-data-vector-ref/check-bounds + slow-hairy-data-vector-ref/check-bounds + !find-data-vector-reffer/check-bounds + nil (%check-bound array (array-dimension array 0))) + (define hairy-data-vector-set/check-bounds + slow-hairy-data-vector-set/check-bounds + !find-data-vector-setter/check-bounds + (new-value) (%check-bound array (array-dimension array 0)))) + +(defun hairy-ref-error (array index &optional new-value) + (declare (ignore index new-value)) + (error 'type-error + :datum array + :expected-type 'vector)) + +;;; Populate the dispatch tables. +(macrolet ((define-reffer (saetp check-form) + (let* ((type (sb!vm:saetp-specifier saetp)) + (atype `(simple-array ,type (*)))) + `(named-lambda optimized-data-vector-ref (vector index) + (declare (optimize speed (safety 0))) + (data-vector-ref (the ,atype vector) + (locally + (declare (optimize (safety 1))) + (the index + (,@check-form index))))))) + (define-setter (saetp check-form) + (let* ((type (sb!vm:saetp-specifier saetp)) + (atype `(simple-array ,type (*)))) + `(named-lambda optimized-data-vector-set (vector index new-value) + (declare (optimize speed (safety 0))) + (data-vector-set (the ,atype vector) + (locally + (declare (optimize (safety 1))) + (the index + (,@check-form index))) + (locally + ;; SPEED 1 needed to avoid the compiler + ;; from downgrading the type check to + ;; a cheaper one. + (declare (optimize (speed 1) + (safety 1))) + (the ,type new-value))) + ;; For specialized arrays, the return from + ;; data-vector-set would have to be reboxed to be a + ;; (Lisp) return value; instead, we use the + ;; already-boxed value as the return. + new-value))) + (define-reffers (symbol deffer check-form slow-path) + `(progn + (setf ,symbol (make-array sb!vm::widetag-mask + :initial-element #'hairy-ref-error)) + ,@(loop for widetag in '(sb!vm:complex-vector-widetag + sb!vm:complex-vector-nil-widetag + sb!vm:complex-bit-vector-widetag + #!+sb-unicode sb!vm:complex-character-string-widetag + sb!vm:complex-base-string-widetag + sb!vm:simple-array-widetag + sb!vm:complex-array-widetag) + collect `(setf (svref ,symbol ,widetag) ,slow-path)) + ,@(loop for saetp across sb!vm:*specialized-array-element-type-properties* + for widetag = (sb!vm:saetp-typecode saetp) + collect `(setf (svref ,symbol ,widetag) + (,deffer ,saetp ,check-form)))))) + (defun !hairy-data-vector-reffer-init () + (define-reffers *data-vector-reffers* define-reffer + (progn) + #'slow-hairy-data-vector-ref) + (define-reffers *data-vector-setters* define-setter + (progn) + #'slow-hairy-data-vector-set) + (define-reffers *data-vector-reffers/check-bounds* define-reffer + (%check-bound vector (length vector)) + #'slow-hairy-data-vector-ref/check-bounds) + (define-reffers *data-vector-setters/check-bounds* define-setter + (%check-bound vector (length vector)) + #'slow-hairy-data-vector-set/check-bounds))) ;;; (Ordinary DATA-VECTOR-REF usage compiles into a vop, but ;;; DATA-VECTOR-REF is also FOLDABLE, and this ordinary function @@ -356,27 +473,8 @@ of specialized arrays is supported." (defun data-vector-ref (array index) (hairy-data-vector-ref array index)) -(defun hairy-data-vector-set (array index new-value) - (with-array-data ((vector array) (index index) (end)) - (declare (ignore end)) - (etypecase vector . - #.(map 'list - (lambda (saetp) - (let* ((type (sb!vm:saetp-specifier saetp)) - (atype `(simple-array ,type (*)))) - `(,atype - (data-vector-set (the ,atype vector) index - (the ,type new-value)) - ;; For specialized arrays, the return from - ;; data-vector-set would have to be - ;; reboxed to be a (Lisp) return value; - ;; instead, we use the already-boxed value - ;; as the return. - new-value))) - (sort - (copy-seq - sb!vm:*specialized-array-element-type-properties*) - #'> :key #'sb!vm:saetp-importance))))) +(defun data-vector-ref-with-offset (array index offset) + (hairy-data-vector-ref array (+ index offset))) ;;; SUBSCRIPTS has a dynamic-extent list structure and is destroyed (defun %array-row-major-index (array subscripts @@ -429,17 +527,17 @@ of specialized arrays is supported." t)) (defun array-row-major-index (array &rest subscripts) - (declare (dynamic-extent subscripts)) + (declare (truly-dynamic-extent subscripts)) (%array-row-major-index array subscripts)) (defun aref (array &rest subscripts) #!+sb-doc "Return the element of the ARRAY specified by the SUBSCRIPTS." - (declare (dynamic-extent subscripts)) + (declare (truly-dynamic-extent subscripts)) (row-major-aref array (%array-row-major-index array subscripts))) (defun %aset (array &rest stuff) - (declare (dynamic-extent stuff)) + (declare (truly-dynamic-extent stuff)) (let ((subscripts (butlast stuff)) (new-value (car (last stuff)))) (setf (row-major-aref array (%array-row-major-index array subscripts)) @@ -472,7 +570,7 @@ of specialized arrays is supported." #!-sb-fluid (declaim (inline (setf aref))) (defun (setf aref) (new-value array &rest subscripts) - (declare (dynamic-extent subscripts)) + (declare (truly-dynamic-extent subscripts)) (declare (type array array)) (setf (row-major-aref array (%array-row-major-index array subscripts)) new-value)) @@ -670,31 +768,37 @@ of specialized arrays is supported." (declare (array array)) (and (array-header-p array) (%array-fill-pointer-p array))) +(defun fill-pointer-error (vector arg) + (cond (arg + (aver (array-has-fill-pointer-p vector)) + (let ((max (%array-available-elements vector))) + (error 'simple-type-error + :datum arg + :expected-type (list 'integer 0 max) + :format-control "The new fill pointer, ~S, is larger than the length of the vector (~S.)" + :format-arguments (list arg max)))) + (t + (error 'simple-type-error + :datum vector + :expected-type '(and vector (satisfies array-has-fill-pointer-p)) + :format-control "~S is not an array with a fill pointer." + :format-arguments (list vector))))) + (defun fill-pointer (vector) #!+sb-doc "Return the FILL-POINTER of the given VECTOR." - (declare (vector vector)) - (if (and (array-header-p vector) (%array-fill-pointer-p vector)) + (if (array-has-fill-pointer-p vector) (%array-fill-pointer vector) - (error 'simple-type-error - :datum vector - :expected-type '(and vector (satisfies array-has-fill-pointer-p)) - :format-control "~S is not an array with a fill pointer." - :format-arguments (list vector)))) + (fill-pointer-error vector nil))) (defun %set-fill-pointer (vector new) - (declare (vector vector) (fixnum new)) - (if (and (array-header-p vector) (%array-fill-pointer-p vector)) - (if (> new (%array-available-elements vector)) - (error - "The new fill pointer, ~S, is larger than the length of the vector." - new) - (setf (%array-fill-pointer vector) new)) - (error 'simple-type-error - :datum vector - :expected-type '(and vector (satisfies array-has-fill-pointer-p)) - :format-control "~S is not an array with a fill pointer." - :format-arguments (list vector)))) + (flet ((oops (x) + (fill-pointer-error vector x))) + (if (array-has-fill-pointer-p vector) + (if (> new (%array-available-elements vector)) + (oops new) + (setf (%array-fill-pointer vector) new)) + (oops nil)))) ;;; FIXME: It'd probably make sense to use a MACROLET to share the ;;; guts of VECTOR-PUSH between VECTOR-PUSH-EXTEND. Such a macro @@ -713,19 +817,23 @@ of specialized arrays is supported." (cond ((= fill-pointer (%array-available-elements array)) nil) (t - (setf (aref array fill-pointer) new-el) + (locally (declare (optimize (safety 0))) + (setf (aref array fill-pointer) new-el)) (setf (%array-fill-pointer array) (1+ fill-pointer)) fill-pointer)))) (defun vector-push-extend (new-element vector &optional - (extension (1+ (length vector)))) - (declare (vector vector) (fixnum extension)) + (min-extension + (let ((length (length vector))) + (min (1+ length) + (- array-dimension-limit length))))) + (declare (vector vector) (fixnum min-extension)) (let ((fill-pointer (fill-pointer vector))) (declare (fixnum fill-pointer)) (when (= fill-pointer (%array-available-elements vector)) - (adjust-array vector (+ fill-pointer extension))) + (adjust-array vector (+ fill-pointer (max 1 min-extension)))) ;; disable bounds checking (locally (declare (optimize (safety 0))) (setf (aref vector fill-pointer) new-element)) @@ -764,7 +872,11 @@ of specialized arrays is supported." (error "The number of dimensions not equal to rank of array.")) ((not (subtypep element-type (array-element-type array))) (error "The new element type, ~S, is incompatible with old type." - element-type))) + element-type)) + ((and fill-pointer (not (array-has-fill-pointer-p array))) + (error 'type-error + :datum array + :expected-type '(satisfies array-has-fill-pointer-p)))) (let ((array-rank (length (the list dimensions)))) (declare (fixnum array-rank)) (unless (= array-rank 1) @@ -825,7 +937,8 @@ of specialized arrays is supported." (declare (fixnum old-length new-length)) (with-array-data ((old-data array) (old-start) (old-end old-length)) - (cond ((or (%array-displaced-p array) + (cond ((or (and (array-header-p array) + (%array-displaced-p array)) (< old-length new-length)) (setf new-data (data-vector-from-inits @@ -849,7 +962,8 @@ of specialized arrays is supported." (with-array-data ((old-data array) (old-start) (old-end old-length)) (declare (ignore old-end)) - (let ((new-data (if (or (%array-displaced-p array) + (let ((new-data (if (or (and (array-header-p array) + (%array-displaced-p array)) (> new-length old-length)) (data-vector-from-inits dimensions new-length @@ -865,12 +979,12 @@ of specialized arrays is supported." initial-element-p)) (if (adjustable-array-p array) (set-array-header array new-data new-length - new-length 0 dimensions nil) + nil 0 dimensions nil) (let ((new-array (make-array-header sb!vm:simple-array-widetag array-rank))) (set-array-header new-array new-data new-length - new-length 0 dimensions nil))))))))))) + nil 0 dimensions nil))))))))))) (defun get-new-fill-pointer (old-array new-array-size fill-pointer) @@ -900,8 +1014,12 @@ of specialized arrays is supported." fill-pointer)))) ;;; Destructively alter VECTOR, changing its length to NEW-LENGTH, -;;; which must be less than or equal to its current length. -(defun shrink-vector (vector new-length) +;;; which must be less than or equal to its current length. This can +;;; be called on vectors without a fill pointer but it is extremely +;;; dangerous to do so: shrinking the size of an object (as viewed by +;;; the gc) makes bounds checking unreliable in the face of interrupts +;;; or multi-threading. Call it only on provably local vectors. +(defun %shrink-vector (vector new-length) (declare (vector vector)) (unless (array-header-p vector) (macrolet ((frob (name &rest things) @@ -915,6 +1033,10 @@ of specialized arrays is supported." ,fill-value :start new-length)))) things)))) + ;; Set the 'tail' of the vector to the appropriate type of zero, + ;; "because in some cases we'll scavenge larger areas in one go, + ;; like groups of pages that had triggered the write barrier, or + ;; the whole static space" according to jsnell. #.`(frob vector ,@(map 'list (lambda (saetp) @@ -932,6 +1054,16 @@ of specialized arrays is supported." (setf (%array-fill-pointer vector) new-length) vector) +(defun shrink-vector (vector new-length) + (declare (vector vector)) + (cond + ((eq (length vector) new-length) + vector) + ((array-has-fill-pointer-p vector) + (setf (%array-fill-pointer vector) new-length) + vector) + (t (subseq vector 0 new-length)))) + ;;; Fill in array header with the provided information, and return the array. (defun set-array-header (array data length fill-pointer displacement dimensions &optional displacedp) @@ -951,47 +1083,98 @@ of specialized arrays is supported." (setf (%array-dimension array 0) dimensions)) (setf (%array-displaced-p array) displacedp) array) + +;;; User visible extension +(declaim (ftype (function (simple-array) (values (simple-array * (*)) &optional)) + simple-array-vector)) +(defun simple-array-vector (array) + "Returns the one-dimensional SIMPLE-ARRAY corresponding to ARRAY. + +The ARRAY must be a SIMPLE-ARRAY. If ARRAY is multidimensional, returns the +underlying one-dimensional SIMPLE-ARRAY which shares storage with ARRAY. +Otherwise returns ARRAY. + +Currently in SBCL a multidimensional SIMPLE-ARRAY has an underlying +one-dimensional SIMPLE-ARRAY, which holds the data in row major order. This +function provides access to that vector. + +Important note: the underlying vector is an implementation detail. Even though +this function exposes it, changes in the implementation may cause this +function to be removed without further warning." + ;; KLUDGE: Without TRULY-THE the system is not smart enough to figure out that + ;; (1) SIMPLE-ARRAY without ARRAY-HEADER-P is a vector (2) the data vector of + ;; a SIMPLE-ARRAY is a vector. + (truly-the (simple-array * (*)) + (if (array-header-p array) + (%array-data-vector array) + array))) +;;;; used by SORT + +;;; temporary vector for stable sorting vectors, allocated for each new thread +(defvar *merge-sort-temp-vector* (vector)) +(declaim (simple-vector *merge-sort-temp-vector*)) + ;;;; ZAP-ARRAY-DATA for ADJUST-ARRAY ;;; a temporary to be used when OLD-DATA and NEW-DATA are EQ. -;;; KLUDGE: Boy, DYNAMIC-EXTENT would be nice. -(defvar *zap-array-data-temp* (make-array 1000 :initial-element t)) +;;; KLUDGE: Boy, DYNAMIC-EXTENT would be nice. This is rebound +;;; to length zero array in each new thread. +;;; +;;; DX is probably a bad idea, because a with a big array it would +;;; be fairly easy to blow the stack. +(defvar *zap-array-data-temp* (vector)) +(declaim (simple-vector *zap-array-data-temp*)) -(defun zap-array-data-temp (length element-type initial-element - initial-element-p) +(defun zap-array-data-temp (length initial-element initial-element-p) (declare (fixnum length)) - (when (> length (the fixnum (length *zap-array-data-temp*))) - (setf *zap-array-data-temp* - (make-array length :initial-element t))) - (when initial-element-p - (unless (typep initial-element element-type) - (error "~S can't be used to initialize an array of type ~S." - initial-element element-type)) - (fill (the simple-vector *zap-array-data-temp*) initial-element - :end length)) - *zap-array-data-temp*) + (let ((tmp *zap-array-data-temp*)) + (declare (simple-vector tmp)) + (cond ((> length (length tmp)) + (setf *zap-array-data-temp* + (if initial-element-p + (make-array length :initial-element initial-element) + (make-array length)))) + (initial-element-p + (fill tmp initial-element :end length)) + (t + tmp)))) ;;; This does the grinding work for ADJUST-ARRAY. It zaps the data ;;; from the OLD-DATA in an arrangement specified by the OLD-DIMS to ;;; the NEW-DATA in an arrangement specified by the NEW-DIMS. OFFSET ;;; is a displaced offset to be added to computed indices of OLD-DATA. -;;; NEW-LENGTH, ELEMENT-TYPE, INITIAL-ELEMENT, and INITIAL-ELEMENT-P -;;; are used when OLD-DATA and NEW-DATA are EQ; in this case, a -;;; temporary must be used and filled appropriately. When OLD-DATA and -;;; NEW-DATA are not EQ, NEW-DATA has already been filled with any -;;; specified initial-element. (defun zap-array-data (old-data old-dims offset new-data new-dims new-length element-type initial-element initial-element-p) (declare (list old-dims new-dims)) - (setq old-dims (nreverse old-dims)) - (setq new-dims (reverse new-dims)) - (if (eq old-data new-data) - (let ((temp (zap-array-data-temp new-length element-type - initial-element initial-element-p))) - (zap-array-data-aux old-data old-dims offset temp new-dims) - (dotimes (i new-length) (setf (aref new-data i) (aref temp i)))) - (zap-array-data-aux old-data old-dims offset new-data new-dims))) + ;; OLD-DIMS comes from array-dimensions, which returns a fresh list + ;; at least in SBCL. + ;; NEW-DIMS comes from the user. + (setf old-dims (nreverse old-dims) + new-dims (reverse new-dims)) + (cond ((eq old-data new-data) + ;; NEW-LENGTH, ELEMENT-TYPE, INITIAL-ELEMENT, and + ;; INITIAL-ELEMENT-P are used when OLD-DATA and NEW-DATA are + ;; EQ; in this case, a temporary must be used and filled + ;; appropriately. specified initial-element. + (when initial-element-p + ;; FIXME: transforming this TYPEP to someting a bit faster + ;; would be a win... + (unless (typep initial-element element-type) + (error "~S can't be used to initialize an array of type ~S." + initial-element element-type))) + (let ((temp (zap-array-data-temp new-length + initial-element initial-element-p))) + (declare (simple-vector temp)) + (zap-array-data-aux old-data old-dims offset temp new-dims) + (dotimes (i new-length) + (setf (aref new-data i) (aref temp i) + ;; zero out any garbage right away + (aref temp i) 0)))) + (t + ;; When OLD-DATA and NEW-DATA are not EQ, NEW-DATA has + ;; already been filled with any + (zap-array-data-aux old-data old-dims offset new-data new-dims)))) (defun zap-array-data-aux (old-data old-dims offset new-data new-dims) (declare (fixnum offset))