CPU cache
A small, very fast memory on the processor that keeps copies of recently used data, and the data next to it, so it can be read again quickly.
In more detail
When the processor reads one value it loads a whole block of neighbouring bytes into the cache. Structures laid out contiguously, like arrays and open-addressed tables, get many values per load and are called cache-friendly. Linked structures jump around memory and miss the cache more often.
Related terms
- contiguous memory — Memory laid out as one unbroken block, with each item directly after the previous one.
- open addressing — A way of resolving hash collisions in which all entries live in one array and a colliding key probes forward to another free slot.
- CPU — The chip in a computer that runs program instructions; a machine can have several.
- memory — The fast, temporary working space where running programs keep their data; it is emptied when the machine powers off.
- nanosecond — One billionth of a second, the time scale of processor caches and memory.
Taught in
- Hash Tables: Chaining, Open Addressing And Load Factor — Algorithms & Data Structures for Working Engineers
- Linked Lists: Nodes, Pointers And Sentinels — Algorithms & Data Structures for Working Engineers
- Latency Numbers Every Engineer Should Know — Scalable System Design & Distributed Architecture