Big arrays (confusion over FAQ 6.14)

[Andrew Fabbro]

I have a need to create an array that is larger than size_t - 1, which
I believe is the largest guaranteed array. I though I'd found
salvation in FAQ 6.14, but it appears I am not understanding
something.

The array is an array of pointers to structs. Here is an example
using a small array:

/* checks that malloc succeeded, main's return, etc. removed for
brevity */

#include <stdio.h>
#include <stdlib.h>

typedef struct {
int foo;
int bar;
} example_struct;

int main (void) {
example_struct * small_array[1000];
example_struct * a_single_struct ;

a_single_struct = malloc ( sizeof(example_ struct *) );
a_single_struct->foo = 4000;
printf ("a_single_stru ct foo: %i \n", a_single_struct->foo);

small_array[900] = a_single_struct ;
printf ("small_arra y 900 foo: %i\n",small_arr ay[900]->foo);

}

This works fine:

a_single_struct foo: 4000
small_array 900 foo: 4000

So far, so good. Now I want to do an array of, say, 3,000,000
members, too large for a simple big_array[3000000] declaration. So I
use the code from faq 6.14:

/* checks that malloc succeeded, main's return, etc. removed for
brevity */

#include <stdio.h>
#include <stdlib.h>

typedef struct {
int foo;
int bar;
} example_struct;

int main (void) {
example_struct * big_array;
example_struct * a_single_struct ;

a_single_struct = malloc ( sizeof(example_ struct *) );
a_single_struct->foo = 4000;
printf ("a_single_stru ct foo: %i \n", a_single_struct->foo);

big_array = malloc ( 3000000 * sizeof ( example_struct * ) );
big_array[1000000] = a_single_struct ; /* line 20, error below */
printf ("big_array foo: %i\n",big_array[1000000]->foo);

}

No go. The compiler (gcc in this case) returns:

test.c: In function 'main':
test.c:20: error: incompatible types in assignment
test.c:21: error: invalid type argument of '->'

So the example in FAQ 6.14 is:

"int *dynarray;
dynarray = malloc(10 * sizeof(int));

....you can reference dynarray[i] (for i from 0 to 9) almost as if
dynarray were a conventional, statically-allocated array (int a[10])"

Given that, I'm confused why

small_array[900] = a_simple_struct ;

works, while

big_array[1000000] = a_simple_struct ;

doesn't.

Is there some obvious error in my code? Have I just embarrassed
myself by displaying my obtusity before the comp.lang.c gods? Or is
there some better method of creating arrays (size_t - 1) ?

Thanks.

[CBFalconer]

Andrew Fabbro wrote:

>
I have a need to create an array that is larger than size_t - 1,
which I believe is the largest guaranteed array. I though I'd
found salvation in FAQ 6.14, but it appears I am not
understanding something.

You can't have it. No object whose size cannot be measured in a
size_t can exist. What are you trying to do?

--
Chuck F (cbfalconer at maineline dot net)
Available for consulting/temporary embedded and systems.
<http://cbfalconer.home .att.net>

--
Posted via a free Usenet account from http://www.teranews.com

[Malcolm McLean]

"CBFalconer " <cb********@yah oo.comwrote in message
news:46******** *******@yahoo.c om...

Andrew Fabbro wrote:

>>
I have a need to create an array that is larger than size_t - 1,
which I believe is the largest guaranteed array. I though I'd
found salvation in FAQ 6.14, but it appears I am not
understandin g something.

You can't have it. No object whose size cannot be measured in a
size_t can exist. What are you trying to do?

It can exist in the backing store.
As long as you don't need too many random accesses to your array, store it
on disk and read in chunks as you need.
Unfortunately the fseek() function quite often takes a long, which might not
be big enough. The fsetpos() takes yet another data type, fpos_t, and may
not be available.

--
Free games and programming goodies.
http://www.personal.leeds.ac.uk/~bgy1mm

[Army1987]

On Sat, 11 Aug 2007 22:09:57 -0700, Andrew Fabbro wrote:

I have a need to create an array that is larger than size_t - 1, which
I believe is the largest guaranteed array. I though I'd found
salvation in FAQ 6.14, but it appears I am not understanding
something.

On modern PCs, (size_t)(-1) is one byte less than 4 GB (on 32-bit
processors), or about 2.8 GB times the human population of the
Earth (on 64-bit processors). You are very likely *not* to have
enough memory, and if you have I think is impossible (or almost so)
to access it. What the hell are you trying to do? You might store
all those structs on a disk file.
(If you're programming for MS-DOS or some other system where it is
not absurd to have more memory than (size_t)(-1), go to
comp.os.msdos.p rogramming or whatever.)
--
Army1987 (Replace "NOSPAM" with "email")
No-one ever won a game by resigning. -- S. Tartakower

[Jens Thoms Toerring]

Andrew Fabbro <an***********@ gmail.comwrote:

I have a need to create an array that is larger than size_t - 1, which
I believe is the largest guaranteed array. I though I'd found
salvation in FAQ 6.14, but it appears I am not understanding
something.

The array is an array of pointers to structs. Here is an example
using a small array:

/* checks that malloc succeeded, main's return, etc. removed for
brevity */

#include <stdio.h>
#include <stdlib.h>

typedef struct {
int foo;
int bar;
} example_struct;

int main (void) {
example_struct * small_array[1000];
example_struct * a_single_struct ;

a_single_struct = malloc ( sizeof(example_ struct *) );

You already have a severe problem here: you don't allocate
enough memory. What you need to to allocate is not just a
pointer to an 'example_struct ' (that you already have with
'a_single_struc t'), but enough memory for an 'example_struct '.
So you need here

a_single_struct = malloc) sizeof( example_struct ) );

a_single_struct->foo = 4000;

With your alloction this only works by pure luck - if the
size of an 'example_struct ' is larger than that of a pointer
to such a structure then you may be overwriting memory you
didn't allocate (since on most machines the size of a pointer
is at least as large as that of an int you may just have
avoided disaster since you only wrote to the 'foo' member,
but if you also write to the 'bar' member then things will
look worse....)

printf ("a_single_stru ct foo: %i \n", a_single_struct->foo);

small_array[900] = a_single_struct ;
printf ("small_arra y 900 foo: %i\n",small_arr ay[900]->foo);

}

This works fine:

a_single_struct foo: 4000
small_array 900 foo: 4000

Unfortunately, it only looks like it works fine.

So far, so good. Now I want to do an array of, say, 3,000,000
members, too large for a simple big_array[3000000] declaration. So I
use the code from faq 6.14:

/* checks that malloc succeeded, main's return, etc. removed for
brevity */

#include <stdio.h>
#include <stdlib.h>

typedef struct {
int foo;
int bar;
} example_struct;

int main (void) {
example_struct * big_array;
example_struct * a_single_struct ;

a_single_struct = malloc ( sizeof(example_ struct *) );
a_single_struct->foo = 4000;
printf ("a_single_stru ct foo: %i \n", a_single_struct->foo);

You have the same problem here as above...

big_array = malloc ( 3000000 * sizeof ( example_struct * ) );

'big_array' is a pointer to an 'example_struct ', but you
allocate memory for 3000000 pointers to 'example_struct '
which you then assign to 'big_array'.

big_array[1000000] = a_single_struct ; /* line 20, error below */

And here you get caught: since 'big_array' is of type
pointer to 'example_struct ' big_array[1000000] is of
type 'example_struct ', but what you try to assign it
is of type pointer to 'example_struct ' and that's why
the compiler tells you

test.c:20: error: incompatible types in assignment

Since you want an array of pointers to 'example_struct '
you must define 'big_array' to be a pointer to pointer
to 'example_struct ', i.e.

example_struct ** big_array;

to get things to work.

printf ("big_array foo: %i\n",big_array[1000000]->foo);

And since 'big_array[1000000]' is of type 'example_struct '
(and not pointer to such a structure) you can't use '->'
with that as the compiler tells you with

test.c:21: error: invalid type argument of '->'

Or is
there some better method of creating arrays (size_t - 1) ?

I don't think you really have a problem with 'size_t' here
and, BTW, size_t is a type and not a value, the maximum
value that can be stored in a variable of type size_t is
SIZE_MAX as defined in <stdint.h>, at least if your com-
piler supports this C99-ism (gcc does), which typically
is much larger than just 3 millions. I guess the problem
is rather that you want an array that's larger than the
amount of memory that the system allows you for local
"real" (fixed sized) array. But no, there's no better way
for creating large arrays (or arrays that have a variable
size) than using memory allocation at run-time.

Regards, Jens
--
\ Jens Thoms Toerring ___ [e-mail]
\______________ ____________ http://toerring.de

[Flash Gordon]

Malcolm McLean wrote, On 12/08/07 08:25:

>
"CBFalconer " <cb********@yah oo.comwrote in message
news:46******** *******@yahoo.c om...

>Andrew Fabbro wrote:

>>>
I have a need to create an array that is larger than size_t - 1,
which I believe is the largest guaranteed array. I though I'd
found salvation in FAQ 6.14, but it appears I am not
understandi ng something.

You can't have it. No object whose size cannot be measured in a
size_t can exist. What are you trying to do?

It can exist in the backing store.

I C terms that is not an object.

As long as you don't need too many random accesses to your array, store
it on disk and read in chunks as you need.
Unfortunately the fseek() function quite often takes a long,

Actually, it *always* takes a long on a conforming implementation.

which might
not be big enough.

True.

The fsetpos() takes yet another data type, fpos_t,

No, it takes a pointer to fpos_t.

and may not be available.

It is not optional on hosted implementations so it will be available on
any hosted implementation claiming conformance to any version of the C
standard. It does, however, have the problem that the only value you can
portably pass to it is one obtained with fgetpos.

You also have the problem that the file system might not support a
sufficiently large file.
--
Flash Gordon

[Mark McIntyre]

On Sun, 12 Aug 2007 11:13:38 +0200, in comp.lang.c , Army1987
<ar******@NOSPA M.itwrote:

>On modern PCs, (size_t)(-1) is one byte less than 4 GB (on 32-bit
processors), or about 2.8 GB times the human population of the
Earth (on 64-bit processors). You are very likely *not* to have
enough memory,

These days, blade PCs with 8+GB aren't that rare, especially in the
commercial sector.

>and if you have I think is impossible (or almost so)
to access it.

4 arrays of 2 GB ?

--
Mark McIntyre

"Debugging is twice as hard as writing the code in the first place.
Therefore, if you write the code as cleverly as possible, you are,
by definition, not smart enough to debug it."
--Brian Kernighan

[Eric Sosman]

Andrew Fabbro wrote:

I have a need to create an array that is larger than size_t - 1, which
I believe is the largest guaranteed array.

If you mean `(size_t)-1', you're out of luck: No object can
have more than SIZE_MAX bytes. Also, it's likely that the O/S
and the rest of your program will chew up some amount of memory,
so you won't even be able to get that high. It's a "theoretica l"
upper limit, not a practical one.

Note that if an array's elements are bigger than one byte
each, then the theoretical upper limit on element count will be
even lower. For example, an array of eight-byte elements cannot
possibly have more than `SIZE_MAX / 8' array slots to stay
within the allowable limit on overall byte count.

I though I'd found
salvation in FAQ 6.14, but it appears I am not understanding
something.

The array is an array of pointers to structs. Here is an example
using a small array:

/* checks that malloc succeeded, main's return, etc. removed for
brevity */

#include <stdio.h>
#include <stdlib.h>

typedef struct {
int foo;
int bar;
} example_struct;

int main (void) {
example_struct * small_array[1000];
example_struct * a_single_struct ;

a_single_struct = malloc ( sizeof(example_ struct *) );

This line requests enough memory for one struct pointer,
not for one struct. In this sample program you only make
use of the first int in the struct, and that's probably why
you seem to get away with the error. But if you tried to
use the second int you'd be very likely to get into trouble.

Avoiding this and similar errors is the big advantage of
the c.l.c. Approved Allocation Idiom:

a_single_struct = malloc(sizeof *a_single_struc t);

.... or more generally

pointer = malloc(count * sizeof *pointer);

One thing to be wary of when allocating "huge" arrays, even
with this improved form, is that the multiplication may not give
the right answer. If the mathematical product of the two terms
is larger than SIZE_MAX, the result is reduced modulo that
amount plus one and you'll wind up requesting a much smaller
block of memory. Your struct is probably about eight bytes
long; if `count' were `SIZE_MAX / 3', say, the mathematical
product would be about two and two-thirds times SIZE_MAX, and
the eventual result would be about two-thirds SIZE_MAX, or
roughly one-quarter the size you intended.

(Pedantry alert: The above description does not hold on
"exotic" machines where SIZE_MAX < INT_MAX. I've never heard
of such a machine, but the C Standard doesn't forbid them.)

a_single_struct->foo = 4000;
printf ("a_single_stru ct foo: %i \n", a_single_struct->foo);

small_array[900] = a_single_struct ;
printf ("small_arra y 900 foo: %i\n",small_arr ay[900]->foo);

}

This works fine:

a_single_struct foo: 4000
small_array 900 foo: 4000

So far, so good. Now I want to do an array of, say, 3,000,000
members, too large for a simple big_array[3000000] declaration. So I
use the code from faq 6.14:

/* checks that malloc succeeded, main's return, etc. removed for
brevity */

#include <stdio.h>
#include <stdlib.h>

typedef struct {
int foo;
int bar;
} example_struct;

int main (void) {
example_struct * big_array;
example_struct * a_single_struct ;

a_single_struct = malloc ( sizeof(example_ struct *) );

Same error as above.

a_single_struct->foo = 4000;
printf ("a_single_stru ct foo: %i \n", a_single_struct->foo);

big_array = malloc ( 3000000 * sizeof ( example_struct * ) );

This might be the same error as above, but if I understand
your purpose I think the actual error is that big_array is not
declared correctly. You may want

example_struct **big_array;

(The c.l.c. AAI works correctly with this declaration, too.)

big_array[1000000] = a_single_struct ; /* line 20, error below */
printf ("big_array foo: %i\n",big_array[1000000]->foo);

These would be correct with the revised big_array declaration.
As things stand, big_array[1000000] is not a struct pointer, but
a struct instance. If that's what you want, you could use

big_array[1000000] = *a_single_struc t;
printf (... big_array[1000000].foo);

>
}

No go. The compiler (gcc in this case) returns:

test.c: In function 'main':
test.c:20: error: incompatible types in assignment
test.c:21: error: invalid type argument of '->'

So the example in FAQ 6.14 is:

"int *dynarray;
dynarray = malloc(10 * sizeof(int));

...you can reference dynarray[i] (for i from 0 to 9) almost as if
dynarray were a conventional, statically-allocated array (int a[10])"

Given that, I'm confused why

small_array[900] = a_simple_struct ;

works, while

big_array[1000000] = a_simple_struct ;

doesn't.

Is there some obvious error in my code? Have I just embarrassed
myself by displaying my obtusity before the comp.lang.c gods? Or is
there some better method of creating arrays (size_t - 1) ?

Thanks.

--
Eric Sosman
es*****@ieee-dot-org.invalid

[Army1987]

On Sun, 12 Aug 2007 13:47:21 +0100, Mark McIntyre wrote:

On Sun, 12 Aug 2007 11:13:38 +0200, in comp.lang.c , Army1987
<ar******@NOSPA M.itwrote:

>>On modern PCs, (size_t)(-1) is one byte less than 4 GB (on 32-bit
processors) , or about 2.8 GB times the human population of the
Earth (on 64-bit processors). You are very likely *not* to have
enough memory,

These days, blade PCs with 8+GB aren't that rare, especially in the
commercial sector.

What kind of processor do they have? How wide is their size_t?
I still think that having more than 4GB on a computer with a 32
bit processor is *very* silly.

--
Army1987 (Replace "NOSPAM" with "email")
No-one ever won a game by resigning. -- S. Tartakower

[Mark McIntyre]

On Sun, 12 Aug 2007 15:34:35 +0200, in comp.lang.c , Army1987
<ar******@NOSPA M.itwrote:

>>
These days, blade PCs with 8+GB aren't that rare, especially in the
commercial sector.

>What kind of processor do they have?

Itanium and Amd-64, typically.

>I still think that having more than 4GB on a computer with a 32
bit processor is *very* silly.

Its just trickier to use.
--
Mark McIntyre

"Debugging is twice as hard as writing the code in the first place.
Therefore, if you write the code as cleverly as possible, you are,
by definition, not smart enough to debug it."
--Brian Kernighan