From: Marco Antoniotti
Subject: Computing the actual size of an array given dimensions and element type.
Date:
Message-ID: <3F268329.20808@cs.nyu.edu>
Hi
I hit the ARRAY-TOTAL-SIZE-LIMIT in my work and I am now working around
it. Essentially I need a way to portably predict the array total size
given the element type and the dimensions of the array.
Unfortunately this seems to be one of those "implementation dependent"
corners of CL (as AFAIU implied by the CLHS ARRAY-TOTAL-SIZE-LIMIT entry).
E.g. LWW seems to be happy with
(apply '* 2 dimension-list)
for DOUBLE-FLOATs. However, I'd like a slightly more general solution.
Any ideas?
Thanks
--
Marco
From: Kent M Pitman
Subject: Re: Computing the actual size of an array given dimensions and element type.
Date:
Message-ID: <sfw1xw9v1md.fsf@shell01.TheWorld.com>
Marco Antoniotti <·······@cs.nyu.edu> writes:
> I hit the ARRAY-TOTAL-SIZE-LIMIT in my work and I am now working
> around it. Essentially I need a way to portably predict the array
> total size given the element type and the dimensions of the array.
Why don't you just figure out a contract for a simple function to ask
every vendor to support and then start asking them to implement it
for you? Is there reason to believe you could not get a reliable
solution and should have to resort to something hokey?
From: Marco Antoniotti
Subject: Re: Computing the actual size of an array given dimensions and element type.
Date:
Message-ID: <3F268D0C.8010206@cs.nyu.edu>
Kent M Pitman wrote:
> Marco Antoniotti <·······@cs.nyu.edu> writes:
>
>
>>I hit the ARRAY-TOTAL-SIZE-LIMIT in my work and I am now working
>>around it. Essentially I need a way to portably predict the array
>>total size given the element type and the dimensions of the array.
>
>
> Why don't you just figure out a contract for a simple function to ask
> every vendor to support and then start asking them to implement it
> for you? Is there reason to believe you could not get a reliable
> solution and should have to resort to something hokey?
Well the contract could be simple.
EXPECT-ARRAY-TOTAL-SIZE element-type &rest dimensions
EXPECT-ARRAY-TOTAL-SIZE* element-type dimensions &key &allow-other-keys
Are there any counter indications in the above?
The first function just takes ELEMENT-TYPE and a list of DIMENSIONS and
returns a FIXNUM (less than or equal to ARRA-TOTAL-SIZE-LIMIT).
The second one is an "extendable" version, where DIMENSIONS is passed as
a list and where the extra keys could be used to do some fancy extra
things. E.g. suppose an implementation supported sparse arrays. The
second version of the function could be called as
(expect-array-total-size 'some-type (list x y z) :sparse t)
Now, for my immediate needs, I could just go ahead and implement the
above if I knew what different implementations do, at least for the
numeric types.
Cheers
--
Marco
From: Erann Gat
Subject: Re: Computing the actual size of an array given dimensions and element type.
Date:
Message-ID: <gat-2907030836240001@192.168.1.51>
In article <················@cs.nyu.edu>, ·······@cs.nyu.edu wrote:
> Kent M Pitman wrote:
> > Marco Antoniotti <·······@cs.nyu.edu> writes:
> >
> >
> >>I hit the ARRAY-TOTAL-SIZE-LIMIT in my work and I am now working
> >>around it. Essentially I need a way to portably predict the array
> >>total size given the element type and the dimensions of the array.
> >
> >
> > Why don't you just figure out a contract for a simple function to ask
> > every vendor to support and then start asking them to implement it
> > for you? Is there reason to believe you could not get a reliable
> > solution and should have to resort to something hokey?
>
> Well the contract could be simple.
>
> EXPECT-ARRAY-TOTAL-SIZE element-type &rest dimensions
> EXPECT-ARRAY-TOTAL-SIZE* element-type dimensions &key &allow-other-keys
>
> Are there any counter indications in the above?
You should call it "EXPECTED-ARRAY-TOTAL-SIZE". The names you've chosen
sound too much like commands.
Also, you shouldn't have two separate functions if the only difference
between them is that one takes keywords and the other doesn't.
Finally, as long as you're asking vendors to do this for you, why not
simply ask for:
(SIZEOF typespec)
That would be at once simpler, more general, and more familiar for C
programmers.
E.
From: Thomas A. Russ
Subject: Re: Computing the actual size of an array given dimensions and element type.
Date:
Message-ID: <ymibrvdrxch.fsf@sevak.isi.edu>
···@jpl.nasa.gov (Erann Gat) writes:
> In article <················@cs.nyu.edu>, ·······@cs.nyu.edu wrote:
> > Well the contract could be simple.
> >
> > EXPECT-ARRAY-TOTAL-SIZE element-type &rest dimensions
> > EXPECT-ARRAY-TOTAL-SIZE* element-type dimensions &key &allow-other-keys
> >
> > Are there any counter indications in the above?
>
> You should call it "EXPECTED-ARRAY-TOTAL-SIZE". The names you've chosen
> sound too much like commands.
>
> Also, you shouldn't have two separate functions if the only difference
> between them is that one takes keywords and the other doesn't.
An even simpler contract would be to use exactly the same argument list
(including keywords) as MAKE-ARRAY. It would have the benefit that you
could then write your own:
(defun make-safe-array (&rest args)
(if (< (apply #'expected-array-total-size args) ARRAY-TOTAL-SIZE-LIMIT)
(apply #'make-array args)
nil)) ; error, whatever...
--
Thomas A. Russ, USC/Information Sciences Institute
In article <···············@sevak.isi.edu>, ···@sevak.isi.edu (Thomas A.
Russ) wrote:
> ···@jpl.nasa.gov (Erann Gat) writes:
>
> > In article <················@cs.nyu.edu>, ·······@cs.nyu.edu wrote:
> > > Well the contract could be simple.
> > >
> > > EXPECT-ARRAY-TOTAL-SIZE element-type &rest dimensions
> > > EXPECT-ARRAY-TOTAL-SIZE* element-type dimensions &key &allow-other-keys
> > >
> > > Are there any counter indications in the above?
> >
> > You should call it "EXPECTED-ARRAY-TOTAL-SIZE". The names you've chosen
> > sound too much like commands.
> >
> > Also, you shouldn't have two separate functions if the only difference
> > between them is that one takes keywords and the other doesn't.
>
> An even simpler contract would be to use exactly the same argument list
> (including keywords) as MAKE-ARRAY. It would have the benefit that you
> could then write your own:
>
> (defun make-safe-array (&rest args)
> (if (< (apply #'expected-array-total-size args) ARRAY-TOTAL-SIZE-LIMIT)
> (apply #'make-array args)
> nil)) ; error, whatever...
(ignore-errors (make-array ...))
?
E.
From: Marco Antoniotti
Subject: Re: Computing the actual size of an array given dimensions and element type.
Date:
Message-ID: <3F269E45.8000800@cs.nyu.edu>
Erann Gat wrote:
> In article <················@cs.nyu.edu>, ·······@cs.nyu.edu wrote:
>
>
>>Kent M Pitman wrote:
>>
>>>Marco Antoniotti <·······@cs.nyu.edu> writes:
>>>
>>>
>>>
>>>>I hit the ARRAY-TOTAL-SIZE-LIMIT in my work and I am now working
>>>>around it. Essentially I need a way to portably predict the array
>>>>total size given the element type and the dimensions of the array.
>>>
>>>
>>>Why don't you just figure out a contract for a simple function to ask
>>>every vendor to support and then start asking them to implement it
>>>for you? Is there reason to believe you could not get a reliable
>>>solution and should have to resort to something hokey?
>>
>>Well the contract could be simple.
>>
>> EXPECT-ARRAY-TOTAL-SIZE element-type &rest dimensions
>> EXPECT-ARRAY-TOTAL-SIZE* element-type dimensions &key &allow-other-keys
>>
>>Are there any counter indications in the above?
>
>
> You should call it "EXPECTED-ARRAY-TOTAL-SIZE". The names you've chosen
> sound too much like commands.
Sounds good.
>
> Also, you shouldn't have two separate functions if the only difference
> between them is that one takes keywords and the other doesn't.
Because the first one is simpler with a different interface. The second
is meant for more complicated things. Not that I am so interested in
having two of them, but, why not?
>
> Finally, as long as you're asking vendors to do this for you, why not
> simply ask for:
>
> (SIZEOF typespec)
>
> That would be at once simpler, more general, and more familiar for C
> programmers.
That would be simpler for C programmers but not simpler in interface,
IMHO, as we do not have a simple way to construct (array) type specs on
the fly other than using backquote. The array ones are well defined
within the limits of the current specification and always return an
"uninterpreted" fixnum.
Having a general SIZEOF operator would be useful, but I don't feel like
asking for it. :)
Cheers
--
Marco
In article <················@cs.nyu.edu>, ·······@cs.nyu.edu wrote:
> > Also, you shouldn't have two separate functions if the only difference
> > between them is that one takes keywords and the other doesn't.
>
> Because the first one is simpler with a different interface. The second
> is meant for more complicated things. Not that I am so interested in
> having two of them, but, why not?
Because the second interface subsumes the first, so it places a burden on
the programmer to remember which is which. The compiler ought to do this
work, not the programmer. Interfaces like this are one of the reasons
that Java is such a pain in the ass.
Also, it's a very slippery slope towards a very messy interface. Why not
also have:
EXPECTED-ARRAY-TOTAL-SIZE** rank element-count
EXPECTED-ARRAY-TOTAL-SIZE*** rank elemenet-count &key &allow-other-keys
EXPECTED-VECTOR-TOTAL-SIZE element-count
etc. etc. etc.
If you still insist on having two functions, then the one with the less
general interface ought to have the longer name.
> > Finally, as long as you're asking vendors to do this for you, why not
> > simply ask for:
> >
> > (SIZEOF typespec)
> >
> > That would be at once simpler, more general, and more familiar for C
> > programmers.
>
> That would be simpler for C programmers but not simpler in interface,
> IMHO, as we do not have a simple way to construct (array) type specs on
> the fly other than using backquote.
What's wrong with using backquote?
> The array ones are well defined
> within the limits of the current specification and always return an
> "uninterpreted" fixnum.
Huh?
E.
From: Marco Antoniotti
Subject: Re: Computing the actual size of an array given dimensions and element type.
Date:
Message-ID: <3F26C7EB.2050203@cs.nyu.edu>
Erann Gat wrote:
> In article <················@cs.nyu.edu>, ·······@cs.nyu.edu wrote:
>
>
>>>Also, you shouldn't have two separate functions if the only difference
>>>between them is that one takes keywords and the other doesn't.
>>
>>Because the first one is simpler with a different interface. The second
>>is meant for more complicated things. Not that I am so interested in
>>having two of them, but, why not?
>
>
> Because the second interface subsumes the first, so it places a burden on
> the programmer to remember which is which. The compiler ought to do this
> work, not the programmer. Interfaces like this are one of the reasons
> that Java is such a pain in the ass.
Point taken. I'd settle for
EXPECTED-ARRAY-TOTAL-SIZE element-type dimensions &key &allow-other-keys
>
> Also, it's a very slippery slope towards a very messy interface. Why not
> also have:
>
> EXPECTED-ARRAY-TOTAL-SIZE** rank element-count
>
> EXPECTED-ARRAY-TOTAL-SIZE*** rank elemenet-count &key &allow-other-keys
>
> EXPECTED-VECTOR-TOTAL-SIZE element-count
>
> etc. etc. etc.
>
> If you still insist on having two functions, then the one with the less
> general interface ought to have the longer name.
>
>
>>>Finally, as long as you're asking vendors to do this for you, why not
>>>simply ask for:
>>>
>>>(SIZEOF typespec)
>>>
>>>That would be at once simpler, more general, and more familiar for C
>>>programmers.
>>
>>That would be simpler for C programmers but not simpler in interface,
>>IMHO, as we do not have a simple way to construct (array) type specs on
>>the fly other than using backquote.
>
>
> What's wrong with using backquote?
Nothing particular. I just dislike having to do things like
(coerce xxx `(vector double-float ,(+ l 2))
and so forth. Maybe it is just me.
>
>
>> The array ones are well defined
>>within the limits of the current specification and always return an
>>"uninterpreted" fixnum.
>
>
> Huh?
What I meant to say (and I didn't say it well) is that ARRAY-TOTAL-SIZE
and ARRAY-TOTAL-SIZE-LIMIT return a fixum that is the number of elements
(or the limit thereof) in an array. If we had a general SIZEOF operator
we'd need to also agree on the actual semantics of the return value.
The EXPECTED-ARRAY-TOTAL-SIZE function would return a number with the
same semantics of ARRAY-TOTAL-SIZE-LIMIT. That's all.
Cheers
--
Marco
From: Kent M Pitman
Subject: Re: Computing the actual size of an array given dimensions and element type.
Date:
Message-ID: <sfw4r156r0p.fsf@shell01.TheWorld.com>
Marco Antoniotti <·······@cs.nyu.edu> writes:
> What I meant to say (and I didn't say it well) is that
> ARRAY-TOTAL-SIZE and ARRAY-TOTAL-SIZE-LIMIT return a fixum that is the
> number of elements (or the limit thereof) in an array. If we had a
> general SIZEOF operator we'd need to also agree on the actual
> semantics of the return value. The EXPECTED-ARRAY-TOTAL-SIZE function
> would return a number with the same semantics of
> ARRAY-TOTAL-SIZE-LIMIT. That's all.
I have always taken the spec to implicitly require that some arrays that
"would fit" to not be "allocatable" such that the ARRAY-TOTAL-SIZE-LIMIT
_was_ the number you were looking for, that is, if double float arrays
or complex arrays can't be allocated of the size in question, then the
max size of all arrays must be backed up to a size that works. The smaller
the element size, the more restriction this is. I'm happy with a function
that produces a more accurate measure; what I'd do is just have the
ARRAY-TOTAL-SIZE-LIMIT variable contain the min (i.e., most conservative)
value of all possible types for "quick checks", and then have the function
compute a larger value for particular types where that would work. I think
that would be both compatible and useful.
I do think it's a bug that you're running into a case where using
ARRAY-TOTAL-SIZE-LIMIT as-is is ever leading you to lose, even though
implicit in what I say is that probably you'd get smaller data areas
than you're presently getting for other arrays in that implementation.
Not that my opinion is authoritative in any way.
From: Kent M Pitman
Subject: Re: Computing the actual size of an array given dimensions and element type.
Date:
Message-ID: <sfwznix5cbn.fsf@shell01.TheWorld.com>
While you're thinking about it, you might want to consider whether a keyword
like :TAKE-ALREADY-USED-MEMORY-INTO-ACCOUNT T would be good. Or, put another
way, are you really asking "do I hae room to allocate this array", in which
case how much memory you have consumed so far also matters and the same
function might be better off not to return a number but simply a T/NIL saying
whether an allocation would succeed right now.
In article <···············@shell01.TheWorld.com>,
Kent M Pitman <······@world.std.com> wrote:
> While you're thinking about it, you might want to consider whether a keyword
> like :TAKE-ALREADY-USED-MEMORY-INTO-ACCOUNT T would be good. Or, put another
> way, are you really asking "do I hae room to allocate this array", in which
> case how much memory you have consumed so far also matters and the same
> function might be better off not to return a number but simply a T/NIL saying
> whether an allocation would succeed right now.
Isn't such a function actually useless in a multithreaded system?
I mean, even if the function returns T you can't be sure that an actual
allocation will succeed even in the very next moment.
I think the only reasonable way is to try to allocate the amount of
memory you need, and wrap that with appropriate error handlers.
Pascal
From: Kent M Pitman
Subject: Re: Computing the actual size of an array given dimensions and element type.
Date:
Message-ID: <sfw1xw97xvc.fsf@shell01.TheWorld.com>
Pascal Costanza <········@web.de> writes:
> In article <···············@shell01.TheWorld.com>,
> Kent M Pitman <······@world.std.com> wrote:
>
> > While you're thinking about it, you might want to consider whether
> > a keyword like :TAKE-ALREADY-USED-MEMORY-INTO-ACCOUNT T would be
> > good. Or, put another way, are you really asking "do I hae room
> > to allocate this array", in which case how much memory you have
> > consumed so far also matters and the same function might be better
> > off not to return a number but simply a T/NIL saying whether an
> > allocation would succeed right now.
>
> Isn't such a function actually useless in a multithreaded system?
>
> I mean, even if the function returns T you can't be sure that an actual
> allocation will succeed even in the very next moment.
>
> I think the only reasonable way is to try to allocate the amount of
> memory you need, and wrap that with appropriate error handlers.
That's a good point, but that's also the reason I wanted to find out what
the intended use of the original operator was. That reduces the problem
to making sure that the system signals an appropriate condition, which
incidentally should be a SERIOUS-CONDITION but not an ERROR since things
like storage exhausted, etc. are not semantics-related conditions but are
practical implementation limitations.
From: Joe Marshall
Subject: Re: Computing the actual size of an array given dimensions and element type.
Date:
Message-ID: <wue1ku90.fsf@ccs.neu.edu>
···@jpl.nasa.gov (Erann Gat) writes:
> Finally, as long as you're asking vendors to do this for you, why not
> simply ask for:
>
> (SIZEOF typespec)
>
> That would be at once simpler, more general, and more familiar for C
> programmers.
> (sizeof (cons 'a 'b))
4
> (sizeof 493894739127413947193248)
4
> (sizeof "I am a long string")
4
In article <············@ccs.neu.edu>, Joe Marshall <···@ccs.neu.edu> wrote:
> ···@jpl.nasa.gov (Erann Gat) writes:
>
> > Finally, as long as you're asking vendors to do this for you, why not
> > simply ask for:
> >
> > (SIZEOF typespec)
> >
> > That would be at once simpler, more general, and more familiar for C
> > programmers.
>
> > (sizeof (cons 'a 'b))
> 4
>
> > (sizeof 493894739127413947193248)
> 4
>
> > (sizeof "I am a long string")
> 4
> (sizeof (cons 'a b))
Error: (a . b) is not a valid type specifier
1>
E.
From: Joe Marshall
Subject: Re: Computing the actual size of an array given dimensions and element type.
Date:
Message-ID: <brvdkq0k.fsf@ccs.neu.edu>
···@jpl.nasa.gov (Erann Gat) writes:
>> (sizeof (cons 'a b))
>
> Error: (a . b) is not a valid type specifier
D'oh!
From: Christophe Rhodes
Subject: Re: Computing the actual size of an array given dimensions and element type.
Date:
Message-ID: <sqbrvd8efs.fsf@lambda.jcn.srcf.net>
Marco Antoniotti <·······@cs.nyu.edu> writes:
> Kent M Pitman wrote:
>> Marco Antoniotti <·······@cs.nyu.edu> writes:
>>
>>>I hit the ARRAY-TOTAL-SIZE-LIMIT in my work and I am now working
>>>around it. Essentially I need a way to portably predict the array
>>>total size given the element type and the dimensions of the array.
>> Why don't you just figure out a contract for a simple function to ask
>> every vendor to support and then start asking them to implement it
>> for you? Is there reason to believe you could not get a reliable
>> solution and should have to resort to something hokey?
>
> Well the contract could be simple.
>
> EXPECT-ARRAY-TOTAL-SIZE element-type &rest dimensions
> EXPECT-ARRAY-TOTAL-SIZE* element-type dimensions &key &allow-other-keys
>
> Are there any counter indications in the above?
>
> The first function just takes ELEMENT-TYPE and a list of DIMENSIONS
> and returns a FIXNUM (less than or equal to ARRA-TOTAL-SIZE-LIMIT).
I don't understand this. Why is this not equivalent to (apply #'*
dimensions)?
Christophe
--
http://www-jcsu.jesus.cam.ac.uk/~csr21/ +44 1223 510 299/+44 7729 383 757
(set-pprint-dispatch 'number (lambda (s o) (declare (special b)) (format s b)))
(defvar b "~&Just another Lisp hacker~%") (pprint #36rJesusCollegeCambridge)
From: Thomas A. Russ
Subject: Re: Computing the actual size of an array given dimensions and element type.
Date:
Message-ID: <ymi7k61rx3q.fsf@sevak.isi.edu>
Christophe Rhodes <·····@cam.ac.uk> writes:
> Marco Antoniotti <·······@cs.nyu.edu> writes:
>
> >
> > Well the contract could be simple.
> >
> > EXPECT-ARRAY-TOTAL-SIZE element-type &rest dimensions
> > EXPECT-ARRAY-TOTAL-SIZE* element-type dimensions &key &allow-other-keys
>
> I don't understand this. Why is this not equivalent to (apply #'*
> dimensions)?
There are two different resource limitations here. One of them is the
size of the array in elements. This is constrained at one end by the
requirement that an array's index be a fixnum (or some
implementation-dependent smaller number) coupled with the ability to
access any array in row-major order as a vector. That particular
constraint could be checked by the multiplication.
The other constraint is a possible implementation limit on the largest
contiguous block of memory that can be allocated. This is where the
element type may come into play, since an array of bytes is smaller than
an array of pointers which is often smaller than an array of double
floats. (Assuming some typical 32-bit architecture where a byte takes
one byte, a pointer 4 bytes and a double 8 bytes of storage).
--
Thomas A. Russ, USC/Information Sciences Institute
From: Marco Antoniotti
Subject: Re: Computing the actual size of an array given dimensions and element type.
Date:
Message-ID: <3F26C53A.7040509@cs.nyu.edu>
Christophe Rhodes wrote:
> Marco Antoniotti <·······@cs.nyu.edu> writes:
>
>
>>Kent M Pitman wrote:
>>
>>>Marco Antoniotti <·······@cs.nyu.edu> writes:
>>>
>>>
>>>>I hit the ARRAY-TOTAL-SIZE-LIMIT in my work and I am now working
>>>>around it. Essentially I need a way to portably predict the array
>>>>total size given the element type and the dimensions of the array.
>>>
>>>Why don't you just figure out a contract for a simple function to ask
>>>every vendor to support and then start asking them to implement it
>>>for you? Is there reason to believe you could not get a reliable
>>>solution and should have to resort to something hokey?
>>
>>Well the contract could be simple.
>>
>> EXPECT-ARRAY-TOTAL-SIZE element-type &rest dimensions
>> EXPECT-ARRAY-TOTAL-SIZE* element-type dimensions &key &allow-other-keys
>>
>>Are there any counter indications in the above?
>>
>>The first function just takes ELEMENT-TYPE and a list of DIMENSIONS
>>and returns a FIXNUM (less than or equal to ARRA-TOTAL-SIZE-LIMIT).
>
>
> I don't understand this. Why is this not equivalent to (apply #'*
> dimensions)?
Because teh entry for ARRAY-TOTAL-SIZE-LIMIT seems to imply that that is
not necessarily the case. I am willing to stand corrected. :)
Cheers
--
Marco
From: Barry Margolin
Subject: Re: Computing the actual size of an array given dimensions and element type.
Date:
Message-ID: <kPzVa.2$631.1@news.level3.com>
In article <················@cs.nyu.edu>,
Marco Antoniotti <·······@cs.nyu.edu> wrote:
>Christophe Rhodes wrote:
>> I don't understand this. Why is this not equivalent to (apply #'*
>> dimensions)?
>
>Because teh entry for ARRAY-TOTAL-SIZE-LIMIT seems to imply that that is
>not necessarily the case. I am willing to stand corrected. :)
It says "upper exclusive bound on the total number of elements in an
array". It's not a limit on the amount of memory used by the array; that
would be useless, since CL doesn't provide any way for you to determine how
much memory any data type uses. The implementor will most likely derive
the value of this constant by dividing the maximum amount of memory that an
array can consume by the size of the largest possible element type.
Perhaps what confused you is the part of the description that refers to the
"actual limit on array total size". Here's an example of how to understand
this.
Suppose the implementation supports arrays that use up to 4096 8-bit bytes
of memory, and the largest data type uses 4 bytes. It would set
ARRAY-TOTAL-SIZE-LIMIT to 1024. But an array of (unsigned-byte 8) elements
would only require 1 byte per element, so this type of array can actually
have 4096 elements.
The constant ARRAY-TOTAL-SIZE-LIMIT is basically the most conservative
limit, because it doesn't account for the fact that different types of
arrays may have different limits. Perhaps a better mechanism would have
been a function that takes all the same parameters as MAKE-ARRAY except the
dimensions, and returns the maximum number of elements for that type of
array. But we opted in favor of simplicity rather than precision.
--
Barry Margolin, ··············@level3.com
Level(3), Woburn, MA
*** DON'T SEND TECHNICAL QUESTIONS DIRECTLY TO ME, post them to newsgroups.
Please DON'T copy followups to me -- I'll assume it wasn't posted to the group.
From: Marco Antoniotti
Subject: Re: Computing the actual size of an array given dimensions and element type.
Date:
Message-ID: <3F2A9CD1.4060803@cs.nyu.edu>
Barry Margolin wrote:
> In article <················@cs.nyu.edu>,
> Marco Antoniotti <·······@cs.nyu.edu> wrote:
>
>>Christophe Rhodes wrote:
>>
>>>I don't understand this. Why is this not equivalent to (apply #'*
>>>dimensions)?
>>
>>Because teh entry for ARRAY-TOTAL-SIZE-LIMIT seems to imply that that is
>>not necessarily the case. I am willing to stand corrected. :)
>
>
> It says "upper exclusive bound on the total number of elements in an
> array". It's not a limit on the amount of memory used by the array; that
> would be useless, since CL doesn't provide any way for you to determine how
> much memory any data type uses. The implementor will most likely derive
> the value of this constant by dividing the maximum amount of memory that an
> array can consume by the size of the largest possible element type.
>
> Perhaps what confused you is the part of the description that refers to the
> "actual limit on array total size". Here's an example of how to understand
> this.
>
> Suppose the implementation supports arrays that use up to 4096 8-bit bytes
> of memory, and the largest data type uses 4 bytes. It would set
> ARRAY-TOTAL-SIZE-LIMIT to 1024. But an array of (unsigned-byte 8) elements
> would only require 1 byte per element, so this type of array can actually
> have 4096 elements.
>
> The constant ARRAY-TOTAL-SIZE-LIMIT is basically the most conservative
> limit, because it doesn't account for the fact that different types of
> arrays may have different limits. Perhaps a better mechanism would have
> been a function that takes all the same parameters as MAKE-ARRAY except the
> dimensions, and returns the maximum number of elements for that type of
> array. But we opted in favor of simplicity rather than precision.
>
Yep. I think that is what confused me. Anyway. I think I settled for
the conservative interpretation of A-T-S-L. This implies that there is
a bug in LWW, as admitted by the Xanalys folks.
Whether EXPECTED-ARRAY-SIZE is still useful I'll leave it to popular
wisdom :)
Cheers
--
Marco
From: Paul F. Dietz
Subject: Re: Computing the actual size of an array given dimensions and element type.
Date:
Message-ID: <WVOdnbC6TZvUg7GiXTWJkQ@dls.net>
Barry Margolin wrote:
> The constant ARRAY-TOTAL-SIZE-LIMIT is basically the most conservative
> limit, because it doesn't account for the fact that different types of
> arrays may have different limits. Perhaps a better mechanism would have
> been a function that takes all the same parameters as MAKE-ARRAY except the
> dimensions, and returns the maximum number of elements for that type of
> array. But we opted in favor of simplicity rather than precision.
ARRAY-TOTAL-SIZE-LIMIT does require that one of the array types
cannot have total size > MOST-POSITIVE-FIXNUM (since a-t-s-l is
a fixnum).
If you (as an implementor) want all arrays to have no size limit,
some sacrificial array type must be found to produce a-t-s-l.
Hmm. Anyone know of an array elment type that isn't useful for
anything else? :)
Paul
Hi Paul F. Dietz,
> ARRAY-TOTAL-SIZE-LIMIT does require that one of the array types cannot
> have total size > MOST-POSITIVE-FIXNUM (since a-t-s-l is a fixnum).
>
> If you (as an implementor) want all arrays to have no size limit, some
> sacrificial array type must be found to produce a-t-s-l.
>
> Hmm. Anyone know of an array elment type that isn't useful for anything
> else? :)
This limitation is beginning to make no sense for 32-bit deployments with
gigabytes of RAM. One should at least be able to create an array that uses
up all physical memory (including swap). This limitation is also a letdown
after one reads 15.1.1.2 Array Dimensions and goes "yipee, each dimension
only has to be a non-negative fixnum".
One obvious solution would be to move to 64-bit computing. Intel's
continued promotion of CPUs with a 4GB virtual address space for years to
come is pathetic. One imagines that the ANSI Committee had no idea that in
the 21st century people would again be encouraged to bank swap memory.
Given the sorry state of virtual address space for years to come I think
this limitation could be worked around. If one can find the nth bignum
element of a list one should be able to find a bignum element of an array
when it is feasible.
Given the performance implications (one imagines 64-bit implementations
shouldn't be slowed down by supporting bignum array dimensions) and the
fact an implementation may want to strictly conform I'd suggest a dynamic
variable that permits bignum array dimensions when true. Simply set to nil
when performing conformance tests.
In practice many implementors will obtain shiny new x86-64 systems and
won't be enthusiastic about implementing bignum array dimensions.
Another idea which may not be completely insane: Implementors could start
abstracting existing and future x86-32 systems as 64-bit. That is all
fixnums would be composed out of two 32-bit integers. This wouldn't raise
issues of conformance and would probably make it easier to support both
32-bit and 64-bit systems over the long term. One already needs greater
than 32-bit pointers to reference any part of a bank swapped address
space.
I'd likely accept as a user that some fixnum operations could be at least
twice as slow (and perhaps 32-bit declarations could still be supported).
And dedicated larger fixnum arithmetic would probably be faster than using
existing bignums.
Regards,
Adam
On Sun, 03 Aug 2003 12:24:49 +1200, Adam Warner
<······@consulting.net.nz> wrote:
>One obvious solution would be to move to 64-bit computing. Intel's
>continued promotion of CPUs with a 4GB virtual address space for years to
>come is pathetic. One imagines that the ANSI Committee had no idea that in
>the 21st century people would again be encouraged to bank swap memory.
>
It's a nice thought, but for problems that need the address space,
populating the 64-bit CPU with enough actual RAM to matter is still
going to be prohibitively expensive.
George
From: Erann Gat
Subject: Re: Computing the actual size of an array given dimensions and element type.
Date:
Message-ID: <gat-0808032102470001@192.168.1.51>
In article <··································@4ax.com>, George Neuner
<········@comcast.net> wrote:
> On Sun, 03 Aug 2003 12:24:49 +1200, Adam Warner
> <······@consulting.net.nz> wrote:
>
> >One obvious solution would be to move to 64-bit computing. Intel's
> >continued promotion of CPUs with a 4GB virtual address space for years to
> >come is pathetic. One imagines that the ANSI Committee had no idea that in
> >the 21st century people would again be encouraged to bank swap memory.
> >
>
> It's a nice thought, but for problems that need the address space,
> populating the 64-bit CPU with enough actual RAM to matter is still
> going to be prohibitively expensive.
Street price for RAM seems to be about $200/GB nowadays, so it only takes
about $1000 to get you beyond 4GB.
If the trends of the last decade continue into the next, we will see
prices drop below $1/GB within ten years. At that point you'll be able to
go beyond the 4GB limit for the price of a Big Mac.
The trend in disk drives is even more dramatic, where street price is
about $500 per *terabyte*.
I can still remember paying a few hundred dollars for 16k of RAM (and that
was just the chips, not a completed board) and $1000 for a 5 MB hard
drive.
Moore's law is truly an awesome thing.
E.
From: Joe Marshall
Subject: Re: Computing the actual size of an array given dimensions and element type.
Date:
Message-ID: <n0eccmch.fsf@ccs.neu.edu>
···@jpl.nasa.gov (Erann Gat) writes:
> In article <··································@4ax.com>, George Neuner
> <········@comcast.net> wrote:
>>
>> It's a nice thought, but for problems that need the address space,
>> populating the 64-bit CPU with enough actual RAM to matter is still
>> going to be prohibitively expensive.
>
> Street price for RAM seems to be about $200/GB nowadays, so it only takes
> about $1000 to get you beyond 4GB.
>
> If the trends of the last decade continue into the next, we will see
> prices drop below $1/GB within ten years. At that point you'll be able to
> go beyond the 4GB limit for the price of a Big Mac.
You'd still need tens of millions of dollars to make a dent in 64
bits, though.
Hi George Neuner,
>>One obvious solution would be to move to 64-bit computing. Intel's
>>continued promotion of CPUs with a 4GB virtual address space for years to
>>come is pathetic. One imagines that the ANSI Committee had no idea that in
>>the 21st century people would again be encouraged to bank swap memory.
>
> It's a nice thought, but for problems that need the address space,
> populating the 64-bit CPU with enough actual RAM to matter is still
> going to be prohibitively expensive.
That's part of the solution. The address space will be so large that using
fixnums instead of a 64-bit address space may not be a constraint over our
lifetimes.
Problem: We need to index arrays with more elements than is possible
with the positive fixnum limit in 32-bit implementations.
Best outcome: Larger fixnums.
Solution: 64-bit computing.
Remember that a larger virtual address space is useful for much more than
just accessing physical RAM. With a larger address space one could, for
example, simply map whole hard disk partitions to absolute addresses. An
array could map straight to a 100GB disk partition (with the operating
system transparently and efficiently caching the data).
64-bit computing already matters. Intel is just downplaying it because
they don't have an adequate response to the AMD Opteron and next month's
Athlon 64--although rumours continue about Yamhill:
http://news.google.com/news?hl=en&q=intel+yamhill&btnG=Search+News
So let's work out a worse case scenario for when fixnum issues might bite
again. Let's have 60-bit positive fixnums and a desire to index a boolean
array (i.e. where each element takes up one bit of storage).
* (format t "~:DGiB" (/ (expt 2 60) 8 1024 1024 1024))
134,217,728GiB
We have divided the number of bits by 8 to get bytes, divided the number
of bytes by 1024 to get KiB, divided the number of kilobytes by 1024 to
get MiB and divided this by 1024 to get Gigabytes.
That's 131,072 Terabytes or 128 Petabytes. 60-bit positive fixnums will be
sufficient for a while.
Regards,
Adam
On Sat, 09 Aug 2003 15:05:39 +1200, Adam Warner
<······@consulting.net.nz> wrote:
>Hi George Neuner,
>
>>>One obvious solution would be to move to 64-bit computing. Intel's
>>>continued promotion of CPUs with a 4GB virtual address space for years to
>>>come is pathetic. One imagines that the ANSI Committee had no idea that in
>>>the 21st century people would again be encouraged to bank swap memory.
>>
>> It's a nice thought, but for problems that need the address space,
>> populating the 64-bit CPU with enough actual RAM to matter is still
>> going to be prohibitively expensive.
>
>That's part of the solution. The address space will be so large that using
>fixnums instead of a 64-bit address space may not be a constraint over our
>lifetimes.
>
> Problem: We need to index arrays with more elements than is possible
> with the positive fixnum limit in 32-bit implementations.
>Best outcome: Larger fixnums.
> Solution: 64-bit computing.
>
>Remember that a larger virtual address space is useful for much more than
>just accessing physical RAM. With a larger address space one could, for
>example, simply map whole hard disk partitions to absolute addresses. An
>array could map straight to a 100GB disk partition (with the operating
>system transparently and efficiently caching the data).
>
Who said "programs expand to fill the available address space"? The
Amoeba OS already uses a 128-bit virtual address space ... 64-bits
wasn't enough.
I understand that 64-bit fixnums will subsume much or all of the
territory of bignums ... and drastically shrink the memory
requirements of programs that currently must use bignums.
My point is that simply expanding the virtual memory space does little
to help performance of a RAM constrained application ... even if the
page file/device is significantly faster than the general file system
(the norm on most OSes). The large address space certainly makes
developing such a program easier, but the more important metric is
executing the program ... no?
This particular thread involved a problem best solved by 64-bit
fixnums, but I am speaking to the more general case of programs with
huge data sets.
George
From: lin8080
Subject: Re: Computing the actual size of an array given dimensions and element type.
Date:
Message-ID: <3F35EFC0.E83A7DFA@freenet.de>
George Neuner schrieb:
> Who said "programs expand to fill the available address space"? The
> Amoeba OS already uses a 128-bit virtual address space ... 64-bits
> wasn't enough.
...
hm -think big
then the day will come you have 1024-bit ...
how many circuits can fit into a small ic (integrated circuit)?
so increase the bus takt and set the cpu between 2 motherbords or ...
stefan
>>>>> "Marco" == Marco Antoniotti <·······@cs.nyu.edu> writes:
Marco> Hi
Marco> I hit the ARRAY-TOTAL-SIZE-LIMIT in my work and I am now working
Marco> around it. Essentially I need a way to portably predict the array
Marco> total size given the element type and the dimensions of the array.
What do you mean by "array total size" here? I guess it's not
ARRAY-TOTAL-SIZE but something else, like the number of words used by
the array?
Ray
From: Marco Antoniotti
Subject: Re: Computing the actual size of an array given dimensions and element type.
Date:
Message-ID: <3F26AE49.70704@cs.nyu.edu>
Raymond Toy wrote:
>>>>>>"Marco" == Marco Antoniotti <·······@cs.nyu.edu> writes:
>>>>>
>
> Marco> Hi
>
> Marco> I hit the ARRAY-TOTAL-SIZE-LIMIT in my work and I am now working
> Marco> around it. Essentially I need a way to portably predict the array
> Marco> total size given the element type and the dimensions of the array.
>
> What do you mean by "array total size" here? I guess it's not
> ARRAY-TOTAL-SIZE but something else, like the number of words used by
> the array?
ARRAY-TOTAL-SIZE taks an array and returns its "size".
ARRAY-TOTAL-SIZE-LIMIT is a fixum that gives you an implementation
dependent limit. I need to figure out if I can allocate an array
beforehand. That is the difference.
Cheers
Marco
From: Barry Margolin
Subject: Re: Computing the actual size of an array given dimensions and element type.
Date:
Message-ID: <HPvVa.23$EE2.15@news.level3.com>
In article <··············@cs.nyu.edu>,
Marco Antoniotti <·······@cs.nyu.edu> wrote:
>Hi
>
>I hit the ARRAY-TOTAL-SIZE-LIMIT in my work and I am now working around
>it. Essentially I need a way to portably predict the array total size
>given the element type and the dimensions of the array.
The total size, for purposes of meeting that restriction, is not dependent
on the element type, it's just the total number of elements. To calculate
the total size, use:
(apply #'* (array-dimensions array))
--
Barry Margolin, ··············@level3.com
Level(3), Woburn, MA
*** DON'T SEND TECHNICAL QUESTIONS DIRECTLY TO ME, post them to newsgroups.
Please DON'T copy followups to me -- I'll assume it wasn't posted to the group.
From: Marco Antoniotti
Subject: Re: Computing the actual size of an array given dimensions and element type.
Date:
Message-ID: <3F26CBDE.5090605@cs.nyu.edu>
Barry Margolin wrote:
> In article <··············@cs.nyu.edu>,
> Marco Antoniotti <·······@cs.nyu.edu> wrote:
>
>>Hi
>>
>>I hit the ARRAY-TOTAL-SIZE-LIMIT in my work and I am now working around
>>it. Essentially I need a way to portably predict the array total size
>>given the element type and the dimensions of the array.
>
>
> The total size, for purposes of meeting that restriction, is not dependent
> on the element type, it's just the total number of elements. To calculate
> the total size, use:
>
> (apply #'* (array-dimensions array))
You assume that I already have the array. This is not the case and
ARRAY-TOTAL-SIZE-LIMIT implies that the actual number of elements you
can stuff in the array is dependent on the element type.
I may be paranoid, but maybe, because of the entry for A-T-S-L, doing
(apply #'* dimensions)
does not seem a reliable way to ensure that your array.
A case in point: under LW Windows
CL-USER> array-total-size-limit
2096896
CL-USER> (* 21 51201) ; The dimensions I need
1075221
CL-USER> (< * **)
T
CL-USER> (progn (make-array (list 21 51201)) t)
T
CL-USER> (progn (make-array (list 21 51201) :element-type 'double-float) t)
Error: Can't make an array of 8601792 bytes
...
Cheers
--
Marco
>>>>> "Marco" == Marco Antoniotti <·······@cs.nyu.edu> writes:
Marco> You assume that I already have the array. This is not the case and
Marco> ARRAY-TOTAL-SIZE-LIMIT implies that the actual number of elements you
Marco> can stuff in the array is dependent on the element type.
Marco> I may be paranoid, but maybe, because of the entry for A-T-S-L, doing
Marco> (apply #'* dimensions)
Marco> does not seem a reliable way to ensure that your array.
Marco> A case in point: under LW Windows
CL-USER> array-total-size-limit
Marco> 2096896
CL-USER> (* 21 51201) ; The dimensions I need
Marco> 1075221
CL-USER> (< * **)
Marco> T
CL-USER> (progn (make-array (list 21 51201)) t)
Marco> T
CL-USER> (progn (make-array (list 21 51201) :element-type 'double-float) t)
Marco> Error: Can't make an array of 8601792 bytes
Marco> ...
Interesting.
The entry for A-T-S-L says it's the smallest of the possible limits if
the total size varies according to the element type. I would say LW
is wrong here and A-T-S-L is too large, if you can't make a
double-float array with that many elements.
Ray
From: Steven M. Haflich
Subject: Re: Computing the actual size of an array given dimensions and element type.
Date:
Message-ID: <3F27456A.9030100@alum.mit.edu>
Marco Antoniotti wrote:
> I may be paranoid, but maybe, because of the entry for A-T-S-L, doing
>
> (apply #'* dimensions)
>
> does not seem a reliable way to ensure that your array.
You may be in need of an alternative CL array implementation I designed
some years ago. An important feature of this implementation is that the
upper limit on array size can be as large as you like, and that you are
guaranteed to be able to allocate as many large arrays as you like,
provided each one would individually fit in available memory, and that this
virtual machine would run on a machine wih only slightly more memory and/or
paging space than needed to allocate a single worst-possible-case array.
The idea isn't particularly valuable, so I'll explain how it works:
Each array (or alternatively, each _large_ array, leaving open how to
define "large") is assigned an index when it is created. The array is
then linearized and packaged in an email message, and then emailed to
some store-and-forward mail service.
The Lisp implementation has a couple threads. One opens a smtp listener
and awaits connection attempts. When an array is created, the Lisp
implementatiom linearizes the array contents into an email message and
mails it to itself using one of an arbitrary number of store-and-forward
email servers. The smtp listener is informed when a particular array is
needed by the main-thread Lisp computation. When some innocent remote
mailer attempts to deliver its array, the connection is refused unless
it is the array Lisp currently needs. But if the particular array has
not been referenced in two days, the background process accepts it and
retransmits it, preventing delivery timeout.
The result is a CL system that can use arbitrary amounts of memory with
only a trivial amount of local memory. Of course, execution speed
suffers a hit of a couple dozen orders of magnitude, but theoretical
correctness is aesthetically more important than the real cost of
purchasing memory, or even swap space on disk.
My ultimate goal is to devise a Common Lisp system that can execute
without significant dependence on any home host at all. Viruses are
smarter than you are, because as a speciaes they've been programming a
lot longer. Learn to live with it...
From: Marco Antoniotti
Subject: Re: Computing the actual size of an array given dimensions and element type.
Date:
Message-ID: <3F27E9F9.5010009@cs.nyu.edu>
I really like your idea. Do you have some (portable) source code
anywhere implementing the beast? :}
Cheers
marco
Steven M. Haflich wrote:
> Marco Antoniotti wrote:
>
>> I may be paranoid, but maybe, because of the entry for A-T-S-L, doing
>>
>> (apply #'* dimensions)
>>
>> does not seem a reliable way to ensure that your array.
>
>
> You may be in need of an alternative CL array implementation I designed
> some years ago. An important feature of this implementation is that the
> upper limit on array size can be as large as you like, and that you are
> guaranteed to be able to allocate as many large arrays as you like,
> provided each one would individually fit in available memory, and that this
> virtual machine would run on a machine wih only slightly more memory and/or
> paging space than needed to allocate a single worst-possible-case array.
>
> The idea isn't particularly valuable, so I'll explain how it works:
>
> Each array (or alternatively, each _large_ array, leaving open how to
> define "large") is assigned an index when it is created. The array is
> then linearized and packaged in an email message, and then emailed to
> some store-and-forward mail service.
>
> The Lisp implementation has a couple threads. One opens a smtp listener
> and awaits connection attempts. When an array is created, the Lisp
> implementatiom linearizes the array contents into an email message and
> mails it to itself using one of an arbitrary number of store-and-forward
> email servers. The smtp listener is informed when a particular array is
> needed by the main-thread Lisp computation. When some innocent remote
> mailer attempts to deliver its array, the connection is refused unless
> it is the array Lisp currently needs. But if the particular array has
> not been referenced in two days, the background process accepts it and
> retransmits it, preventing delivery timeout.
>
> The result is a CL system that can use arbitrary amounts of memory with
> only a trivial amount of local memory. Of course, execution speed
> suffers a hit of a couple dozen orders of magnitude, but theoretical
> correctness is aesthetically more important than the real cost of
> purchasing memory, or even swap space on disk.
>
> My ultimate goal is to devise a Common Lisp system that can execute
> without significant dependence on any home host at all. Viruses are
> smarter than you are, because as a speciaes they've been programming a
> lot longer. Learn to live with it...
>
From: Duane Rettig
Subject: Re: Computing the actual size of an array given dimensions and element type.
Date:
Message-ID: <4wue0rlpq.fsf@beta.franz.com>
Marco Antoniotti <·······@cs.nyu.edu> writes:
> I really like your idea. Do you have some (portable) source code
> anywhere implementing the beast? :}
I think I remember seeing his code placed in a large array somewhere
(to make it really portable). Unfortunately, we had a three-day plant
shutdown several years back, and I haven't seen the code since then.
Perhaps it is sitting in some virtual dead-letter archive on the internet...
> Cheers
>
> marco
>
> Steven M. Haflich wrote:
> > Marco Antoniotti wrote:
> >
>
> >> I may be paranoid, but maybe, because of the entry for A-T-S-L, doing
> >>
> >> (apply #'* dimensions)
> >>
> >> does not seem a reliable way to ensure that your array.
> > You may be in need of an alternative CL array implementation I
> > designed
>
> > some years ago. An important feature of this implementation is that the
> > upper limit on array size can be as large as you like, and that you are
> > guaranteed to be able to allocate as many large arrays as you like,
> > provided each one would individually fit in available memory, and that this
> > virtual machine would run on a machine wih only slightly more memory and/or
> > paging space than needed to allocate a single worst-possible-case array.
> > The idea isn't particularly valuable, so I'll explain how it works:
>
> > Each array (or alternatively, each _large_ array, leaving open how to
>
> > define "large") is assigned an index when it is created. The array is
> > then linearized and packaged in an email message, and then emailed to
> > some store-and-forward mail service.
> > The Lisp implementation has a couple threads. One opens a smtp
> > listener
>
> > and awaits connection attempts. When an array is created, the Lisp
> > implementatiom linearizes the array contents into an email message and
> > mails it to itself using one of an arbitrary number of store-and-forward
> > email servers. The smtp listener is informed when a particular array is
> > needed by the main-thread Lisp computation. When some innocent remote
> > mailer attempts to deliver its array, the connection is refused unless
> > it is the array Lisp currently needs. But if the particular array has
> > not been referenced in two days, the background process accepts it and
> > retransmits it, preventing delivery timeout.
> > The result is a CL system that can use arbitrary amounts of memory
> > with
>
> > only a trivial amount of local memory. Of course, execution speed
> > suffers a hit of a couple dozen orders of magnitude, but theoretical
> > correctness is aesthetically more important than the real cost of
> > purchasing memory, or even swap space on disk.
> > My ultimate goal is to devise a Common Lisp system that can execute
>
> > without significant dependence on any home host at all. Viruses are
> > smarter than you are, because as a speciaes they've been programming a
> > lot longer. Learn to live with it...
--
Duane Rettig ·····@franz.com Franz Inc. http://www.franz.com/
555 12th St., Suite 1450 http://www.555citycenter.com/
Oakland, Ca. 94607 Phone: (510) 452-2000; Fax: (510) 452-0182
From: Marco Antoniotti
Subject: Re: Computing the actual size of an array given dimensions and element type.
Date:
Message-ID: <3F2812FE.50001@cs.nyu.edu>
Duane Rettig wrote:
> Marco Antoniotti <·······@cs.nyu.edu> writes:
>
>
>>I really like your idea. Do you have some (portable) source code
>>anywhere implementing the beast? :}
>
>
> I think I remember seeing his code placed in a large array somewhere
> (to make it really portable). Unfortunately, we had a three-day plant
> shutdown several years back, and I haven't seen the code since then.
> Perhaps it is sitting in some virtual dead-letter archive on the internet...
Ahhh. That is what the 4.2 feet high printout of my old account mailbox
is. I'll microfilm it to make it more portable. :)
Seriously. I think this is getting out of hand :)
It looks like it is a LW bug after all.
Cheers
--
Marco