3 ms·

Interestingly the article doesn't mention two-dimensional arrays and they're curios because they bring a certain asymmetry with them. It always tripped me over

Interestingly the article doesn't mention two-dimensional arrays and they're curios because they bring a certain asymmetry with them. It always tripped me over the most in C because I otherwise find the language very "symmetrical". It often feels like in design of this language the beauty of expressing certain things took priority over readability or safety which I admire in a way. But somehow not in the case of the two-dimensional arrays. If you see a[i][j] it could mean two completely different things: 1) "a" is a continuous chunk of memory of N*M bytes, so it behaves as char*; a[i][j] == *(a + i*M + j) 2) "a" is an array of char* pointers that point to N completely distinct memory chunks of size M, so it behaves as char**; a[i][j] == *(*(a + i) + j) With flat arrays the difference between an array as a variable and a pointer to the first element is literally negligible because you won't even see the difference in the assembly. This is why the automatic decay-to-pointer makes a lot of sense. But that breaks completely with multiple dimensions. You definitely see the difference in the assembly because the memory layout is so different.

ActorNightly 5mo ago
I mean, just like with 1 dimensional arrays, it depends on the context. Array memory is on the stack. The size of that array is actually not known at run time, its only known at compile time, where any reference to that length gets resolved by the compiled. If your 2d array sits on the stack, then inferring memory layout is pretty easy. If you are dealing with pointer that was passed to a function, then you can't assume anything about data size or limits, which is why many functions that take pointers take a size parameter as well.
- alexey-salmin 5mo ago
  > If your 2d array sits on the stack, then inferring memory layout is pretty easy. If you are dealing with pointer that was passed to a function, then you can't assume anything about data size or limits, which is why many functions that take pointers take a size parameter as well. Right, but 2d arrays come into this picture with their own quirks again. You're not just passing the size as the parameter, you can pass it as a "special" parameter that influences how the compiler will interpret other parameters. E.g. in C99 you can do this: void do(size_t x, size_t y, int a[][y]); Here "y" plays the critical role because it will be used to compute offsets in the a[i][j] expression. For 1d arrays this doesn't happen. Of course it's still generalizable as "all but the outermost dimensions should be known" and for 1d array the outermost dimension is the only dimension. Still, this whole thing always felt a bit odd to me.
  - uecker 5mo ago
    Well, you give the explanation yourself: The size for the outermost array is not always needed, and then C allows it to be omitted. But my recommendation is to always give the size and then everything is regular and the compiler can use the information for warnings.
- simiones 5mo ago
  > Array memory is on the stack. Array memory can sit on either the stack or the heap. > The size of that array is actually not known at run time, its only known at compile time, where any reference to that length gets resolved by the compiled. This is also a bit misleading, in two ways. First, it's not clear what you mean by "size" here - the size of the memory block(s), or the shape of the array? Second, many people think that the C runtime doesn't know the amount of memory allocated to an array, but this is actually false. It's just the C abstract model that for some reason chose to not expose this information - but the size is actually always stored and accessible, and this is virtually mandated by the standard: otherwise, `free(arr)` couldn't realistically work, it would have to be `free(arr, size)`. This is one of the weirdest inefficiencies of C, in fact - it requires you to store the size of arrays twice - once in user code, and another time in the internal logic of the allocator. Edit: and as a fun extra, C++ not only inherited this mistake from C, but reproduced it again, meaning that a C++ array allocated with new[] actually stores the size twice, at least with typical implementations - once in the C++ runtime and again in the allocator - and still requires the user-space code to store it a third time. This is because `delete[]` needs to call the destructors of all of the elements of the array, regardless of where and how the array was allocated, so the number of array elements needs to be stored alongside the object itself.
  - ActorNightly 5mo ago
    >Array memory can sit on either the stack or the heap. No, if we are using the definition of an array that is like int c[] = ..., that is always going to be on the stack. Heap continuous memory =/= array. You can use the [] operator to access it like an array, but fundamentally, as far as structures in C language are concerned, those 2 are different, because they get treated by compiler differently. >but the size is actually always stored and accessible, and this is virtually mandated by the standard: otherwise, `free(arr)` couldn't realistically work, That would only be true if each element in the array was a char. The dynamic data structure stores total amount of memory allocated by address, it has no info about the size of the element, so it can't infer the actual number of items at runtime. You could write your own malloc that does this, but generally, that is left to the user for flexibility. For example, a really good practice in C coding that basically solves any double free is a mempool that allocates all the memory up front. That way, you never really even have to call free, and the memory you allocate can be partitioned any way you chose dynamically.
uecker 5mo ago
"breaks completely" I rather would say it works nicely in auto-generating the complex indexing operation for n-dimensional arrays which makes it a lot more convenient and less error-prone to write such code. The compiler may also flatten a loop. The array of pointer hack used previously to similate 2d arrays using an array to pointers to arrays should not be used outside of special algorithms, as it is error prone and slow.
- fooker 5mo ago
  > The compiler may also flatten a loop. http://c2.com/cgi/wiki?SufficientlySmartCompiler http://c2.com/cgi/wiki?SufficientlySmartCompiler In practice, C compilers are still notoriously bad at loop optimizations. Polyhedral optimizations provided some hope, but no compiler managed to adopt it in production.
  - uecker 5mo ago
    Maybe, but also irrelevant to the discussion because whether you write mat[b * A + a] by hand or mat[b][a] and let the compiler frontend expand then makes no difference to the optimizer.
    - fooker 5mo ago
      You missed the point. Those two representations are equivalent, yes. But that's not what flattening loops mean.
      - uecker 5mo ago
        You are telling me what my point was?
ossopite 5mo ago
As I recall, C# supports this in a completely sensible way by distinguishing a[i,j] and a[i][j]. If I understand right, in C, a[i][j] means what C# would spell a[i,j], which does seem rather surprising and inconsistent
- mananaysiempre 5mo ago
  Not quite. As GP mentions, a[i][j] might mean either, depending on what the type of a is: (a) If the type of a is “array of length N of pointer to (say) char” (declaration: char *a[N]), then a[i][j] means the jth char in the contiguous block pointed to by the ith pointer. In C#, this is what you get with an array of arrays. (b) If the type of a is “array of length N of array of length M of char” (declaration: char a[N][M] — sic!), then a[i][j] means the jth element of the ith element, aka the (i*M+j)th char in the single contiguous memory block. In C#, this is what you get with a two-dimensional array. The way this happens is a bit subtle: (a) The value a, of type “array of size N of pointer to char”, first decays into “pointer to pointer to char”, then a[i] retrieves the ith “pointer to char” starting from it as a base, then in turn a[i][j] retrieves the jth “char” starting from that as a base. (b) The value a, of type “array of length N of array of length M of char”, first decays into “pointer to array of length M of char” (sic!), then a[i] retrieves the ith “array of length M of char” starting from it as a base, which then decays into “pointer to char”, then a[i][j] retrieves the jth “char” starting from that as a base. NB: There are no implicit references here, unlike in C#; in part (b), a is an N*M-byte chunk of memory and a[i] is an M-byte piece of it.
- simiones 5mo ago
  In C, a[i][j] can mean either a[i,j] or a[i][j], depending on the type of a.
deleted 5mo ago
[deleted]
fooker 5mo ago
And just in case you have not come across this, C++ allows you you overload all the relevant operators here: [], *, -> So, you really can't tell what's going on behind the scenes. I wanted to pull my hair out seeing some 'enterprise' code use state[i] = foo; for some kind of logging where i was the severity level. There were even instances of state[i++], where the severity was incremental. I hope someone has rewritten that codebase with AI by now.
- BeetleB 5mo ago
  So you would be equally critical of overloading [] for maps? Sorry, hard for me to relate, as I've overloaded [] (in, say, Python) to make life easy on everyone. People loved it. I hope you're aware that there is a long standing debate on whether overloading operators is good/bad, and it comes down to personal preference?
  - fooker 5mo ago
    > So you would be equally critical of overloading [] for maps? No, I'm not sure how you got that impression. Overloading is great. It's also confusing when it does something completely different from what you intuitively expect.
    - BeetleB 5mo ago
      If you're an old timer, you expect [] to index into an array, and you definitely do not expect it to do a lookup in a map/dict. Older languages just didn't include a dict-like structure in the language (technically, even C++ didn't). Do you not see that for them, overloading [] for dictionary lookups is "something completely different from what you intuitively expect"?
      - tialaramex 5mo ago
        More strikingly, C++ doesn't distinguish what Rust would call IndexMut and just Index, the use of the [idx] operator in a context where we'll mutate things and one where we don't want that. Rust's HashMap implements Index because answer = map[name] is a perfectly reasonable thing to do, and if there is no key matching name then we panic, makes sense but it does not provide IndexMut so that you could write map[name] = answer because the edge cases are non-obvious so better to make you write what you meant. C++ hash tables implement operator[] but the result is mutable, in order that map[name] = 123.0 can work which in Rust would be IndexMut and isn't provided. Because this is true, the index operation always succeeds, if you ask for map["not-present"] it creates the hash table entry for "not-present" and tries to store a default value ready to update it if you later assign to the reference.
quietbritishjim 5mo ago
> If you see a[i][j] it could mean two completely different things: > 1) ... a[i][j] == *((char*)a + i*M + j) // I added the char* cast to make it correct > 2) ... a[i][j] == *(*(a + i) + j) You may already understand this but: even in case (1), you still have a[i][j] = *(*(a + i) + j) (It has to - that's what operator[] means in C.) It's just that, in this case, `a + i` is applying pointer arithmetic to char[M]* so it adds M * i bytes to a's address. This is similar to how `a + i`, if a is int32_t*, will give you an address 4 * i bytes bigger than a. Really the confusing part of this is that *(a + i), which is an array value i.e. has type char[M], decays to char* when you add an integer to it (or dereference it). This is a pretty crazy hack really. Imagine if, in C++, you could do this std::vector<int> v = {1, 2, 3}; int* x = v + 1; // equivalent to &v[1] Yuck.
- quietbritishjim 5mo ago
  Too late to edit but I wrote pointer to char[M] as char[M]* when, of course(!), it should be written as char(*)[M].
1718627440 5mo ago
For 1), you can just write (&a[i])[j] .

ActorNightly 5mo ago

I mean, just like with 1 dimensional arrays, it depends on the context. Array memory is on the stack. The size of that array is actually not known at run time, its only known at compile time, where any reference to that length gets resolved by the compiled. If your 2d array sits on the stack, then inferring memory layout is pretty easy. If you are dealing with pointer that was passed to a function, then you can't assume anything about data size or limits, which is why many functions that take pointers take a size parameter as well.

alexey-salmin 5mo ago
> If your 2d array sits on the stack, then inferring memory layout is pretty easy. If you are dealing with pointer that was passed to a function, then you can't assume anything about data size or limits, which is why many functions that take pointers take a size parameter as well. Right, but 2d arrays come into this picture with their own quirks again. You're not just passing the size as the parameter, you can pass it as a "special" parameter that influences how the compiler will interpret other parameters. E.g. in C99 you can do this: void do(size_t x, size_t y, int a[][y]); Here "y" plays the critical role because it will be used to compute offsets in the a[i][j] expression. For 1d arrays this doesn't happen. Of course it's still generalizable as "all but the outermost dimensions should be known" and for 1d array the outermost dimension is the only dimension. Still, this whole thing always felt a bit odd to me.
- uecker 5mo ago
  Well, you give the explanation yourself: The size for the outermost array is not always needed, and then C allows it to be omitted. But my recommendation is to always give the size and then everything is regular and the compiler can use the information for warnings.
simiones 5mo ago
> Array memory is on the stack. Array memory can sit on either the stack or the heap. > The size of that array is actually not known at run time, its only known at compile time, where any reference to that length gets resolved by the compiled. This is also a bit misleading, in two ways. First, it's not clear what you mean by "size" here - the size of the memory block(s), or the shape of the array? Second, many people think that the C runtime doesn't know the amount of memory allocated to an array, but this is actually false. It's just the C abstract model that for some reason chose to not expose this information - but the size is actually always stored and accessible, and this is virtually mandated by the standard: otherwise, `free(arr)` couldn't realistically work, it would have to be `free(arr, size)`. This is one of the weirdest inefficiencies of C, in fact - it requires you to store the size of arrays twice - once in user code, and another time in the internal logic of the allocator. Edit: and as a fun extra, C++ not only inherited this mistake from C, but reproduced it again, meaning that a C++ array allocated with new[] actually stores the size twice, at least with typical implementations - once in the C++ runtime and again in the allocator - and still requires the user-space code to store it a third time. This is because `delete[]` needs to call the destructors of all of the elements of the array, regardless of where and how the array was allocated, so the number of array elements needs to be stored alongside the object itself.
- ActorNightly 5mo ago
  >Array memory can sit on either the stack or the heap. No, if we are using the definition of an array that is like int c[] = ..., that is always going to be on the stack. Heap continuous memory =/= array. You can use the [] operator to access it like an array, but fundamentally, as far as structures in C language are concerned, those 2 are different, because they get treated by compiler differently. >but the size is actually always stored and accessible, and this is virtually mandated by the standard: otherwise, `free(arr)` couldn't realistically work, That would only be true if each element in the array was a char. The dynamic data structure stores total amount of memory allocated by address, it has no info about the size of the element, so it can't infer the actual number of items at runtime. You could write your own malloc that does this, but generally, that is left to the user for flexibility. For example, a really good practice in C coding that basically solves any double free is a mempool that allocates all the memory up front. That way, you never really even have to call free, and the memory you allocate can be partitioned any way you chose dynamically.

uecker 5mo ago

"breaks completely" I rather would say it works nicely in auto-generating the complex indexing operation for n-dimensional arrays which makes it a lot more convenient and less error-prone to write such code. The compiler may also flatten a loop. The array of pointer hack used previously to similate 2d arrays using an array to pointers to arrays should not be used outside of special algorithms, as it is error prone and slow.

fooker 5mo ago
> The compiler may also flatten a loop. http://c2.com/cgi/wiki?SufficientlySmartCompiler http://c2.com/cgi/wiki?SufficientlySmartCompiler In practice, C compilers are still notoriously bad at loop optimizations. Polyhedral optimizations provided some hope, but no compiler managed to adopt it in production.
- uecker 5mo ago
  Maybe, but also irrelevant to the discussion because whether you write mat[b * A + a] by hand or mat[b][a] and let the compiler frontend expand then makes no difference to the optimizer.
  - fooker 5mo ago
    You missed the point. Those two representations are equivalent, yes. But that's not what flattening loops mean.
    - uecker 5mo ago
      You are telling me what my point was?

ossopite 5mo ago

As I recall, C# supports this in a completely sensible way by distinguishing a[i,j] and a[i][j]. If I understand right, in C, a[i][j] means what C# would spell a[i,j], which does seem rather surprising and inconsistent

mananaysiempre 5mo ago
Not quite. As GP mentions, a[i][j] might mean either, depending on what the type of a is: (a) If the type of a is “array of length N of pointer to (say) char” (declaration: char *a[N]), then a[i][j] means the jth char in the contiguous block pointed to by the ith pointer. In C#, this is what you get with an array of arrays. (b) If the type of a is “array of length N of array of length M of char” (declaration: char a[N][M] — sic!), then a[i][j] means the jth element of the ith element, aka the (i*M+j)th char in the single contiguous memory block. In C#, this is what you get with a two-dimensional array. The way this happens is a bit subtle: (a) The value a, of type “array of size N of pointer to char”, first decays into “pointer to pointer to char”, then a[i] retrieves the ith “pointer to char” starting from it as a base, then in turn a[i][j] retrieves the jth “char” starting from that as a base. (b) The value a, of type “array of length N of array of length M of char”, first decays into “pointer to array of length M of char” (sic!), then a[i] retrieves the ith “array of length M of char” starting from it as a base, which then decays into “pointer to char”, then a[i][j] retrieves the jth “char” starting from that as a base. NB: There are no implicit references here, unlike in C#; in part (b), a is an N*M-byte chunk of memory and a[i] is an M-byte piece of it.
simiones 5mo ago
In C, a[i][j] can mean either a[i,j] or a[i][j], depending on the type of a.

deleted 5mo ago

[deleted]

fooker 5mo ago

And just in case you have not come across this, C++ allows you you overload all the relevant operators here: [], *, -> So, you really can't tell what's going on behind the scenes. I wanted to pull my hair out seeing some 'enterprise' code use state[i] = foo; for some kind of logging where i was the severity level. There were even instances of state[i++], where the severity was incremental. I hope someone has rewritten that codebase with AI by now.

BeetleB 5mo ago
So you would be equally critical of overloading [] for maps? Sorry, hard for me to relate, as I've overloaded [] (in, say, Python) to make life easy on everyone. People loved it. I hope you're aware that there is a long standing debate on whether overloading operators is good/bad, and it comes down to personal preference?
- fooker 5mo ago
  > So you would be equally critical of overloading [] for maps? No, I'm not sure how you got that impression. Overloading is great. It's also confusing when it does something completely different from what you intuitively expect.
  - BeetleB 5mo ago
    If you're an old timer, you expect [] to index into an array, and you definitely do not expect it to do a lookup in a map/dict. Older languages just didn't include a dict-like structure in the language (technically, even C++ didn't). Do you not see that for them, overloading [] for dictionary lookups is "something completely different from what you intuitively expect"?
    - tialaramex 5mo ago
      More strikingly, C++ doesn't distinguish what Rust would call IndexMut and just Index, the use of the [idx] operator in a context where we'll mutate things and one where we don't want that. Rust's HashMap implements Index because answer = map[name] is a perfectly reasonable thing to do, and if there is no key matching name then we panic, makes sense but it does not provide IndexMut so that you could write map[name] = answer because the edge cases are non-obvious so better to make you write what you meant. C++ hash tables implement operator[] but the result is mutable, in order that map[name] = 123.0 can work which in Rust would be IndexMut and isn't provided. Because this is true, the index operation always succeeds, if you ask for map["not-present"] it creates the hash table entry for "not-present" and tries to store a default value ready to update it if you later assign to the reference.

quietbritishjim 5mo ago

> If you see a[i][j] it could mean two completely different things: > 1) ... a[i][j] == *((char*)a + i*M + j) // I added the char* cast to make it correct > 2) ... a[i][j] == *(*(a + i) + j) You may already understand this but: even in case (1), you still have a[i][j] = *(*(a + i) + j) (It has to - that's what operator[] means in C.) It's just that, in this case, `a + i` is applying pointer arithmetic to char[M]* so it adds M * i bytes to a's address. This is similar to how `a + i`, if a is int32_t*, will give you an address 4 * i bytes bigger than a. Really the confusing part of this is that *(a + i), which is an array value i.e. has type char[M], decays to char* when you add an integer to it (or dereference it). This is a pretty crazy hack really. Imagine if, in C++, you could do this std::vector<int> v = {1, 2, 3}; int* x = v + 1; // equivalent to &v[1] Yuck.

quietbritishjim 5mo ago
Too late to edit but I wrote pointer to char[M] as char[M]* when, of course(!), it should be written as char(*)[M].

1718627440 5mo ago

For 1), you can just write (&a[i])[j] .