Question about how arrays stored in memory

Question

I'm a beginner in c language and programming, I heard that an array's elements were stored in successive memory location.

if I somehow manage to make memory location like this: what will happen if I declare an int8_t arr[2], will it go wrong?
does compiler have a list of the allocated memory and check when it declares variable?
calling malloc(1) in a while loop, why their return value has the difference of 0x20?

thanks for your helping!

1. Why should `int arr[2]` go wrong. I didn't understand the question. 2. It's the compiler's job. Didn't really get the question either. 3. `malloc` allocates memory, but there is a lot of internal book keeping to be done, so it's quite normal that each chunk of memory allocated via malloc actually uses more bytes than actually allocated. 4. I have absolutely no idea what you're talking about, which irrelevant part of your code? — Jabberwocky, Oct 21 '22 at 07:41
Could you please show what you mean by code, a [mcve]. Also, the 3rd question seems unrelated to first two. — hyde, Oct 21 '22 at 10:11

0___________ · Answer 1 · 2022-10-21T08:50:57.327

I'm a beginner in c language and programming, I heard that an array's elements were stored in successive memory locations.

How the memory allocation process works is left to the implementation. Every compiler, hardware port or version may do this completely different way. So you can't assume that the arrays will be placed in the successive memory location.

But the array is a continuous chunk of memory and elements are stored one after another so you can use element type pointer arithmetic to calculate references.

if I somehow manage to stuff values in every 8-bit location (like buttons on the flute, sorry for my broken English). what will happen if I declare an int arr[2], will it go wrong?

I do not understand what you mean, but if you want to store 8 bits of data use the array of int8_t. Use the correct type for the job. int8_t array[2] and you will have an array of the two 8 bits integer numbers.

how the compiler knows which location is allocated?

I think it is much too early for you to think about the compiler design. At the moment simply assume that it happens magically behind the scenes.

calling malloc(1) in a while loop, why their return value has the difference of 0x20?

Because it is how your malloc function works. Another implementation may work a completely different way and some will return addresses not related to the previous one.

will the irrelevant part of my code executed at the same time to save the time?

The code will be executed exactly as you wrote it, but if you do not have processes/tasks nothing in your code will execute in parallel.

score 0 · Answer 2 · answered Oct 21 '22 at 13:56

Given the declaration

int a[5];

you get something like this in memory (each square represents an int object):

   +---+
a: |   | a[0]
   +---+
   |   | a[1]
   +---+
   |   | a[2]
   +---+
   |   | a[3]
   +---+
   |   | a[4]
   +---+

That's it - no other metadata regarding size or type or starting address is stored as part of the array. All you get is a contiguous sequence of objects of the specified type. There is no object a that's separate from the array elements themselves.

what will happen if I declare an int8_t arr[2], will it go wrong?

Not sure what you mean. Declarations are not processed at runtime; during translation, the compiler analyzes the code and generates the machine code necessary to set aside any storage at program or function entry.

does compiler have a list of the allocated memory and check when it declares variable?

During translation, the compiler will keep track of declarations (using what's often called a symbol table) and will issue any diagnostics if the declaration isn't valid (incomplete type, no size, syntax error, whatever). No such checks are done at runtime.

calling malloc(1) in a while loop, why their return value has the difference of 0x20?

Because unless you're also calling free() on the memory you allocated, you're allocating a new block of memory every time through the loop, each of which starts at a different address.

Depending on the implementation, malloc may allocate more memory than necessary for the given object to store bookkeeping information about that object. After all, when you call free, all you give it is the starting address of the memory you allocated - you don't tell it how much memory to free. That information has to be stored somewhere, and many implementations set aside some extra space prior to the allocated block to do so:

+---+ ---+
|   |    | 
+---+    |
 ...     +---- bookkeeping data
+---+    |
|   |    |
+---+ ---+
|   |    | <--- this byte's address returned by malloc
+---+    |
|   |    |
+---+    +---- Requested block
 ...     |
+---+    | 
|   |    |
+---+ ---+

Özgür Güzeldereli · Answer 3 · 2022-10-21T09:41:09.790

-1

An array is a collection of a data type stored in memory. When you declare an array like:

int arr[2];

Your compiler allocates 2 * sizeof(int) amount of memory in RAM and the pointer to the beginning of that memory is used when arr is referenced. I don't know what could go wrong or what you mean by "will it go wrong?"

Compiler knows the location of the allocated array because compiler is the one to allocate it in the first place. The place is already (mostly) determined by the compiler.
Calling malloc in a while loop is different from declaring an array such as int arr[2]. malloc is a function which allocates some space on the heap. Heap is a special memory allocated for the dynamic use in a program. The space for heap is provided by the OS and this space is divided into smaller chunks by the implementation of malloc. The reason that there is 0x20 difference between the addresses that there may be a heap entry for each malloc you do. For example think of a heap entry such as:

0x1000 : 4 Bytes stores the size of the data inside the entry
0x1004 : 8 Bytes stores a pointer to the next entry 
0x100C : 8 Bytes some other data that maybe used in heap entry
0x1014 : 4 Bytes the integer itself
0x1018 : The start of the next entry etc.

I do not know what that means.

Edit: For all those who say that arrays are not pointers. Consider the following code:

int someArrFunc()
{
    int arr[2];
    int *ptr = arr;

    arr[0] = 451;
    *ptr = 885;

    arr[1] = 452;
    *++ptr = 886;

    int abc = sizeof(arr);
}

If we compiled this code the disassembly would be:

someArrFunc():
        push    rbp
        mov     rbp, rsp

        lea     rax, [rbp-20]
        mov     QWORD PTR [rbp-8], rax

        mov     DWORD PTR [rbp-20], 451

        mov     rax, QWORD PTR [rbp-8]
        mov     DWORD PTR [rax], 885

        mov     DWORD PTR [rbp-16], 452

        add     QWORD PTR [rbp-8], 4
        mov     rax, QWORD PTR [rbp-8]
        mov     DWORD PTR [rax], 886

        mov     DWORD PTR [rbp-12], 8

        nop
        pop     rbp
        ret

Here rbp-20 is the start address of the arr and rbp-8 is adress of ptr value. You can observe from the code that there is no difference between setting the arr and ptr in terms of memory. The variable arr in this case refers to rbp-20 while the pointer's value is also rbp-20. The only real difference between them is that the pointer holds extra memory since we are able to change its value.

I see that there is a decay but it is not relevant to my explanation of the memory structure. Moreover see that sizeof isn't stored in memory. It is an immediate value that is placed by the compiler with prior knowledge of its size.

edited Oct 21 '22 at 09:41

answered Oct 21 '22 at 07:46

Özgür Güzeldereli

1,630
7
23

3

*`sets the arr to be the pointer to the start of that memory address`* - no it is not the truth – 0___________ Oct 21 '22 at 07:47
@0___________ what do you mean? The variable ```arr``` stores the memory address that points to the stored data – Özgür Güzeldereli Oct 21 '22 at 07:48
1

"and sets the arr to be the pointer to the start of that memory address." That would mean that at address `&arr` there would be an address stored in memory. That is not true. `arr` is an array, not a pointer. What you might have in mind is that in some situations `arr` decays to a pointer to first element. – Gerhardh Oct 21 '22 at 07:48
2

variable `arr` does not store the address of the array. ***IT IS THE ARRAY*** – 0___________ Oct 21 '22 at 07:49
@Gerhardh If you run the following code ```int arr[2]; printf("%x", arr);``` what would happen? As a matter of fact ```arr``` and ```&arr``` have no difference whatsoever – Özgür Güzeldereli Oct 21 '22 at 07:51
That is one situation where the array decays to a pointer. Try `int arr[100]; printf(size=%zu\n", sizeof(arr));`. Do you expect to get size of a pointer? – Gerhardh Oct 21 '22 at 07:52
@0___________ I don't see how it is relevant to my explanation. In the end ```arr``` holds an address. The address points to the memory which contains the data. Everything else is irrelevant to my explanation of the structure of memory. – Özgür Güzeldereli Oct 21 '22 at 07:55
You may want to read this: [What is array to pointer decay?](https://stackoverflow.com/q/1461432/12149471) Note that this question is about both C and C++, so you may not understand the references to C++. – Andreas Wenzel Oct 21 '22 at 07:56
@Gerhardh it is because the size of an array is known by the compiler. The size or other data about the array is not stored in memory per se, it is not a different type of data. – Özgür Güzeldereli Oct 21 '22 at 07:57
@AndreasWenzel I didn't know about array-to-pointer decay but now knowing it doesn't change my explanation a bit. Although a pointer and an array doesn't share the same properties (i.e being able to determine size), an array is a pointer nonetheless. – Özgür Güzeldereli Oct 21 '22 at 08:00
@ÖzgürGüzeldereli: When used in an expression, in most situations, but not all (for example not in the case of `sizeof`), the type of the expression is converted to a pointer type which points to the first element of the array, according to [§6.3.2.1 ¶3 of the ISO C11 standard](http://port70.net/~nsz/c/c11/n1570.html#6.3.2.1p3). This is generally called "array to pointer decay". This does not mean that an array **is** a pointer. For example, you can assign a value to a pointer, but you cannot assign a value to an array. – Andreas Wenzel Oct 21 '22 at 08:19
@AndreasWenzel those are the things done by the compiler. They have no significance in the structure of the memory. – Özgür Güzeldereli Oct 21 '22 at 08:24
@AndreasWenzel I have added an edit. – Özgür Güzeldereli Oct 21 '22 at 08:34
@ÖzgürGüzeldereli try to `++` an array :) Also learn how to use the correct **types**. `int abc = sizeof(arr);` is wrond and potentially UB – 0___________ Oct 21 '22 at 08:36
@0___________ ```arr[1]``` already resolves to ```*(arr + 1)``` try using ```1[arr]``` as well. Also, I have added an edit. – Özgür Güzeldereli Oct 21 '22 at 08:38
@ÖzgürGüzeldereli try `++` not `+1` – 0___________ Oct 21 '22 at 08:42
@0___________ What you are saying is syntax-wise wrong. I still don't see how it is relevant. – Özgür Güzeldereli Oct 21 '22 at 08:47
@ÖzgürGüzeldereli In your answer you say: "...sets the `arr` to be the pointer to the start of that memory address". This statement is wrong!! `arr` decays to a pointer, BUT it is not a pointer. A pointer can be incremented, decremented or generally speaking point to elsewhere. Your variable `arr` does not satisfy this property. This by itself should clarify that there is a distinction between arrays and pointers. – Andreas Hadjigeorgiou Oct 21 '22 at 09:21
@AndreasHadjigeorgiou my point was strictly on memory sttucture. The compilation of the program or c cyntax is irrelevant – Özgür Güzeldereli Oct 21 '22 at 09:25
@ÖzgürGüzeldereli I accept your description on memory, it is fair! Your explanation though has a loss, an array is not a pointer. – Andreas Hadjigeorgiou Oct 21 '22 at 09:34
@AndreasHadjigeorgiou It is a semantic issue then. I may try to phrase it better – Özgür Güzeldereli Oct 21 '22 at 09:38
@AndreasHadjigeorgiou I have added an edit. – Özgür Güzeldereli Oct 21 '22 at 09:42
1

*" the pointer to the beginning of that memory is used when arr is referenced"*, no, there is no pointer. The compiler knows the address of the array, it doesn't need a separate pointer. Pointer contains a memory address. There's nothing containing the memory address of the array here. `rbp-20` is not a pointer. – hyde Oct 21 '22 at 10:16
@hyde ```rbp - 20``` is the pointer to the array. – Özgür Güzeldereli Oct 21 '22 at 10:17
1

The memory at address `rbp-20` contains the first value in the array. `rbp` contains the "base" of the stack frame (BP comes from Base Pointer). `rbp-20` is not stored anywhere, it is calculated on the fly by the CPU circuitry (or microcode or whatnot you may have in the CPU). – hyde Oct 21 '22 at 10:19
1

You could say "when `arr` is used in an expression, it is often (but not always, `sizeof` and `&` address-of operator being the important exceptions) converted to pointer to the first element of the array" or some such. – hyde Oct 21 '22 at 10:23
@hyde ```[rbp-20]``` is the first value in the array, ```rbp-20``` is the pointer to it. As I have said before, the issue is purely on semantics, I am not claiming that the compiler is treating an array exactly the same as it treats a pointer. They are same in the sense that an array is represented by a pointer. That is the only thing that is relevant to my answer which only talks about the structure in memory rather than C syntax – Özgür Güzeldereli Oct 21 '22 at 10:31
1

Semantics are important. Words mean specific things. This is extra important when communicating about programming concepts, which have exact technical meanings, which may even be conflicting in different contexts. Array vs pointer in C is _so_ common source of confusion, that being pedantic is warranted. YMMV. – hyde Oct 21 '22 at 10:59

Question about how arrays stored in memory

3 Answers3