2

I have been thinking of a couple of possible extensions to the C language which I'd like to know the opinion of others about.1 This one is about multi-dimensional arrays.

Imagine the following situation in C:

void matrix_mul(double **res, double **a, double **b, size_t n, size_t m, size_t r);

You cannot pass a double mat[4][4] (for example) to this function. If you define the function as:

void matrix_mul_N_M_R(double res[N][R], double a[N][M], double b[M][R]);

You'd just be wasting a perfectly written fine algorithm on a certain size of matrices.

What came to me (in shower obviously), was decay of multi-dimensional arrays to multi-level pointers. This is an extension to decay of 1d arrays to pointers.

Semantically, this would allow the first type of function to work on any two-dimensional array. Technically, this is how it would be implemented. The following code:

double a[3][5];
double b[5][4];
double c[3][4];
...
matrix_mul(c, a, b, 3, 5, 4);

would be equivalent to:

double a[3][5];
double b[5][4];
double c[3][4];
...
double **__a_decay = {a[0], a[1], a[2]};               /* generated by compiler */
double **__b_decay = {b[0], b[1], b[2], b[3], b[4]};   /* generated by compiler */
double **__c_decay = {c[0], c[1], c[2]};               /* generated by compiler */
matrix_mul(__c_decay, __a_decay, __b_decay, 3, 5, 4);  /* first three arguments decayed */

Is the application for such an extension very limited? Are there pitfalls? Could this possibly lead to insecure code where not using this feature wouldn't? Where else could such a feature come in handy?

1 Note that I'm not going to make another language myself, but would like to be sure of the feature's benefits and pitfalls before trying to suggest them to the C Standard Committee.

1

How would your proposed extension handle the situation where a multi-dimensional array isn't allocated statically? Having the extension be limited to cases where the allocation is static would make its behavior inconsistent with other array handling, but if the extension isn't limited to static array allocations then passing a double[5000][5000] to function which is expecting a double** would require the compiler to generate and fully populate a (double*)[5000], even if the function wouldn't use most of (or even any of) its elements each time the function was called.

A more useful extension might be to add types like double[][] and double[][][] as types in the language, and have each such type with N dimensions be stored as a double* along with N-1 values of type type size_t. It would be necessary to have separate methods for jagged and linear arrays, but it would not be necessary to have different methods for each size of linear array.

  • Actually you are right. The biggest problem with this, is that it's doing more than what's necessary. That is both possibly inefficient and not in the spirit of C, which is to do what you explicitly tell it, rather than automatically do complicated stuff (like C++ does). In that sense, your suggestion in the second paragraph is equally bad. – Shahbaz Nov 7 '14 at 15:24
  • @Shahbaz: What is wrong with the suggestion in the second paragraph? While it would be possible write a routine which accepts separately-passed parameters for starting address and stride, being able to have the compiler automatically supply both if given e.g. a double[12][34] would seem less error-prone. If the routine doesn't know the stride, it's going to have to get passed somehow, so having the compiler do it isn't going to be any less efficient than anything the programmer could do. I wouldn't think such an extension should be nearly as high a priority as... – supercat Nov 7 '14 at 15:35
  • @Shahbaz: ...e.g. supplying a means of declaring fixed-limit unsigned types that wouldn't promote (so that given wrap32_t n = 0xFFFFFFFF;, the value of n*n would be (wrap32_t)1 even on machines where int is 64 bits, but I would still consider such a thing helpful. – supercat Nov 7 '14 at 15:37
  • Oh, I'm sorry I misinterpreted stored as a double* along with N-1 values as something where N depends on the size of the array (like my original suggestion) instead of number of dimensions. Ok your suggestion is quite similar to what the compiler already does, a double x[N][M][R] is already an array of doubles with (unstored) 3-1 values. That wouldn't help with sending it through a double *** parameter. – Shahbaz Nov 7 '14 at 16:06
  • @Shahbaz: No, it wouldn't, but it would allow a method to work with arbitrarily-sized arrays while being able to access elements as arr[bank][row][column] rather than arr[(bank*num_rows+row)*num_columns+column]. – supercat Nov 7 '14 at 16:12
5

Perhaps you have heard the famous quote of Antoine de Saint-Exupery before:

A designer knows he has achieved perfection not when there is nothing left to add, but when there is nothing left to take away.

So before thinking about language extensions one should think about solving a problem with the existing language features in a convenient way (and I guess that's what the C standard commitee will answer you if you really make such a proposal).

In C, the natural solution to this kind of problem is to define a

struct Matrix
{
    int sizeX;
    int sizeY;
    double *values; /* vector with sizeX * sizeY elements */
};

(or something similar), and create operations working on that kind of data type, including operations for memory allocation and freeing, operations to fill that kind of structure with values from a 2D-array etc.

  • While I agree that solving problems with C would be great, I can't agree that you should stop thinking about features. When GNU added extensions to C (which mostly ended up adapted in C99 or C11), they helped improve the language, didn't they? – Shahbaz Sep 16 '13 at 9:46
  • @Shahbaz: of course, you should stop not thinking about new features (I did not write this, didn't I?). But before proposing a new feature for a problem one should check if there is not a convenient way to solve the same problem without any language extension. And AFAIK only a few of the GCC extensions were included in the newer C standards, not "most of them". – Doc Brown Sep 16 '13 at 11:44
4

The biggest problem with this seems to me to be that it's taking the C concept of arrays decaying to pointers and building on it.

Arrays decaying to pointers is already problematic in terms of clarity. If you see a function that takes a parameter of type int*, does this mean it expects an array of integers, or a single integer as a "fake passed-by-reference" argument? There's no way to know without examining the code of the function--or the documentation, assuming it exists and is up-to-date and accurate.

If you then expand on this to multiple levels of array-decay, the complexity and uncertainty grows exponentially with each dimension...

  • How could you expect to use a function without knowing what it does and what parameters it takes? If you have a function that's unclear, for example int calculate(int *x, int y), I highly doubt making it int calculate(int x[], int y) would help in any way. You have to look at the documentation of a function (e.g. the comments above it) to know what it does, and once you do, you'd also know if it takes an array or a pointer to a single int. – Shahbaz Sep 16 '13 at 9:40
  • Is that the only reason you are not a fan of arrays decaying to pointers? It seems to me at least, that it's a very convenient feature. How could you work on both arrays and malloced "arrays" without this feature? – Shahbaz Sep 16 '13 at 9:42
  • @Shahbaz: my main reason against decaying multidimensional array is that for higher dimensions (let's say N), each element requires N dereferences to access, thus there are N memory operations. perhaps you can do some benchmarks to see if it will meet your performance goals. If so, go for it. – rwong Sep 16 '13 at 14:00
  • @rwong, right. I'd benchmark it and let you know. It would be N dereferences vs. (N - 1) multiplications + N additions. I couldn't tell right now which is more expensive. – Shahbaz Sep 16 '13 at 14:37
  • For high speed array processing, OpenCV's remap parallelizes the multiplication step. This technique is probably also adopted by GPU programmers. Array speed benchmarking is also sensitive to cache effects. Some CPUs have cache implementation containing various "benchmarking glitches". – rwong Sep 16 '13 at 15:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.