<?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[Stories by Andriy Berestovskyy on Medium]]></title>
        <description><![CDATA[Stories by Andriy Berestovskyy on Medium]]></description>
        <link>https://medium.com/@berestovskyy?source=rss-b9b3f6604dfb------2</link>
        <image>
            <url>https://cdn-images-1.medium.com/fit/c/150/150/1*nGukhmyp5rP4T2Ae5UBucQ.jpeg</url>
            <title>Stories by Andriy Berestovskyy on Medium</title>
            <link>https://medium.com/@berestovskyy?source=rss-b9b3f6604dfb------2</link>
        </image>
        <generator>Medium</generator>
        <lastBuildDate>Thu, 19 Nov 2026 16:52:39 GMT</lastBuildDate>
        <atom:link href="https://medium.com/@berestovskyy/feed" rel="self" type="application/rss+xml"/>
        <webMaster><![CDATA[yourfriends@medium.com]]></webMaster>
        <atom:link href="http://medium.superfeedr.com/" rel="hub"/>
        <item>
            <title><![CDATA[Improving Query Execution Latencies]]></title>
            <link>https://medium.com/dfinity/improving-query-latencies-f5bb2bc019dd?source=rss-b9b3f6604dfb------2</link>
            <guid isPermaLink="false">https://medium.com/p/f5bb2bc019dd</guid>
            <category><![CDATA[the-internet-computer]]></category>
            <category><![CDATA[query-optimization]]></category>
            <category><![CDATA[performance-optimization]]></category>
            <category><![CDATA[smart-contracts]]></category>
            <category><![CDATA[query-cache]]></category>
            <dc:creator><![CDATA[Andriy Berestovskyy]]></dc:creator>
            <pubDate>Mon, 05 Feb 2024 16:21:59 GMT</pubDate>
            <atom:updated>2024-02-05T16:27:27.949Z</atom:updated>
            <content:encoded><![CDATA[<h4>The improved in-replica caching reduces query execution latencies on the Internet Computer.</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*96cRZ9e8vWmaKETzALTM_g.png" /></figure><h3>Background</h3><p>The Internet Computer can host a full dapp — frontend, backend, and data. Users can deploy their dapp as a canister (smart contract).</p><p>Just like HTTP POST and GET methods, the Internet Computer Protocol supports two types of messages: updates and queries. <strong>An update message</strong> is executed on all subnet nodes and persists canister state changes. <strong>A query message</strong> discards state changes and typically runs on a single node.</p><p>Web caching is a well-known technique to accelerate requests and reduces peak server load. However, <strong>the common caching challenge is data consistency</strong>, and the decentralized Web3 world raises the bar even higher.</p><p>Keep on reading to find out how <strong>the Internet Computer implements in-replica query caching</strong>.</p><h3>Query Cache Properties</h3><p>The Internet Computer implements an in-replica query cache with the following features:</p><ol><li><strong>Transparency:</strong> the cache is completely transparent, there is no need to worry about cache validity, max age etc.</li><li><strong>LRU cache replacement policy:</strong> the query cache discards least recently used (LRU) entries first. On a cache hit into a valid entry, that entry becomes the most recently used. Entries that remain unused for some time become less recently used and are eventually evicted from the cache.</li><li><strong>Cache validity:</strong> the implementation ensures that, for a given replicated state, any valid cache entry contains the most up-to-date result of query execution.</li></ol><p><strong>Cache validity is the main challenge</strong> of the query cache implementation, so let’s delve further!</p><h3>Cache Invalidation Factors</h3><p>Cache validity means that a cached result matches the result of actual query execution.</p><p>The query cache is a key-value map, where each key is a tuple of (source, receiver, method, payload) and value is a result of the query execution. A cache hit happens when all 4 key components match.</p><p>But even if there is a hit, is the cached result still up-to-date? The result might become stale after:</p><ol><li><strong>State changes:</strong> update calls or canister upgrades alter the state, so the cached result is no longer up-to-date.</li><li><strong>Cycle balance and system time:</strong> the canister is periodically charged for the CPU and memory resources, execution, ingress messages, etc. The query might take a different execution path based on a specific balance level or at a particular point in time. Therefore, if the canister balance or system time changes, the cache entry becomes stale.</li></ol><pre>#[query]<br>fn event_started() -&gt; Option&lt;String&gt; {<br>  if ic_cdk::api::time() &gt; EVENT_START_TIME {<br>    Some(&quot;The new event has started!&quot;)<br>  } else {<br>    None<br>  }<br>}</pre><p>Given that many changing factors and the live data freshness property, the data might become stale too quickly to achieve high query cache efficiency. In fact, the initial implementation of the query cache released in May 2023 was just that.</p><p>The cache hit ratio of the initial version was about 10%. Most of the time, <strong>the cache was invalidated due to cycle balance and system time changes</strong>. Is there room for improvement?</p><h3>Improving Cache Invalidations</h3><p>One way to improve cache invalidations is to determine whether the query execution depends on the cycle balance and system time:</p><ol><li><strong>Query execution does not modify the blockchain state:</strong> this Internet Computer property enables executing queries in any order and cache the result of their execution.</li><li><strong>Query execution is deterministic:</strong> the result of the execution is always the same, provided the same state, cycles balance, and system time. This property is also crucial for query caching.</li><li><strong>Tracking query execution:</strong> the system can monitor if the query attempted to read the current cycle balance or system time.</li><li><strong>Ignoring cache invalidations:</strong> since most queries never read the balance and time, their cached result remains valid even when the balance or time changes.</li></ol><h3>Results</h3><p>With the query execution tracking, the cache hit ratio has increased from around 10% to 50%:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*REM5h_SfRnZE7Q_zpOs9RQ.png" /></figure><p>Also, the median query latency is also improved from around 1.2ms down to 0.4ms. When the cache hit ratio reaches above 50%, the median goes down to just 0.1ms:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*ASDILolcHawQlhA9fDGcWA.png" /></figure><h3>Takeaways: How To Improve Query Latencies?</h3><p>Developers can improve cache efficiency of their queries even more by following these tips.</p><p>1. Avoid unnecessary calls to the time() and balance() System APIs:</p><pre>#[query]<br>fn status() -&gt; (String, u64) {<br>  (<br>    STATUS.clone(),<br>    ic_cdk::api::time() // ← this is BAD for caching!<br>  )<br>}</pre><p>2. Try to move the System API calls to places where they are actually used:</p><pre>#[query]<br>fn ready_time() -&gt; Option&lt;u64&gt; {<br>  let now = ic_cdk::api::time(); // ← this is BAD for caching!<br>  if STATUS.is_ready() {<br>    // The `time()` should be called here, when the STATUS is ready.<br>    Some(now)<br>  } else {<br>    None<br>  }<br>}</pre><p>The new functionality is transparent and available on all the subnets and local development environments.</p><h3>References</h3><ol><li>Source code of the Internet Computer query cache implementation: <a href="https://github.com/dfinity/ic/blob/master/rs/execution_environment/src/query_handler/query_cache.rs">github.com/dfinity/ic/</a></li><li>The Internet Computer Interface Specification: <a href="https://internetcomputer.org/docs/current/references/ic-interface-spec#synchronicity-across-nodes">Synchronicity across nodes</a></li></ol><p>If you have questions/suggestions or just want to meet Internet Computer developers and DFINITY engineers, join the <a href="https://forum.dfinity.org/">forum.dfinity.org</a>.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=f5bb2bc019dd" width="1" height="1" alt=""><hr><p><a href="https://medium.com/dfinity/improving-query-latencies-f5bb2bc019dd">Improving Query Execution Latencies</a> was originally published in <a href="https://medium.com/dfinity">The Internet Computer Review</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Async-Friendly Performance Counter]]></title>
            <link>https://medium.com/dfinity/async-friendly-performance-counter-dcf928226c2b?source=rss-b9b3f6604dfb------2</link>
            <guid isPermaLink="false">https://medium.com/p/dcf928226c2b</guid>
            <category><![CDATA[motoko]]></category>
            <category><![CDATA[the-internet-computer]]></category>
            <category><![CDATA[rust]]></category>
            <category><![CDATA[performance-optimization]]></category>
            <category><![CDATA[smart-contracts]]></category>
            <dc:creator><![CDATA[Andriy Berestovskyy]]></dc:creator>
            <pubDate>Thu, 07 Dec 2023 10:52:06 GMT</pubDate>
            <atom:updated>2023-12-07T10:52:06.138Z</atom:updated>
            <content:encoded><![CDATA[<h4>Introducing a new performance counter on the Internet Computer to easily optimize async canister code</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*BHTLw7s3D053axSlmhP49g.png" /></figure><h3>Background</h3><p>The Internet Computer can host a full dapp — frontend, backend and data. Users can deploy their dapp as a canister (smart contract) on the Internet Computer. Each canister can store up to 96 GB of data and execute up to 20 Billion WebAssembly instructions per transaction.</p><p>Unlike other blockchains, the Internet Computer offers developers <a href="https://internetcomputer.org/docs/current/developer-docs/production/resource-limits">enormous amounts of resources</a>. This poses a real challenge for canister developers: writing efficient canister code. The more efficient a canister is, the less cycles it pays.</p><p>Performance counter is the way for a canister (smart contract) to track the amount of work done. This information could be used as the main metric to optimize the code.</p><p>The Internet Computer provides this System API call:</p><pre>ic0.performance_counter : (counter_type : i32) -&gt; i64</pre><p>The type argument specifies which performance counter to return. For a long time only type 0 counter was supported on the Internet Computer — the number of WebAssembly instructions the canister has executed since the beginning of the current message execution.</p><p>This type 0 counter works well, and many developers use it daily. But the counter is valid only for the current message, and it resets after each await point.</p><p>How could it be improved?</p><p>We are introducing a new call context performance counter (type 1) to track the executed WebAssembly instructions across await points.</p><h3>Comparing The Performance Counters</h3><p>Consider this example function:</p><pre>#[query(composite = true)]<br>async fn example() -&gt; (u64, u64) {<br>    do_some_work();<br>❶   call(id(), &quot;nested_call&quot;, ())<br>❷       .await;<br>    do_some_work();<br>❶   call(id(), &quot;nested_call&quot;, ()) <br>❷       .await; <br>    do_some_work();<br>❸   (performance_counter(0), performance_counter(1))<br>}</pre><p>The function ❶ makes two nested calls, ❷ awaits them, and finally ❸ replies to the original call.</p><p>From the developer’s point of view, it’s just one function. From the user’s perspective, it’s just one call. But in fact, under the hood, there are three message executions:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/720/1*sQcxeUZo_6Qs4KzL85JKPw.png" /></figure><ol><li>The original call is executed up until the first await point.</li><li>Then the reply to that call triggers the second execution.</li><li>At the end, yet another reply triggers the final part, which replies to the original call with two performance counters.</li></ol><p>There is a call context to track the original call. The Internet Computer creates it for each call and keeps it around until the call is either replied or rejected.</p><p>The performance counter type 0 just follows those three message executions. It starts from 0 and goes up to some value i. After the first await, it resets and goes up to j, and then up to k.</p><p>On the other hand, the new type 1 counter lives in the call context, so it monotonically increases until the original call is replied. In this example, it starts from 0 and goes to i, i+j and then up to i+j+k.</p><p>The results are similar. Can just the old type 0 counter do the job?</p><p>To get the same i+j+k result with the counter type 0, the counter should be saved before each reset:</p><pre>#[query(composite = true)]<br>async fn example() -&gt; u64 {<br>    do_some_work();<br>    let c = call(id(), &quot;nested_call&quot;, ());<br>❶   let i = performance_counter(0);<br>    c.await;<br>    do_some_work();<br>    let c = call(id(), &quot;nested_call&quot;, ());<br>❷   let j = performance_counter(0);<br>    c.await;<br>    do_some_work();<br>❸   let k = performance_counter(0);<br>    i + j + k<br>}</pre><p>Even this simple example becomes spaghetti, as every single await point must be changed. Imagine a bit more complicated code, with many nested functions and library calls… It’s a challenge to properly instrument production asynchronous code!</p><p>On the other hand, the new call context counter still must be explicitly collected at the end of the function:</p><pre>#[query(composite = true)]<br>async fn example() -&gt; u64 {<br>    do_some_work();<br>    call(id(), &quot;nested_call&quot;, ()).await;<br>    do_some_work();<br>    call(id(), &quot;nested_call&quot;, ()).await; <br>    do_some_work();<br>❶   performance_counter(1) // i + j + k<br>}</pre><p>But in this case there is no need to instrument every single await point in the nested functions or libraries. There is just one place, right before the counter is returned. It’s a huge step forward to fully automate the code instrumentation and profiling in the future.</p><h3>Using Performance Counters</h3><p>To quickly run the performance counters example (assuming the Internet Computer SDK is <a href="https://internetcomputer.org/docs/current/developer-docs/setup/install/">already installed</a>):</p><pre>$ git clone git@github.com:dfinity/examples.git<br>$ cd examples/rust/performance_counters<br>$ cargo update<br>$ dfx start --clean --background<br>$ dfx deploy<br>$ dfx canister call performance_counters example<br>(7_012_128 : nat64, 21_568_690 : nat64)</pre><p>The example function returns two values: the old counter (type 0) and the new one (type 1). As the new call context counter includes all three message executions, it reports three times more WebAssembly instructions: 21 Millions vs just 7 Millions.</p><p>Please check the <a href="https://github.com/dfinity/examples/tree/master/rust/performance_counters">Performance Counters Example</a> on GitHub for detailed instructions.</p><p>The new async-friendly performance counter is available everywhere:</p><pre>Rust:       ic_cdk::api::performance_counter(1);<br>Motoko:     import IC &quot;mo:base/ExperimentalInternetComputer&quot;;<br>            IC.performanceCounter(1);<br>TypeScript: import ic from &#39;azle&#39;;<br>            ic.performanceCounter(1);<br>Python:     from kybra import ic<br>            ic.performance_counter(1)</pre><h3>References</h3><ol><li>Backend Developers Guide: <a href="https://internetcomputer.org/docs/current/developer-docs/backend/rust/optimizing">Optimizing Rust Canisters</a></li><li>Motoko Developers Guide: <a href="https://internetcomputer.org/docs/current/developer-docs/backend/motoko/optimizing">Optimizing Canisters</a></li></ol><p>If you have questions/suggestions or just want to meet Internet Computer developers and DFINITY engineers, join the <a href="https://forum.dfinity.org/t/introducing-performance-counter-on-the-internet-computer/14027">forum.dfinity.org</a>.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=dcf928226c2b" width="1" height="1" alt=""><hr><p><a href="https://medium.com/dfinity/async-friendly-performance-counter-dcf928226c2b">Async-Friendly Performance Counter</a> was originally published in <a href="https://medium.com/dfinity">The Internet Computer Review</a> on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>]]></content:encoded>
        </item>
        <item>
            <title><![CDATA[Internet Computer: Canister Timers]]></title>
            <link>https://medium.com/dfinity/internet-computer-canister-timers-21cd3201b831?source=rss-b9b3f6604dfb------2</link>
            <guid isPermaLink="false">https://medium.com/p/21cd3201b831</guid>
            <category><![CDATA[the-internet-computer]]></category>
            <category><![CDATA[rust]]></category>
            <category><![CDATA[smart-contracts]]></category>
            <category><![CDATA[motoko]]></category>
            <dc:creator><![CDATA[Andriy Berestovskyy]]></dc:creator>
            <pubDate>Wed, 29 Mar 2023 15:49:07 GMT</pubDate>
            <atom:updated>2023-03-29T16:04:02.280Z</atom:updated>
            <content:encoded><![CDATA[<h4>Introducing Canister Timers — a better way to schedule one-shot and periodic tasks on the Internet Computer.</h4><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*jfHk7FhgtIXplDNWi1a7qg.jpeg" /></figure><p>Unlike other blockchains, the Internet Computer can automatically execute canister smart contracts after a <strong>specified delay or periodically</strong>. The <strong>Canister Timers</strong> functionality has been available for early adopters since December. Just in three months timers made it into <a href="https://github.com/search?p=2&amp;q=ic_cdk_timers&amp;type=Code">many internal and community</a> projects: OpenChat, Bitcoin integration, ckBTC, Azle and many many more…</p><p>While it’s still early days for the timers, the usage has been doubled for the past month:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/1024/1*Z97mGZPWXFCgVkCD1pfvTw.png" /></figure><h3>Showcases</h3><p>Below are a few inspiring patterns where the timers might get handy.</p><h4>Memoization</h4><p><strong>Store the results of expensive operations and return the cached result.<br></strong>For example, a canister can do an expensive <a href="https://internetcomputer.org/https-outcalls">HTTP outcall</a> to CoinBase every 15 minutes to <a href="https://docs.cloud.coinbase.com/sign-in-with-coinbase/docs/api-exchange-rates">update exchange rates</a>, using the cached rates in between the updates.</p><p>This pattern is probably the most used one. For example, it’s in the production <a href="https://github.com/dfinity/ic/blob/9a1f70d6e1b03ef27e86f8094ee48b83846e482d/rs/bitcoin/ckbtc/minter/src/lib.rs#L765-L771">Bitcoin Integration ckBTC Minter</a> and <a href="https://github.com/dfinity/ic/blob/9a1f70d6e1b03ef27e86f8094ee48b83846e482d/rs/rosetta-api/tvl/src/lib.rs#L64-L67">Rosetta API Total Value Locked</a> canisters.</p><h4>Limited Time Events</h4><p><strong>Schedule a one-shot task at the specific date and time.<br></strong>For example, during the <a href="https://internetcomputer.org/sns">SNS launch events</a>, the governance token sale starts and ends at specific point in time.</p><h4>Very Long Computations</h4><p><strong>Split a very long computation into multiple chunks.<br></strong>With the <a href="https://internetcomputer.org/how-it-works">Deterministic Time Slicing</a> feature, the Internet Computer can execute billions of instructions without blocking the subnet progress. But even billions have their limits, so for even longer executions, the timers might be handy.</p><p>For example, consider a canister to generate many assets:</p><figure><img alt="" src="https://cdn-images-1.medium.com/max/754/1*6Xy6gmN2ySl59ANup6W3eQ.png" /></figure><ol><li><strong>Begin:</strong> User starts a process by calling an asset generator canister. The canister creates zero delay <strong>Canister Timer</strong> to generate the first asset, and then immediately replies to the user: “0% done so far”.</li><li><strong>Separation of execution contexts:</strong> The actual asset generation is happening in the timer handler. Note, any traps during the generation won’t be affecting the progress reports.</li><li><strong>Status report:</strong> Once the first asset is generated, the canister schedules the next one using zero delay <strong>Canister Timer</strong> again. The user tracks the progress time to time, and the canister is immediately reports “n% done so far”.</li><li><strong>End:</strong> The process repeats until all the assets are generated.</li></ol><h3>The Timers Story</h3><p>The canister timers is not all that new functionality. From the genesis of the Internet Computer there were heartbeats — periodic canister invocations with intervals close to the blockchain finalization rate (1s).</p><p>The heartbeats worked fine, and continue to work just fine. There are many production solutions built on that. But because the heartbeat interval is quite short and there is no way to adjust the interval or pause, the heartbeats are just too expensive for many use cases.</p><p>DFINITY engineers together with the community came up with the following solution:</p><ol><li><strong>Keep the current </strong><strong>heartbeat functionality as is</strong> for backward compatibility. And then, based on the heartbeat experience and real use cases, implement a new functionality — <strong>Canister Timers</strong>.</li><li><strong>Minimalistic protocol level changes.</strong> The Internet Computer Protocol supports single on-shot timer per canister via ic0.global_timer_set() system API call and canister_global_timer handler (see the <a href="https://internetcomputer.org/docs/current/references/ic-interface-spec">Internet Computer Interface Specification</a>).</li><li><strong>Convenient CDK timers library.</strong> The library wraps the minimalistic protocol implementation, implementing multiple and periodic timers. Canister developers can enjoy the familiar timers functionality using the <a href="https://crates.io/crates/ic-cdk-timers">CDK timers library for Rust</a> or <a href="https://internetcomputer.org/docs/current/motoko/main/timers">Motoko</a>.</li></ol><p>This approach facilitates the protocol changes and makes it easy to improve the functionality in the CDK library without breaking the existing canisters.</p><p>The three main differences between the new timers and the old heartbeats:</p><ol><li><strong>Costs.</strong> Heartbeats are periodic by design. The only way to disable the heartbeats is to upgrade the canister to a version which does not export the canister_heartbeat method. Timers solve this by allowing to schedule a one-shot tasks, and hence reduce the overall costs.</li><li><strong>Flexibility.</strong> The heartbeat interval is implementation-defined, and there is no way to adjust it. While timers still does not provide strict scheduling guarantees, yet the minimum delay specified by the canister developer is guaranteed to be respected.</li><li><strong>Composability.</strong> The heartbeats are global, so it’s impossible to use different libraries with heartbeats in a single project. Timers solve this issue by providing the CDK library supporting multiple timers.</li></ol><h3>Using Timers in Rust</h3><p>To use the new functionality in Rust project, just add the library:</p><pre>cargo add ic-cdk-timers</pre><p>And it’s ready to use:</p><pre>use std::time::Duration;<br><br>const N: Duration = Duration::from_secs(5);<br><br>fn ring() {<br>    ic_cdk::println!(&quot;Rust Timer Ring!&quot;);<br>}<br><br>#[ic_cdk::init]<br>fn init() {<br>    let _timer_id = ic_cdk_timers::set_timer_interval(N, ring);<br>}<br><br>#[ic_cdk::post_upgrade]<br>fn post_upgrade() {<br>    init();<br>}</pre><p>For more details, see the Rust Backend Tutorials: <a href="https://internetcomputer.org/docs/current/developer-docs/backend/rust/timers">Using Timers</a></p><h3>Using Timers in Motoko</h3><p><a href="https://internetcomputer.org/how-it-works/motoko">Motoko</a> is a programming language to seamlessly support the programming model of the Internet Computer and makes it easier to take advantage of the unique features of the blockchain.</p><p>Timers in Motoko are also a piece of cake:</p><pre>import { print } = &quot;mo:base/Debug&quot;;<br>import { recurringTimer } = &quot;mo:base/Timer&quot;;<br><br>actor Alarm {<br><br>  let N = 5;<br><br>  private func ring() : async () {<br>    print(&quot;Motoko Timer Ring!&quot;);<br>  };<br><br>  ignore recurringTimer(#seconds N, ring);<br>};</pre><p>For more details, see Motoko Developer Guide: <a href="https://internetcomputer.org/docs/current/motoko/main/timers">Timers</a></p><h3>References</h3><ol><li>Backend Developer Guide: <a href="https://internetcomputer.org/docs/current/developer-docs/backend/periodic-tasks">Periodic Tasks and Timers</a></li><li>Rust Backend tutorials: <a href="https://internetcomputer.org/docs/current/developer-docs/backend/rust/timers">Using Timers</a></li><li>Rust Examples: <a href="https://github.com/dfinity/examples/tree/master/rust/periodic_tasks">Periodic Tasks and Timers</a><br>(compares the costs of timers and heartbeats)</li><li>Motoko Developer Guide: <a href="https://internetcomputer.org/docs/current/motoko/main/timers">Timers</a></li></ol><p>If you have questions/suggestions or just want to meet Internet Computer developers and DFINITY engineers, join the <a href="https://forum.dfinity.org/">forum.dfinity.org</a>.</p><img src="https://medium.com/_/stat?event=post.clientViewed&referrerSource=full_rss&postId=21cd3201b831" width="1" height="1" alt=""><hr><p><a href="https://medium.com/dfinity/internet-computer-canister-timers-21cd3201b831">Internet Computer: Canister Timers</a> was originally published in <a href="https://medium.com/dfinity">The Internet Computer Review</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++: Memory Latency]]></title>
            <link>https://medium.com/applied/applied-c-memory-latency-d05a42fe354e?source=rss-b9b3f6604dfb------2</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-b9b3f6604dfb------2</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-b9b3f6604dfb------2</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>