7

I know that array elements are contiguous in virtual memory for sure, but are they in terms of physical memory like this one?

#define N 100*1024*1024
int arr[N];

Please Note, Until now most of you said the answer is NO but again my main question is the one below in bold.

If not, at-least if one element was found in a page then can I suppose the whole page is filled of array elements (in other words they may not be contiguous as one in different pages but contiguous in each single page thus improving performance when reading 1 element we read a full page of nearby element ie 4096 byte instead of reading another page for next elements)?

If yes, what if I tried to allocate a big array where there is no available contiguous physical memory (which can happen a lot I believe)?

If the answer depends on programming language I'm interested in C and C++ and if it depends on the OS I'm interested in linux and it's variants like ubuntu

  • Hello. Have you looked "memory fragmentation" up? Maybe it can helps. But short answer: in theory you have no guarantee. In practice: the OS does what ever it wants. – YSC Jul 02 '21 at 16:22
  • 10
    Physical memory is invisible to programs in virtual memory systems - as a programmer you're not required to reason about it. – 500 - Internal Server Error Jul 02 '21 at 16:23
  • Platform dependant... But in terms of memory accessible by program on low level, they are, it's in definition of array. Answer to second question: platform and implementation dependant – Swift - Friday Pie Jul 02 '21 at 16:26
  • @500-InternalServerError I'm interested to know how the division is done –  Jul 02 '21 at 16:26
  • @daniel it depends on compiler and OS settings... Also is array is static or automatic, you either hit memory limit (hard or soft one) or the stack limit – Swift - Friday Pie Jul 02 '21 at 16:29
  • Does this answer your question? [Are the physical memory addresses of an array also stored in order like the virtual ones?](https://stackoverflow.com/q/60169369/11683) – GSerg Jul 02 '21 at 16:30
  • With new Intel chipset contiguosness of memory may become moot at all.And you program doesn't interact with physical memory in OS you have in mind – Swift - Friday Pie Jul 02 '21 at 16:31
  • @GSerg I read it, not exactly as my question had sub-questions too –  Jul 02 '21 at 16:31
  • In my option, if you write `int arr[100000];`, then the array is allocate in stack, the stack is pre allocate pages, then it's contiguous; If you write `arr = malloc(100000 * sizeof(int))` then OS will allocate memory for you, the pages may contiguous, or else. – superK Jul 02 '21 at 16:32
  • @daniel I believe the second link [specifically addresses](https://stackoverflow.com/a/60170220/11683) contiguity within the same page. – GSerg Jul 02 '21 at 16:34
  • @GSerg doesn't answer if they will be in single page or not ie can there be a situation were each element is in a single page ? –  Jul 02 '21 at 16:37
  • 1
    @daniel Yes it does. "*everything that's contiguous within a page will be contiguous for both virtual memory and physical memory*". That is the only guarantee you get. – GSerg Jul 02 '21 at 16:39
  • 1
    There is no performance difference between contiguous and non-contiguous memory. That's what random access means. – stark Jul 02 '21 at 16:47
  • @大宝剑: No, there is no guarantee that the stack is contiguous physical memory. Most OSes have a stack that grows on demand; the stack may be allowed to be several megabytes, but only a few pages are backed by physical memory initially, and more are allocated as the application touches more pages and faults. There is no reason to expect that physically contiguous memory would be available for any of those allocations, and no need to provide it anyway. – Nate Eldredge Jul 02 '21 at 17:18
  • 2
    @GSerg and that's not what I asked... I asked if they are contiguous physical memory will they be contiguous in same page... A is B doesn't say B is A –  Jul 02 '21 at 17:29
  • @daniel It does. Items contiguous in the physical memory will necessarily be contiguous within boundaries of each respective page of the virtual memory. That is again the only guarantee. – GSerg Jul 02 '21 at 17:32
  • 2
    @GSerg It doesn't "Items contiguous in the physical memory will" that's not what I am asking Again. I am asking if they are contiguous in virtual memory will ... –  Jul 02 '21 at 17:33
  • @ariel You are probably confusing pages and cache-lines. – stark Jul 02 '21 at 17:34
  • @daniel Make up your mind about what you are asking then, as you keep changing it. [Here](https://stackoverflow.com/questions/68228499/are-arrays-contiguous-in-physical-memory#comment120585778_68228499), [here](https://stackoverflow.com/questions/68228499/are-arrays-contiguous-in-physical-memory#comment120585861_68228499) and in the body of the question you asked *three* different things, all of which are covered by https://stackoverflow.com/a/60170220/11683. – GSerg Jul 02 '21 at 17:44

3 Answers3

4

On Linux x86, contiguous virtual memory is allocated in pages of 4 KB:

By definition, memory within a page is contiguous. But the physical pages can be mapped in any order. This allows the OS to allocate and deallocate any amount of virtual memory, as long as physical pages (or swap space) are available. Fragmentation at page level isn't an issue for the CPU or cache, but can affect allocation performance, and so Linux page allocation algorithms are constantly evolving, as described in this article.

It means a large contiguous array will reside in RAM in chunks of 4 KB (aligned to 4 KB). The first and last chunks may occupy a part of a page, and the rest will occupy full pages.

rustyx
  • 80,671
  • 25
  • 200
  • 267
  • So except 2 the answer to: "If not, at-least if one element was found in a page then can I suppose the whole page is filled of array elements" is Correct? –  Jul 02 '21 at 17:44
  • @daniel yes, a whole page will be filled by array elements. – rustyx Jul 02 '21 at 17:46
1

Each page of virtual memory is mapped identically to a page of physical memory; there is no remapping for units of smaller than a page. This is inherent in the principle of paging. Assuming 4KB pages, the top 20 or 52 bits of a 32- or 64-bit address are looked up in the page tables to identify a physical page, and the low 12 bits are used as an offset into that physical page. So if you have two addresses within the same page of virtual memory (i.e. the virtual addresses differ only in their 12 low bits), then they will be located at the same relative offsets in some single page of physical memory. (Assuming the virtual page is backed by physical memory at all; it could of course be swapped out at any instant.)

For different virtual pages, there is no guarantee at all about how they are mapped to physical memory. They could easily be mapped to entirely different locations of physical memory (or of course one or both could be swapped out).

So if you allocate a very large array in virtual memory, there is no need for a sufficiently large contiguous block of physical memory to be available; the OS can simply map those pages of virtual memory to any arbitrary pages in physical memory. (Or more likely, it will initially leave the pages unmapped, then allocate physical memory for them in smaller chunks as you touch the pages and trigger page faults.)

This applies to all parts of a process's virtual memory: static code and data, stack, memory dynamically allocated with malloc/sbrk/mmap etc.

Linux does have support for huge pages, in which case the same logic applies but the pages are larger (a few MB or GB; the available sizes are fixed by hardware).

Other than very specialized applications like hardware DMA, there isn't normally any reason for an application programmer to care about how physical memory is arranged behind the scenes.

Nate Eldredge
  • 48,811
  • 6
  • 54
  • 82
  • "So if you allocate a very large array in virtual memory, there is no need for a sufficiently large contiguous block of physical memory to be available" Won't this improve performance? If I'm reading values of array I need to only find the first physical page and then I check the next page and so on but if that doesn't happen then I need to refind the next page which will take some time –  Jul 02 '21 at 17:46
  • @daniel: Not really. Since pages *can* be placed arbitrarily, when you access the next page, the CPU has to perform a new walk of the page tables to see where that page lives in physical memory and populate the TLB accordingly. (I assume that's what you mean by "refind".) It can't assume it will be the next contiguous physical page, and once the page walk is done, it makes no difference whether it turned out to be the next page, or a page somewhere else. – Nate Eldredge Jul 02 '21 at 18:20
0

I know that array elements are contiguous in virtual memory for sure, but are they in terms of physical memory

No. All the computers you and I use on a daily basis feature a memory management unit to translate virtual addresses to physical addresses. Addresses are translated in granular blocks called pages, and a typical page size is 4 kB. Within a page, physical addresses will be contiguous, but an array needing many pages will most likely end up completely fragmented and scattered across physical memory addresses in an arbitrary way.

Even if the physical addresses are contiguous, the way that "physical" addresses map to true on-chip locations on the RAM sticks depends on the motherboard.

It's unlikely to be necessary to worry about this.

If not, at-least if one element was found in a page then can I suppose the whole page is filled of array elements (in other words they may not be contiguous as one in different pages but contiguous in each single page thus improving performance when reading 1 element we read a full page of nearby element ie 4096 byte instead of reading another page for next elements)?

If the page is not previously resident in RAM, accessing any part of it will perform the costly operation of pulling that full page from the operating system's page file, etc, into RAM (and the operating system will probably prefetch some subsequent pages as well).

This still doesn't mean that every part of the page in RAM can then be accessed at the same speed, because you are still affected by CPU caches, and accessing caches is even faster than accessing RAM on the motherboard.

A typical CPU cache line size is 64 or 128 bytes, for example, rather smaller than a page. But accessing part of a cache line will certainly pull the whole line into the cache.

See also: https://igoro.com/archive/gallery-of-processor-cache-effects/

Boann
  • 48,794
  • 16
  • 117
  • 146
  • ״Even if the physical addresses are contiguous, the way that "physical" addresses map to true on-chip locations on the RAM sticks depends on the motherboard.״ this got me interested. isn't "physical" the real on-chip location on RAM? where can I read more regarding this? –  Jul 02 '21 at 17:59
  • 1
    Physical addresses are the addresses the kernel (and CPU) sends to the memory controller when requesting data from it. How the memory controller maps those physical addresses to an actual location on a particular RAM chip is a private implementation detail between it and the SIMMs. – Jeremy Friesner Jul 02 '21 at 18:03
  • Any link to where I can read more on this new low - layer ? Thanks –  Jul 02 '21 at 18:04
  • 1
    @daniel Real physical RAM is addressed using "banks", "rows", and "columns". I don't know much about it, but that should give you some words to search for. Reads and writes of chunks of RAM are divided among all the chips on a RAM stick, so the chips can work in parallel, so that is another level of physical fragmentation. – Boann Jul 02 '21 at 18:11
  • 1
    @daniel: Check out Ulrich Drepper's excellent paper, ["What Every Programmer Should Know About Memory"](https://people.freebsd.org/~lstewart/articles/cpumemory.pdf). – Nate Eldredge Jul 02 '21 at 18:22