/usr/share/doc/sbcl/sbcl-internals/The-Cacheing-Mechanism.html

<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd">
<html>
<!-- This manual is part of the SBCL software system. See the
README file for more information.

This manual is in the public domain and is provided with absolutely no
warranty. See the COPYING and CREDITS files for more
information. -->
<!-- Created by GNU Texinfo 6.5, http://www.gnu.org/software/texinfo/ -->
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
<title>The Cacheing Mechanism (SBCL Internals)</title>

<meta name="description" content="The Cacheing Mechanism (SBCL Internals)">
<meta name="keywords" content="The Cacheing Mechanism (SBCL Internals)">
<meta name="resource-type" content="document">
<meta name="distribution" content="global">
<meta name="Generator" content="makeinfo">
<link href="index.html#Top" rel="start" title="Top">
<link href="index.html#SEC_Contents" rel="contents" title="Table of Contents">
<link href="Discriminating-Functions.html#Discriminating-Functions" rel="up" title="Discriminating Functions">
<link href="Foreign-Linkage.html#Foreign-Linkage" rel="next" title="Foreign Linkage">
<link href="Cacheing-and-Dispatch-Functions.html#Cacheing-and-Dispatch-Functions" rel="prev" title="Cacheing and Dispatch Functions">
<style type="text/css">
<!--
a.summary-letter {text-decoration: none}
blockquote.indentedblock {margin-right: 0em}
blockquote.smallindentedblock {margin-right: 0em; font-size: smaller}
blockquote.smallquotation {font-size: smaller}
div.display {margin-left: 3.2em}
div.example {margin-left: 3.2em}
div.lisp {margin-left: 3.2em}
div.smalldisplay {margin-left: 3.2em}
div.smallexample {margin-left: 3.2em}
div.smalllisp {margin-left: 3.2em}
kbd {font-style: oblique}
pre.display {font-family: inherit}
pre.format {font-family: inherit}
pre.menu-comment {font-family: serif}
pre.menu-preformatted {font-family: serif}
pre.smalldisplay {font-family: inherit; font-size: smaller}
pre.smallexample {font-size: smaller}
pre.smallformat {font-family: inherit; font-size: smaller}
pre.smalllisp {font-size: smaller}
span.nolinebreak {white-space: nowrap}
span.roman {font-family: initial; font-weight: normal}
span.sansserif {font-family: sans-serif; font-weight: normal}
ul.no-bullet {list-style: none}
-->
</style>


</head>

<body lang="en">
<a name="The-Cacheing-Mechanism"></a>
<div class="header">
<p>
Previous: <a href="Cacheing-and-Dispatch-Functions.html#Cacheing-and-Dispatch-Functions" accesskey="p" rel="prev">Cacheing and Dispatch Functions</a>, Up: <a href="Discriminating-Functions.html#Discriminating-Functions" accesskey="u" rel="up">Discriminating Functions</a> &nbsp; [<a href="index.html#SEC_Contents" title="Table of contents" rel="contents">Contents</a>]</p>
</div>
<hr>
<a name="The-Cacheing-Mechanism-1"></a>
<h3 class="section">3.5 The Cacheing Mechanism</h3>

<p>In general, the cacheing mechanism works as follows: each class has an
associated wrapper, with some number of uniformly-distributed random
hash values associated with it; each cache has an associated index into
this pseudovector of random hash values.  To look a value up from a
cache from a single class, the hash corresponding to the cache&rsquo;s index
is looked up and reduced to the size of the cache (by bitmasking, for
cache sizes of a power of two); then the entry at that index is looked
up and compared for identity with the wrapper in question.  If it
matches, this is a hit; otherwise the cache is walked sequentially from
this index, skipping the 0th entry.  If the original index is reached,
the cache does not contain the value sought<a name="DOCF7" href="#FOOT7"><sup>7</sup></a>.
</p>
<p>To add an entry to a cache, much the same computation is executed.
However, if there is a collision in hash values, before the cache is
grown, an attempt is made to fill the cache using a different index into
the wrappers&rsquo; hash values.
</p>
<p>Wrappers are invalidated for caches by setting all of their hash values
to zero.  (Additionally, they are invalidated by setting their
<code>depthoid</code> to -1, to communicate to structure type testers, and
their <code>invalid</code> to non-<code>nil</code>, communicating to
<code>obsolete-instance-trap</code>.
</p>
<p>The hash value for multiple dispatch is computed by summing all of the
individual hash values from each wrapper (excluding arguments for which
all methods have <code>t</code> specializers, for which no dispatch
computation needs to be done), jumping to the cache miss case if any
wrapper has a zero hash index.
</p>
<p>(FIXME: As of sbcl-0.9.x.y, the generality of multiple hash values per
wrapper was removed, as it appeared to do nothing in particular for
performance in real-world situations.)
</p>
<p>References (O for working BibTeX):
</p>
<p>The CLOS standards proposal
</p>
<p>Kiczales and Rodruigez
</p>
<p>AMOP
</p><div class="footnote">
<hr>
<h4 class="footnotes-heading">Footnotes</h4>

<h3><a name="FOOT7" href="#DOCF7">(7)</a></h3>
<p>Actually, there&rsquo;s
some kind of scope for overflow.</p>
</div>
<hr>
<div class="header">
<p>
Previous: <a href="Cacheing-and-Dispatch-Functions.html#Cacheing-and-Dispatch-Functions" accesskey="p" rel="prev">Cacheing and Dispatch Functions</a>, Up: <a href="Discriminating-Functions.html#Discriminating-Functions" accesskey="u" rel="up">Discriminating Functions</a> &nbsp; [<a href="index.html#SEC_Contents" title="Table of contents" rel="contents">Contents</a>]</p>
</div>



</body>
</html>
sbcl-doc 2:1.4.5-1 / usr / share / doc / sbcl / sbcl-internals / The-Cacheing-Mechanism.html
