Function needs its own array for workspace - best practices?

Question

Suppose that the function

void foo(int n, double x[])

sorts the n-vector x, does some operations on x, and then restores the original ordering to x before returning. So internally, foo needs some temporary storage, e.g., at least an n-vector of integers so that it store the original ordering.

What's the best way to handle this temporary storage? I can think of two obvious approaches:

1. foo declares its own workspace by declaring an internal array, i.e., at the top of foo we have

   int temp[n];
   

2. in the main calling routine, dynamically allocate the n-vector of ints once and pass in the storage at each call to a version of foo that accepts the temporary storage as a 3rd arg, i.e.,

   double *temp = malloc(n*sizeof(double));
   foo(n, x, temp);
   

I'm worried that option 1 is inefficient (the function foo will get called many times with the same n), and option 2 is just plain ugly, since I have to carry around this temporary storage so that it's always available wherever I happen to need a call to foo(n,x).

Are there other more elegant options?

Answer 1

If you end up using option 2 – that is, the function uses memory that is allocated elsewhere – use proper encapsulation.

In a nutshell, don’t pass in a raw array, pass in a context object which has matching init and release functions.

Then the user must still pass in the context and properly set it up and tear it down but the details are hidden from her and she doesn’t care about the details of the allocation. This is a common pattern in C.

typedef struct {
    double* storage;
} foo_context;

void foo_context_init(foo_context*, int n);

void foo_context_free(foo_context*);

void foo(foo_context* context, int n, double x[]);

Now, for a very simple case this is clearly a tremendous overhead and I agree with Oli that option 1 called for.

Answer 2

Option 1 is clearly the cleanest (because it's completely encapsulated). So go with Option 1 until profiling has determined that this is a bottleneck.

Update

@R's comment below is correct; this could blow your stack if n is large. The pre-C99 "encapsulated" method would be to malloc the local array, rather than putting it on the stack.

Answer 3

On most architectures option 1 is very efficient since it allocates memory on the stack and is typically an add to the stack and/or frame pointer. Just be careful not to make n too large.

Answer 4

As Oli said in his answer the best is to have the function being autonomous about this temporary array. A single allocation is not going to cost a lot unless that function is called in a very fast loop... so get it right first, then profile and then decide if it's worth doing an optimization.

That said in a few cases after profiling and when the temp data structure needed was a bit more complex that a single int array I adopted the following approach:

void foo(int n, ... other parameters ...)
{
    static int *temp_array, temp_array_size;
    if (n > temp_array_size)
    {
        /* The temp array we have is not big enough, increase it */
        temp_array = realloc(temp_array, n*sizeof(int));
        if (!temp_array) abort("Out of memory");
        temp_array_size = n;
    }
    ... use temp_array ...
}

note that using a static array rules out for example multithreading or recursion and this should be clearly stated in the documentation.