Velocity Reviews > Re: Size of an arraylist in bytes

Re: Size of an arraylist in bytes

Tim Rentsch
Guest
Posts: n/a

 02-01-2012
Keith Thompson <(E-Mail Removed)> writes:

> Tim Rentsch <(E-Mail Removed)> writes:
>> Keith Thompson <(E-Mail Removed)> writes:
>>> Nick Keighley <(E-Mail Removed)> writes:
>>>> On Nov 21, 9:25 pm, Joe Wright <(E-Mail Removed)> wrote:
>>>>> On 11/21/2011 15:06, Stefan Ram wrote:
>>> [...]
>>>>> A pointer is a variable object in storage which can hold the address of
>>>>> another object in storage. The address is a value, the pointer is an object.
>>>>>
>>>>> This concept is too complicated (or too simple) to some of my old friends
>>>>> but it works for me. Keith Thompson beat me into semi-submission several
>>>>> years ago until I got too tired to play. But here I am again.
>>>>>
>>>>> A pointer is an object. A function cannot return an object.
>>>>
>>>> surely this happens all the time
>>>>
>>>> struct point
>>>> {
>>>> int x;
>>>> int y;
>>>> };
>>>>
>>>> struct point make_point (int a, int b)
>>>> { struct point p; p.x = a; p.y = b; return p; }
>>>>
>>>> isn't that returning an object? In fact doesn't this return an object?
>>>>
>>>> int f (void) { return 1; }
>>>
>>> I'd say no. In both cases, the function returns a value, not an
>>> object. (There might be a "region of data storage" (from C99 3.14,
>>> the definition of "object") that's allocated to hold the value, but
>>> logically what the function returns is the value, not the object.)
>>>
>>> The value returned by a call to
>>>
>>> int f (void) { return 1; }
>>>
>>> is no more an object than the evaluation of the RHS of
>>>
>>> n = 1;
>>>
>>> results in an object. In particular, objects generally have

>>
>> In C99 this point could be argued. Under the new Standard,
>> however, it's clear that struct/union expressions do in
>> fact return objects, not just values. See 6.2.4 p8 (N154.

>

It is. Are N1548 and N1570 different in any way other than the
presence or absence of change bars?

> No, that paragraph refers *only* to a struct or union that contains a
> member with array type:
>
> A non-lvalue expression with structure or union type, where
> the structure or union contains a member with array type
> (including, recursively, members of all contained structures
> and unions) refers to an object with automatic storage duration
> expression is evaluated and its initial value is the value
> of the expression. Its lifetime ends when the evaluation of
> the containing full expression or full declarator ends. Any
> attempt to modify an object with temporary lifetime results in
> undefined behavior.
>
> That's a special case that was added to deal with code like this:
> [snip example]

Quite right. Thank you for the correction.

> In C99, there's no more an "object" created by func() [which
> returns a struct that has an array member] than there is one
> created by "int foo(void) { return 42; }". [snip C11 comment]

The Standard doesn't say so, but I argue that for all practical
purposes there is, because of how array conversion works. In
particular, the resulting pointer value is AFAIK valid, eg, can
be compared against NULL or other pointers, etc.

> If the struct returned by the function doesn't contain an array
> member, then it's still covered by the old rules which don't imply
> that there's an object. (Implementations might treat both cases
> the same way, but they needn't do so.)

Since member selection can be applied to the results of such
functions, the semantic descriptions of '.' and '->' imply that
there is.

Keith Thompson
Guest
Posts: n/a

 02-01-2012
Tim Rentsch <(E-Mail Removed)> writes:
> Keith Thompson <(E-Mail Removed)> writes:
>> Tim Rentsch <(E-Mail Removed)> writes:
>>> Keith Thompson <(E-Mail Removed)> writes:
>>>> Nick Keighley <(E-Mail Removed)> writes:
>>>>> On Nov 21, 9:25 pm, Joe Wright <(E-Mail Removed)> wrote:
>>>>>> On 11/21/2011 15:06, Stefan Ram wrote:
>>>> [...]
>>>>>> A pointer is a variable object in storage which can hold the address of
>>>>>> another object in storage. The address is a value, the pointer is an object.
>>>>>>
>>>>>> This concept is too complicated (or too simple) to some of my old friends
>>>>>> but it works for me. Keith Thompson beat me into semi-submission several
>>>>>> years ago until I got too tired to play. But here I am again.
>>>>>>
>>>>>> A pointer is an object. A function cannot return an object.
>>>>>
>>>>> surely this happens all the time
>>>>>
>>>>> struct point
>>>>> {
>>>>> int x;
>>>>> int y;
>>>>> };
>>>>>
>>>>> struct point make_point (int a, int b)
>>>>> { struct point p; p.x = a; p.y = b; return p; }
>>>>>
>>>>> isn't that returning an object? In fact doesn't this return an object?
>>>>>
>>>>> int f (void) { return 1; }
>>>>
>>>> I'd say no. In both cases, the function returns a value, not an
>>>> object. (There might be a "region of data storage" (from C99 3.14,
>>>> the definition of "object") that's allocated to hold the value, but
>>>> logically what the function returns is the value, not the object.)
>>>>
>>>> The value returned by a call to
>>>>
>>>> int f (void) { return 1; }
>>>>
>>>> is no more an object than the evaluation of the RHS of
>>>>
>>>> n = 1;
>>>>
>>>> results in an object. In particular, objects generally have
>>>
>>> In C99 this point could be argued. Under the new Standard,
>>> however, it's clear that struct/union expressions do in
>>> fact return objects, not just values. See 6.2.4 p8 (N154.

>>

>
> It is. Are N1548 and N1570 different in any way other than the
> presence or absence of change bars?

I don't know (is there a "diff" for PDF files?), but they're dated
2010-12-02 and 2011-04-12, respectively. I presume the latter
reflects whatever changes the committee made in those 4+ months.

N1570 has change bars marking changes relative to N1539.

[...]

>> In C99, there's no more an "object" created by func() [which
>> returns a struct that has an array member] than there is one
>> created by "int foo(void) { return 42; }". [snip C11 comment]

>
> The Standard doesn't say so, but I argue that for all practical
> purposes there is, because of how array conversion works. In
> particular, the resulting pointer value is AFAIK valid, eg, can
> be compared against NULL or other pointers, etc.
>
>
>> If the struct returned by the function doesn't contain an array
>> member, then it's still covered by the old rules which don't imply
>> that there's an object. (Implementations might treat both cases
>> the same way, but they needn't do so.)

>
> Since member selection can be applied to the results of such
> functions, the semantic descriptions of '.' and '->' imply that
> there is.

Here's what both N1256 (C99) and N1570 (C11) 6.5.2.3p3 say about the
semantics of "." (C90 is very similar.)

A postfix expression followed by the . operator and an identifier
designates a member of a structure or union object. The value
is that of the named member, and is an lvalue if the first
expression is an lvalue. If the first expression has qualified
type, the result has the so-qualified version of the type of
the designated member.

The first sentence clearly implies that the prefix must refer to
an object. The second sentence, though talks about what happens
if the prefix is not an lvalue. An lvalue is an expression that
(potentially(!)) designates an object.

So if the prefix isn't an lvalue, and therefore doesn't designate an
object, what object's member does the expression designate?

Personally, I think it would have made more sense to say that the
prefix is an expression (lvalue or not) of struct or union type, and
that x.y, if x is not an lvalue, yields the value of the member of
the struct or union value. In other words, values can have member
values even if there's no object in sight. (Probably not the best
possible wording.)

(An aside: I've complained before that the C90 and C99 standards'
definitions of "lvalue" were flawed, and suggested "expression that
potentially designates an object" to fix the problem. The word
"potentially" is needed to ensure that *ptr is an lvalue even if
ptr==NULL. I just now noticed that N1570 has this updated wording.
Looks like somebody was listening. I am inordinately pleased.)

--
Keith Thompson (The_Other_Keith) http://www.velocityreviews.com/forums/(E-Mail Removed) <http://www.ghoti.net/~kst>
Will write code for food.
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"

lawrence.jones@siemens.com
Guest
Posts: n/a

 02-01-2012
Tim Rentsch <(E-Mail Removed)> wrote:
>
> Are N1548 and N1570 different in any way other than the
> presence or absence of change bars?

Yes, there were lots of changes.
--
Larry Jones

We seem to be out of gun powder. -- Calvin

lawrence.jones@siemens.com
Guest
Posts: n/a

 02-01-2012
Keith Thompson <(E-Mail Removed)> wrote:
> Tim Rentsch <(E-Mail Removed)> writes:
> >
> > It is. Are N1548 and N1570 different in any way other than the
> > presence or absence of change bars?

>
> I don't know (is there a "diff" for PDF files?), but they're dated
> 2010-12-02 and 2011-04-12, respectively. I presume the latter
> reflects whatever changes the committee made in those 4+ months.
>
> N1570 has change bars marking changes relative to N1539.

For the record, N1539, N1547, and N1548 have identical content but
different diff marks: N1539 has none, N1547 is against N1516 (the
previous draft), and N1548 is against N1256 (C99 as corrected).
Likewise, N1569 and N1570 have identical content but only N1570 has diff
marks.
--
Larry Jones

Like I'm going to get any sleep NOW. -- Calvin

Shao Miller
Guest
Posts: n/a

 02-02-2012
On 2/1/2012 16:53, Keith Thompson wrote:
>
> Personally, I think it would have made more sense to say that the
> prefix is an expression (lvalue or not) of struct or union type, and
> that x.y, if x is not an lvalue, yields the value of the member of
> the struct or union value. In other words, values can have member
> values even if there's no object in sight. (Probably not the best
> possible wording.)
>
> (An aside: I've complained before that the C90 and C99 standards'
> definitions of "lvalue" were flawed, and suggested "expression that
> potentially designates an object" to fix the problem. The word
> "potentially" is needed to ensure that *ptr is an lvalue even if
> ptr==NULL. I just now noticed that N1570 has this updated wording.
> Looks like somebody was listening. I am inordinately pleased.)
>

Cool. Whether a co-incidence or not.

Now I have to read it to find out if there've been any changes in
regards to bounds-checking.

int a[2][2];
int * p = &a[0][3];

--
"The stationery store has moved. Aaargh!"

Joe keane
Guest
Posts: n/a

 02-02-2012
>Now I have to read it to find out if there've been any changes in
>regards to bounds-checking.
>
> int a[2][2];
> int * p = &a[0][3];
>

So far i know

int d(int x)
{
int a[4][5];
int j;

for (j =0 < j < 20; j++)
{
a[[0][j] = 0;
}

..
}

is legval C, and if it is not please let me know.

Keith Thompson
Guest
Posts: n/a

 02-02-2012
(E-Mail Removed) writes:
> Keith Thompson <(E-Mail Removed)> wrote:
>> Tim Rentsch <(E-Mail Removed)> writes:
>> >
>> > It is. Are N1548 and N1570 different in any way other than the
>> > presence or absence of change bars?

>>
>> I don't know (is there a "diff" for PDF files?), but they're dated
>> 2010-12-02 and 2011-04-12, respectively. I presume the latter
>> reflects whatever changes the committee made in those 4+ months.
>>
>> N1570 has change bars marking changes relative to N1539.

>
> For the record, N1539, N1547, and N1548 have identical content but
> different diff marks: N1539 has none, N1547 is against N1516 (the
> previous draft), and N1548 is against N1256 (C99 as corrected).
> Likewise, N1569 and N1570 have identical content but only N1570 has diff
> marks.

N1570's diff marks are against N1539.

And you've stated previously that the released C2011 standard has no
significant changes relatve to N1569/N1570.

--
Keith Thompson (The_Other_Keith) (E-Mail Removed) <http://www.ghoti.net/~kst>
Will write code for food.
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"

Keith Thompson
Guest
Posts: n/a

 02-02-2012
(E-Mail Removed) (Joe keane) writes:
>>Now I have to read it to find out if there've been any changes in
>>regards to bounds-checking.
>>
>> int a[2][2];
>> int * p = &a[0][3];
>>

>
> So far i know
>
> int d(int x)
> {
> int a[4][5];
> int j;
>
> for (j =0 < j < 20; j++)
> {
> a[[0][j] = 0;
> }
>
> ..
> }
>
> is legval C, and if it is not please let me know.

Once you delete the extra "[", the code's behavior is undefined; this
did not change between C99 and C11.

N1570 J.2 lists instances of undefined behavior, including this:

An array subscript is out of range, even if an object is
apparently accessible with the given subscript (as in the lvalue
expression a[1][7] given the declaration int a[4][5]) (6.5.6).

Annex J is informative, not normative, but 6.5.6p8 describes the rules
for pointer+integer addition, and it does not allow for interpreting an
array of array of int as it it were an array of int (and of course the
indexing operator is defined in terms of pointer addition).

In practice, you could get unexpected results in the presence of
optimization; the compiler may assume that j is in the range 0..4.

--
Keith Thompson (The_Other_Keith) (E-Mail Removed) <http://www.ghoti.net/~kst>
Will write code for food.
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"

Eric Sosman
Guest
Posts: n/a

 02-02-2012
On 2/1/2012 10:45 PM, Joe keane wrote:
>> Now I have to read it to find out if there've been any changes in
>> regards to bounds-checking.
>>
>> int a[2][2];
>> int * p =&a[0][3];
>>

>
> So far i know
>
> int d(int x)
> {
> int a[4][5];
> int j;
>
> for (j =0< j< 20; j++)
> {
> a[[0][j] = 0;
> }
>
> ..
> }
>
> is legval C, and if it is not please let me know.

It won't even compvile.

If you change `=0<' to `=0;' and change `[[' to `[' and
change `..' to zero or more valid statements, you'll have something
compvilable. It will, however, exhibit undefined behavior if you
execute it.

Here's the problem: The line `a[0][j] = 0;' (as amended) is
valid only when `0 <= j && j < 5'. For all other values of `j'
its behavior is undefined. Why?

`a[0]' is an array of five `int' elements. To this five-element
array we apply the `[j]' operator. In a five-element array, only the
elements [0],[1],[2],[3],[4] can be dereferenced (it is legal to form
a pointer to the non-existent element [5], but you mustn't try to
dereference that pointer). Therefore, if `j' is negative or >= 5,
the effect of the assignment is undefined.

Yes, yes, yes, we all know `a[0][5]' and `a[1][0]' are "at the
same location." Big deal: `a[0]' is still a five-element array, not
a twenty-element array. Your implementation may define the effect of
the (amended) code, but C does not.

--
Eric Sosman
(E-Mail Removed)d

Shao Miller
Guest
Posts: n/a

 02-02-2012
On 2/1/2012 22:45, Joe keane wrote:
>> Now I have to read it to find out if there've been any changes in
>> regards to bounds-checking.
>>
>> int a[2][2];
>> int * p =&a[0][3];
>>

>
> So far i know
>
> int d(int x)
> {
> int a[4][5];
> int j;
>
> for (j =0< j< 20; j++)
> {
> a[[0][j] = 0;
> }
>
> ..
> }
>
> is legval C, and if it is not please let me know.

Stepping through the critical [corrected] line 'a[0][j] = 0;', we have:

j -> identifier -> primary-expression -> ... -> expression

0 (both instances) -> constant -> primary-expression -> ... -> expression

a -> identifier -> primary-expression -> ... -> expression

a[0] -> postfix-expression -> ... -> expression

a[0][j] -> postfix-expression -> ... -> expression

a[0][j] = 0 -> assignment-expression -> ... -> expression

a[0][j] = 0; -> expression-statement -> statement

#1 'a' is an "lvalue": an expression that designates an object and has
type 'int[4][5]' as per the declaration.

#2 'a' is not the operand of either 'sizeof' nor of '&', so its
evaluation yields an expression with type 'int(*)[5]' and with value
"pointing to the first element of the array."

#3 'E1[E2]' is identical to '(*((E1)+(E2)))', so...

#4 First we add 0 to the pointer we obtained above (#2). That result
will be an expression with the same type and same value as the original
pointer (#2).

#5 Then we apply the unary indirection '*' operator. Since our pointer
(#4) does point to the first element of the array, an object is
designated and the result has type 'int[5]' and is an lvalue designating
that array object.

#6 Meanwhile 'j' has been evaluated and it has yielded a particular
run-time value with type 'int'.

#7 Just before we apply the '[]' operator, the lvalue we obtained (#5)
that has array type is not the operand or either 'sizeof' nor of '&', so
its evaluation yields an expression with type 'int *' and with value
"pointing to the first element of the array."

#8 Then we apply the second '[]' array subscripting operator.
Considering the identity above, again we first have a pointer (#7) and
an 'int' value (#6) being added together. If the
pointed-to/pointed-into array is large enough, the result will point to
an element of the array, or one element past the final element. If the
pointed-to/pointed-into array is not large enough, the behaviour is
undefined. We need to figure out this result before we can proceed with
application of the unary '*' operator (#3).

So is the array large enough for all the values of 'j' you allowed in
your 'for' loop? Your loop body is allowed to have values of 'j' from 0
through 19. How large is the array object? Well, that depends...

Is the array object the 'int[5]'-typed array designated by the lvalue
from #5? If so, then 'j' can run out of bounds.

Is the array object the 'int[4][5]'-typed array designated by the lvalue
from #1? If so, how many 'int'-typed elements are in that array? 0? 20?

Is the array object a region of data storage with contents that can
represent values for 20 contiguous 'int's and so happens to be suitably
aligned for 20 contiguous 'int's?

If the answers for these questions aren't clearly defined, perhaps
implementations will define the answers according to some particular
interpretation, including "bounds-checking" interpretations which define
your 'j' to go out of bounds.

--
"The stationery store has moved. Aaargh!"