Read the original article here.

---

The Forbidden Code: Underground Programming Techniques They Won’t Teach You in School

Module 1: Caching - The Silent Accelerator (Unlocking Hidden Performance)

Welcome to the first module of "The Forbidden Code," where we peel back the layers of abstraction that mainstream programming education often leaves untouched. Today, we delve into the world of caching – a concept so fundamental, so pervasive across computing, yet often treated superficially. Understanding caches isn't just about knowing what they are; it's about understanding how they work at a deep level to gain a significant edge in optimizing the performance of your code, from the lowest hardware levels to distributed systems. This is knowledge that separates the good programmers from the masters who can squeeze every last drop of performance out of a system.

At its core, caching is about leveraging speed. It's a critical component in bridging the vast speed gaps between different levels of storage and processing.

Definition: A cache (pronounced KASH) is a hardware or software component that stores copies of data from a slower "backing store" or the results of expensive computations, so that future requests for that data or computation can be served much faster.

Think of it like having a small, incredibly fast notepad next to your desk (the CPU) where you keep the information you're using right now or just used, rather than having to walk all the way across the building to the massive library (main memory or disk) every time you need a single piece of data.

The Fundamental Mechanics: Hit and Miss

The basic operation of a cache revolves around checking if the desired data is already present in the cache.

Definition: A cache hit occurs when the requested data is found in the cache.

When a cache hit occurs, the system retrieves the data directly from the cache. This is significantly faster than fetching it from the original, slower backing store or recomputing it.

Definition: A cache miss occurs when the requested data is not found in the cache.

When a cache miss occurs, the system must go to the slower backing store to retrieve the data. Once retrieved, a copy of this data is typically placed in the cache, so that future requests for the same data (or nearby data) can result in a cache hit.

The efficiency of a cache is often measured by its hit rate (or hit ratio).

Definition: The hit rate (or hit ratio) is the percentage of data requests that result in a cache hit. A higher hit rate means the system is spending more time accessing fast cache memory and less time waiting for slow backing stores, leading to better overall performance.

For example, imagine a web browser cache. When you visit a webpage, the browser stores copies of the page's images, CSS files, and HTML in a local cache on your hard drive. The next time you visit that page, the browser first checks its cache. If an image is found in the cache (a cache hit), it loads instantly from your fast local disk instead of being downloaded again over the slower internet (a cache miss). The webpage loads much faster because many requests result in hits.

Why Caching Works: Locality of Reference

If caches are small (and they must be for speed), why are they so effective? The secret lies in a fundamental principle observed in typical computer workloads: Locality of Reference.

Definition: Locality of Reference is the tendency of computer programs to access data items that are close to each other in time (temporal locality) or space (spatial locality).

Understanding and exploiting locality is forbidden knowledge in the sense that truly optimizing performance requires you to design your algorithms and data structures to maximize this principle.

1. Temporal Locality: This means if a data item is accessed now, it is likely to be accessed again in the near future.

   • Explanation: Think about variables in a loop. A loop counter, or data being processed within the loop, is accessed repeatedly over a short period.
   • Example: In code like for (int i = 0; i < 1000; i++) { sum += array[i]; }, the variable i and the current element array[i] exhibit strong temporal locality.

2. Spatial Locality: This means if a data item is accessed now, data items located near it in memory are likely to be accessed soon.

   • Explanation: This is common with arrays, structures, and sequential code execution. When you access one element of an array, it's highly probable you'll access the next one. When one instruction is executed, the next instruction in memory is usually executed right after.
   • Example: In the same loop for (int i = 0; i < 1000; i++) { sum += array[i]; }, when array[i] is accessed, it's very likely array[i+1], array[i+2], etc., will be accessed next. Caches exploit this by fetching not just the requested byte, but a larger block of data (a "cache line") that includes neighboring bytes.

By keeping recently used data (temporal locality) and data located near recently used data (spatial locality) in the fast cache, the system significantly increases the chances of a hit on future accesses. This is the core performance boost provided by caching.

The Motivation: Bridging the Speed Gap

The primary motivation for using caches is the fundamental trade-off between storage capacity and access speed.

• Large Capacity vs. Speed: The larger a memory component is, the longer it takes for signals to travel across it. Fast memory technologies (like SRAM used in CPU caches) are expensive and consume more power per bit than slower, higher-capacity technologies (like DRAM for main memory, or Flash/HDD for storage).
• The Hierarchy: This leads to a memory hierarchy:
  • CPU Registers: Fastest, smallest capacity.
  • L1 Cache: Extremely fast, very small, usually on the CPU core.
  • L2 Cache: Fast, larger than L1, often per core or shared.
  • L3 Cache: Faster than main memory, larger than L2, usually shared across cores.
  • Main Memory (DRAM): Slower than caches, much larger capacity.
  • SSD/HDD Storage: Much slower than DRAM, vastly larger capacity.
  • Network/Cloud Storage: Slowest, potentially infinite capacity.

Caching sits between these layers, holding copies of data from the slower layer to serve requests from the faster layer.

Caches improve performance in two key ways:

1. Reducing Latency: Caches hide the time delay (latency) of accessing slower storage. Accessing main memory can take hundreds of CPU clock cycles. By reading a block of data into the cache on a miss, subsequent accesses to data within that block (due to spatial locality) are served from the cache with much lower latency (tens or even single clock cycles). Prefetching data (loading it before it's explicitly requested) can even bypass latency entirely if the prediction is correct.
2. Increasing Throughput: Caching can help structure data transfers to be more efficient. Slower devices (like hard drives) are much more efficient at transferring large blocks of data sequentially than many small, random accesses. Caches can absorb fine-grained reads/writes from the CPU/application and assemble them into larger, more efficient transfer requests to the backing store, effectively increasing the rate at which data can be moved (throughput or bandwidth).

Deep Dive into Cache Operations

Beyond just hitting and missing, the internal workings of caches involve sophisticated policies to manage their limited space and ensure data consistency.

Structure of a Cache Entry

Each piece of data stored in a cache is part of a cache entry. An entry typically consists of:

1. Data: A copy of a block of data from the backing store (e.g., a cache line from main memory, or a web page file).
2. Tag: An identifier that maps the data in the cache entry back to its original location in the backing store (e.g., a memory address range, a URL).
3. Flags/Metadata: Bits that store information about the entry, such as:
   • Valid bit: Indicates if the entry contains valid data or is empty.
   • Dirty bit: (Used in write-back caches) Indicates if the data in the cache entry has been modified and needs to be written back to the backing store.

When the system needs data, it calculates the corresponding tag for the desired data location in the backing store and checks if an entry with a matching tag and valid bit set exists in the cache.

Replacement Policies: What Gets Evicted?

Since caches are small, they constantly fill up. When a cache miss occurs and new data needs to be brought in, an existing entry must often be removed to make space. The logic used to decide which entry to remove is called the replacement policy.

Definition: A replacement policy is an algorithm used by a cache to decide which existing cache entry to evict (remove) when the cache is full and new data needs to be stored.

Choosing the right replacement policy is crucial for maximizing the hit rate, but it's a complex problem as the cache needs to predict which data will not be needed soon.

• Least Recently Used (LRU): A very common policy. It evicts the entry that has not been accessed for the longest time, based on the principle of temporal locality (data accessed less recently is less likely to be accessed again soon).
• Least Frequently Used (LFU): Evicts the entry that has been accessed the fewest times.
• Time Aware Least Recently Used (TLRU): (Discussed later in In-Network Caching) Incorporates a time-to-use (TTU) value, useful for data with a limited valid lifetime.
• Least Frequent Recently Used (LFRU): (Discussed later in In-Network Caching) Combines aspects of LFU and LRU.
• Random Replacement: Simply evicts a random entry. Simple but often less effective than LRU/LFU variants.
• Optimal Replacement: Evicts the entry that will be used furthest in the future. This is impossible to implement in practice as it requires knowing the future access pattern, but it serves as a benchmark for comparing other policies.

Implementing efficient replacement policies, especially true LRU, can be computationally expensive for large caches, so approximations are often used.

Write Policies: When Does Data Hit the Backing Store?

When data is modified by the application, it needs to be written to the cache. This modified data must eventually be reflected in the backing store. The timing of this synchronization is governed by the write policy.

Definition: A write policy determines when modifications made to data in the cache are propagated to the backing store.

The two primary write policies are:

1. Write-Through:
   • Mechanism: Writes are performed synchronously to both the cache and the backing store simultaneously.
   • Pros: The backing store is always up-to-date. Simplifies cache coherence issues if other agents access the backing store directly.
   • Cons: Write operations are slowed down by the latency of the backing store.
2. Write-Back (or Write-Behind):
   • Mechanism: Writes are initially performed only to the cache. The cache entry's "dirty bit" is set to indicate it's been modified. The modified data is written back to the backing store only when the cache entry is replaced (evicted) or explicitly flushed.
   • Pros: Writes can complete at cache speed, improving write performance, especially for multiple writes to the same location. Reduces traffic to the backing store by coalescing multiple writes into one.
   • Cons: The backing store may be temporarily out-of-date ("stale"). Requires more complex logic to manage dirty bits. A system crash before dirty data is written back can lead to data loss. Evicting a dirty entry requires an extra write cycle to the backing store.

Write-Miss Policies: What Happens on a Write Miss?

When an application writes to a location that is not currently in the cache (a write miss), the system needs a policy to decide whether to load the data into the cache before writing to it.

Definition: A write-miss policy determines whether data is loaded into the cache on a write miss.

The two main write-miss policies are:

1. Write Allocate (or Fetch on Write):
   • Mechanism: On a write miss, the block containing the target location is first loaded into the cache from the backing store (like a read miss). Then, the write operation proceeds as a write hit.
   • Logic: Anticipates future accesses (reads or writes) to the same location or nearby locations due to locality. Typically paired with a Write-Back policy.
2. No-Write Allocate (or Write-No-Allocate, Write Around):
   • Mechanism: On a write miss, the write is performed directly to the backing store, bypassing the cache entirely. The data block is not loaded into the cache.
   • Logic: Avoids polluting the cache with data that might only be written once and not subsequently read. Typically paired with a Write-Through policy, as the write is going to the backing store anyway.

The common pairings (Write-Back + Write Allocate and Write-Through + No-Write Allocate) reflect strategies to maximize the benefits of each approach. Write-back benefits from having data in the cache for subsequent writes, so it loads it on a miss. Write-through is already hitting the backing store on every write, so there's less incentive to load the data into the cache on a write miss unless reads are expected immediately after.

Cache Coherence: Keeping Data Consistent

In systems where multiple caches might hold copies of the same data (e.g., multi-core CPUs, distributed systems), ensuring that all copies are consistent is critical and complex.

Definition: Cache Coherence refers to the problem of ensuring that all caches in a system or network see the same, consistent view of data that might be replicated across multiple caches and the main backing store.

If one processor modifies data in its cache using a Write-Back policy, other processors with copies of the old data in their caches will have stale (out-of-date) data. Cache coherence protocols (like MESI for CPU caches) are sophisticated mechanisms involving snooping on bus traffic or directory-based methods to invalidate or update stale cache entries when a write occurs elsewhere. This is one of the most challenging aspects of multi-processor system design.

Prefetching: Guessing the Future

Caches typically operate on demand: data is loaded only when a miss occurs (demand paging). However, exploiting spatial locality and predicting future access patterns can be enhanced by prefetching.

Definition: Prefetching is a technique where data is loaded into the cache before it is requested by the processor or application, based on predictions about future access patterns.

• Mechanism: When a cache miss occurs for a block, the system might not only fetch that block but also the next block(s) in sequence. More advanced prefetchers use complex algorithms to detect access patterns (like accessing elements of a sparse matrix) and fetch data accordingly.
• Benefit: If the prediction is correct, the data is already in the cache when requested, effectively eliminating the latency of the miss.
• Risk: If the prediction is wrong, prefetching wastes memory bandwidth, pollutes the cache with unused data (potentially evicting useful data), and can actually harm performance.

Prefetching is particularly effective when the backing store has high latency but high sequential throughput (like hard drives or even DRAM). Some operating systems pre-load entire executables or libraries, and web browsers use link prefetching to potentially load pages a user might click on next.

Where Caches Lurk: Examples Across the Stack

Caches are found throughout the computing stack, from the silicon inside your CPU to the global network infrastructure. Understanding these different layers of caching is essential for holistic performance optimization.

Hardware Caches

These are managed directly by hardware for maximum speed.

• CPU Cache: The most critical hardware cache for application performance. Modern CPUs have multiple levels (L1, L2, L3) with increasing size and latency.
  • L1 Cache: Smallest, fastest, typically split into an Instruction Cache (I-cache) for program instructions and a Data Cache (D-cache) for data operands. Usually per-core.
  • L2 Cache: Larger than L1, slightly slower, may be per-core or shared between a few cores.
  • L3 Cache: Largest CPU cache, slowest of the CPU caches, typically shared by all cores on a chip.
  • Specialized Caches: Many other caches exist on a CPU, like the Translation Lookaside Buffer (TLB).
• Translation Lookaside Buffer (TLB):

  Definition: A Translation Lookaside Buffer (TLB) is a specialized, high-speed cache used by the Memory Management Unit (MMU) to store recent translations of virtual memory addresses to physical memory addresses.

  • Context: Operating systems use virtual memory, where programs see a large, contiguous address space, but the actual data is scattered in physical RAM or even on disk. The MMU translates these virtual addresses. Looking up the translation in page tables stored in main memory is slow. The TLB caches these translations to speed up memory access. A TLB miss is effectively a cache miss on the address translation itself, which requires walking the page table (a much slower process).
• GPU Cache: Graphics Processing Units (GPUs) also have caches, initially primarily for textures (like read-only texture caches that leveraged spatial locality for 2D image data). As GPUs evolved for general-purpose computing (GPGPU), their caches became more general-purpose, supporting instruction caching for shaders, data caching, and even atomic operations, mirroring CPU cache complexity.
• DSP Cache: Digital Signal Processors (DSPs) used in audio, video, and communication processing also include caching mechanisms, often similar to CPU caches with split instruction and data caches.

Software Caches

These are managed by software (operating systems, applications, servers) and typically operate at higher levels of abstraction.

• Disk Cache / Page Cache:
  • Context: The operating system manages a significant portion of main memory as a cache for the file system and block devices (disks). This is often called the page cache.

    Definition: The page cache is a cache in main memory managed by the operating system kernel, storing copies of disk blocks or file pages to speed up file system access and block device I/O.

  • Explanation: When a program reads from a file, the OS first checks the page cache. If the data is there (a hit), it's returned instantly. If not (a miss), the OS reads the data from the disk into the page cache and then provides it to the program. Writes often go into the page cache first and are written to disk later (write-back policy, often called "dirty pages").
  • Distinction: Note that the disk buffer integrated into the hard drive or SSD itself is often not a general-purpose cache but more of a buffer for read-ahead and write-combining, although it can have caching effects. High-end disk controllers do have dedicated caches for data blocks.
  • Hierarchical Storage Management: Caching principles are extended to systems where faster storage (SSDs, HDDs) acts as a cache for slower storage (tape drives, cloud storage). Hybrid drives combine SSDs and HDDs for this purpose.
• Web Cache:
  • Browser Cache: Your web browser stores copies of web resources (pages, images, scripts) on your local disk.
  • Proxy Cache: Servers (often at ISPs or within organizations) can cache web content accessed by multiple users.
  • Benefits: Reduces latency for users, reduces load on web servers, saves network bandwidth.
  • P2P Caching: ISPs or decentralized networks can cache popular files accessed by peer-to-peer applications to speed up downloads.
• Memoization:

  Definition: Memoization is an optimization technique where the results of expensive function calls are stored ("cached") in a lookup table (often a hash map or dictionary) and returned when the same inputs occur again, avoiding redundant computation.

  • Context: This is a form of application-level caching for computation results rather than raw data blocks.
  • Example: Consider a function to calculate Fibonacci numbers recursively: fib(n) = fib(n-1) + fib(n-2). Computing fib(5) involves computing fib(4) and fib(3). fib(4) requires fib(3) and fib(2). Notice fib(3) is computed multiple times. With memoization, after computing fib(3) the first time, its result is stored. The second time fib(3) is needed, the function checks the cache, finds the result, and returns it instantly, avoiding the recursive calls. This drastically improves performance for certain types of algorithms, particularly those exhibiting overlapping subproblems (like dynamic programming).
• Content Delivery Network (CDN):

  Definition: A Content Delivery Network (CDN) is a geographically distributed network of servers that cache copies of web content (static files, streaming media) closer to end-users.

  • Context: CDNs use caching to improve website speed and reliability. When a user requests content, the CDN directs the request to the server nearest to them that has a cached copy, reducing latency and network hops.
• Cloud Storage Gateway: These devices provide local network access to cloud storage. They use a local cache (often on SSDs or HDDs) to store frequently accessed cloud data, providing fast local access while keeping the bulk of the data in the cheaper cloud storage.
• Other Software Caches:
  • DNS Cache: Operating systems and DNS servers cache mappings of domain names (like google.com) to IP addresses.
  • Database Cache: Database systems cache frequently accessed data, query results, execution plans, and metadata in memory to speed up queries.
  • Distributed Cache: Systems like Memcached or Redis provide in-memory key-value stores that act as distributed caches across multiple servers, used by applications to cache database queries, session data, or API responses.

In-Network Caches

Caching isn't limited to end devices or servers; it's increasingly being integrated into the network infrastructure itself.

• Information-Centric Networking (ICN):

  Definition: Information-Centric Networking (ICN) is an experimental network architecture where the network focuses on what information is requested (identified by content name) rather than where it is located (identified by host address). ICN nodes inherently include caching capabilities.

  • Context: In ICN, data can be cached at any node along the path from the content source to the user. This is a more fundamental shift than traditional proxy caches.
  • Challenges: ICN caches have unique requirements: fast lookup/eviction policies due to high request rates and rapidly changing state, and careful consideration of content security and cache coherence across the network.
  • ICN-Specific Policies: Novel replacement policies have been developed for ICN:
    • Time Aware Least Recently Used (TLRU): An LRU variant that incorporates a "Time To Use" (TTU) value set by the content publisher or calculated locally. This allows content with a limited valid lifetime (like a weather forecast) to be managed appropriately, ensuring stale data is evicted faster.
    • Least Frequent Recently Used (LFRU): Combines LFU (frequency) and LRU (recency). It often partitions the cache into a "privileged" section for very popular content (managed with LRU or similar) and an "unprivileged" section managed with an approximated LFU, aiming to keep popular content longer while allowing less popular recent content some time in the cache.
  • Real-world Example: The weather forecast example mentioned in the source (truncating GPS coordinates for caching) is a practical application of caching principles in a network setting, though not necessarily a pure ICN example. By aggregating slightly different requests for nearby locations under a single cache key, the hit rate is drastically increased.

Buffer vs. Cache: A Critical Distinction

Although sometimes used interchangeably, "buffer" and "cache" serve distinct primary purposes. Understanding this difference is key to correctly diagnosing performance issues and designing efficient I/O.

Definition: A buffer is a temporary storage area used to hold data during transfer between two devices or processes that operate at different speeds, or to collect small writes/reads into larger, more efficient blocks.

Definition: A cache is a temporary storage area holding copies of data (or computation results) from a slower backing store, with the primary intent of serving future requests for that same data faster.

Here's a breakdown of their core differences:

Feature	Buffer	Cache
Primary Goal	Smooth data flow, match speeds, aggregate I/O, temporary holding	Speed up repeated access to the same data/computation
Data Used	Typically used/consumed once	Data is expected to be used multiple times
Mechanism	FIFO (usually), holds data in transit	Lookup based on key/tag, manages copies, uses replacement policy
Benefit For	Single transfers, matching I/O rates	Repeated transfers of the same data, exploiting locality
Consistency	Less concern for consistency (data is moving)	Requires cache coherence protocols if multiple copies exist
Relationship	Caching often uses buffering internally (e.g., writing a dirty cache line back in large blocks).	Buffering does not necessarily involve caching.

Examples:

• Buffer: A keyboard buffer holds keystrokes until the CPU can process them. A network card buffer holds incoming packets until the OS can receive them. A disk write buffer collects small writes into a larger block before sending it to the hard drive.
• Cache: CPU caches store copies of frequently used memory blocks. A web browser cache stores copies of web pages you've visited. Memoization caches the results of function calls.

While a cache might improve performance on the first write by holding it in a buffer (write-back policy), its true value comes from subsequent accesses to that same data or nearby data being served from the cache. A buffer, on the other hand, provides its benefit even if the data is written once and read once, by making the transfer itself more efficient or by acting as an intermediary.

Conclusion: The Power of Deep Understanding

Caching is not just a simple layer you can ignore; it's a fundamental mechanism that dictates performance across every level of a computing system. Mastering the concepts of hits, misses, locality, write policies, replacement policies, and the various places caches appear is crucial for any programmer aiming for peak performance.

While schools teach the basics, the "forbidden code" lies in truly internalizing these concepts and their interactions. It's in designing your data structures to maximize spatial locality for CPU caches, understanding the page cache impact on file I/O, choosing the right caching layer (or layers) for your application, and even considering network-level caching strategies.

This deep understanding allows you to predict performance bottlenecks, design efficient algorithms, and troubleshoot complex system behaviors that baffle programmers who only see the high-level abstractions. Embrace this knowledge, and you'll gain an unfair advantage in the race for performance.