<?xml version="1.0" encoding="UTF-8"?><rss xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:content="http://purl.org/rss/1.0/modules/content/" xmlns:atom="http://www.w3.org/2005/Atom" version="2.0" xmlns:cc="http://cyber.law.harvard.edu/rss/creativeCommonsRssModule.html">
    <channel>
        <title><![CDATA[Applied - Medium]]></title>
        <description><![CDATA[Articles on software performance and IP networking - Medium]]></description>
        <link>https://medium.com/applied?source=rss----e4ce1e8848ee---4</link>
        <image>
            <url>https://cdn-images-1.medium.com/proxy/1*TGH72Nnw24QL3iV9IOm4VA.png</url>
            <title>Applied - Medium</title>
            <link>https://medium.com/applied?source=rss----e4ce1e8848ee---4</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Thu, 19 Nov 2026 16:47:09 GMT</lastBuildDate>
        <atom:link href="https://medium.com/feed/applied" rel="self" type="application/rss+xml"/>
        <webMaster><![CDATA[yourfriends@medium.com]]></webMaster>
        <atom:link href="http://medium.superfeedr.com/" rel="hub"/>
        <item>
            <title><![CDATA[Applied C++: Memory Latency]]></title>
            <link>https://medium.com/applied/applied-c-memory-latency-d05a42fe354e?source=rss----e4ce1e8848ee---4</link>
            <guid isPermaLink="false">https://medium.com/p/d05a42fe354e</guid>
            <category><![CDATA[programming]]></category>
            <category><![CDATA[cplusplus]]></category>
            <category><![CDATA[benchmark]]></category>
            <category><![CDATA[cpu]]></category>
            <category><![CDATA[performance]]></category>
            <dc:creator><![CDATA[Andriy Berestovskyy]]></dc:creator>
            <pubDate>Tue, 09 Apr 2019 20:43:19 GMT</pubDate>
            <atom:updated>2019-04-09T20:43:19.625Z</atom:updated>
            <content:encoded><![CDATA[<h4>Benchmarking Kaby Lake and Haswell memory latency using lists</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*U17PBn50zBw0NmjizbLnWg.png" /></figure><p>Modern CPUs are complex beasts with <a href="https://en.wikipedia.org/wiki/Transistor_count">billions of transistors</a>. This complexity in hardware brings indeterminacy even in simple software algorithms.</p><p>Let’s benchmark a simple list traversal. An average node access latency corresponds to CPU cache latencies. Or does it? Let’s put it to the test!</p><h3>“Do I Know This Already?” Quiz</h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*dv1jtrf4QDfIlM2iHaZFKQ.png" /></figure><p>Benchmarking <strong>access latency</strong> for lists with a <strong>different number of nodes</strong>. All the lists are <strong>contiguous</strong> in memory, traversed <strong>sequentially</strong>, and have a <strong>4 KB padding</strong> between the next pointers.</p><p>If we plot on the x-axis the <a href="https://en.wikipedia.org/wiki/Working_set_size"><strong>working sets</strong></a> of benchmark iterations, and on the y-axis the <strong>node access latencies</strong>, how the graph will look on a modern CPU?</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*vELiwC-8V0CPp4Upa4ygsg.png" /></figure><ol><li>The latency graph will have a few steps <strong>matching CPU caches specs</strong>.</li><li>The graph will be steeper, and the <strong>latency much higher than the specs</strong>.</li><li>The graph will be gradual, with <strong>no obvious steps</strong>.</li></ol><p>The correct answer is at the very bottom of the article.</p><h3>Modern CPUs Basics: Cache Hierarchy</h3><p>Modern processors are fast, memory is slow. So CPUs have cache hierarchies:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/920/1*ns6F6cMmInDcCZ_Tsha0yA.png" /><figcaption>Intel Kaby Lake Cache Hierarchy and Access Latency. Source: <a href="https://software.intel.com/en-us/articles/intel-sdm#optimization">Intel SDM</a></figcaption></figure><p>Once CPU tries to access a memory location, first it checks the level 1 cache. If the location is there, it’s an L1 “cache hit”. Otherwise, it’s an L1 “cache miss”, and CPU reaches for the next cache level, down to the memory.</p><p>The cache latencies depend on CPU clock speed, so in specs they are usually listed in cycles. To convert CPU cycles to nanoseconds:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*cuFXm24okhCk2KT14YMJ0Q.png" /></figure><p>For my laptop with Kaby Lake i7–7660U CPU running at 2.5GHz:</p><pre>L1 cache hit latency:   5 cycles / 2.5 GHz = 2 ns<br>L2 cache hit latency:  12 cycles / 2.5 GHz = 4.8 ns<br>L3 cache hit latency:  42 cycles / 2.5 GHz = 16.8 ns<br>Memory access latency: L3 cache latency + DRAM latency = ~60-100 ns</pre><p>Note: modern CPUs support <a href="https://en.wikipedia.org/wiki/Dynamic_frequency_scaling">frequency scaling</a>, and DRAM latency greatly depends on its <a href="https://en.wikipedia.org/wiki/Dynamic_random-access_memory#Principles_of_operation">internal organization and timing</a>. But those are minor details.</p><p>And one more thing. <strong>CPU loads and stores “cache lines”</strong> at a time, not bytes. For x86–64 CPUs the cache line size is 64 bytes, for A64 ARMs it’s 128 bytes. So even if we need to access just one byte, x86 CPU fetches at least 64.</p><p>Now we’ve done with the basics and ready for the real stuff!</p><h3>Benchmarking Intel Kaby Lake Memory Latency</h3><p>Let’s benchmark memory latency by traversing lists with a different number of nodes. If the <a href="https://en.wikipedia.org/wiki/Working_set_size">working set size</a> of a traversal is less than level 1 cache, the node access latency will correspond to the L1 latency. If the working set is less than level 2 cache, the latency will correspond to the L2 cache, and so on.</p><h4>List Nodes Padding</h4><p>The devil is in the detail. Remember CPU fetches cache lines, not bytes? Since the lists are contiguous, the adjacent nodes share the same cache line:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*5sAvn6Epjf7zphg8rdmr-g.png" /><figcaption>Adjacent Nodes Share the Same Cache Line</figcaption></figure><p>As we access the nodes sequentially, after each cache miss there are always a few cache hits within the same cache line. This will skew the average latency.</p><p>To avoid the cache hits, let’s add 4 KB padding to our ListNode struct:</p><pre>// Memory page size. Default page size is 4 KB<br><strong>const</strong> <strong>auto</strong> kPageSize = 4_KB;</pre><pre><strong>struct</strong> ListNode {<br>  ListNode *next;<br>  std::byte padding[kPageSize];<br>};</pre><p>Note: we absolutely want smaller structures and more cache hits in our apps. Adding the padding is just a <strong>trick to avoid some CPU optimizations</strong>, so the memory access latency is not skewed. But more on that later.</p><h4>Working Set Size vs Number of Nodes</h4><p>Traversing a list, each access to the next pointer fetches a cache line, so:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*gLVNTVEE8rO8itPLFb5smQ.png" /></figure><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*dmJ9Br4_ixkO_nG3HlaM_Q.png" /></figure><p>To plot the latency graph, the benchmark iterates over the different working sets, allocating corresponding number of list nodes for each iteration:</p><pre>// Cache line size: 64 bytes for x86-64, 128 bytes for A64 ARMs<br><strong>const</strong> <strong>auto</strong> kCachelineSize = 64_B;</pre><pre>// Each memory access fetches a cache line<br><strong>const</strong> <strong>auto</strong> num_nodes = mem_block_size / kCachelineSize;</pre><pre>// Allocate a contiguous list of nodes for an iteration<br>std::vector&lt;ListNode&gt; list(num_nodes);</pre><h4>The List Traversal Benchmark</h4><p>Let’s initialize the next pointers so they point to the adjacent nodes:</p><pre>// Make a cycle of the list nodes<br><strong>for</strong> (<strong>size_t</strong> i = 0; i &lt; list.size() - 1; i++)<br>  list[i].next = &amp;list[i + 1];<br>list[list.size() - 1].next = &amp;list[0];</pre><p>Now when we have our cyclic graph, the benchmark is trivial:</p><pre><strong>static</strong> <strong>auto</strong> traverse_list(ListNode *head, <strong>size_t</strong> num_ops) {<br>  <strong>while</strong> (num_ops--) head = head-&gt;next;<br>  <strong>return</strong> head;<br>}</pre><p>We just access the nodes sequentially num_ops times. The nodes are located <strong>contiguous</strong>, and we access them <strong>sequentially</strong>. Let’s <a href="https://github.com/berestovskyy/applied-benchmarks/tree/master/memory-latency">run it</a>!</p><h4>Intel Kaby Lake Memory Latency Results</h4><p>Here are somewhat shortened results for my Kaby Lake laptop:</p><pre>-----------------------------------------------------------<br>Benchmark                                   Time      Nodes<br>-----------------------------------------------------------<br>memory_latency_list/size KB:1            1.01 ns         16<br>memory_latency_list/size KB:2            1.02 ns         32<br>memory_latency_list/size KB:4            1.10 ns         64<br>memory_latency_list/size KB:8            3.32 ns        128<br>memory_latency_list/size KB:16           3.32 ns        256<br>memory_latency_list/size KB:32           3.33 ns        512<br>memory_latency_list/size KB:64           5.33 ns       1024<br>memory_latency_list/size KB:128          8.58 ns         2k<br>memory_latency_list/size KB:256          13.9 ns         4k<br>memory_latency_list/size KB:512          14.2 ns         8k<br>memory_latency_list/size KB:1024         14.2 ns        16k<br>memory_latency_list/size KB:2048         17.3 ns        32k<br>memory_latency_list/size KB:4096         63.1 ns        64k<br>memory_latency_list/size KB:8192         96.4 ns       128k<br>memory_latency_list/size KB:16384         104 ns       256k</pre><p>Let’s add to the picture the cache size and latency from the specs above:</p><pre>L1 cache hit latency:   5 cycles / 2.5 GHz = 2 ns<br>L2 cache hit latency:  12 cycles / 2.5 GHz = 4.8 ns<br>L3 cache hit latency:  42 cycles / 2.5 GHz = 16.8 ns<br>Memory access latency: L3 cache latency + DRAM latency = ~60-100 ns</pre><p>And put it all on the graph:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*W_jBLDMwdSvNnq1xKz-ZdA.png" /><figcaption>Intel Kaby Lake List Node Access Latency</figcaption></figure><p>The colored vertical bars represent the cache size and latency from the specs. The black-red line is the average access latency from the benchmark.</p><p>Note the parts of the graph marked in red. The difference between the CPU specifications and the benchmark results is huge! Hmm…</p><h3>Benchmarking Intel Haswell Memory Latency</h3><p>Let’s confirm the results on a different architecture. I have another laptop with older Haswell i5–4278U CPU running at 2.6GHz, so let’s run the same benchmark there. Here are the Haswell specs:</p><pre>L1 cache hit latency:   5 cycles / 2.6 GHz = 1.92 ns<br>L2 cache hit latency:  11 cycles / 2.6 GHz = 4.23 ns<br>L3 cache hit latency:  34 cycles / 2.6 GHz = 13.08 ns<br>Memory access latency: L3 cache latency + DRAM latency = ~60-100 ns</pre><p>The raw benchmark results:</p><pre>-----------------------------------------------------------<br>Benchmark                                   Time      Nodes<br>-----------------------------------------------------------<br>memory_latency_list/size KB:1            1.30 ns         16<br>memory_latency_list/size KB:2            1.29 ns         32<br>memory_latency_list/size KB:4            1.30 ns         64<br>memory_latency_list/size KB:8            3.92 ns        128<br>memory_latency_list/size KB:16           4.03 ns        256<br>memory_latency_list/size KB:32           3.90 ns        512<br>memory_latency_list/size KB:64           6.54 ns       1024<br>memory_latency_list/size KB:128          9.71 ns         2k<br>memory_latency_list/size KB:256          17.4 ns         4k<br>memory_latency_list/size KB:512          21.2 ns         8k<br>memory_latency_list/size KB:1024         21.2 ns        16k<br>memory_latency_list/size KB:2048         28.9 ns        32k<br>memory_latency_list/size KB:3072         43.3 ns        48k<br>memory_latency_list/size KB:4096         52.0 ns        64k<br>memory_latency_list/size KB:8192         71.8 ns       128k<br>memory_latency_list/size KB:16384        80.4 ns       256k</pre><p>And here is the graph for the Haswell microarchitecture:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*x1Rp0eCg29Qv98kjoiF22Q.png" /><figcaption>Intel Haswell List Node Access Latency</figcaption></figure><p>Not only it confirms the huge difference between the CPU specs and the results, but L3 latency from the specs not even touching the results graph!</p><h3>Analyzing Memory Latency Benchmark</h3><p>It appears, the simple list traversal is a bit more complicated than it seemed. Looking at the Kaby Lake and Haswell latency graphs above, there are a few questions for a deeper analysis:</p><ol><li>Why the latency graph matches CPU specifications only up to 4 KB?</li><li>Why the measured latency is much higher than the CPU specs?</li><li>The list nodes are accessed sequentially, with fixed steps. Despite that simple access pattern, why CPU <a href="https://en.wikipedia.org/wiki/Cache_prefetching">cache prefetching</a> doesn’t help?</li><li>And the most important: what do we do to lower the access latency?</li></ol><h3>Intel Kaby Lake Level 1 Cache Latency Analysis</h3><p>To zoom into L1 cache, let’s run the same benchmark with 1 KB step:</p><pre>------------------------------------------------------<br>Benchmark                              Time      Nodes<br>------------------------------------------------------<br>memory_latency_list/size KB:1       1.02 ns         16<br>memory_latency_list/size KB:2       1.03 ns         32<br>memory_latency_list/size KB:3       1.03 ns         48<br><strong>memory_latency_list/size KB:4       1.05 ns         64<br>memory_latency_list/size KB:5       3.33 ns         80<br></strong>memory_latency_list/size KB:6       3.33 ns         96<br>memory_latency_list/size KB:7       3.33 ns        112<br>memory_latency_list/size KB:8       3.35 ns        128</pre><p>Here is the graph:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*xovEueiry-ExwBW3u9IblQ.png" /><figcaption>Intel Kaby Lake Level 1 Cache Access Latency Jump</figcaption></figure><p>The graph is flat and in accordance with the specs up until the <strong>“magic” 4 KB</strong> point. Then the latency jumps from 1.05 ns to 3.33 ns. It’s three times slower!</p><p>Let’s make a break for some bits of knowledge.</p><h3>Modern CPUs Basics: Virtual and Physical Memory</h3><p>Modern processors run each process in a <strong>virtual address space</strong>:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*cLjESLA8WYKLH1wc0ljFFQ.png" /><figcaption>Process Virtual Address Space and Physical Memory</figcaption></figure><p>Each process has an illusion of a huge 64-bit contiguous address space available just for its needs, but in fact, each memory allocation maps a piece of physical memory called “page” to process virtual address space. That is convenient and secure (due to process isolation), but now <strong>each memory access requires translation from virtual to physical address space</strong>.</p><p>There is a part of CPUs called the Memory Management Unit (MMU) which translates virtual to physical addresses. MMU uses a cache to translate virtual to physical addresses called Translation Lookaside Buffer (TLB).</p><p>What often slips from the attention is that <strong>TLB is a hierarchy of caches</strong>, not just a plain cache. Here is the Kaby Lake TLB hierarchy specification:</p><pre>Level 1 Instruction Cache TLB (ITLB) for 4 KB pages: 128 entries<br><strong>Level 1 Data Cache TLB (DTLB) for 4 KB pages:        64 entries<br></strong>Level 1 Data Cache TLB (DTLB) for 2/4 MB pages:      32 entries<br>Level 1 Data Cache TLB (DTLB) for 1 GB pages:        4 entries<br>Level 2 Unified TLB (STLB) for 4 KB and 2 MB pages:  1536 entries<br>Level 2 Unified Cache TLB (STLB) for 1 GB pages:     16 entries</pre><p>For 4 KB pages, there are just 64 level 1 cache entries and up to 1536 level 2 cache entries shared with instructions. That’s not much…</p><h3>Level 1 Cache Latency Analysis (continued)</h3><p>Getting back to the level 1 access latency jump. Remember the 4 KB padding between the next pointers, so <strong>each node is at least a memory page size</strong>. The latency jumps after 64 list nodes, hence after 64 pages:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*bJCYi2hZsJjW3eJdnHkYLw.png" /><figcaption>Intel Kaby Lake Level 1 Cache Access Latency Jump</figcaption></figure><p>That’s the exact number of level 1 DTLB cache entries from the specs:</p><pre>Level 1 Data Cache TLB (DTLB) for 4 KB pages:        64 entries</pre><p>So, while the data still fits into the L1 cache, <strong>virtual to physical address translation does not fit into L1 DTLB</strong>. That explains the latency jump.</p><h3>Intel Kaby Lake Level 2 Cache Latency Analysis</h3><p>Now let’s zoom into level 2 cache latency:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*KFzFU_bHq2KI07sIO_6nxg.png" /><figcaption>Intel Kaby Lake Level 2 Cache Latency Jump</figcaption></figure><p>As we just discovered, <strong>because of the L1 TLB misses the latency is much higher</strong> than the specs across all level 2 latency graph. The step between 96 KB and 112 KB is not that dramatic as in level 1 graph, but still quite prominent. Let’s check the number of list nodes again:</p><pre>--------------------------------------------------------<br>Benchmark                                Time      Nodes<br>--------------------------------------------------------<br>memory_latency_list/size KB:48        4.72 ns        768<br>memory_latency_list/size KB:64        5.42 ns       1024<br>memory_latency_list/size KB:80        5.34 ns      1.25k<br><strong>memory_latency_list/size KB:96        5.80 ns       1.5k<br>memory_latency_list/size KB:112       7.97 ns      1.75k<br></strong>memory_latency_list/size KB:128       8.34 ns         2k<br>memory_latency_list/size KB:144       8.36 ns      2.25k<br>memory_latency_list/size KB:160       8.82 ns       2.5k</pre><p>And here are the Kaby Lake specs:</p><pre>Level 2 Unified TLB (STLB) for 4 KB and 2 MB pages:  1536 entries</pre><p>Due to the 4 KB padding, each list node is at least a memory page size. So the reason is quite the same: once the number of nodes (i.e. the number of pages) is greater than the number of STLB entries, the latency increases significantly.</p><h3>Intel Kaby Lake Level 3 Cache Latency Analysis</h3><p>There are no TLB tricks left in the sleeves, so what’s going on in level 3 cache?</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*KxNtPSB46aG6LG_dHphwBA.png" /><figcaption>Intel Kaby Lake Level 3 Cache Latency Jump</figcaption></figure><p><strong>Level 3 cache is a point of coherency</strong>, so it’s shared across all the cores. Despite the 4 MB size, <strong>each core is able to use only up to 2 MB</strong> of L3 cache.</p><p>The <a href="https://software.intel.com/en-us/articles/intel-sdm">software developer manuals</a> cover this subtle detail. The information is also available on Wikipedia: <a href="https://en.wikipedia.org/wiki/Kaby_Lake">https://en.wikipedia.org/wiki/Kaby_Lake</a></p><h3>What About The Cache Prefetching?</h3><p>Some of you might have noticed the trick we played in this benchmark: the page size padding makes the TLB hierarchy more prominent.</p><p>Kaby Lake has two <a href="https://en.wikipedia.org/wiki/Cache_prefetching">hardware prefetchers</a>. The CPU predicts memory locations to be accessed, and fetches the data in advance. All the lists are <strong>contiguous</strong>, and traversed <strong>sequentially</strong>, so the <strong>access pattern is easily predictable</strong>.</p><p>With prefetching, the average access latency should be below the specs. But on the graph across all the working sets, the latency is always above the specs.</p><p>The answer is in the <a href="https://software.intel.com/en-us/articles/intel-sdm">Intel manuals</a>: data prefetching requires the prefetched <strong>cache lines to be in the same 4 KB page</strong>. So with a page size padding not only we emphasized the TLB effect but also disabled the cache prefetching.</p><h3>The Way to Avoid TLB Misses</h3><p>In this particular benchmark, the obvious solution would be to use TLB caches more efficiently by simply removing the padding, hence making the list nodes more compact. But it’s not always an option: for large data structures or when the nodes are not contiguous, we are limited to just 64 pages.</p><p>All modern CPUs support <a href="https://en.wikipedia.org/wiki/Page_(computer_memory)#Multiple_page_sizes">pages larger than 4 KB</a>. In Linux, those called huge pages, in FreeBSD — super pages, and in Windows those are just large pages.</p><p>To avoid TLB misses, <strong>the lists must be allocated using huge pages</strong>.<br>But it’s another story. Stay tuned!</p><h3>Takeaways</h3><p>Memory access in modern CPUs is a huge topic, and we’ve just scratched the surface here. Main takeaways:</p><ol><li>Besides the CPU cache hierarchy, <strong>there is also a TLB cache hierarchy</strong>.</li><li><strong>There are just 64 L1 cache DTLB entries</strong>, so once an app uses more than 64 of 4 KB pages, there are always L1 TLB cache misses.</li><li>The cache <strong>prefetching works only within the same 4 KB page</strong>.</li></ol><p><strong>Full source code: </strong><a href="https://github.com/berestovskyy/applied-benchmarks">https://github.com/berestovskyy/applied-benchmarks</a></p><h3>The Answer to “Do I Know This Already?” Quiz</h3><p>The graph will be steeper, and the latency much higher than the CPU specifications. See the article for more details.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=d05a42fe354e" width="1" height="1" alt=""><hr><p><a href="https://medium.com/applied/applied-c-memory-latency-d05a42fe354e">Applied C++: Memory Latency</a> was originally published in <a href="https://medium.com/applied">Applied</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Applied C++: Align Array Elements]]></title>
            <link>https://medium.com/applied/applied-c-align-array-elements-32af40a768ee?source=rss----e4ce1e8848ee---4</link>
            <guid isPermaLink="false">https://medium.com/p/32af40a768ee</guid>
            <category><![CDATA[technology]]></category>
            <category><![CDATA[tutorial]]></category>
            <category><![CDATA[cplusplus]]></category>
            <category><![CDATA[c]]></category>
            <category><![CDATA[programming]]></category>
            <dc:creator><![CDATA[Andriy Berestovskyy]]></dc:creator>
            <pubDate>Fri, 21 Dec 2018 16:08:43 GMT</pubDate>
            <atom:updated>2025-11-06T09:42:11.895Z</atom:updated>
            <content:encoded><![CDATA[<h4>How to align elements in an array using C++11 alignas specifier</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*JIso8iKYKveTpsLBemSXXw.png" /></figure><h3>“Do I Know This Already?” Quiz</h3><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*n1YsJnG_Ns3031i7tmay_w.png" /></figure><p>How to define an array so each its element is aligned to 64 bytes?</p><ol><li><strong>alignas</strong>(64) <strong>int</strong> option_1[4];</li><li><strong>int</strong> CACHE_ALIGNED option_2[4];</li><li><strong>int</strong> option_3[4] CACHE_ALIGNED;</li><li><strong>typedef</strong> CACHE_ALIGNED <strong>int</strong> aligned_t;<br>aligned_t option_4[4];</li></ol><p>Where the CACHE_ALIGNED macro is defined as follows:</p><pre><strong>#if</strong> <strong>defined</strong>(__GNUC__)<br><strong>#define</strong> CACHE_ALIGNED <strong>__attribute__</strong>((<strong>aligned</strong>(64))) // clang and GCC<br><strong>#elif</strong> <strong>defined</strong>(_MSC_VER)<br><strong>#define</strong> CACHE_ALIGNED <strong>__declspec</strong>(<strong>align</strong>(64))        // MSVC<br><strong>#endif</strong></pre><p>The answer is at the very bottom of the article.</p><h3>Use Case: Why to Align Array Elements?</h3><p>Imagine an array of thread states: <strong>enum</strong> ThreadState state_flags[kMaxCPUs]; There are few worker threads and each thread reads and updates its state: state_flags[this_thread_id] = kThreadAlive; No synchronization is needed, since each array element is accessed exclusively by one thread. But what’s the problem with alignment here?</p><blockquote>False sharing — performance-degrading usage pattern when concurrently running threads store their private data in the same cache line.</blockquote><blockquote>— <a href="https://en.wikipedia.org/wiki/False_sharing">Wikipedia</a></blockquote><p><strong>To avoid false sharing</strong> among the workers, each element has to be aligned to the CPU cache line size: 64 bytes for x86 CPUs and 128 bytes for ARMs. Let’s see how to align the elements.</p><h3>Analysis</h3><p>Every complete object <strong>type in C++ has its alignment requirement</strong>. The C++11 standard conveniently offers an alignof() operator to query the alignment requirement of a given type:</p><pre>/* The output on my system is 16 (long double) */<br>printf(&quot;Alignment of &#39;max_align_t&#39; is %zd\n&quot;, <strong>alignof</strong>(max_align_t));<br>/* The output on my system is 4 */<br>printf(&quot;Alignment of &#39;int&#39; is %zd\n&quot;, <strong>alignof</strong>(<strong>int</strong>));</pre><p>Both the specifier alignas and attribute((aligned)) (or declspec(align) for MSVC) increase alignment requirement, but <strong>could only be applied to </strong><a href="https://gcc.gnu.org/onlinedocs/gcc/Common-Variable-Attributes.html#Common-Variable-Attributes"><strong>variables or structure fields</strong></a>. There is no way to increase the alignment requirement for each array element, as the alignment requirement is for the whole array:</p><pre><strong>alignas</strong>(64) <strong>int</strong> option_1[4];</pre><p>This alignas(64) specifier produces the following result:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*oc3Dva1qqHKs4rQtEVPavg.png" /></figure><p>There is a workaround. We can use an array of structures and align a filed in the structure or the structure itself:</p><pre><strong>struct</strong> AlignedField {<br>  <strong>alignas</strong>(64) <strong>int</strong> field;<br>};<br>AlignedField solution_1[4];</pre><pre><strong>struct</strong> <strong>alignas</strong>(64) AlignedStruct {<br>  <strong>int</strong> field;<br>};<br>AlignedStruct solution_2[4];</pre><p>Both produce the desired result:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*n1YsJnG_Ns3031i7tmay_w.png" /></figure><p>The downside is that every access to the array elements now has to be changed from array[i] to array[i].field.</p><p>Another bad news is that support for the restriction larger than alignof(max_align_t) (16 on my system) is implementation-defined:</p><blockquote>If an object’s alignment is larger than max_align_t, it has extended alignment requirement. A struct whose member has extended alignment is an over-aligned type. It is implementation-defined if over-aligned types are supported.</blockquote><blockquote>— <a href="https://en.cppreference.com/w/c/language/object#Alignment">CPP reference</a></blockquote><p>All modern compilers support over-aligned types. That makes sense since it is a common practice to align data to at least a cache line size (64 or 128 bytes).</p><h3>Specifier alignas vs attribute((aligned)) vs declspec</h3><p>In most cases, they are identical and do the same thing. There is a subtle difference though: alignas() appears in the declaration syntax as one of the type specifiers, so the declarations below are invalid:</p><pre>// Invalid: not a type specifier<br><strong>int</strong> option_3[4] <strong>alignas</strong>(64);</pre><pre>// Invalid: cannot be used in typedef<br><strong>typedef</strong> <strong>alignas</strong>(64) <strong>int</strong> aligned_t;</pre><p>The alignas specifier is neat, so I prefer to use it whenever possible.</p><h3>Takeaways</h3><ol><li>Every complete object type in C++ has its alignment requirement.</li><li><a href="https://en.cppreference.com/w/cpp/language/alignof">Operator </a><a href="https://en.cppreference.com/w/cpp/language/alignof">alignof</a> since C++11 is to query the alignment requirement.</li><li><a href="https://en.cppreference.com/w/cpp/language/alignas">Specifier </a><a href="https://en.cppreference.com/w/cpp/language/alignas">alignas</a> since C++11 is to increase the alignment requirement.</li><li>Alignment requirements apply only to variables and structure fields.</li></ol><p><strong>Source code:</strong> <a href="https://github.com/berestovskyy/applied-cpp">https://github.com/berestovskyy/applied-cpp</a></p><h3>The Answer to “Do I Know This Already?” Quiz</h3><p>None of the answers are correct. See the Analysis part for the explanations.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=32af40a768ee" width="1" height="1" alt=""><hr><p><a href="https://medium.com/applied/applied-c-align-array-elements-32af40a768ee">Applied C++: Align Array Elements</a> was originally published in <a href="https://medium.com/applied">Applied</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Applied C++: Return Multiple Values]]></title>
            <link>https://medium.com/applied/applied-c-return-multiple-values-b142ff8c014a?source=rss----e4ce1e8848ee---4</link>
            <guid isPermaLink="false">https://medium.com/p/b142ff8c014a</guid>
            <category><![CDATA[programming]]></category>
            <category><![CDATA[cplusplus]]></category>
            <category><![CDATA[tutorial]]></category>
            <category><![CDATA[technology]]></category>
            <category><![CDATA[c]]></category>
            <dc:creator><![CDATA[Andriy Berestovskyy]]></dc:creator>
            <pubDate>Wed, 19 Dec 2018 23:33:32 GMT</pubDate>
            <atom:updated>2018-12-25T08:22:18.402Z</atom:updated>
            <content:encoded><![CDATA[<h4>The best way to return multiple values from a C++17 function</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*JIso8iKYKveTpsLBemSXXw.png" /></figure><h3>“Do I Know This Already?” Quiz</h3><p>What is the best way to return multiple values from a C++17 function?</p><ol><li>Using output parameters: <br> <strong>auto</strong> output_1(<strong>int</strong> &amp;i1) { i1 = 11; <strong>return</strong> 12; }</li><li>Using a local structure:<br><strong>auto</strong> struct_2() { <strong>struct</strong> _ { <strong>int</strong> i1, i2; }; <strong>return</strong> _{21, 22}; }</li><li>Using an std::pair:<br><strong>auto</strong> pair_2() { <strong>return</strong> std::make_pair(31, 32); }</li><li>Using an std::tuple:<br><strong>auto</strong> tuple_2() { <strong>return</strong> std::make_tuple(41, 42); }</li></ol><p>The answer is at the very bottom of the article.</p><h3>Use Case: Why to Return Multiple Values?</h3><p>A typical example is the <a href="https://en.cppreference.com/w/cpp/utility/from_chars">std::from_chars(</a>), a C++17 function similar to strtol(). But from_chars() <strong>returns 3 values</strong>: a parsed number, an error code, and a pointer to the first invalid character.</p><p>The function <strong>uses a mix of techniques</strong>: the number is returned as an output parameter, but the error code and the pointer are returned as a structure. Why is so? Let’s analyze…</p><h3>Analysis</h3><h4>Return Multiple Values Using Output Parameters</h4><p>Example code:</p><pre><strong>auto</strong> output_1(<strong>int</strong> &amp;i1) {<br>  i1 = 11;   // Output first parameter<br>  <strong>return</strong> 12; // Return second value<br>}</pre><pre>// Use volatile pointers so compiler could not inline the function<br><strong>auto</strong> (*<strong>volatile</strong> output_1_ptr)(<strong>int</strong> &amp;i1) = output_1;</pre><pre><strong>int</strong> main() {<br>  <strong>int</strong> o1, o2;            // Define local variables<br>  o2 = output_1_ptr(o1); // Output 1st param and assign the 2nd<br>  printf(&quot;output_1 o1 = %d, o2 = %d\n&quot;, o1, o2);<br>}</pre><p>The code compiles to:</p><pre>output_1(int&amp;):<br>  <strong>mov</strong> [<strong>rdi</strong>], 11       # Output first param to the address in <strong>rdi</strong><br>  <strong>mov</strong> <strong>eax</strong>, 12         # Return second value in <strong>eax</strong><br>  <strong>ret</strong></pre><pre>main:                 # Note: simplified<br>  <strong>lea</strong> <strong>rdi</strong>, [<strong>rsp</strong> + 4]  # Load address of the 1st param (on stack)<br>  <strong>call</strong> [output_1_ptr] # Call output_1 using a pointer</pre><pre><strong>  mov</strong> <strong>esi</strong>, [<strong>rsp</strong> + 4]  # Load 1st param from the stack<br><strong>  mov</strong> <strong>ecx</strong>, <strong>eax</strong>        # Load 2nd param from <strong>eax</strong><br>  <strong>call</strong> printf</pre><p><strong>Compiler Explorer: </strong><a href="https://godbolt.org/z/Fan8OH">https://godbolt.org/z/Fan8OH</a></p><p><strong>Pros:</strong></p><ul><li>Classic. Easy to understand.</li><li>Works with any C++ standard, including C (using pointers).</li><li>Supports function overloading.</li></ul><p><strong>Cons:</strong></p><ul><li>Address of the first parameter need to be loaded prior the function call.</li><li>First parameter is passed using stack. Slow :(</li><li>Due to <a href="https://en.wikipedia.org/wiki/X86_calling_conventions#System_V_AMD64_ABI">System V AMD64 ABI</a>, we can pass in registers up to 6 addresses. The sack must be used to pass more than 6 params. Even slower :(</li></ul><p>To illustrate the last cons, here is an example code to output 7 params:</p><pre>// Output more than 6 params<br><strong>int</strong> output_7(<strong>int</strong> &amp;i1, <strong>int</strong> &amp;i2, <strong>int</strong> &amp;i3, <strong>int</strong> &amp;i4,<br>             <strong>int</strong> &amp;i5, <strong>int</strong> &amp;i6, <strong>int</strong> &amp;i7) {<br>  i1 = 11;<br>  i2 = 12;<br>  i3 = 13;<br>  i4 = 14;<br>  i5 = 15;<br>  i6 = 16;<br>  i7 = 17;<br>  <strong>return</strong> 18;<br>}</pre><p>And the disassembly of the output_7():</p><pre>output_7(int&amp;, int&amp;, int&amp;, int&amp;, int&amp;, int&amp;, int&amp;):<br>  <strong>mov</strong> [<strong>rdi</strong>], 11      #<br>  <strong>mov</strong> [<strong>rsi</strong>], 12      # Addresses of the first 6 params get passed<br>  <strong>mov</strong> [<strong>rdx</strong>], 13      # via rdi, rsi, rdx, rcx, r8, and r9<br>  <strong>mov</strong> [<strong>rcx</strong>], 14      # according to System V AMD64 ABI<br>  <strong>mov</strong> [<strong>r8</strong>], 15       # (for Linux, macOS, FreeBSD etc)<br>  <strong>mov</strong> [<strong>r9</strong>], 16       #<br>  <strong>mov</strong> <strong>rax</strong>, [<strong>rsp</strong> + 8] # But address for the 7th is on the stack,<br>  <strong>mov</strong> [<strong>rax</strong>], 17      # which is slow<br>  <strong>mov</strong> <strong>eax</strong>, 18<br>  <strong>ret</strong></pre><p>The 7th address is passed via stack, so we put the address on the stack, then we read it from the stack, then we output the value to that address… A bit too much of memory operations. Slow :(</p><h4>Return Multiple Values Using a Local Structure</h4><p>Example code:</p><pre><strong>auto</strong> struct_2() {<br>  <strong>struct</strong> _ {        // Declare a local structure with 2 integers<br>    <strong>int</strong> i1, i2;<br>  };<br>  <strong>return</strong> _{21, 22}; // Return the local structure<br>}</pre><pre>// Use volatile pointers so compiler could not inline the function<br><strong>auto</strong> (*<strong>volatile</strong> struct_2_ptr)() = struct_2;</pre><pre><strong>int</strong> main() {<br>  <strong>auto</strong> [s1, s2] = struct_2_ptr(); // Structured binding declaration<br>  printf(&quot;struct_2 s1 = %d, s2 = %d\n&quot;, s1, s2);<br>}</pre><p>Disassembly:</p><pre>struct_2():<br>  <strong>movabs</strong> <strong>rax</strong>, 0x1600000015  # Just return 2 integers in <strong>rax</strong><br>  <strong>ret</strong></pre><pre>main:                 # Note: simplified<br>  <strong>call</strong> [struct_2_ptr] # No need to load output param addresses<br>  <strong>mov</strong> <strong>rdx</strong>, <strong>rax        </strong># Just use the values returned in <strong>rax</strong><br>  <strong>shr</strong> <strong>rdx</strong>, 32         # High 32 bits of <strong>rax</strong><br>  <strong>mov</strong> <strong>rcx</strong>, <strong>rax<br></strong>  <strong>mov</strong> <strong>esi</strong>, <strong>ecx</strong>        # Low 32 bits of <strong>rax</strong><br>  <strong>call</strong> printf</pre><p><strong>Compiler Explorer: </strong><a href="https://godbolt.org/z/Q7P4q0">https://godbolt.org/z/Q7P4q0</a></p><p><strong>Pros:</strong></p><ul><li>Works with any C++ standard, including C, though the structure must be declared outside the function scope.</li><li>Returns up to 128 bits in registers, no stack is used. Fast!</li><li>Does not require addresses of the params, which allows compiler to better optimize the code.</li></ul><p><strong>Cons:</strong></p><ul><li>Requires C++17 <a href="https://en.cppreference.com/w/cpp/language/structured_binding">structured binding declaration</a>.</li><li>The function can’t be overloaded, since the return type is not a part of function identification.</li></ul><p>What happens when we try to return more values? According to the <a href="https://en.wikipedia.org/wiki/X86_calling_conventions#System_V_AMD64_ABI">System V AMD64 ABI</a>, values up to 128 bits are stored in RAX and RDX. So up to four 32-bit integers will be returned in registers. One byte more and we have to use the stack.</p><p>Still, we don’t need to load output param addresses, so it is faster than the output parameters method.</p><h4>Return Multiple Values Using an std::pair</h4><p>Example:</p><pre><strong>auto</strong> pair_2() { <strong>return</strong> std::make_pair(31, 32); } // Just one line!</pre><pre>// Use volatile pointers so compiler could not inline the function<br><strong>auto</strong> (*<strong>volatile</strong> pair_2_ptr)() = pair_2;</pre><pre><strong>int</strong> main() {<br>  <strong>auto</strong> [p1, p2] = pair_2_ptr();  // Structured binding declaration<br>  printf(&quot;pair_2 p1 = %d, p2 = %d\n&quot;, p1, p2);<br>}</pre><p>The generated assembly code:</p><pre>pair_2():<br>  <strong>movabs</strong> <strong>rax</strong>, 0x200000001f  # Just return 2 integers in <strong>rax</strong><br>  <strong>ret</strong></pre><pre>main:                 # Note: simplified<br>  <strong>call</strong> [pair_2_ptr]   # Just call the function<br>  <strong>mov</strong> <strong>rdx</strong>, <strong>rax</strong>        # Use the values returned in <strong>rax</strong><br>  <strong>shr</strong> <strong>rdx</strong>, 32<br>  <strong>mov rcx</strong>, <strong>rax<br></strong>  <strong>mov</strong> <strong>esi</strong>, <strong>ecx</strong><br>  <strong>call</strong> printf</pre><p><strong>Compiler Explorer: </strong><a href="https://godbolt.org/z/9iXzSb">https://godbolt.org/z/9iXzSb</a></p><p><strong>Pros:</strong></p><ul><li>Just one line of code!</li><li>No need to declare the local structure.</li><li>Just like with the structures, returns up to 128 buts in registers, no stack is used.</li></ul><p><strong>Cons:</strong></p><ul><li>Pair is just two return values :(</li><li>Just like with the structures, the function can’t be overloaded.</li></ul><h4>Return Multiple Values Using an std::tuple</h4><p>Example:</p><pre><strong>auto</strong> tuple_2() { <strong>return</strong> std::make_tuple(41, 42); } // Just one line!</pre><pre>// Use volatile pointers so compiler could not inline the function<br><strong>auto</strong> (*<strong>volatile</strong> tuple_2_ptr)() = tuple_2;</pre><pre><strong>int</strong> main() {<br>  <strong>auto</strong> [t1, t2] = tuple_2_ptr();  // Structured binding declaration<br>  printf(&quot;tuple_2 t1 = %d, t2 = %d\n&quot;, t1, t2);<br>}</pre><p>The code compiles to:</p><pre>tuple_2():<br>  <strong>movabs</strong> <strong>rax</strong>, 0x290000002a. # Good start, but...<br>  <strong>mov</strong> [<strong>rdi</strong>], <strong>rax</strong>            # Indirect write to a output parameter?<br>  <strong>mov</strong> <strong>rax</strong>, <strong>rdi</strong>              # Return the address of the parameter<br>  <strong>ret</strong></pre><pre>main:                 # Note: simplified<br>  <strong>mov</strong> <strong>rdi</strong>, <strong>rsp</strong>        # Pass stack pointer as a parameter<br>  <strong>call</strong> [tuple_2_ptr]  # Call the function<br>  <strong>mov</strong> <strong>edx</strong>, [<strong>rsp</strong>]      # Get the values from the stack<br>  <strong>mov</strong> <strong>esi</strong>, [<strong>rsp</strong> + 4]<br>  <strong>call</strong> printf</pre><p><strong>Compiler Explorer:</strong> <a href="https://godbolt.org/z/hSVV72">https://godbolt.org/z/hSVV72</a></p><p><strong>Pros:</strong></p><ul><li>The source code is one liner, just like with the std::pair.</li><li>Unlike the std::pair, easy to add more values.</li></ul><p><strong>Cons:</strong></p><ul><li>Unfortunately, the disassembly is a mixed bag. We need to pass an address of the output tuple to the function, one per tuple.</li><li>Even for two integers (64 bits), the return values are always on the stack. Slow :(</li></ul><p>What if we return more values in the tuple? Adding more values does not change the disassembly much: we still pass just one address pointing on the stack, then we put the values under that address (on stack), and then we load them back from the stack to use for printf().</p><p>It’s slower than the pair and the structure, which both return up to 128 bits in the registers. But it’s faster than the output parameters, where we need to pass to the function few addresses, not just one.</p><h3>Takeaways</h3><ol><li>The fastest methods to return multiple parameters in C++17 are by using local structure and std::pair.</li><li>The std::pair must be preferred to return two values as the most convenient and fast method.</li><li>Use output parameters when the function overload is needed. That’s why std::from_chars() uses output parameters and a return structure.</li></ol><p><strong>Full source code: </strong><a href="https://github.com/berestovskyy/applied-cpp">https://github.com/berestovskyy/applied-cpp</a></p><h3>The Answer to “Do I Know This Already?” Quiz</h3><p>The std::pair is the most convenient and fast method to return two values. If we need to return more than two values, local structure (faster) or std::tuple (convenient) must be used instead.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=b142ff8c014a" width="1" height="1" alt=""><hr><p><a href="https://medium.com/applied/applied-c-return-multiple-values-b142ff8c014a">Applied C++: Return Multiple Values</a> was originally published in <a href="https://medium.com/applied">Applied</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
    </channel>
</rss>