CODEWITHSUNDEEP
c++memorymemory-management
jsguy
jsguy

Reputation: 2179

When you call new[] to allocate an array for N integers is it guaranteed that the array is going to be allocated sequentially in physical memory?

From my understanding every computer program always works with virtual memory and the way physical memory is handled is up to the operating system.

I am attending an algorithm engineering's course and at some point it was mentioned that if the cache memory is infinite and one cache line is of size B then the expected amount of cache misses that would be incurred if you wanted to just scan through an array of N elements would be N/B

I can see how this would work in theory, because we assume that the N elements are positioned one after the other in physical memory.

But, is this actually true in practice? If virtual memory is allocated sequentially, does that also mean that the physical memory will also be allocated sequentially?

It sounds to me that in practice, assuming that N is not larger than the cache size, you would get more than N/B cache misses if the N elements weren't allocated sequentially in the physical memory (RAM).

Maybe I am misunderstanding the difference between virtual memory and physical memory, I am not sure.

Upvotes: 4

Views: 177

Answers (3)

Sergey Kalinichenko
Sergey Kalinichenko

Reputation: 726809

The physical memory does not need to be allocated globally sequentially for the entire array. In order for the N/B observation to hold, all you need is for the physical memory to be allocated sequentially within the bounds of a single cache line. In other words, when you cross the boundary of a cache line, it does not matter if the next line comes from adjacent address in physical memory or from some physical address far away.

This will be true if virtual memory pages are allocated in increments of some number of cache lines, and also aligned with cache lines.

Both these assumptions are probably true for all architectures in existence today, because allowing misalignment of virtual pages with cache lines or making virtual pages in odd sizes would put a lot more requirements on the hardware support for virtual memory architecture.

Upvotes: 1

bobah
bobah

Reputation: 18864

Array will be contiguous in the virtual memory space. In the physical space only fragments fitting within a single page will be contiguous. The best introduction into computer memory I have seen can be downloaded from here.

Upvotes: 0

Mike Seymour
Mike Seymour

Reputation: 254631

It's just as you say: the array elements are contiguous in virtual memory, but not necessarily in physical memory.

On a PC-like architecture, memory is allocated in pages, which are typically much larger than cache lines (typically several kilobytes versus dozens of bytes). Each page maps a contiguous range of virtual memory to a contiguous range of physical memory. So each cache line will still span a contiguous range of physical memory, and the discontinuities in physical memory won't cause any extra cache misses.

Upvotes: 4

Related Questions