improve union of 2 arrays in c++

Question

Is there a way to make this way of making a Union of 2 arrays A and B in c++ faster (given any n)? I have beeing thinking but can not see other way...

double *A = (double *)malloc( n*n *sizeof(double));
double *B = (double *)malloc(   n *sizeof(double));
double *U = (double *)malloc((n*n+n) *sizeof(double));


int i=0, ci=0;
for (i = 0; i <n*n; i++)
    U[ci++] = A[i];
for (i = 0; i < n; i++)
    U[ci++] = B[i];

Answer 1

There isn't an asymptotically better way to do this, because you have to copy over every element exactly once. However, you might be able to do better by using a bulk copy operation like memcpy to do the work for you:

double *A = (double *)malloc( n*n *sizeof(double));
double *B = (double *)malloc(   n *sizeof(double));
double *U = (double *)malloc((n*n+n) *sizeof(double));

/* Copy over A onto U. */
memcpy(U, A, n * n * sizeof(double));

/* Append B to U. */
memcpy((char*)U + n * n * sizeof(double), B, n * sizeof(double));

This may be faster because the logic to copy the bytes over may be hand-optimized.

You've tagged this question with C++, though it looks more like C code. That said, if you are using C++, you could write it like this (using std::copy):

double *A = new double[n * n];
double *B = new double[n];
double *U = new double[n * n + n];

std::copy(A, A + n * n, U);
std::copy(B, B + n,     U + n * n);

Or, better yet, using std::vector with no exposed memory management or pointers:

vector<double> A(n * n);
vector<double> B(n);

vector<double> U;
U.reserve(A.size() + B.size());
U.insert(U.end(), A.begin(), A.end());
U.insert(U.end(), B.begin(), B.end());

Hope this helps!

Answer 2

Since all you do is concatenating two memory blocks, you can use memcpy:

double *A = (double *)malloc( n*n *sizeof(double));
double *B = (double *)malloc(   n *sizeof(double));
double *U = (double *)malloc((n*n+n) *sizeof(double));
memcpy(U, A, n*n *sizeof(double));
memcpy(U+n*n *sizeof(double), B, n *sizeof(double));

If hardware provides single-instruction copying, you may get some performance improvement from it. On the other hand, optimizers can probably figure out what you're doing anyway, and replace your code with calls to memcpy for you.