# Memory Access Patterns Are Important

DevFeed: [Memory Access Patterns Are Important](<https://devfeed.tech/articles/memory-access-patterns-are-important-13627.md>)

Original publisher: [Read original article](<https://mechanical-sympathy.blogspot.com/2012/08/memory-access-patterns-are-important.html>)

Author: Martin Thompson (noreply@blogger.com)

Published: 2012-08-05T20:12:00Z

Content type: article

Language: en

Sources: [Mechanical Sympathy](<https://devfeed.tech/sources/mechanical-sympathy.md>)

Topics: [Cache](<https://devfeed.tech/topics/cache.md>), [Latency](<https://devfeed.tech/topics/latency.md>), [Hardware](<https://devfeed.tech/topics/hardware.md>), [cpu](<https://devfeed.tech/topics/cpu.md>), [systems](<https://devfeed.tech/topics/systems.md>), [Code](<https://devfeed.tech/topics/code.md>)

Tags: [algorithm](<https://devfeed.tech/tags/algorithm.md>), [big-data](<https://devfeed.tech/tags/big-data.md>), [cache](<https://devfeed.tech/tags/cache.md>), [code](<https://devfeed.tech/tags/code.md>), [hardware](<https://devfeed.tech/tags/hardware.md>), [latency](<https://devfeed.tech/tags/latency.md>), [memory](<https://devfeed.tech/tags/memory.md>), [performance](<https://devfeed.tech/tags/performance.md>), [processors](<https://devfeed.tech/tags/processors.md>)

## AI overview

This article explains how processor cache hierarchies and memory-access patterns affect performance. It describes temporal, spatial, and striding patterns, then compares linear and increasingly random heap walks across CPU architectures. The results indicate that caches can hide main-memory latency more effectively for predictable access patterns, while larger memory regions and random access expose latency.

## Source excerpt

In high-performance computing it is often said that the cost of a cache-miss is the largest performance penalty for an algorithm. For many years the increase in speed of our processors has greatly outstripped latency gains to main-memory. Bandwidth to main-memory has greatly increased via wider, and multi-channel, buses however the latency has not significantly reduced. To hide this latency our processors employ evermore complex cache sub-systems that have many layers. The 1994 paper "Hitting the memory wall: implications of the obvious" describes the problem and goes on to argue that caches do not ultimately help because of compulsory cache-misses. I aim to show that by using access patterns which display consideration for the cache hierarchy, this conclusion is not inevitable. Let's start putting the problem in context with some examples. Our hardware tries to hide the main-memory latency via a number of techniques. Basically three major bets are taken on memory access patterns: Temporal: Memory accessed recently will likely be required again soon. Spatial: Adjacent memory is likely to be required soon. Striding: Memory access is likely to follow a predictable pattern. To illustrate these three bets in action let's write some code and measure the results. Walk through memory in a linear fashion being completely predictable. Pseudo randomly walk round memory within a restricted area then move on. This restricted area is what is commonly known as an operating system page of memory. Pseudo randomly walk around a large area of the heap. Code The following code should be run with the -Xmx4g JVM option. public class TestMemoryAccessPatterns { private static final int LONG_SIZE = 8; private static final int PAGE_SIZE = 2 * 1024 * 1024; private static final int ONE_GIG = 1024 * 1024 * 1024; private static final long TWO_GIG = 2L * ONE_GIG; private static final int ARRAY_SIZE = (int)(TWO_GIG / LONG_SIZE); private static final int WORDS_PER_PAGE = PAGE_SIZE / LONG_SIZE; pri