Specialized arrays, what to expect?
in [Lisp]
|
From: Waldek Hebisch on 2 Jan 2010 21:30 Suppose we have array constructed like below: (setf a (make-array 1000 :element-type '(unsigned-byte 13))) What is expected representation of such array? Of course, implementation could just use generic arrays, but what do Lispers expect? One choice is 16 bit machine integers. Another possibility is to use packed array of 13 bit numbers. I wonder it this second representation is considered reasonable. Let me note that packed representation saves some space, but may be quite slow (in practice it may be slower than generic array). -- Waldek Hebisch hebisch(a)math.uni.wroc.pl
From: Barry Margolin on 2 Jan 2010 21:50 In article <hhovh3$lsv$1(a)z-news.wcss.wroc.pl>, Waldek Hebisch <hebisch(a)math.uni.wroc.pl> wrote: > Suppose we have array constructed like below: > > (setf a (make-array 1000 :element-type '(unsigned-byte 13))) > > What is expected representation of such array? Of course, > implementation could just use generic arrays, but what do Lispers > expect? One choice is 16 bit machine integers. Another possibility > is to use packed array of 13 bit numbers. I wonder it this second > representation is considered reasonable. Let me note that packed > representation saves some space, but may be quite slow (in practice > it may be slower than generic array). Very few machines have efficient mechanisms for dealing with packed 13-bit objects. I'd expect most implementations to use 16 bit machine integers. One could imagine an implementation that used the setting of the SPACE and TIME optimization settings at the time of creation to decide how to implement it. But I wouldn't bet on anyone going to that length. -- Barry Margolin, barmar(a)alum.mit.edu Arlington, MA *** PLEASE post questions in newsgroups, not directly to me *** *** PLEASE don't copy me on replies, I'll read them in the group ***
From: D Herring on 2 Jan 2010 22:56 Waldek Hebisch wrote: > Suppose we have array constructed like below: > > (setf a (make-array 1000 :element-type '(unsigned-byte 13))) > > What is expected representation of such array? Of course, > implementation could just use generic arrays, but what do Lispers > expect? One choice is 16 bit machine integers. Another possibility > is to use packed array of 13 bit numbers. I wonder it this second > representation is considered reasonable. Let me note that packed > representation saves some space, but may be quite slow (in practice > it may be slower than generic array). I would expect an array of 16-bit objects. To get an array of 13-bit chunks, I would write my own code on top of bit-vector. To explain this, CL hides the actual machine representation fairly well (e.g. a fixnum is most of a 32-bit integer). So I would expect a CL to store 13-bit numbers in a generally efficient way (i.e. byte-aligned) since the user generally doesn't care about the actual memory layout. By using a bit-vector, I can express the desire to have a tight packing. - Daniel
From: Waldek Hebisch on 3 Jan 2010 00:58 Barry Margolin <barmar(a)alum.mit.edu> wrote: > In article <hhovh3$lsv$1(a)z-news.wcss.wroc.pl>, > Waldek Hebisch <hebisch(a)math.uni.wroc.pl> wrote: > > > Suppose we have array constructed like below: > > > > (setf a (make-array 1000 :element-type '(unsigned-byte 13))) > > > > What is expected representation of such array? Of course, > > implementation could just use generic arrays, but what do Lispers > > expect? One choice is 16 bit machine integers. Another possibility > > is to use packed array of 13 bit numbers. I wonder it this second > > representation is considered reasonable. Let me note that packed > > representation saves some space, but may be quite slow (in practice > > it may be slower than generic array). > > Very few machines have efficient mechanisms for dealing with packed > 13-bit objects. I'd expect most implementations to use 16 bit machine > integers. > So do I. But one real implementation (Poplog) ATM actually creates packed arrays... > One could imagine an implementation that used the setting of the SPACE > and TIME optimization settings at the time of creation to decide how to > implement it. But I wouldn't bet on anyone going to that length. > I would be very surprised to such an implementation. Declarations available at place where array is used contain only information about type, but no information about optimization settinngs at point where array was created. So making array representaion dependent on optimization setting would require runtime dispatching even when type is declared. Looks like very bad tradeoff: why spent a lot of effort "optimizing" implementation when the result is inability to apply most important optimization? -- Waldek Hebisch hebisch(a)math.uni.wroc.pl
From: Rob Warnock on 3 Jan 2010 05:26 Waldek Hebisch <hebisch(a)math.uni.wroc.pl> wrote: +--------------- | Suppose we have array constructed like below: | | (setf a (make-array 1000 :element-type '(unsigned-byte 13))) | | What is expected representation of such array? +--------------- See CLHS "Function UPGRADED-ARRAY-ELEMENT-TYPE". It very much depends upon the implementation. CMUCL-19c, for example, will pad out 13-bit things to "shorts" for both unsigned & signed: cmu> (upgraded-array-element-type '(unsigned-byte 13)) (UNSIGNED-BYTE 16) cmu> (upgraded-array-element-type '(signed-byte 13)) (SIGNED-BYTE 16) cmu> Whereas in SBCL-0.9.8, on the other hand, the results differ slightly: * (upgraded-array-element-type '(unsigned-byte 13)) (UNSIGNED-BYTE 15) * (upgraded-array-element-type '(signed-byte 13)) (SIGNED-BYTE 16) * But in CLISP-2.36 the differences are even larger: [1]> (upgraded-array-element-type '(unsigned-byte 13)) (UNSIGNED-BYTE 16) [2]> (upgraded-array-element-type '(signed-byte 13)) T [3]> Basically, it just depends on the implementation's choice of tradeoffs. -Rob ----- Rob Warnock <rpw3(a)rpw3.org> 627 26th Avenue <URL:http://rpw3.org/> San Mateo, CA 94403 (650)572-2607
|
Pages: 1 Prev: What is the best way to process this list Next: A example in SICP |