Jens Gustedt's Blog

January 13, 2011

VLA as function arguments

Filed under: C99, language, P99 — Jens Gustedt @ 22:05

Now that we aren’t afraid of variably modified types anymore let us have a look on how these can be used as function arguments.

Therefore we will


An array with known size at compile time can be handled relatively simple by the compiler:

  • somewhere it reserves the necessary memory space for the array (static global space or locally, on the stack)
  • in places where the array is used it places the address of that memory
  • in places where the size of the array is needed it places the compile time known value

The implicit size information of VLA

Since the size of a VLA is not known at compile or startup time the size information has to be maintained differently for them. A natural idea would be to have a VLA implemented as some sort of compound structure that contains the size plus the array itself. Unfortunately if we want VLA be compatible with “classic” arrays in C this is not possible, because otherwise a definition such as the following would fail:

double (*A)[n] = malloc(n * sizeof(double));

Here we assign a memory location on the heap to a pointer to VLA. The RHS malloc is anything that a C programmer would want to do about such an allocation. If we’d had a hidden “size” field in the VLA, the RHS would have to take that into account

double (*A)[n] = malloc(n * sizeof(double) + /* some overhead? */);
double (*A)[n] = malloc(sizeof(double[n]));

By long experience such requirement and attention doesn’t even work well for strings and their infamous terminating 0 character, so this would never work reliably with humans as programmers. In particular, since the status of being a VLA is only implicit to the declaration, the first variant would have to be modified if the status of n changes: the two declarations for n

size_t const n = 100;
enum { n = 100 };

would make A a VLA for the first (needing an overhead) and a “classic” array for the second.

So the size information can’t be held in the same place as the array itself and must be held implicitly at some place that is to the discretion of the compiler. Usually this will be some hidden variable that the compiler places where appropriate and that is evaluated wherever the size information is needed. Such a variable can not be made visible to other compilation units since when we pass the address of VLA to a function in a different unit, this function can not know if this VLA was a global variable, allocated on the stack or on the heap.

There is another complication to operate the size information of a VLA well, a precise time point during the execution of the program where the declaration with all its size expressions is evaluated. Variables with static storage duration don’t have such a point so VLA and generally all VM types can’t be of static storage duration. We the defining execution order of a surrounding function that precisely defines when and of what size a VLA is created, VM type or variable is defined.

Arrays as function parameters

If we look at a function prototype as the following

double sum(double A[100]);

When we call such a function

double myArr[100];
.
double theSum = sum(myArr);

the array, as in all expression but sizeof, evaluates to the address of the first element in the array. So in fact an equivalent specification would have been

double theSum = sum(&myArr[0]);

So all size information even the compile time constant 100 is lost in that calling mechanism. Consequently C silently also changes our function prototype under the hood. In fact the above prototype is equivalent to

double sum(double (*A));

Now is all size information lost? No for multidimensional arrays things are different, fortunately. If we have a function and a call as here

double eigen(double  A[100][100]);
double mySquare[100][100];
double lambda = eigen(mySquare);

the evaluation of mySquare leads to a pointer to double[100], noted in the crude C type notation as double(*)[100]. The above is thus equivalent to

double eigen(double  (*A)[100]);
double mySquare[100][100];
double lambda = eigen(&mySquare[0]);

So in essence only the first dimension of an array parameter is transformed into a pointer the other type information, including the size, is kept.

In oldish C there only has been the equivalence of

double sum(double A[]);
double sum(double (*A));

C99 also allows us to specify type modifiers (const and/or volatile) for the pointer like this

double sum(double A[const]);
double sum(double (*const A));

In a syntactically obscure way it has also the possibility to specify that the function can expect a minimum size of elements that are passed via the pointer.

double sum(double A[const static 100]);
double sum(double (*const A));

Here the array notation is equivalent to the pointer notation only that the function has the right to expect that *A has at least 100 elements, meaning in particular that the pointer can’t be 0.

Passing VM types

When passing a variable X of a VM type the implicit size information of X must be passed to the called. Since there is no such thing like run time type information in C and since generally the implementation of the function will be in another compilation unit that information has to be made explicit. The approach that C takes here is really basic: a parameter declaration is just a declaration as any other, so we have to specify the bounds. Analogously to the above example we may declare

double eigen(size_t n, double  A[n][n]);
double mySquare[n][n];
double lambda = eigen(n, mySquare);

So here the declaration of parameter A of eigen evaluates the value n that it received as a first parameter. As we know now this is silently rewritten as

double eigen(size_t n, double  (*A)[n]);
double mySquare[n][n];
double lambda = eigen(n, &mySquare[0]);

As effect, now in the implementation of eigen expressions such as A[4][4] can be interpreted at runtime and the correct index computations can be provided by the compiler.

The rules for that kind of function definition are simple. At the point of definition you can put any expression in the [] that is valid at that point. Just as if you had placed the declaration at the beginning of the block of the function:

extern size_t factor;
double augen(size_t n, double  (*A)[factor * n]) {
.
}

has the same effect as

extern size_t factor;
double augen(size_t n, void*secondParameter) {
double  (*A)[factor * n] = secondParameter;
.
}

So the way we specified the bounds for the function eigen above is just a convention, but probably a quite sane one. Only see that the definition of the function is important for the evaluation of the parameter types not the point of declaration of the prototype. That the expressions for the bound are “unimportant” at the point where the prototype is declared can also be seen from the fact that we may replace them by ‘*’, there.

double augen(size_t n, double  (*A)[*]) ;

This ‘*’ inside the ‘[]’ is not the dereference operator but a completely new overloading of the ‘*’ token.

P99 for simple interfaces

Making the bounds of a VM typed parameters explicit can be tedious and error prone. P99 tries to help you on that by providing several macros that help you with that. We already have seen P99_ALEN(A, N) that with its second argument N allows to ask for the bound in the Nth dimension of N. This can be handy where the expressions that leads to these bounds are complicated or where the variables that entered in these expressions might already have changed their value.

P99 also lets you declare, define and call functions easily and can keep track of all the bounds. Let us look at the following inline definition dotproductFunc and and macro declaration dotproduct that operate on pointers to 1-dimensional VLA:

/* header file */
inline
double dotproductFunc(P99_AARG(double, A),
                      P99_AARG(double, B)) {
  register double ret = 0.0;
  P99_DO(size_t, i, 0, P99_ALEN(A, 1))
    ret += (*A)[i] * (*B)[i];
  return ret;
}

#define dotproduct(VA, VB) dotproductFunc(P99_ACALL(VA), P99_ACALL(VB))

/* in just one compilation unit */
extern inline
double dotproductFunc(P99_AARG(double, A),
                      P99_AARG(double, B));

The designated user interface is the macro. Whenever there is an expression of the form dotproduct(myS, myT) is found in the code it will be replaced by a four argument call that is similar to dotproductFunc(P99_ALEN(myS, 1), myS, P99_ALEN(myT, 1), myT). The function dotproductFunc itself is declared with a prototype like

double dotproductFunc(size_t const nA, double (*A)[nA],
                      size_t const nB, double (*B)[nB]);

In essence this declares two extra parameters for the bounds of the arrays. Inside the function body we don’t need these parameters (nA and nB of the example) and may entirely work with the macro P99_ALEN.

These macros can even do better than that. 2-dimensional matrix multiplication can be declared with the simple interfaces

void multFunc(P99_AARG(double, C, 2),
              P99_AARG(double, A, 2),
              P99_AARG(double, B, 2));
#define mult(CRR, ARR, BRR) multFunc(P99_ACALL(CRR, 2), P99_ACALL(ARR, 2), P99_ACALL(BRR, 2))

So here an additional parameter controls the dimension of the VLAs to which the arguments point. The expansion of these macros gets a bit too complicated to present here. If you are really interested in learning on how this works (and not simply want to use it) it is definitively time to read the source.

Advertisements

7 Comments

  1. You might also want to say something about the overload of the static keyword in this context, i.e.,

    double sum(double A[static 100]);
    and the other syntax for passing VLAs,
    
    double sum(double A[*]);
    
    	

    Comment by Joel Salomon — January 14, 2011 @ 14:11

    • Good idea, though hopefully this already complex and lengthy post doesn’t become too long.

      Comment by Jens Gustedt — January 14, 2011 @ 14:14

  2. BTW, I’ve seen a trick that might protect from some incorrect usages of P99_ALEN() for function parameters in the Stack Overflow thread Is there a standard function in C that would return the length of an array?

    Comment by Joel Salomon — January 24, 2011 @ 16:07

    • I don’t like the “0[pointer]” trick too much, and it really only helps to avoid C++ errors with operator overloading. Since C++ doesn’t (and will never) have VLA, this isn’t too usefull. Also for the iterated version of P99_ALEN this would be a bit difficult to implement.

      But in fact the compile time assertion to avoid at least some pointer errors is probably a good idea. I will look into it. [Done now, included in the latest version.]

      Comment by Jens Gustedt — January 24, 2011 @ 16:35

      • Looking ahead to the P1x library:

        Something that’s recently been discussed on comp.std.c is C1x’s _Generic keyword, and how it might fit in. Note that the modulo trick I pointed to fails for any type where sizeof (type) % sizeof(type *) == 0. But there are only so many built-in types for which this is true. So…

        #define NELEM_(arr) (sizeof (arr) / sizeof (arr)[0])
        #define NELEM(arr) _Generic(&(arr),                  \
            long(*)[] : NELEM_(arr),                         \
            long ** : _Static_assert(0, "not an array"),     \
            … &c., &c., …
            long long(*)[] : NELEM_(arr),                    \
            long long ** : _Static_assert(0, "not an array), \
            default: (NELEM_(arr) / !(sizeof(arr) % sizeof(arr)[0])))
        

        A comment I got: “Wow. If that’s the solution, all I can say is that I really, really hate the problem. ☺”

        Comment by Joel Salomon — February 14, 2011 @ 23:10

        • Yes, _Generic and _Static_assert might definitively be helpful. BTW, if you have _Static_assert you probably wouldn’t do the division by zero trick for the general case any more.
          I agree that this is ugly. The advantage would be to encapsulate that in a P1X macro such that a user would never have to write such code.
          Also, this adds safety for the 20 or so standard types and their pointer derivatives, but still none for extended integer or floating point types, nor for struct or union that just happen to have half the width of a pointer or so.

          Comment by Jens Gustedt — February 15, 2011 @ 09:36

      • Actually, I’d intended for the floating-point types to be included in the “… &c., &c., …” line. Also, I’m not saying this can be done in a platform-independent way; on the contrary, to write the code you’d need to know all the built-in types available on the given platform. And it’s ugly.

        But assuming GCC et al. retain the __typeof__ extension, this becomes something like:

        #define NELEM(arr) \
          _Generic(&(arr), \
            (__typeof__ arr[0])(*)[]: (sizeof (arr) / sizeof (arr)[0]) \
            default: _Static_assert(0, #arr " not an array") )
        

        A less-intrusive extension might be to recognize “void(*)[]” as compatible to “pointers to array of anything”, as distinct from “void**”. It’s kind of a single-use extension, though.

        BTW: Looking at N1547 §6.7.10, it seems _Static_assert() cannot be used in middle of an expression, and you’d always need the divide-by-zero trick. Oh, well. ☹

        Comment by Joel Salomon — February 16, 2011 @ 16:08


RSS feed for comments on this post.

Sorry, the comment form is closed at this time.

Blog at WordPress.com.