Subject: make-array with initial-contents in gcl is slow
From: John Lapeyre
Date: Wed, 18 Jan 2012 15:41:23 +0100
In gcl make-array with :initial-contents from a list
is poorly implemented in that the copying is O(n^2).
A test on one machine shows that initializing a
list of length of 5 10^4 takes 1 minute in gcl and a few ms in sbcl.
This potentially affects some code in the share directory.
The relevant part of the gcl code in make-array is:
((= (length dimensions) 1)
(let ((x (si:make-vector element-type (car dimensions)
adjustable fill-pointer
displaced-to displaced-index-offset
static initial-element)))
(when initial-contents-supplied-p
(do ((n (car dimensions))
(i 0 (1+ i)))
((>= i n))
(declare (fixnum n i))
(si:aset x i (elt initial-contents i))))
x))
The following passed a quick test:
((= (length dimensions) 1)
(let ((x (si:make-vector element-type (car dimensions)
adjustable fill-pointer
displaced-to displaced-index-offset
static initial-element)))
(when initial-contents-supplied-p
(if (listp initial-contents)
(do ( (e initial-contents (cdr e))
(i 0 (1+ i)))
((null e))
(declare (fixnum i))
(si:aset x i (car e)))
(do ((n (car dimensions))
(i 0 (1+ i)))
((>= i n))
(declare (fixnum n i))
(si:aset x i (elt initial-contents i)))))
x))
-- John Lapeyre