Memory Hierarchy

Optimization involves the memory hierarchy. We see an example memory hierarchy in a fairly modern computer. This guides optimization of computer programs. It also influences how compilers, operating systems and databases work.

This page describes memory hierarchies, which determine the efficiency of data access.

Virtual Memory (Disk)

> 2GB (Typical size)
3-15 ms (Access time)

Physical Memory

256MB-2GB
100-150 ns

2nd-Level Cache

128KB-4MB
40-60 ns

1st-Level Cache

16-64KB
5-10 ns

Registers (Processor)

32 Words
1 ns

Introduction

The above table shows the critical performance aspects of a somewhat recent memory hierarchy on a personal computer. You can see that reading a file from the disk requires about 3-15 milliseconds; reading that data from memory requires 100-150 nanoseconds; and reading data from the processor caches requires between 1 and 60 nanoseconds.

How much faster is physical memory than the disk? Here we use the table shown above to compute how much faster you can load a small data object from memory instead of the disk. Recall that one millisecond is equal to one million nanoseconds. Let's say that the computer is busy and the disk requires 15 milliseconds, and the memory requires 150 nanoseconds.

Disk time

15 ms * 1000000 = 15000000 ns

Memory time

150 ns

Memory performance

Memory is 100,000x (one-hundred thousand) times faster.

Uses

There is more complexity to computers than this memory hierarchy. All modern operating systems use a file cache, which puts disk files into memory, essentially making accesses one-hundred thousand times faster. However, this is not configurable in many cases and it can be better to use custom file caches that will not be expired.

Summary

We looked at the concept of memory hierarchy in a very brief way using a table from the book Compilers: Principles, Techniques and Tools. The memory hierarchy shows us that disk accesses are far more expensive than in-memory reads with similar complexity. Often, avoiding accessing virtual memory (disk) is one of the most important optimizations to make.