fast array copy

[simkn]

Hello,

I'm writing a function that updates an array. That is, given an
array, change each element.

The trick is this: I can't change any elements until I've processed
the entire array. For example, the manner in which I update element 1
depends on several other (randomly numbered) elements in the array.
So, I can't change an element until I've figured out how every element
changes.

To do this, I am simply creating a duplicate array and writing the new
values in that array. When I'm done, I copy the new array over the
old one. My question is, what's the best way of doing this?

The (seemingly) naive way is to copy the elements from the new over
the old array one-by-one. For example:

double h[SIZE];
void update()
{
double hnew[SIZE];
// do stuff to populate hnew
memcpy(h,hnew,SIZE*sizeof(double));
}


However, since arrays are pointers, it seems like it'd be much more
efficient to just change where the pointer is pointing. For example:

double h[SIZE];
void update(double* hnew)
{
// do stuff to populate hnew
delete(h);
h = hnew;
}

This requires relying on the caller to allocate memory for hnew.

Is the pointer method better? Does anyone have any better ideas?

Thanks,
Mark

 

[E. Robert Tisdale]

I'm writing a function that updates an array.
That is, given an array, change each element.

The trick is this: I can't change any elements until I've processed
the entire array. For example, the manner in which I update element 1
depends on several other (randomly numbered) elements in the array.
So, I can't change an element
until I've figured out how every element changes.

To do this, I am simply creating a duplicate array and writing the new
values in that array. When I'm done, I copy the new array over the
old one. My question is, what's the best way of doing this?

The (seemingly) naive way is to copy the elements from the new over
the old array one-by-one. For example:

double h[SIZE];
void update()
{
double hnew[SIZE];
// do stuff to populate hnew
memcpy(h,hnew,SIZE*sizeof(double));
}


However, since arrays are pointers, it seems like it'd be much more
efficient to just change where the pointer is pointing. For example:

double h[SIZE];
void update(double* hnew)
{
// do stuff to populate hnew
delete(h);
h = hnew;
}

This requires relying on the caller to allocate memory for hnew.

Is the pointer method better? Does anyone have any better ideas?

double* update(size_t size, double h[size]) {
double hnew[size];
// do stuff to populate hnew
memcpy(h, hnew, size*sizeof(double));
return h;
}

 

[Chris Torek]

Hello,

I'm writing a function that updates an array. That is, given an
array, change each element.

The trick is this: I can't change any elements until I've processed
the entire array. For example, the manner in which I update element 1
depends on several other (randomly numbered) elements in the array.
So, I can't change an element until I've figured out how every element
changes.

To do this, I am simply creating a duplicate array and writing the new
values in that array. When I'm done, I copy the new array over the
old one. My question is, what's the best way of doing this?

The (seemingly) naive way [to put the new values back into an
existing array] is to copy the elements from the new over
the old array one-by-one. ...

That will indeed work:

double h[SIZE];
void update()
{
double hnew[SIZE];
// do stuff to populate hnew
memcpy(h,hnew,SIZE*sizeof(double));
}

Or, simpler:

memcpy(h, hnew, sizeof h);

However, since arrays are pointers ...

But arrays are not pointers. You might as well start with "since
cows are hamburger". Cows are not hamburger, and a pile of ground
beef cannot do everything a cow can do.

It *is* true that the "good stuff" you get with arrays is basically
as useful as the "good stuff" you get with pointers. If you just
want the protein, the bones and other bits in a cow just get in
the way. But while you only may *want* the one part or the other,
never mistake the one *for* the other.

it seems like it'd be much more
efficient to just change where the pointer is pointing.

You can do that, provided you have a pointer (not an array) *and*
sufficient memory to which the pointer can point.

For example:

double h[SIZE];
void update(double* hnew)
{
// do stuff to populate hnew
delete(h);
h = hnew;
}

This requires relying on the caller to allocate memory for hnew.

This also does not work, because h is still an array. C forbids
the assignment (h is not a "modifiable lvalue", in standard-ese).

Note that if you use a pointer, it takes *more* space than if
you just use an array, because the pointer itself requires space,
and you still need just as much space as you used to have in the
array. Consider the two versions diagrammatically:

(A) array version:

+---------------------------------+
| big chunk of memory |
+---------------------------------+

(B) pointer version:

+---------------------------------+
| big chunk of memory |
+---------------------------------+
^
| +---+
+-------------------|-* | tiny little pointer
+---+

Is the pointer method better?

"Better" is subjective; but if your application currently spends
a lot of time copying memory from hnew to h, and you can remove
all the "copy" time, your application may run noticeably faster.

Does anyone have any better ideas?

"Better" is subjective...

Note that regardless of which version (array or pointer) you have
above, you *also* need, at least temporarily, a second "big chunk
of memory" (hnew -- whether this is another array, or a pointer
plus a chunk of memory it points to) to hold all the new values.
If there is no reason not to leave that big chunk of memory around
all the time, you can simply make *two* arrays:

(C) two-array version:

+---------------------------------+
| big chunk of memory |
+---------------------------------+

+---------------------------------+
| big chunk of memory |
+---------------------------------+

Now you just need a way to select which of the two arrays to use.
You can do this with a pointer, and point it to either array, or
with a simple two-valued variable:

double array0[SIZE], array1[SIZE];
int which_array = 0;
...
which_array = 1 - which_array; /* from 0 to 1, or 1 to 0 */

Of course, writing:

if (which_array == 0)
... array0 ...
else
... array1 ...

is a pain -- but it is also unnecessary. Just make your two arrays
into a single variable, by using an array of two arrays:

(D) array of two arrays version:

+---------------------------------+
| big chunk of memory |
+---------------------------------+
| big chunk of memory |
+---------------------------------+

double array[2][SIZE];
int which_array = 0;
...
which_array = 1 - which_array; /* from 0 to 1, or 1 to 0 */

... array[which_array] ...

Alternatively, use that "tiny little pointer", along with the arrays.
This works with both arrangements (C) and (D):

(C):
which_array = 1 - which_array;
ptr = (which_array == 0 ? &array0[0] : &array1[0]);

(D):
which_array = 1 - which_array;
ptr = &array[which_array][0];

Instead of actual arrays, of course, if you have pointers, you can
use malloc():

#include <stdlib.h>

double *mem_blob_0, *mem_blob_1;
...
mem_blob_0 = malloc(SIZE * sizeof *mem_blob_0);
mem_blob_1 = malloc(SIZE * sizeof *mem_blob_1);

or an array of two pointers:

double *mem_blob[2];
...
mem_blob[0] = malloc(SIZE * sizeof *mem_blob[0]);
mem_blob[1] = malloc(SIZE * sizeof *mem_blob[1]);

and/or you can get twice as much memory with a single malloc():

double *mem_blob_of_twice_the_size;
...
mem_blob_times_two = malloc(2 * SIZE * sizeof *mem_blob_times_two);

after which something like:

double *p = &mem_blob_times_two[SIZE];
/* or: = mem_blob_times_two + SIZE; */

gets you the "second half".

Of all these methods, which one is the best? "Best" is subjective....

 

[Charlie Gordon]

Hello,

I'm writing a function that updates an array. That is, given an
array, change each element.

The trick is this: I can't change any elements until I've processed
the entire array. For example, the manner in which I update element 1
depends on several other (randomly numbered) elements in the array.
So, I can't change an element until I've figured out how every element
changes.

To do this, I am simply creating a duplicate array and writing the new
values in that array. When I'm done, I copy the new array over the
old one. My question is, what's the best way of doing this?

The (seemingly) naive way is to copy the elements from the new over
the old array one-by-one. For example:

double h[SIZE];
void update()
{
double hnew[SIZE];
// do stuff to populate hnew
memcpy(h,hnew,SIZE*sizeof(double));

better yet : memcpy(h, hnew, sizeof(h));

}


However, since arrays are pointers, it seems like it'd be much more
efficient to just change where the pointer is pointing. For example:

NONONONO : arrays are not pointers.
but you can use pointers to arrays to avoid the final copying step.

double h[SIZE];
void update(double* hnew)
{
// do stuff to populate hnew
delete(h);

Do you mean the C++ delete operator ? even C++ won't let you do that.

h = hnew;

Both C and C++ will refuse to compile this.

}

This requires relying on the caller to allocate memory for hnew.
Is the pointer method better? Does anyone have any better ideas?

Doing it with pointers is OK, but you have to be consistent in your memory
allocation scheme.
And allocating memory with malloc is definitely less efficient than defining an
automatic array.
It might even be less efficient than the copying stage it saves.

This is an example with pointers :

double *h;

int main() {
...
/* initialization of h */
h = malloc(SIZE * sizeof(*h));
for (int i = 0; i < SIZE; i++) {
h = some_initial_value...
}
...
}

void update() {
double *hnew;
hnew = malloc(SIZE * sizeof(*hnew));
/* do stuff to populate hnew */

free(h);
h = hnew;
}

Another caveat with this method is error checking, that I left out, but must be
written in a real world program.

Chqrlie.

 

[Eric Sosman]

Hello,

I'm writing a function that updates an array. That is, given an
array, change each element.

The trick is this: I can't change any elements until I've processed
the entire array. For example, the manner in which I update element 1
depends on several other (randomly numbered) elements in the array.
So, I can't change an element until I've figured out how every element
changes.

To do this, I am simply creating a duplicate array and writing the new
values in that array. When I'm done, I copy the new array over the
old one. My question is, what's the best way of doing this?

The (seemingly) naive way is to copy the elements from the new over
the old array one-by-one. For example:

double h[SIZE];
void update()
{
double hnew[SIZE];
// do stuff to populate hnew
memcpy(h,hnew,SIZE*sizeof(double));

Nitpick: Write the third argument as `sizeof h'.
At the very least, write `SIZE * sizeof h[0]'. The
reasons are the same as those given in connection
with the argument to malloc().

}


However, since arrays are pointers, it seems like it'd be much more
efficient to just change where the pointer is pointing. For example:

double h[SIZE];
void update(double* hnew)
{
// do stuff to populate hnew
delete(h);
h = hnew;
}

This requires relying on the caller to allocate memory for hnew.

Is the pointer method better? Does anyone have any better ideas?

What language are you using? If it's C++, ignore the
C answer I'm about to write and take your question to
comp.lang.c++ instead.

As written, the code won't work at all: The line
`h = hnew' will not compile. `h' is an array, and arrays
are not assignable.

You could, however, use pointers throughout instead of
trying to mix pointers and arrays. Something like this
could be done:

double h1[SIZE], h2[SIZE];
double *hcurr = h1, *hnext = h2;

void update(void) {
/* Compute `hnext' values from `hcurr' values */
...

/* Swap the "next" and "current" roles */
hcurr = hnext;
hnext = (hcurr == h1) ? h2 : h1;
}

 

[Andrey Tarasevich]

...
However, since arrays are pointers, it seems like it'd be much more
efficient to just change where the pointer is pointing. For example:

double h[SIZE];
void update(double* hnew)
{
// do stuff to populate hnew
delete(h);
h = hnew;
}

This requires relying on the caller to allocate memory for hnew.

Is the pointer method better? Does anyone have any better ideas?
...

There's no "pointer method". Arrays are _not_ pointers, which means that
there's no way to "just change where the pointer is pointing". Read the
FAQ about arrays, look up some information on the net or get yourself a
good C book.

 

[Xenos]

However, since arrays are pointers, it seems like it'd be much more
efficient to just change where the pointer is pointing. For example:

double h[SIZE];
void update(double* hnew)
{
// do stuff to populate hnew
delete(h);
h = hnew;
}

No, arrays are not pointers. This will not work. Even if you change the
array to be a pointer to an array to make it work, you will probably find
that the allocation/deallocation takes more time than simply copying the
array.

Is the size of the array constant? Then just keep two of them, and use a
pointer to an array to swap between them each time you do an update.

DrX

 

[Herbert Rosenau]

Hello,

I'm writing a function that updates an array. That is, given an
array, change each element.

The trick is this: I can't change any elements until I've processed
the entire array. For example, the manner in which I update element 1
depends on several other (randomly numbered) elements in the array.
So, I can't change an element until I've figured out how every element
changes.

To do this, I am simply creating a duplicate array and writing the new
values in that array. When I'm done, I copy the new array over the
old one. My question is, what's the best way of doing this?

The (seemingly) naive way is to copy the elements from the new over
the old array one-by-one. For example:

double h[SIZE];
void update()
{
double hnew[SIZE];
// do stuff to populate hnew
memcpy(h,hnew,SIZE*sizeof(double));
}


However, since arrays are pointers, it seems like it'd be much more
efficient to just change where the pointer is pointing.

No, a pointer NOT an array and an array is NOT a pointer. An Array is
an array - even as the address opf an array(member) is a pointer.

For example:

double h[SIZE];
void update(double* hnew)
{
// do stuff to populate hnew
delete(h);
h = hnew;
}

This requires relying on the caller to allocate memory for hnew.

Is the pointer method better? Does anyone have any better ideas?

Thanks,
Mark

You describes lists, not arrays, sou you should create a list of
objects instead an a simple array, because reordering or resizing a
list is much easier than reordering an array.

There are some types of lists you can use depending on the type of
work you have to do on:
- single linked list: designed to work straight forward on
- double linked list: go through in both directions quickly
- tree: insert, remove, sort, search
makes search quick
can easy malformed to an double linked list,
making search really time intensive
- AVL tree: sorted insert, remove, search(, resort)
like simple tree but extended to hold
each branch in (nearly) same deep
making search really quick,

to name only the most common used types.