longlinht.github.io/cache-friendly-code.html at master · longlinht/longlinht.github.io · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
<!DOCTYPE html>
<html>
<head>
    <!-- [[! Document Settings ]] -->
    <meta charset="utf-8" />
    <meta http-equiv="X-UA-Compatible" content="IE=edge" />

    <!-- [[! Page Meta ]] -->
    <title>What is cache-friendly code</title>
    <meta name="description" content="与机器，人，神共舞 - 编程，读书，思考，旅行，与机器对话，与人交谈，对神发问，探索，体验人生美丽的风景" />

    <meta name="HandheldFriendly" content="True" />
    <meta name="viewport" content="width=device-width, initial-scale=1.0" />

    <link rel="shortcut icon" href="/assets/images/favicon.ico" >

    <!-- [[! Styles'n'Scripts ]] -->
    <link rel="stylesheet" type="text/css" href="/assets/css/screen.css" />
    <link rel="stylesheet" type="text/css"
          href="//fonts.googleapis.com/css?family=Merriweather:300,700,700italic,300italic|Open+Sans:700,400" />
    <link rel="stylesheet" type="text/css" href="/assets/css/syntax.css" />

    <!-- [[! Ghost outputs important style and meta data with this tag ]] -->
        <link rel="canonical" href="/" />
    <meta name="referrer" content="origin" />
    <link rel="next" href="/page2/" />

    <meta property="og:site_name" content="与机器，人，神共舞" />
    <meta property="og:type" content="website" />
    <meta property="og:title" content="与机器，人，神共舞" />
    <meta property="og:description" content="编程，读书，思考，旅行，与机器对话，与人交谈，对神发问，探索，体验人生美丽的风景" />
    <meta property="og:url" content="/" />
    <meta property="og:image" content="/assets/images/cover1.jpg" />

    <meta name="twitter:card" content="summary_large_image" />
    <meta name="twitter:title" content="与机器，人，神共舞" />
    <meta name="twitter:description" content="编程，读书，思考，旅行，与机器对话，与人交谈，对神发问，探索，体验人生美丽的风景" />
    <meta name="twitter:url" content="/" />
    <meta name="twitter:image:src" content="/assets/images/cover1.jpg" />

    <script type="application/ld+json">
{
    "@context": "http://schema.org",
    "@type": "Website",
    "publisher": "Tao's Page",
    "url": "/",
    "image": "/assets/images/cover1.jpg",
    "description": "编程，读书，思考，旅行，与机器对话，与人交谈，对神发问，探索，体验人生美丽的风景"
}
    </script>

    <meta name="generator" content="Jekyll 3.0.0" />
    <link rel="alternate" type="application/rss+xml" title="与机器，人，神共舞" href="/rss.xml" />

</head>
<body class="home-template nav-closed">

    <div class="nav">
    <h3 class="nav-title">Menu</h3>
    <a href="#" class="nav-close">
        <span class="hidden">Close</span>
    </a>
    <ul>
        <li class="nav-home " role="presentation"><a href="/">Home</a></li>
        <li class="nav-about " role="presentation"><a href="/about.html">About</a></li>
        <li class="nav-fables " role="presentation"><a href="/tag/machine/">Machine</a></li>
        <li class="nav-speeches " role="presentation"><a href="/tag/human/">Human</a></li>
        <li class="nav-fiction " role="presentation"><a href="/tag/god/">God</a></li>
        <li class="nav-author " role="presentation"><a href="/author/hetao/">Author</a></li>
    </ul>
    <a class="subscribe-button icon-feed" href="/vocab.html">Apps</a>
</div>
<span class="nav-cover"></span>


    <div class="site-wrapper">

        <!-- [[! Everything else gets inserted here ]] -->
        <!-- default -->

<!-- The comment above "< default" means - insert everything in this file into -->
    <!-- the [body] of the default.hbs template, which contains our header/footer. -->

<!-- Everything inside the #post tags pulls data from the post -->
<!-- #post -->

<header class="main-header post-head no-cover">
    <nav class="main-nav  clearfix">


    </nav>
</header>

<main class="content" role="main">

    <article class="post tag-machine">

        <header class="post-header">
            <h1 class="post-title">What is cache-friendly code</h1>
            <section class="post-meta">
            <!-- <a href='/'>Tao He</a> -->


            <time class="post-date" datetime="2011-03-12">12 Mar 2011</time>
                <!-- [[tags prefix=" on "]] -->

                on


                       <a href='/tag/machine'>Machine</a>


            </section>
        </header>

        <section class="post-content">

            <p>In modern computer systems, the memory hierarchy plays a crucial role in balancing performance and cost. At the top of this hierarchy are the registers, which are extremely fast but very limited in number due to their high cost. On the other end, we have DRAM, which is inexpensive but significantly slower, taking hundreds of clock cycles to access data. To bridge this gap between fast and costly registers and slow but cheap DRAM, intermediate cache memories—namely L1, L2, and L3 caches—are used. These caches progressively decrease in speed and cost, allowing frequently accessed data to be retrieved quickly, while less frequently accessed data is stored in slower, cheaper memory.</p>

<p>Caching works on the principle that most executing code frequently accesses a small set of variables, while a much larger set of variables is accessed infrequently. If the processor cannot find the needed data in the L1 cache, it checks the L2 cache, then the L3 cache, and finally the main memory. Each cache miss, where data is not found in the cache and must be retrieved from a lower level, incurs a significant time penalty.</p>

<p>This hierarchical approach is analogous to the relationship between system memory and hard disk storage: system memory is faster but more expensive, while hard disk storage is slower but much cheaper. Effective caching is essential to mitigate latency, as increasing bandwidth alone cannot solve the latency problem.</p>

<p>Data retrieval always follows the memory hierarchy, moving from the fastest, smallest memory to the slowest, largest memory. The performance of a system heavily depends on the cache hit rate, which refers to the frequency with which data requests are successfully served from the cache. High cache hit rates are crucial because cache misses result in slower data retrieval from RAM or, worse, the hard disk, significantly impacting performance.</p>

<p>In contemporary computer architectures, the main performance bottleneck is accessing memory outside the CPU die, such as RAM. This issue has become more pronounced over time, as increases in processor frequency no longer translate to significant performance gains due to memory access limitations. Consequently, modern CPU designs focus heavily on optimizing caches, prefetching data, pipeline efficiency, and concurrency. Notably, up to 85% of a CPU’s die area is devoted to caches, and up to 99% for data storage and movement.</p>

<h4 id="key-concepts-for-cache-friendly-code">Key Concepts for Cache-Friendly Code</h4>

<ol>
  <li><strong>Principle of Locality</strong>:
    <ul>
      <li><strong>Temporal Locality</strong>: Frequently accessed data is likely to be accessed again soon.</li>
      <li><strong>Spatial Locality</strong>: Data located near recently accessed data is also likely to be accessed soon.</li>
    </ul>
  </li>
  <li><strong>Cache Lines</strong>:
    <ul>
      <li>Understanding cache lines is critical, as data is fetched in blocks, making contiguous memory access more efficient.</li>
    </ul>
  </li>
  <li><strong>Choosing Appropriate Containers</strong>:
    <ul>
      <li>For instance, in C++, <code class="language-plaintext highlighter-rouge">std::vector</code> stores elements contiguously, enhancing cache efficiency, whereas <code class="language-plaintext highlighter-rouge">std::list</code> does not, leading to poorer cache performance.</li>
    </ul>
  </li>
  <li><strong>Data Structure and Algorithm Design</strong>:
    <ul>
      <li>Techniques like cache blocking and exploiting data structure order (e.g., row-major vs. column-major ordering) are essential to optimize cache usage.</li>
    </ul>
  </li>
  <li><strong>Avoid Unpredictable Branches</strong>:
    <ul>
      <li>These complicate prefetching and lead to more cache misses.</li>
    </ul>
  </li>
  <li><strong>Minimize Use of Virtual Functions</strong>:
    <ul>
      <li>Virtual function calls can cause cache misses, although frequent calls might mitigate this issue.</li>
    </ul>
  </li>
  <li><strong>Prevent False Sharing</strong>:
    <ul>
      <li>This occurs when multiple processors write to different variables in the same cache line, causing excessive cache coherence traffic.</li>
    </ul>
  </li>
</ol>

<h3 id="conclusion">Conclusion</h3>

<p>Efficient caching is fundamental to the performance of modern computer systems. By leveraging principles of locality, choosing appropriate data structures, and optimizing algorithms, programmers can significantly enhance their code’s efficiency. Understanding and addressing common caching issues, such as false sharing and unpredictable branches, further helps in achieving optimal performance.</p>


        </section>

        <footer class="post-footer">

            <!-- Everything inside the #author tags pulls data from the author -->
            <!-- #author-->


            <!-- Add Disqus Comments -->


        </footer>

    </article>

</main>

<aside class="read-next">

    <!-- [[! next_post ]] -->

        <a class="read-next-story no-cover" href="/segmentation-fault">
            <section class="post">
                <h2>Segmentation-fault in C++</h2>
                <p>A segmentation fault, commonly referred to as a segfault, is a specific error that occurs...</p>
            </section>
        </a>

    <!-- [[! /next_post ]] -->
    <!-- [[! prev_post ]] -->

        <a class="read-next-story prev no-cover" href="/singleton-in-cpp">
            <section class="post">
                <h2>Singleton Design Pattern in C++</h2>
                <p>The Singleton design pattern ensures a class has only one instance and provides a global...</p>
            </section>
        </a>

    <!-- [[! /prev_post ]] -->
</aside>

<!-- /post -->


        <footer class="site-footer clearfix">
          <section class="copyright"><a href="/">与机器，人，神共舞</a> &copy; 2024</section>
        </footer>
    </div>
    <!-- [[! Ghost outputs important scripts and data with this tag ]] -->
    <script type="text/javascript" src="https://code.jquery.com/jquery-1.11.3.min.js"></script>
    <!-- [[! The main JavaScript file for Casper ]] -->
    <script type="text/javascript" src="/assets/js/jquery.fitvids.js"></script>
    <script type="text/javascript" src="/assets/js/index.js"></script>

    <!-- Add Google Analytics  -->
        <!-- Google Analytics Tracking code -->
     <script>
	    (function(i,s,o,g,r,a,m){i['GoogleAnalyticsObject']=r;i[r]=i[r]||function(){
	    (i[r].q=i[r].q||[]).push(arguments)},i[r].l=1*new Date();a=s.createElement(o),
	    m=s.getElementsByTagName(o)[0];a.async=1;a.src=g;m.parentNode.insertBefore(a,m)
	    })(window,document,'script','//www.google-analytics.com/analytics.js','ga');

	    ga('create', 'UA-78960009-1', 'auto');
	    ga('send', 'pageview');

     </script>

</body>
</html>