Pattern-based prefetching predicts future data accesses from regularities in current and past accesses. It retrieves likely-needed data before the application requests it, aiming to hide access latency. Its predictions follow access patterns and physical data layout, not the meaning of the data or the user’s intent. section 11.2.1 section 11.2
Common patterns suggest different data to fetch:
- Sequential: after an access, fetch the next elements. When processing a file line by line, I/O for later lines can overlap processing of the current line. section 11.2.1
- Spatial: fetch nearby elements, such as those on either side of the element just accessed. section 11.2.1
- Stride-based: fetch elements at a recurring fixed interval, such as every second element. section 11.2.1
Figure 11.1 With sequential prefetching, we predict that successive data elements relative to the one we’re accessing will be needed in the future. In this example, we access the first data element and, therefore, predict that the next data elements will also be needed.
The first access triggers retrieval of the next two elements while the first is being processed, so the second can be ready when requested. section 11.2.1
For sequential access to data larger than memory, keep a resident prefetch window and configure its size to keep upcoming elements available. Prefetching too little misses opportunities to hide latency; prefetching the wrong data wastes resources and can worsen latency. A pattern can also be misleading: physically adjacent orders may be fetched even though proximity says nothing about which order a user wants next. section 11.2.1 section 11.2
Choose a semantic strategy when application state or user behavior is the better clue. Dependency-based prefetching uses relationships between data; context-based prefetching uses current application state; history-based prefetching uses recorded user actions. These differ from predicting accesses solely from a recurring physical pattern. Pattern detection also appears below the application: operating-system readahead fetches disk pages into the page cache ahead of use. section 11.2.2 section 11.2
