298 lines
18 KiB
HTML
298 lines
18 KiB
HTML
<!DOCTYPE HTML>
|
|
<html lang="en" class="light sidebar-visible" dir="ltr">
|
|
<head>
|
|
<!-- Book generated using mdBook -->
|
|
<meta charset="UTF-8">
|
|
<title>Caching - Rust Compiler Development Guide</title>
|
|
|
|
|
|
<!-- Custom HTML head -->
|
|
|
|
<meta name="description" content="A guide to developing the Rust compiler (rustc)">
|
|
<meta name="viewport" content="width=device-width, initial-scale=1">
|
|
<meta name="theme-color" content="#ffffff">
|
|
|
|
<link rel="icon" href="../favicon.svg">
|
|
<link rel="shortcut icon" href="../favicon.png">
|
|
<link rel="stylesheet" href="../css/variables.css">
|
|
<link rel="stylesheet" href="../css/general.css">
|
|
<link rel="stylesheet" href="../css/chrome.css">
|
|
<link rel="stylesheet" href="../css/print.css" media="print">
|
|
|
|
<!-- Fonts -->
|
|
<link rel="stylesheet" href="../FontAwesome/css/font-awesome.css">
|
|
<link rel="stylesheet" href="../fonts/fonts.css">
|
|
|
|
<!-- Highlight.js Stylesheets -->
|
|
<link rel="stylesheet" id="highlight-css" href="../highlight.css">
|
|
<link rel="stylesheet" id="tomorrow-night-css" href="../tomorrow-night.css">
|
|
<link rel="stylesheet" id="ayu-highlight-css" href="../ayu-highlight.css">
|
|
|
|
<!-- Custom theme stylesheets -->
|
|
|
|
|
|
<!-- Provide site root and default themes to javascript -->
|
|
<script>
|
|
const path_to_root = "../";
|
|
const default_light_theme = "light";
|
|
const default_dark_theme = "navy";
|
|
</script>
|
|
<!-- Start loading toc.js asap -->
|
|
<script src="../toc.js"></script>
|
|
</head>
|
|
<body>
|
|
<div id="body-container">
|
|
<!-- Work around some values being stored in localStorage wrapped in quotes -->
|
|
<script>
|
|
try {
|
|
let theme = localStorage.getItem('mdbook-theme');
|
|
let sidebar = localStorage.getItem('mdbook-sidebar');
|
|
|
|
if (theme.startsWith('"') && theme.endsWith('"')) {
|
|
localStorage.setItem('mdbook-theme', theme.slice(1, theme.length - 1));
|
|
}
|
|
|
|
if (sidebar.startsWith('"') && sidebar.endsWith('"')) {
|
|
localStorage.setItem('mdbook-sidebar', sidebar.slice(1, sidebar.length - 1));
|
|
}
|
|
} catch (e) { }
|
|
</script>
|
|
|
|
<!-- Set the theme before any content is loaded, prevents flash -->
|
|
<script>
|
|
const default_theme = window.matchMedia("(prefers-color-scheme: dark)").matches ? default_dark_theme : default_light_theme;
|
|
let theme;
|
|
try { theme = localStorage.getItem('mdbook-theme'); } catch(e) { }
|
|
if (theme === null || theme === undefined) { theme = default_theme; }
|
|
const html = document.documentElement;
|
|
html.classList.remove('light')
|
|
html.classList.add(theme);
|
|
html.classList.add("js");
|
|
</script>
|
|
|
|
<input type="checkbox" id="sidebar-toggle-anchor" class="hidden">
|
|
|
|
<!-- Hide / unhide sidebar before it is displayed -->
|
|
<script>
|
|
let sidebar = null;
|
|
const sidebar_toggle = document.getElementById("sidebar-toggle-anchor");
|
|
if (document.body.clientWidth >= 1080) {
|
|
try { sidebar = localStorage.getItem('mdbook-sidebar'); } catch(e) { }
|
|
sidebar = sidebar || 'visible';
|
|
} else {
|
|
sidebar = 'hidden';
|
|
}
|
|
sidebar_toggle.checked = sidebar === 'visible';
|
|
html.classList.remove('sidebar-visible');
|
|
html.classList.add("sidebar-" + sidebar);
|
|
</script>
|
|
|
|
<nav id="sidebar" class="sidebar" aria-label="Table of contents">
|
|
<!-- populated by js -->
|
|
<mdbook-sidebar-scrollbox class="sidebar-scrollbox"></mdbook-sidebar-scrollbox>
|
|
<noscript>
|
|
<iframe class="sidebar-iframe-outer" src="../toc.html"></iframe>
|
|
</noscript>
|
|
<div id="sidebar-resize-handle" class="sidebar-resize-handle">
|
|
<div class="sidebar-resize-indicator"></div>
|
|
</div>
|
|
</nav>
|
|
|
|
<div id="page-wrapper" class="page-wrapper">
|
|
|
|
<div class="page">
|
|
<div id="menu-bar-hover-placeholder"></div>
|
|
<div id="menu-bar" class="menu-bar sticky">
|
|
<div class="left-buttons">
|
|
<label id="sidebar-toggle" class="icon-button" for="sidebar-toggle-anchor" title="Toggle Table of Contents" aria-label="Toggle Table of Contents" aria-controls="sidebar">
|
|
<i class="fa fa-bars"></i>
|
|
</label>
|
|
<button id="theme-toggle" class="icon-button" type="button" title="Change theme" aria-label="Change theme" aria-haspopup="true" aria-expanded="false" aria-controls="theme-list">
|
|
<i class="fa fa-paint-brush"></i>
|
|
</button>
|
|
<ul id="theme-list" class="theme-popup" aria-label="Themes" role="menu">
|
|
<li role="none"><button role="menuitem" class="theme" id="default_theme">Auto</button></li>
|
|
<li role="none"><button role="menuitem" class="theme" id="light">Light</button></li>
|
|
<li role="none"><button role="menuitem" class="theme" id="rust">Rust</button></li>
|
|
<li role="none"><button role="menuitem" class="theme" id="coal">Coal</button></li>
|
|
<li role="none"><button role="menuitem" class="theme" id="navy">Navy</button></li>
|
|
<li role="none"><button role="menuitem" class="theme" id="ayu">Ayu</button></li>
|
|
</ul>
|
|
<button id="search-toggle" class="icon-button" type="button" title="Search. (Shortkey: s)" aria-label="Toggle Searchbar" aria-expanded="false" aria-keyshortcuts="S" aria-controls="searchbar">
|
|
<i class="fa fa-search"></i>
|
|
</button>
|
|
</div>
|
|
|
|
<h1 class="menu-title">Rust Compiler Development Guide</h1>
|
|
|
|
<div class="right-buttons">
|
|
<a href="../print.html" title="Print this book" aria-label="Print this book">
|
|
<i id="print-button" class="fa fa-print"></i>
|
|
</a>
|
|
<a href="https://github.com/rust-lang/rustc-dev-guide" title="Git repository" aria-label="Git repository">
|
|
<i id="git-repository-button" class="fa fa-github"></i>
|
|
</a>
|
|
<a href="https://github.com/rust-lang/rustc-dev-guide/edit/master/src/solve/caching.md" title="Suggest an edit" aria-label="Suggest an edit">
|
|
<i id="git-edit-button" class="fa fa-edit"></i>
|
|
</a>
|
|
|
|
</div>
|
|
</div>
|
|
|
|
<div id="search-wrapper" class="hidden">
|
|
<form id="searchbar-outer" class="searchbar-outer">
|
|
<input type="search" id="searchbar" name="searchbar" placeholder="Search this book ..." aria-controls="searchresults-outer" aria-describedby="searchresults-header">
|
|
</form>
|
|
<div id="searchresults-outer" class="searchresults-outer hidden">
|
|
<div id="searchresults-header" class="searchresults-header"></div>
|
|
<ul id="searchresults">
|
|
</ul>
|
|
</div>
|
|
</div>
|
|
|
|
<!-- Apply ARIA attributes after the sidebar and the sidebar toggle button are added to the DOM -->
|
|
<script>
|
|
document.getElementById('sidebar-toggle').setAttribute('aria-expanded', sidebar === 'visible');
|
|
document.getElementById('sidebar').setAttribute('aria-hidden', sidebar !== 'visible');
|
|
Array.from(document.querySelectorAll('#sidebar a')).forEach(function(link) {
|
|
link.setAttribute('tabIndex', sidebar === 'visible' ? 0 : -1);
|
|
});
|
|
</script>
|
|
|
|
<div id="content" class="content">
|
|
<main>
|
|
<h1 id="caching-in-the-new-trait-solver"><a class="header" href="#caching-in-the-new-trait-solver">Caching in the new trait solver</a></h1>
|
|
<p>Caching results of the trait solver is necessary for performance.
|
|
We have to make sure that it is sound. Caching is handled by the
|
|
<a href="https://github.com/rust-lang/rust/blob/7606c13961ddc1174b70638e934df0439b7dc515/compiler/rustc_trait_selection/src/solve/search_graph.rs#L102-L117"><code>SearchGraph</code></a></p>
|
|
<h2 id="the-global-cache"><a class="header" href="#the-global-cache">The global cache</a></h2>
|
|
<p>At its core, the cache is fairly straightforward. When evaluating a goal, we
|
|
check whether it's in the global cache. If so, we reuse that entry. If not, we
|
|
compute the goal and then store its result in the cache.</p>
|
|
<p>To handle incremental compilation the computation of a goal happens inside of
|
|
<a href="https://github.com/rust-lang/rust/blob/7606c13961ddc1174b70638e934df0439b7dc515/compiler/rustc_trait_selection/src/solve/search_graph.rs#L391"><code>DepGraph::with_anon_task</code></a> which creates a new <code>DepNode</code> which depends on all queries
|
|
used inside of this computation. When accessing the global cache we then read this
|
|
<code>DepNode</code>, manually adding a dependency edge to all the queries used: <a href="https://github.com/rust-lang/rust/blob/7606c13961ddc1174b70638e934df0439b7dc515/compiler/rustc_middle/src/traits/solve/cache.rs#L78">source</a>.</p>
|
|
<h3 id="dealing-with-overflow"><a class="header" href="#dealing-with-overflow">Dealing with overflow</a></h3>
|
|
<p>Hitting the recursion limit is not fatal in the new trait solver but instead simply
|
|
causes it to return ambiguity: <a href="https://github.com/rust-lang/rust/blob/7606c13961ddc1174b70638e934df0439b7dc515/compiler/rustc_trait_selection/src/solve/search_graph.rs#L276">source</a>. Whether we hit the recursion limit
|
|
can therefore change the result without resulting in a compilation failure. This
|
|
means we must consider the remaining available depth when accessing a cache result.</p>
|
|
<p>We do this by storing more information in the cache entry. For goals whose evaluation
|
|
did not reach the recursion limit, we simply store its reached depth: <a href="https://github.com/rust-lang/rust/blob/7606c13961ddc1174b70638e934df0439b7dc515/compiler/rustc_middle/src/traits/solve/cache.rs#L102">source</a>.
|
|
These results can freely be used as long as the current <code>available_depth</code> is higher than
|
|
its <code>reached_depth</code>: <a href="https://github.com/rust-lang/rust/blob/7606c13961ddc1174b70638e934df0439b7dc515/compiler/rustc_middle/src/traits/solve/cache.rs#L76-L86">source</a>. We then update the reached depth of the
|
|
current goal to make sure that whether we've used the global cache entry is not
|
|
observable: <a href="https://github.com/rust-lang/rust/blob/7606c13961ddc1174b70638e934df0439b7dc515/compiler/rustc_trait_selection/src/solve/search_graph.rs#L308">source</a>.</p>
|
|
<p>For goals which reach the recursion limit we currently only use the cached result if the
|
|
available depth <em>exactly matches</em> the depth of the entry. The cache entry for each goal
|
|
therefore contains a separate result for each remaining depth: <a href="https://github.com/rust-lang/rust/blob/7606c13961ddc1174b70638e934df0439b7dc515/compiler/rustc_middle/src/traits/solve/cache.rs#L124">source</a>.<sup class="footnote-reference" id="fr-1-1"><a href="#footnote-1">1</a></sup></p>
|
|
<h2 id="handling-cycles"><a class="header" href="#handling-cycles">Handling cycles</a></h2>
|
|
<p>The trait solver has to support cycles. These cycles are either inductive or coinductive,
|
|
depending on the participating goals. See the <a href="./coinduction.html">chapter on coinduction</a> for more details.
|
|
We distinguish between the cycle heads and the cycle root: a stack entry is a
|
|
cycle head if it recursively accessed. The <em>root</em> is the deepest goal on the stack which
|
|
is involved in any cycle. Given the following dependency tree, <code>A</code> and <code>B</code> are both cycle
|
|
heads, while only <code>A</code> is a root.</p>
|
|
<pre class="mermaid">graph TB
|
|
A --> B
|
|
B --> C
|
|
C --> B
|
|
C --> A
|
|
</pre>
|
|
<p>The result of cycle participants depends on the result of goals still on the stack.
|
|
However, we are currently computing that result, so its result is still unknown. This is
|
|
handled by evaluating cycle heads until we reach a fixpoint. In the first iteration, we
|
|
return either success or overflow with no constraints, depending on whether the cycle is
|
|
coinductive: <a href="https://github.com/rust-lang/rust/blob/7606c13961ddc1174b70638e934df0439b7dc515/compiler/rustc_trait_selection/src/solve/search_graph.rs#L366-L370">source</a>. After evaluating the head of a cycle, we
|
|
check whether its <a href="https://github.com/rust-lang/rust/blob/7606c13961ddc1174b70638e934df0439b7dc515/compiler/rustc_trait_selection/src/solve/search_graph.rs#L57"><code>provisional_result</code></a> is equal to the result of this iteration. If so,
|
|
we've finished evaluating this cycle and return its result. If not, we update the provisional
|
|
result and reevaluate the goal: <a href="https://github.com/rust-lang/rust/blob/7606c13961ddc1174b70638e934df0439b7dc515/compiler/rustc_trait_selection/src/solve/search_graph.rs#L425-L446">source</a>. After the first iteration it does not
|
|
matter whether cycles are coinductive or inductive. We always use the provisional result.</p>
|
|
<h3 id="only-caching-cycle-roots"><a class="header" href="#only-caching-cycle-roots">Only caching cycle roots</a></h3>
|
|
<p>We cannot move the result of any cycle participant to the global cache until we've
|
|
finished evaluating the cycle root. However, even after we've completely evaluated the
|
|
cycle, we are still forced to discard the result of all participants apart from the root
|
|
itself.</p>
|
|
<p>We track the query dependencies of all global cache entries. This causes the caching of
|
|
cycle participants to be non-trivial. We cannot simply reuse the <code>DepNode</code> of the cycle
|
|
root.<sup class="footnote-reference" id="fr-2-1"><a href="#footnote-2">2</a></sup> If we have a cycle <code>A -> B -> A</code>, then the <code>DepNode</code> for <code>A</code> contains a dependency
|
|
from <code>A -> B</code>. Reusing this entry for <code>B</code> may break if the source is changed. The <code>B -> A</code>
|
|
edge may not exist anymore and <code>A</code> may have been completely removed. This can easily result
|
|
in an ICE.</p>
|
|
<p>However, it's even worse as the result of a cycle can change depending on which goal is
|
|
the root: <a href="https://github.com/rust-lang/rust/blob/7606c13961ddc1174b70638e934df0439b7dc515/tests/ui/traits/next-solver/cycles/coinduction/incompleteness-unstable-result.rs#L4-L16">example</a>. This forces us to weaken caching even further.
|
|
We must not use a cache entry of a cycle root, if there exists a stack entry, which was
|
|
a participant of its cycle involving that root. We do this by storing all cycle participants
|
|
of a given root in its global cache entry and checking that it contains no element of the
|
|
stack: <a href="https://github.com/rust-lang/rust/blob/7606c13961ddc1174b70638e934df0439b7dc515/compiler/rustc_middle/src/traits/solve/cache.rs#L72-L74">source</a>.</p>
|
|
<h3 id="the-provisional-cache"><a class="header" href="#the-provisional-cache">The provisional cache</a></h3>
|
|
<p>TODO: write this :3</p>
|
|
<ul>
|
|
<li>stack dependence of provisional results</li>
|
|
<li>edge case: provisional cache impacts behavior</li>
|
|
</ul>
|
|
<hr>
|
|
<ol class="footnote-definition"><li id="footnote-1">
|
|
<p>This is overly restrictive: if all nested goals return the overflow response with some
|
|
available depth <code>n</code>, then their result should be the same for any depths smaller than <code>n</code>.
|
|
We can implement this optimization in the future. <a href="#fr-1-1">↩</a></p>
|
|
</li>
|
|
<li id="footnote-2">
|
|
<p>summarizing the relevant <a href="https://rust-lang.zulipchat.com/#narrow/stream/364551-t-types.2Ftrait-system-refactor/topic/global.20cache">zulip thread</a> <a href="#fr-2-1">↩</a></p>
|
|
</li>
|
|
</ol>
|
|
</main>
|
|
|
|
<nav class="nav-wrapper" aria-label="Page navigation">
|
|
<!-- Mobile navigation buttons -->
|
|
<a rel="prev" href="../solve/coinduction.html" class="mobile-nav-chapters previous" title="Previous chapter" aria-label="Previous chapter" aria-keyshortcuts="Left">
|
|
<i class="fa fa-angle-left"></i>
|
|
</a>
|
|
|
|
<a rel="next prefetch" href="../solve/proof-trees.html" class="mobile-nav-chapters next" title="Next chapter" aria-label="Next chapter" aria-keyshortcuts="Right">
|
|
<i class="fa fa-angle-right"></i>
|
|
</a>
|
|
|
|
<div style="clear: both"></div>
|
|
</nav>
|
|
</div>
|
|
</div>
|
|
|
|
<nav class="nav-wide-wrapper" aria-label="Page navigation">
|
|
<a rel="prev" href="../solve/coinduction.html" class="nav-chapters previous" title="Previous chapter" aria-label="Previous chapter" aria-keyshortcuts="Left">
|
|
<i class="fa fa-angle-left"></i>
|
|
</a>
|
|
|
|
<a rel="next prefetch" href="../solve/proof-trees.html" class="nav-chapters next" title="Next chapter" aria-label="Next chapter" aria-keyshortcuts="Right">
|
|
<i class="fa fa-angle-right"></i>
|
|
</a>
|
|
</nav>
|
|
|
|
</div>
|
|
|
|
|
|
|
|
|
|
<script>
|
|
window.playground_copyable = true;
|
|
</script>
|
|
|
|
|
|
<script src="../elasticlunr.min.js"></script>
|
|
<script src="../mark.min.js"></script>
|
|
<script src="../searcher.js"></script>
|
|
|
|
<script src="../clipboard.min.js"></script>
|
|
<script src="../highlight.js"></script>
|
|
<script src="../book.js"></script>
|
|
|
|
<!-- Custom JS scripts -->
|
|
<script src="../mermaid.min.js"></script>
|
|
<script src="../mermaid-init.js"></script>
|
|
|
|
|
|
</div>
|
|
</body>
|
|
</html>
|