Are Arrays Contiguous in *Physical* Memory?

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.

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.

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/