From: Fredrik T. <fr...@do...> - 2010-04-25 19:17:51
|
Hi list, How would I do to create a very large array of some structure in SBCL to be as memory-conservative as possible? Consider the following code: (defstruct test a b) (type-of (make-array '(10 10) :element-type 'test)) SBCL tells me that the type of the array is a (simple-array t (10 10)), and I guess that means that it's effectively holding pointers to structs. If I'm not mistaken, such a struct takes at least 16 bytes on a 64-bit machine (I don't know what other overhead SBCL imposes), and the array would require at least 8 bytes per element, which makes for at least 24 bytes per element, meaning at least 50% overhead. The overhead becomes even more obvious if the elements of the structure are, say, (unsigned-byte 8), where only two bytes should be required per element. Would it be possible, somehow, to make SBCL store structures directly in the array, as I can make a C compiler do (with a "struct test array[100]"), or will I have to live with this overhead unless I declare multiple arrays (one per structure element) and do away with structures instead? Thanks for reading! Fredrik Tolf |
From: Paul K. <pv...@pv...> - 2010-04-25 20:57:01
|
In article <127...@pc...>, Fredrik Tolf <fr...@do...> wrote: > How would I do to create a very large array of some structure in SBCL to > be as memory-conservative as possible? > > Consider the following code: > > (defstruct test a b) > (type-of (make-array '(10 10) :element-type 'test)) > > SBCL tells me that the type of the array is a (simple-array t (10 10)), > and I guess that means that it's effectively holding pointers to > structs. If I'm not mistaken, such a struct takes at least 16 bytes on a > 64-bit machine (I don't know what other overhead SBCL imposes), and the > array would require at least 8 bytes per element, which makes for at > least 24 bytes per element, meaning at least 50% overhead. The overhead > becomes even more obvious if the elements of the structure are, say, > (unsigned-byte 8), where only two bytes should be required per element. The space usage for structures goes like: 1. Header word (1 word) 2. Type descriptor (1 word) ... data ... So the space overhead is 2 words/struct for the metadata and 1 more for the pointer from the array. > Would it be possible, somehow, to make SBCL store structures directly in > the array, as I can make a C compiler do (with a "struct test > array[100]"), or will I have to live with this overhead unless I declare > multiple arrays (one per structure element) and do away with structures > instead? The problem is that this breaks object identity. The semantics of CL dictate that, given A an array of TEST, I can do (setf (aref A 0) (aref A 1)) and both indices should point to the same (wrt object identity) object. For instance, side-effects to the structure in either index will be reflected in the other. It would be possible to hack up a special type of vectors or arrays that doesn't preserve object identity. However, practically, it's probably easier to use SB-ALIEN and work with a C array of structures if you don't need pointers from the structures back to lisp objects. More portably, you may be able to encode each structure in a fixnum or machine word. Paul Khuong |
From: james a. <jam...@se...> - 2010-04-26 09:49:34
|
On 2010-04-25, at 22:56 , Paul Khuong wrote: > [ ... ] > >> Would it be possible, somehow, to make SBCL store structures >> directly in >> the array, as I can make a C compiler do (with a "struct test >> array[100]"), or will I have to live with this overhead unless I >> declare >> multiple arrays (one per structure element) and do away with >> structures >> instead? > > The problem is that this breaks object identity. The semantics of CL > dictate that, given A an array of TEST, I can do > (setf (aref A 0) (aref A 1)) > and both indices should point to the same (wrt object identity) > object. > For instance, side-effects to the structure in either index will be > reflected in the other. As essential as the notion is, it should be easy to verify. As it stands, I can find discussion of - the permission to copy characters and numbers, of which simple arrays takes advantage - class identity - symbol identity but, beyond that, there is only the definition of identical in terms of eq. which begs the question. Where is this constraint specified? |
From: Daniel H. <dhe...@te...> - 2010-04-26 06:29:41
|
On Sun, 25 Apr 2010, Fredrik Tolf wrote: > Would it be possible, somehow, to make SBCL store structures directly in > the array, as I can make a C compiler do (with a "struct test > array[100]"), or will I have to live with this overhead unless I declare > multiple arrays (one per structure element) and do away with structures > instead? Paul Khuong explained why this overhead won't go away. Rather than creating multiple arrays, may I suggest representing your structures as arrays? Then you can store them as rows in one multidimensional array, and use displaced arrays to pull elements out of the main array. ;; simple example (let ((main-array (make-array '(10 3)))) ;; modify the last entry in each row ;; but use displaced arrays as a subview (dotimes (i 10) (let ((view (make-array 3 :displaced-to main-array :displaced-index-offset (* 3 i)))) (setf (aref view 2) i))) ;; see that the main array was modified main-array) I was then going to say you can sugar this with a clever defstruct; but the following fails to work in either SBCL or Clisp (it does work in ECL). (defstruct (test (:type vector)) a b c) (let ((main-array (make-array '(10 3)))) (dotimes (i 10) (let ((view (make-array 3 :displaced-to main-array :displaced-index-offset (* 3 i)))) (setf (test-a view) i))) main-array) Not sure why SBCL and Clisp think the struct is a simple-vector; CLHS for defstruct says "The structure is represented as a general vector, storing components as vector elements." Later, Daniel |
From: Paul K. <pv...@pv...> - 2010-04-26 19:45:37
|
In article <326...@se...>, james anderson <jam...@se...> wrote: > On 2010-04-25, at 22:56 , Paul Khuong wrote: > > The problem is that this breaks object identity. The semantics of CL > > dictate that, given A an array of TEST, I can do > > (setf (aref A 0) (aref A 1)) > > and both indices should point to the same (wrt object identity) > > object. > > For instance, side-effects to the structure in either index will be > > reflected in the other. [...] > Where is this constraint specified? What constraint? That the implementation won't copy objects behind your back? Paul Khuong |
From: james a. <jam...@se...> - 2010-04-26 20:47:56
|
On 2010-04-26, at 21:45 , Paul Khuong wrote: > In article <326...@se...>, > james anderson <jam...@se...> wrote: >> On 2010-04-25, at 22:56 , Paul Khuong wrote: >>> The problem is that this breaks object identity. The semantics of CL >>> dictate that, given A an array of TEST, I can do >>> (setf (aref A 0) (aref A 1)) >>> and both indices should point to the same (wrt object identity) >>> object. >>> For instance, side-effects to the structure in either index will be >>> reflected in the other. > [...] >> Where is this constraint specified? > > What constraint? That the implementation won't copy objects behind > your > back? i'm more concerned with "before your very eyes." that is, is it anywhere specified that a conforming implementation could not define the behavior of simple-array to include structures. with the same consequences as for floating point numbers. |
From: Paul K. <pv...@pv...> - 2010-04-26 22:00:46
|
In article <2AD...@se...>, james anderson <jam...@se...> wrote: > On 2010-04-26, at 21:45 , Paul Khuong wrote: > > > In article <326...@se...>, > > james anderson <jam...@se...> wrote: > >> On 2010-04-25, at 22:56 , Paul Khuong wrote: > >>> The problem is that this breaks object identity. The semantics of CL > >>> dictate that, given A an array of TEST, I can do > >>> (setf (aref A 0) (aref A 1)) > >>> and both indices should point to the same (wrt object identity) > >>> object. > >>> For instance, side-effects to the structure in either index will be > >>> reflected in the other. > > [...] > >> Where is this constraint specified? > > > > What constraint? That the implementation won't copy objects behind > > your > > back? > > i'm more concerned with "before your very eyes." > that is, is it anywhere specified that a conforming implementation > could not define the behavior of simple-array to include structures. > with the same consequences as for floating point numbers. EQ is defined to work on structures, unlike numbers. |
From: Stig H. <sti...@gm...> - 2010-04-26 22:53:38
|
Immutables, e.g. floats, can be copied at will. Mutables, e.g. structs, can not. |
From: james a. <jam...@se...> - 2010-04-26 23:14:25
|
On 2010-04-27, at 00:00 , Paul Khuong wrote: > In article <2AD...@se...>, > james anderson <jam...@se...> wrote: >> On 2010-04-26, at 21:45 , Paul Khuong wrote: >> >>> In article <326...@se...>, >>> james anderson <jam...@se...> wrote: >>>> On 2010-04-25, at 22:56 , Paul Khuong wrote: >>>>> The problem is that this breaks object identity. The semantics >>>>> of CL >>>>> dictate that, given A an array of TEST, I can do >>>>> (setf (aref A 0) (aref A 1)) >>>>> and both indices should point to the same (wrt object identity) >>>>> object. >>>>> For instance, side-effects to the structure in either index >>>>> will be >>>>> reflected in the other. >>> [...] >>>> Where is this constraint specified? >>> >>> What constraint? That the implementation won't copy objects behind >>> your >>> back? >> >> i'm more concerned with "before your very eyes." >> that is, is it anywhere specified that a conforming implementation >> could not define the behavior of simple-array to include structures. >> with the same consequences as for floating point numbers. > > EQ is defined to work on structures, unlike numbers. ? i thought eq was specified to work on any object, but that is a secondary issue, as the direct concern is with places. while there is discussion under the topics of generalized references, symbol-value, and eq which implies that copying can not occur when symbol-value is used as a place, i still have not found any discussion which requires that with respect to aref. not even for general arrays. i am as surprised to not find it as you appear to be that one would suggest that the behavior which you expect is a matter of convention not specification. |
From: Tobias C. R. <tc...@fr...> - 2010-04-26 23:57:09
|
james anderson <jam...@se...> writes: > while there is discussion under the topics of generalized references, > symbol-value, and eq which implies that copying can not occur when > symbol-value is used as a place, i still have not found any > discussion which requires that with respect to aref. not even for > general arrays. > > i am as surprised to not find it as you appear to be that one would > suggest that the behavior which you expect is a matter of convention > not specification. 3.1.2.1.3 says that evaluating an object always yields the same object, so objects have identity in Common Lisp. CLHS entry for system class ARRAY says that an array contains objects, and the glossary entry for array says an array is a container for objects. AREF accesses and stores objects (with identity) from/into that container. It may not be explicit but an interpretation towards allowance for randomly creating copies at discretion of the implementation sounds a bit like squaring the circle. The only reason why it's allowed for numbers, and characters is because it's specifically allowed by the definition of EQ. -T. |
From: <pj...@in...> - 2010-04-27 18:55:21
|
james anderson <jam...@se...> writes: > On 2010-04-27, at 00:00 , Paul Khuong wrote: > >> In article <2AD...@se...>, >> james anderson <jam...@se...> wrote: >>> On 2010-04-26, at 21:45 , Paul Khuong wrote: >>> >>>> In article <326...@se...>, >>>> james anderson <jam...@se...> wrote: >>>>> On 2010-04-25, at 22:56 , Paul Khuong wrote: >>>>>> The problem is that this breaks object identity. The semantics >>>>>> of CL >>>>>> dictate that, given A an array of TEST, I can do >>>>>> (setf (aref A 0) (aref A 1)) >>>>>> and both indices should point to the same (wrt object identity) >>>>>> object. >>>>>> For instance, side-effects to the structure in either index >>>>>> will be >>>>>> reflected in the other. >>>> [...] >>>>> Where is this constraint specified? >>>> >>>> What constraint? That the implementation won't copy objects behind >>>> your >>>> back? >>> >>> i'm more concerned with "before your very eyes." >>> that is, is it anywhere specified that a conforming implementation >>> could not define the behavior of simple-array to include structures. >>> with the same consequences as for floating point numbers. >> >> EQ is defined to work on structures, unlike numbers. > > ? i thought eq was specified to work on any object, but that is a > secondary issue, as the direct concern is with places. > > while there is discussion under the topics of generalized references, > symbol-value, and eq which implies that copying can not occur when > symbol-value is used as a place, i still have not found any > discussion which requires that with respect to aref. not even for > general arrays. > > i am as surprised to not find it as you appear to be that one would > suggest that the behavior which you expect is a matter of convention > not specification. AIUI, this is a general property of places. Refering the glossary: place n. 1. a form which is suitable for use as a generalized reference. 2. the conceptual location referred to by such a place[1]. generalized reference n. a reference to a location storing an object as if to a variable. (Such a reference can be either to read or write the location.) See Section 5.1 (Generalized Reference). See also place. Since (aref a 0) is a place, it should behave as a variable. If you allowed copies of structures when storing into (aref a 0), then you would have to allow such a copy when binding a variable too. Indeed, I cannot find wording forbidding it, unless you understand the possibility given to copy numbers and characters as exclusive. On the other hand, variables are bound to objects, they are not the receptacle of copies of objects: binding n. an association between a name and that which the name denotes. ``A lexical binding is a lexical association between a name and its value.'' When the term binding is qualified by the name of a namespace, such as ``variable'' or ``function,'' it restricts the binding to the indicated namespace, as in: ``let establishes variable bindings.'' or ``let establishes bindings of variables.'' Therefore we can argue that this wraps it up and that you cannot copy lisp objects such as a structure into an array slot (only character and numbers may be copied there and elsewhere). -- __Pascal Bourguignon__ |