How does a C program get information from an array internally?

Question

I'm relatively new to programming, so when someone suggested that building an array of structs (each containing n attributes of a particular "item") was faster than building n arrays of attributes, I found that I didn't know enough about arrays to argue one way or the other.

I read this:

how do arrays work internally in c/c++

and

Basic Arrays Tutorial

But I still don't really understand how a C program retrieves a particular value from an array by index.

It seems pretty clear that data elements of the array are stored adjacent in memory, and that the array name points to the first element.

Are C programs smart enough to do the arithmetic based on data-type and index to figure out the exact memory address of the target data, or does the program have to somehow iterate over every intermediary piece of data before it gets there (as in the linkedlist data structure)?

More fundamentally, if a program asks for a piece of information by its memory address, how does the machine find it?

compilers are written by people, and people are smart enough to do with array arithmetics — phuclv, Feb 11 '14 at 01:41
A lot of what makes memory access efficient or inefficient is related to cache-friendliness: http://stackoverflow.com/questions/16699247/what-is-cache-friendly-code — happydave, Feb 11 '14 at 01:43

score 7 · Accepted Answer · answered Feb 11 '14 at 01:43

Let's take a simpler example. Let's say you have a array int test[10] which is stored like this at address 1000:

1|2|3|4|5|6|7|8|9|10

The complier knows that, for example, an int is 4 bytes. The array access formula is this:

baseaddr + sizeof(type) * index

The size of a struct is just the sum of the sizes of its elements plus any padding added by the compiler. So the size of this struct:

struct test {
  int i;
  char c;
}

Might be 5. It also might not be, because of padding.

As for your last question, very shortly (this is very complicated) the MMU uses the page table to translate the virtual address to a physical address, which is then requested, which if it's in cache, is returned, and otherwise is fetched from main memory.

score 2 · Answer 2 · answered Feb 11 '14 at 01:39

2

You wrote:

Are C programs smart enough to do the arithmetic based on data-type and index to figure out the exact memory address of the target data

Yes, that is exactly what they do. They do not iterate over intervening items (and doing so would not help since there are no markers to guide beginning and end of each item).

answered Feb 11 '14 at 01:39

jeremycole

2,741
12
15

That makes a lot of sense! – user2127595 Feb 11 '14 at 02:25

Moha the almighty camel · Answer 3 · 2020-05-30T20:41:35.947

so here is the whole trick, array elements are adjacent in memory.

when you declare an array for example: int A[10];
the variable A is a pointer to the first element in the array.

now comes the indexing part, whenever you do A[i] it is exactly as if you were doing *(A+i).

the index is just an offset to the beginning address of the array, also keep in mind that in pointer arithmetic the offset is multiplied by the size of the data type of the array.

to get a better understanding of this write a little code, declare an array and print the address of it and then of each element in the array. and notice how the offset is always the same and equal to the size of the data type of your array on your machine.

How does a C program get information from an array internally?

3 Answers3