Locality Principles (Temporal and Spatial)¶

Programs exhibit predictable access patterns: recently accessed data will likely be accessed again (temporal), and data near recently accessed locations will likely be accessed soon (spatial). Exploiting these patterns is the foundation of all caching.

Tension Addressed¶

Speed vs. Capacity

Recognizable As¶

Loop variables (temporal), array traversals (spatial), working sets, hot/cold data separation, prefetching strategies.

Canonical Sources¶

Denning, "The Working Set Model for Program Behavior" (1968); Drepper, "What Every Programmer Should Know About Memory" (2007)

Transfers To¶

Database query optimization, file system design, garbage collection, JIT compilation, recommendation systems

Sub-concepts: - Temporal locality: If data was accessed, it will likely be accessed again soon - Spatial locality: If data was accessed, nearby data will likely be accessed soon - Working set: The set of data actively in use during a time period