Hacker News Reader

Comment by DSMan195276 | Hacker News Reader

DSMan195276

I like it, but the array details are a little bit off. An actual array does have a known size, that's why when given a real array `sizeof` can give the size of the array itself rather than the size of a pointer. There's no particular reason why C doesn't allow you to assign one array to another of the same length, it's largely just an arbitrary restriction. As you noted, it already has to be able to do this when assigning `struct`s.

Additionally a declared array such as `int arr[5]` does actually have the type `int [5]`, that is the array type. In most situations that decays to a pointer to the first element, but not always, such as with `sizeof`. This becomes a bit more relevant if you take the address of an array as you get a pointer to an array, Ex. `int (*ptr)[5] = &arr;`. As you can see the size is still there in the type, and if you do `sizeof *ptr` you'll get the size of the array.

View on HN

I really wish that int arr[5] adopted the semantics of struct { int arr[5]; } -- that is, you can copy it, and you can pass it through a function without it decaying to a pointer. Right now in C:

    typedef uint32_t t1[5];
    typedef struct { uint32_t arr[5]; } t2;
    void test(t1 a, t2 b) {
        t1 c;
        t2 d;
        printf("%d %d %d %d\n", sizeof(a), sizeof(b), sizeof(c), sizeof(d));
    }

will print 4, 20, 20, 20. I understand that array types having their sizes in their types was one of Kernighan's gripes with Pascal [0], which likely explains why arrays decay to pointers, but for those cases, I'd say you should still decay to a pointer if you really wanted to, with an explicit length parameter.

[0] http://www.lysator.liu.se/c/bwk-on-pascal.html

> I really wish that int arr[5] adopted the semantics of struct { int arr[5]; }

You and me both. In fact, D does this. `int arr[5]` can be passed as a value argument to a function, and returned as a value argument, just as if it was wrapped in a struct.

It's sad that C (and C++) take every opportunity to instantly decay the array to a pointer, which I've dubbed "C's Biggest Mistake":

https://www.digitalmars.com/articles/C-biggest-mistake.html

That would be a nice little "gcc addition" to the C standard, honestly.

To bad they spend most their time doing whatever it is they do.

Earlier versions of gcc actually used to support this in a very restricted context in C90 (or maybe gnu89) mode:

  struct foo { int a[10]; };
  struct foo f(void);
  int b[10];
  b = f().a;

In C90, you can't actually do anything with `f().a` because the conversion from array to pointer only happened to lvalues (`f().a` is not an lvalue), and assignment is not defined for array variables (though gcc allowed it). The meaning is changed in C90 so that non-lvalue arrays are also converted to pointers. gcc used to take this distinction into account, so the above program would compile in C90 mode but not in C99 mode. New versions of gcc seem to forbid array assignment in all cases.

I think this quirk also means that it's technically possible to pass actual arrays to variadic functions in C90, since there was nothing to forbid the passing (it worked in gcc at least, though in strict C90, you wouldn't be able to use the non-lvalue array). In C99 and above, a pointer will be passed instead.

I have long been convinced that WG14 has no real interest in improving C's security beyond what a Macro Assembler already offers out of the box.

Even the few "security" attempts that they have made, still require separate pointer and length arguments, thus voiding any kind of "security" that the functions might try to achieve.

However even a Macro Assembler is safer than modern C compilers, as they don't remove your code when one steps into a UB mine.

One of the members of WG14 posted here a few days ago that they only use C89.

Mind blown.

Beware of struct padding.

sizeof(b.arr) != sizeof(b)

Consider:

  #include <stddef.h>

  #include <inttypes.h>

  typedef struct Array Array;

  struct Array {
      int32_t data[8];
  };

  void foo(Array const* arr) {
      size_t sz = sizeof(arr->data);
  }

> There's no particular reason why C doesn't allow you to assign one array to another of the same length

Actually, there is a particular (though not necessarily good) reason, since that would require the compiler to either generate a loop (with conditional branch) for a (unconditional) assignment or generate unboundedly many assembly instructions (essentially a unrolled loop) for a single source operation.

Of course, that stopped being relevant when they added proper (assign, return, etc) support for structs, which can embed arrays anyway, but that wasn't part of the language initially.

It was initially available in 1982, so plenty of time to add the other features.

https://www.bell-labs.com/usr/dmr/www/chist.html

Another weird property about C arrays is that &arr == arr. The reference of an array is the pointer to the first element, which is what `arr` itself decays to. If arr was a pointer, &arr != arr.

I think it is clearer to say that arr == &arr[0] but your mileage may vary.

Is today international speak like a pirate day? arr arr arr

&arr is a pointer to the array. It will happen to point to the same place as the first element, but in fact they have different types, and e.g. (&arr)[0] == arr != arr[0].

> There's no particular reason why C doesn't allow you to assign one array to another of the same length, it's largely just an arbitrary restriction.

IIRC C has an informal guarantee that no primitive syntax will ever cause the CPU to do more than O(1) work at runtime. Assignment is always O(1), and therefore assignment is limited to scalars. If you need assignment that might do O(N) work, you need to call a stdlib function (memcpy/memmove) instead. If you need an allocation that might do O(N) work, you either need a function (malloc) or you need to do your allocation not-at-runtime, by structuring the data in the program's [writable] data segment, such that it gets "allocated" at exec(2) time.

This is really one of the biggest formal changes between C and C++ — C++ assignment, and keywords `new` and `delete`, can both do O(N) work.

(Before anyone asks: a declaration `int foo[5];` in your code doesn't do O(N) work — it just moves the stack pointer, which is O(1).)

This reasoning falls apart for structs with array members.

> Assignment is always O(1)

This depends on what you consider to be O(1) - being that the size of the array is fixed it's by definition O(1) to copy it, but I might get your point. I think in general your point isn't true though, C often supports integer types that are too large to be copied in a single instruction on the target CPU, instead it becomes a multi-instruction affair. If you consider that to still be O(1) then I think it's splitting hairs to say a fixed-size array copy would be O(N) when it's still just a fixed number of instructions or loop iterations to achieve the copy.

Beyond that, struct assignments can already generate loops of as large a size as you want, Ex: https://godbolt.org/z/8Td7PT4af

I think the meaning here is that assignment is never O(N) for any variable N computed at runtime. Of course, you can create arbitrarily large assignments at compile time, but this always has an upper bound for a given program.

Then you are wrong, since we're already talking about arrays of sizes known at compile time. Indeed, otherwise we would also need to remember the size in the runtime.

IIRC this is valid in C99:

    void foo(size_t n) {
        int arr[n];
        …
    }

VLAs can be declared in a single statement, but they cannot be initialized in C17 (6.7.9):

> The type of the entity to be initialized shall be an array of unknown size or a complete object type that is not a variable length array type.

Curiously, C23 actually seems to break the O(1) rule, by allowing VLAs to be initialized with an empty initializer:

  int arr[n] = {};

GCC generates a memset call (https://godbolt.org/z/5v31bKs5a) to fill the array with zeros.

How do you think it works? Does the compiler generate some kind of stack alloc?

Stupid question: Does that mean a huge value for 'n' can cause stack overflow at runtime? I recall that threads normally get a fixed size stack size, e.g., 1MB.

It just moves the stack pointer by n which is O(1). It doesn’t initialize it of course. But my point is that the array size isn’t known at compile time.

Yes, it causes stack overflow at runtime. Compilers warn for it, in particular clang has a warning that you can configure to pop up whenever the stack usage of a function goes beyond some limit you set - I think that setting it to 32k or 64k is a safe and sane default as e.g. macOS thread stack sizes are just 512kb

I don't think we're actually in disagreement here. It looks like I misread the parent comment to be claiming that fixed-size array assignment ought to be considered O(N), when no such claim is made.

Yeah to clarify I'm definitely in agreement with you that it's O(1), the size is fixed so it's constant time. It's not like the 'n' has to be "sufficiently small" or something for it to be O(1), it just has to be constant :)

People are being very loose about what O(n) means so I attempted to clarify that a bit. Considering what assignments can already do in C it's somewhat irrelevant whether they think it's O(n) anyway, it doesn't actually make their point correct XD

> IIRC C has an informal guarantee that no primitive syntax will ever cause the CPU to do more than O(1) work at runtime. Assignment is always O(1), and therefore assignment is limited to scalars.

this is absolutely and entirely wrong. You can assign a struct in C and the compiler will call memcpy when you do.

Enjoy: https://godbolt.org/z/98PnhYoev

And any structure is O(1), not O(n), because C structures are not parameterized.

memcpy is not O(1)

It's O(1) relative to any size computed at runtime: that is, running the same program (with the same array size) on different inputs will always take the same of work for a given assignment.

We're in the context of the assignment operation in the language here. Yes, in C you can only assign statically-known types but that does not mean you can just ignore that a = f(); may take a very different time depending on the types of a and f

> IIRC C has an informal guarantee that no primitive syntax will ever cause the CPU to do more than O(1) work at runtime.

How about CPUs that have no, say, division instruction, so it has to be emulated with a loop?

Fixed-width divisions are O(1), just comparatively expensive (and potentially optimized to run in variable time). Consider that you can do long division on pairs of numerals of, say, up to 20 digits and be Pretty Confident of an upper bound on how long it's going to take you (you know it's not going to take more than 20 rounds), even though it's going to take you longer to do that than it would for you to add them.

Well C does allow "copying" an array if it's wrapped inside a struct, which does not make it O(1). gcc generates calls to memcpy in assembly for copying the array.

Interesting, I didn't fully realise that. That it's arbitrary is annoying, I clearly had tried to rationalise it to myself! Thanks for the comments, will get around to amending

Hi, great article. Regarding char, I'd remark that getchar() etc return int so it can return -1 for EOF or error.

I'm pretty sure this implies int as a declaration is always signed, but tbh I'm not completely sure!

int, as all other integer types except char, is indeed signed by default.

Aside: signedness semantics of char is implementation-defined. However, the type char itself is always distinct from both signed char and unsigned char.

Another one corner of the language where arrays actually being arrays is important is multidimensional array access:

    int arr[5][7];
    arr[3][5] = 4; // equivalent to *(*(arr + 3) + 5) = 4;

This works because (arr + 3) has type "pointer to int[7]", not "pointer to int". The resulting address computation is

    (char*)arr + 3 * sizeof(int[7]) + 5 * sizeof(int) ==
    (char*)arr + 26 * sizeof(int)

That's also another reason why types like "int [5][7][]" are legal but "int [5][][]" are not.

Really, are multidimensional arrays an important part of the language?

The above code looks like it's indexing into an array of pointers. If you want a flat array, make a few inlined helper functions that do the multiplying and adding. Your code will be much cleaner and easier to understand.

Of course multidimensional arrays are an important part of the language, just as the ability to have structs inside structs.

> The above code looks like it's indexing into an array of pointers. If you want a flat array, make a few inlined helper functions that do the multiplying and adding. Your code will be much cleaner and easier to understand.

It is a "flat" array already, not an array of pointers: [0]. No need to write the code that compiler generates for you already.

[0] https://godbolt.org/z/x3cPf3TvT

I am aware that it's flat already.

The code above does not mention any pointer types, so why would you assume that it's indexing into an array of pointers?

I can't think of any reason why get(a, i, j) is more readable than a[i][j].

Return pointer to array of 4 integers:

  int32_t (* bar(void))[4] {
      static int32_t u[4] = {1, 0, 1, 0};
      return &u;
  }

Return a pointer to a function taking a char:

  void f(char a) {
      // ...
  }

  void (* baz(void))(char) {
      return f;
  }

This is where you really want to start using typedefs.

> it's largely just an arbitrary restriction

Kind of. But the restriction is in keeping with the C philosophy of no hidden implementation magic. C has the same restriction on structs. That's the same question; an array of bytes of known size to the compiler it could easily abstract away. But assignment is always a very cheap operation in C. If we allow assigning to represent memcpy() that property is no longer true.

Same reason why Rust requires you to .clone() so much. It could do many of the explicit copies transparently, but you might accidentally pass around a 4 terabyte array by value and not notice.

Perhaps I am missing something in the spec - but trying this in various compilers, it seems that you *can* assign structs holding arrays to one another, but you *cannot* assign arrays themselves.

This compiles:

  struct BigStruct {
    int my_array[4];
  };
  int main() {
    struct BigStruct a;
    struct BigStruct b;
    b = a;
  }

But this does not:

  int main() {
    int a[4];
    int b[4];
    b = a;
  }

That seems like an arbitrary restriction to me.

In the first example a & b are variables, which can be assigned to each other. In the second a & b are pointers, but b is fixed, so you can not assign a value to it.

They’re not pointers. sizeof a == 4*sizeof(int), not sizeof(int*).

They're pointers, just weird ones. The compiler knows it's an array, so it gives the result of the actual amount of space it takes up. If you passed it into a function, and used the sizeof operator in the function, it'd give `sizeof(int *)`. Because sizeof is a compile-time operation, so the compiler still knows that info for your example.

That jest means it decays into a pointer after being passed as a function argument. In the example given however it’s not a pointer. Just like it wouldn’t be inside a struct.

Essentially ‘b = a’ in the second example is equivalent to ‘b = &a[0]’ or assigning an array to a pointer.

This is because if you use an array in an expression, it’s value is (most of the time) a pointer to the array’s first element. But the left element is not an expression, therefore it is referring to b the array.

Example one works because no arrays are referred to in the expression side, so this shorthand so to speak is avoided.

Arrays can be a painful edge in C, for example variable length arrays are hair pulling.

The left side of assignment in C is an expression. it's just not in a context where array-to-pointer decay is triggered.

Ironically, Rust does allow you to implicitly copy an array as long as it reduces to a memcpy

Specifically arrays [T; N] are Copy if precisely T is Copy. So, an array of 32-bit unsigned integers [u32; N] can be copied, and so can an array of immutable string references like ["Hacker", "News", "Web", "Site"] but an array of mutable Strings cannot.

The array of mutable Strings can be memcpy'd and there are situations where that's actually what Rust will do, but because Strings aren't Copy, Rust won't let you keep both - if it did this would introduce mutable aliasing and so ruin the language's safety promise.

> But assignment is always a very cheap operation in C.

That's just not true though, you can assign struct's of an arbitrarily large size to each-other and compilers will emit the equivalent of `memcpy()` to do the assignment. They might actually call `memcpy()` automatically depending on the particular compiler.

The fact that if you wrap the array in a struct then you're free to copy it via assignment makes it arbitrary IMO.

Reply on news.ycombinator.com