Differences between one-dimensional arrays in Java and C

[Paul Morrison]

Hi all,

I need to come up with some differences between arrays in Java and C, I have
searched Google and so far all I have found is the following:

Arrays in Java are reference types with automatic allocation of memory. In
C, arrays are groups of variables of the same type in adjacent memory.
Allocation for dynamic arrays is handled by the programmer.

This is an 8 mark question in an old exam paper, so I am assuming there are
more differences, but where can I find them?!

Thank you for your help.

--
Paul Morrison

[osmium]

"Paul Morrison" writes:

I need to come up with some differences between arrays in Java and C, I
have searched Google and so far all I have found is the following:

Arrays in Java are reference types with automatic allocation of memory. In
C, arrays are groups of variables of the same type in adjacent memory.
Allocation for dynamic arrays is handled by the programmer.

This is an 8 mark question in an old exam paper, so I am assuming there
are more differences, but where can I find them?!

I would try this search target on google:
<c arrays shortcomings>

[Malcolm]

"Paul Morrison" <pa**@morrison1 985.freeserve.c o.uk> wrote

I need to come up with some differences between arrays in Java and C, I
have searched Google and so far all I have found is the following:

Arrays in Java are reference types with automatic allocation of memory. In
C, arrays are groups of variables of the same type in adjacent memory.
Allocation for dynamic arrays is handled by the programmer.

This is an 8 mark question in an old exam paper, so I am assuming there
are more differences, but where can I find them?!

A Java array is basically this

struct jdouble1d
{
double *mem;
int size;
};

Evey time you read and write, the java compiler checks against the size
member and throws an exception for out of bounds. Internally it calls
malloc() to allocate the memory, and by some magic the garbage collector
knows when the array goes out of scope and calls free().

A Java 2d array is this

struct jdouble2d
{
struct jdouble1d *mem;
int size;
};

You will see that this has the quirk that not all the sub-arrays need be of
the same length.

What is a C array - just a chunk of memory that the program interprets as
being doubles, or chars, or whatever.
To allocate on the stack you use the notation
double buff[123];

To allocate on the heap you call malloc()

double *buff = malloc(123 * sizeof(double)) ;

If you call malloc() you must call free() manually, the compiler doesn't
have a magic garbage collector that does it for you.

Finally a C 2d arrays are a bit tricky. If we declare

double box[8][10];

we get a chunk of memory containing 800 doubles.

box[3][4] = 1;

and
double box2[800];
box[3 * 10 + 4] = 1;

are essentially equivalent.
However you can also construct a 2d array by calling lots of mallocs().

double **box = malloc(8 * sizeof(double *));
for(i=0;i<8;i++ )
box[i] = malloc(10 * sizeof(double)) ;

and you use the same notation
box[3][4] = 1;

as for the 2d array, despite the fact that the underlying representation is
quite different.

The advantage of Java is that it is impossible to corrupt the computer's
memory, and you d not need to store the array size separately. The advantge
of C is that array accesses compile to direct memory read/writes, and so are
faster.

[Axter]

Malcolm wrote:

"Paul Morrison" <pa**@morrison1 985.freeserve.c o.uk> wrote

I need to come up with some differences between arrays in Java and C, I have searched Google and so far all I have found is the following:

Arrays in Java are reference types with automatic allocation of memory. In C, arrays are groups of variables of the same type in adjacent memory. Allocation for dynamic arrays is handled by the programmer.

This is an 8 mark question in an old exam paper, so I am assuming there are more differences, but where can I find them?!
A Java array is basically this

struct jdouble1d
{
double *mem;
int size;
};

Evey time you read and write, the java compiler checks against the

size member and throws an exception for out of bounds. Internally it calls malloc() to allocate the memory, and by some magic the garbage collector knows when the array goes out of scope and calls free().

A Java 2d array is this

struct jdouble2d
{
struct jdouble1d *mem;
int size;
};

You will see that this has the quirk that not all the sub-arrays need be of the same length.

What is a C array - just a chunk of memory that the program interprets as being doubles, or chars, or whatever.
To allocate on the stack you use the notation
double buff[123];

To allocate on the heap you call malloc()

double *buff = malloc(123 * sizeof(double)) ;

If you call malloc() you must call free() manually, the compiler doesn't have a magic garbage collector that does it for you.

Finally a C 2d arrays are a bit tricky. If we declare

double box[8][10];

we get a chunk of memory containing 800 doubles.

box[3][4] = 1;

and
double box2[800];
box[3 * 10 + 4] = 1;

are essentially equivalent.
However you can also construct a 2d array by calling lots of mallocs().

You can also construct a 2D array by just calling malloc twice.
See C FAQ item 6.16, and look at the second example code.
http://www.eskimo.com/~scs/C-faq/q6.16.html

Also take a look at the following links:
http://code.axter.com/allocate*2darray.h
http://code.axter.com/allocate*2darray.c

double **box = malloc(8 * sizeof(double *));
for(i=0;i<8;i++ )
box[i] = malloc(10 * sizeof(double)) ;

and you use the same notation
box[3][4] = 1;

as for the 2d array, despite the fact that the underlying representation is quite different.

The advantage of Java is that it is impossible to corrupt the computer's memory, and you d not need to store the array size separately. The advantge of C is that array accesses compile to direct memory read/writes, and so are faster.

[Christian Kandeler]

Malcolm wrote:

What is a C array - just a chunk of memory that the program interprets as
being doubles, or chars, or whatever.
To allocate on the stack you use the notation
double buff[123];

To allocate on the heap you call malloc()

double *buff = malloc(123 * sizeof(double)) ;

The latter is not an array.
Christian

[Keith Thompson]

Christian Kandeler <ch************ ****@hob.de_inv alid> writes:

Malcolm wrote:

What is a C array - just a chunk of memory that the program interprets as
being doubles, or chars, or whatever.
To allocate on the stack you use the notation
double buff[123];

To allocate on the heap you call malloc()

double *buff = malloc(123 * sizeof(double)) ;

The latter is not an array.

Sure it is. Specifically, buff is not an array (it's a pointer), but
the object allocated by malloc() is an array (or at least can be
treated as one).

--
Keith Thompson (The_Other_Keit h) ks***@mib.org <http://www.ghoti.net/~kst>
San Diego Supercomputer Center <*> <http://users.sdsc.edu/~kst>
We must do something. This is something. Therefore, we must do this.

[Tim Rentsch]

"Axter" <te**@axter.com > writes:

Malcolm wrote:

[unrelated stuff snipped]

However you can also construct a 2d array by calling lots of

mallocs().

You can also construct a 2D array by just calling malloc twice.
See C FAQ item 6.16, and look at the second example code.
http://www.eskimo.com/~scs/C-faq/q6.16.html

Now here's an interesting question. I believe it's possible to
construct a 2D array (with both dimensions non-constant) by calling
malloc only once. For example:

T *elements, **array;
size_t element_size = sizeof *elements;
size_t pointer_size = sizeof *array;

size_t element_space = element_size * M * N; /* array is [M][N] */
size_t pointer_space = pointer_size * M; /* only need M pointers */

size_t extra_space = pointer_size-1 - (element_space-1) % pointer_size;
size_t space_needed = element_space + extra_space + pointer_space;

void *memory = malloc( space_needed );

size_t i;

if( memory == 0 ) exit(1);

elements = memory;

array = (T**)memory + (element_space + extra_space) / pointer_size;

for( i = 0; i < M; i++ ){
array[i] = & elements[N*i];
}

/* array now can be used as a 2D array */
/* to free, use 'free( & array[0][0] )' */
Since the memory returned by malloc is suitably aligned for all types,
both 'elements' and 'array' are suitably aligned for objects of their
respective types. Note that 'extra_space' is calculated so that
'element_space + extra_space' is a multiple of 'pointer_size'.

Each of the two areas of memory (at 'elements' and 'array') is used
only to store/retrieve objects of their respective types.

According to my best understanding the code above should work in
standard C. But I put it as a question - does anyone have an argument
to the contrary?

If someone has a supporting argument I'm happy to hear that also. :)

[Eric Sosman]

Tim Rentsch wrote:

Now here's an interesting question. I believe it's possible to
construct a 2D array (with both dimensions non-constant) by calling
malloc only once. For example:

[allocate space for elements, padding, and pointers]

Since the memory returned by malloc is suitably aligned for all types,
both 'elements' and 'array' are suitably aligned for objects of their
respective types. Note that 'extra_space' is calculated so that
'element_space + extra_space' is a multiple of 'pointer_size'.

Each of the two areas of memory (at 'elements' and 'array') is used
only to store/retrieve objects of their respective types.

According to my best understanding the code above should work in
standard C. But I put it as a question - does anyone have an argument
to the contrary?

Looks all right. A type's alignment requirement must be
a divisor of its size (otherwise arrays wouldn't work), so the
`extra_space' will be enough padding to get the pointers to
align properly. In fact, `extra_space' may be more than is
needed; if you really want to be parsimonious you can use a
dodge that someone posted here a year or two ago:

#include <stddef.h>
#define alignof(T) offsetof(struct {char c; T t;}, t)

Manually-inserted padding can also be used to write portable
versions of "the struct hack" for C90 implementations (C99
introduced an easier notation).

--
Eric Sosman
esosman#acm-dot-org.invalid

[pete]

Tim Rentsch wrote:

"Axter" <te**@axter.com > writes:

Malcolm wrote:

[unrelated stuff snipped]

However you can also construct a 2d array by calling lots of

mallocs().

You can also construct a 2D array by just calling malloc twice.
See C FAQ item 6.16, and look at the second example code.
http://www.eskimo.com/~scs/C-faq/q6.16.html

Now here's an interesting question. I believe it's possible to
construct a 2D array (with both dimensions non-constant) by calling
malloc only once. For example:

T *elements, **array;
size_t element_size = sizeof *elements;
size_t pointer_size = sizeof *array;

size_t element_space = element_size * M * N; /* array is [M][N] */
size_t pointer_space = pointer_size * M; /* only need M pointers */

size_t extra_space = pointer_size-1 - (element_space-1) % pointer_size;
size_t space_needed = element_space + extra_space + pointer_space;

void *memory = malloc( space_needed );

size_t i;

if( memory == 0 ) exit(1);

elements = memory;

array = (T**)memory + (element_space + extra_space) / pointer_size;

for( i = 0; i < M; i++ ){
array[i] = & elements[N*i];
}

/* array now can be used as a 2D array */
/* to free, use 'free( & array[0][0] )' */

Since the memory returned by malloc is suitably aligned for all types,
both 'elements' and 'array' are suitably aligned for objects of their
respective types. Note that 'extra_space' is calculated so that
'element_space + extra_space' is a multiple of 'pointer_size'.

Each of the two areas of memory (at 'elements' and 'array') is used
only to store/retrieve objects of their respective types.

According to my best understanding the code above should work in
standard C. But I put it as a question - does anyone have an argument
to the contrary?

Maybe.
Since pointer arithmetic is being done with array,
is it enough for array to be lined up with (T *),
or is the alignment requirement that array be lined up with an
array of (T *), which might have a larger alignment requirement?

I seem to recall that the case of

int i_array_2[2][2] = {0};
int *ptr = (int *)&array;

ptr[3] = 0;

wasn't acceptable to Doug Gwynn and several others on comp.std.c
based on the fact that there was no integer array with four elements,
even though there was certainly an object big enough
and also aligned for int.

--
pete

[Tim Rentsch]

Eric Sosman <es*****@acm-dot-org.invalid> writes:

Tim Rentsch wrote:

Now here's an interesting question. I believe it's possible to
construct a 2D array (with both dimensions non-constant) by calling
malloc only once. For example:

> [allocate space for elements, padding, and pointers]

[yada yada yada]
Looks all right. A type's alignment requirement must be
a divisor of its size (otherwise arrays wouldn't work), so the
`extra_space' will be enough padding to get the pointers to
align properly. In fact, `extra_space' may be more than is
needed;

Yes it might! Normally the unneed extra space (and even 'extra_space'
itself) won't be too big: I deliberately put the pointer array second
so that at most sizeof(T*)-1 extra space is needed. Usually a few
bytes at most.

if you really want to be parsimonious you can use a
dodge that someone posted here a year or two ago:

#include <stddef.h>
#define alignof(T) offsetof(struct {char c; T t;}, t)

Manually-inserted padding can also be used to write portable
versions of "the struct hack" for C90 implementations (C99
introduced an easier notation).

That's a nice trick. I'll definitely have to add that to my set of
arcane C knowledge.

Strictly speaking the definition shown isn't guaranteed to work. If
sizeof(T) is 8 and alignment_of(T) is 2, the result of alignof(T)
might be 2 or 4 or 6, or even 22. Using GCD( alignof(T), sizeof(T) )
should at least produce a result that is guaranteed to work (right?).
But using GCD still isn't enough to guarantee that the minimum
alignment necessary will result.

Furthermore I can envision cases where it might reasonably not yield
the minimum alignment needed; a compiler might choose to put the 't'
member of the struct above at offset 4 (rather than 2) in an attempt
to get better cache performance, for example.

Despite my protestations, a good technique to know. Thanks.