Skip to content

HTTPS clone URL

Subversion checkout URL

You can clone with
or
.
Download ZIP
Tree: 11cb0f926d
Fetching contributors…

Cannot retrieve contributors at this time

70 lines (49 sloc) 10.531 kB
<!DOCTYPE html> <html> <head> <title>cache.coffee</title> <meta http-equiv="content-type" content="text/html; charset=UTF-8"> <link rel="stylesheet" media="all" href="docco.css" /> </head> <body> <div id="container"> <div id="background"></div> <div id="jump_to"> Jump To &hellip; <div id="jump_wrapper"> <div id="jump_page"> <a class="source" href="api.html"> api.coffee </a> <a class="source" href="cache.html"> cache.coffee </a> <a class="source" href="cafeaulife.html"> cafeaulife.coffee </a> <a class="source" href="future.html"> future.coffee </a> <a class="source" href="gc.html"> gc.coffee </a> <a class="source" href="menagerie.html"> menagerie.coffee </a> <a class="source" href="rules.html"> rules.coffee </a> </div> </div> </div> <table cellpadding="0" cellspacing="0"> <thead> <tr> <th class="docs"> <h1> cache.coffee </h1> </th> <th class="code"> </th> </tr> </thead> <tbody> <tr id="section-1"> <td class="docs"> <div class="pilwrap"> <a class="pilcrow" href="#section-1">&#182;</a> </div> <p>This module is part of <a href="http://recursiveuniver.se">recursiveuniver.se</a>.</p>
<h2>Cache Module</h2>
<p>HashLife uses extensive <a href="https://en.wikipedia.org/wiki/Canonicalization">canonicalization</a> to optimize the storage of very large patterns with repetitive
components. The Cache Module implements a very naive hash-table for canoncial representations of squares.</p> </td> <td class="code"> <div class="highlight"><pre></pre></div> </td> </tr> <tr id="section-2"> <td class="docs"> <div class="pilwrap"> <a class="pilcrow" href="#section-2">&#182;</a> </div> <h3>Canoncialization: The "Hash" in HashLife</h3>
<p>HashLife gets a tremendous speed-up by storing and reusing squares in a giant cache.
Any result, at any scale, that has been computed before is reused. This is extremely
efficient when dealing with patterns that contain a great deal of redundancy, such as
the kinds of patterns constructed for the purpose of emulating circuits or machines in Life.</p>
<p>Once Cafe au Life has calculated the results for the 65K possible four-by-four
squares, the rules are no longer applied to any generation: Any pattern of any size is
recursively computed terminating in a four-by-four square that has already been computed and cached.</p>
<p>This module provides a <code>mixInto</code> function so that it retroactively modify existing classes.</p> </td> <td class="code"> <div class="highlight"><pre></pre></div> </td> </tr> <tr id="section-3"> <td class="docs"> <div class="pilwrap"> <a class="pilcrow" href="#section-3">&#182;</a> </div> <h3>Baseline Setup</h3> </td> <td class="code"> <div class="highlight"><pre><span class="nv">_ = </span><span class="nx">require</span><span class="p">(</span><span class="s1">&#39;underscore&#39;</span><span class="p">)</span>
<span class="nv">YouAreDaChef = </span><span class="nx">require</span><span class="p">(</span><span class="s1">&#39;YouAreDaChef&#39;</span><span class="p">).</span><span class="nx">YouAreDaChef</span>
<span class="nx">exports</span> <span class="o">?=</span> <span class="nb">window</span> <span class="o">or</span> <span class="k">this</span></pre></div> </td> </tr> <tr id="section-4"> <td class="docs"> <div class="pilwrap"> <a class="pilcrow" href="#section-4">&#182;</a> </div> <h3>Implementing the cache</h3>
<p>The cache is organized into an array of 'buckets', each of which is a hash from a simple key
to a cached square. The buckets are organized by level of the square. This allows some simple
ordering later when we start fooling around with garbage collection: It's easy to find the
largest squares that aren't in use.</p> </td> <td class="code"> <div class="highlight"><pre><span class="nv">exports.mixInto = </span><span class="nf">({Square, Cell}) -&gt;</span>
<span class="nv">counter = </span><span class="mi">0</span>
<span class="nx">YouAreDaChef</span><span class="p">(</span><span class="nx">Cell</span><span class="p">)</span>
<span class="p">.</span><span class="nx">after</span> <span class="s1">&#39;initialize&#39;</span><span class="p">,</span> <span class="o">-&gt;</span>
<span class="vi">@id = </span><span class="p">(</span><span class="nx">counter</span> <span class="o">+=</span> <span class="mi">1</span><span class="p">)</span>
<span class="nx">YouAreDaChef</span><span class="p">(</span><span class="nx">Square</span><span class="p">)</span>
<span class="p">.</span><span class="nx">after</span> <span class="s1">&#39;initialize&#39;</span><span class="p">,</span> <span class="o">-&gt;</span>
<span class="vi">@id = </span><span class="p">(</span><span class="nx">counter</span> <span class="o">+=</span> <span class="mi">1</span><span class="p">)</span>
<span class="nx">_</span><span class="p">.</span><span class="nx">extend</span> <span class="nx">Square</span><span class="p">,</span>
<span class="nv">cache:</span>
<span class="nv">buckets: </span><span class="p">[]</span>
<span class="nv">clear: </span><span class="o">-&gt;</span>
<span class="vi">@buckets = </span><span class="p">[]</span>
<span class="nv">length: </span><span class="mi">0</span>
<span class="nv">find: </span><span class="nf">({nw, ne, se, sw}) -&gt;</span>
<span class="nx">console</span><span class="p">.</span><span class="nx">trace</span><span class="p">()</span> <span class="nx">unless</span> <span class="nx">nw</span><span class="o">?</span><span class="p">.</span><span class="nx">level</span><span class="o">?</span>
<span class="p">(</span><span class="nx">@buckets</span><span class="p">[</span><span class="nx">nw</span><span class="p">.</span><span class="nx">level</span> <span class="o">+</span> <span class="mi">1</span><span class="p">]</span> <span class="o">||=</span> <span class="p">{})[</span><span class="s2">&quot;#{nw.id}-#{ne.id}-#{se.id}-#{sw.id}&quot;</span><span class="p">]</span>
<span class="nv">add: </span><span class="nf">(square) -&gt;</span>
<span class="nx">@length</span> <span class="o">+=</span> <span class="mi">1</span>
<span class="p">{</span><span class="nx">nw</span><span class="p">,</span> <span class="nx">ne</span><span class="p">,</span> <span class="nx">se</span><span class="p">,</span> <span class="nx">sw</span><span class="p">}</span> <span class="o">=</span> <span class="nx">square</span>
<span class="p">(</span><span class="nx">@buckets</span><span class="p">[</span><span class="nx">nw</span><span class="p">.</span><span class="nx">level</span> <span class="o">+</span> <span class="mi">1</span><span class="p">]</span> <span class="o">||=</span> <span class="p">{})[</span><span class="s2">&quot;#{nw.id}-#{ne.id}-#{se.id}-#{sw.id}&quot;</span><span class="p">]</span> <span class="o">=</span> <span class="nx">square</span>
<span class="nv">canonicalize: </span><span class="nf">(quadrants) -&gt;</span>
<span class="nv">found = </span><span class="nx">@cache</span><span class="p">.</span><span class="nx">find</span><span class="p">(</span><span class="nx">quadrants</span><span class="p">)</span>
<span class="k">if</span> <span class="nx">found</span>
<span class="nx">found</span>
<span class="k">else</span>
<span class="nx">@cache</span><span class="p">.</span><span class="nx">add</span><span class="p">(</span><span class="k">new</span> <span class="nx">Square</span><span class="p">.</span><span class="nx">RecursivelyComputable</span><span class="p">(</span><span class="nx">quadrants</span><span class="p">))</span></pre></div> </td> </tr> <tr id="section-5"> <td class="docs"> <div class="pilwrap"> <a class="pilcrow" href="#section-5">&#182;</a> </div> <h2>The first time through</h2>
<p>If this is your first time through the code, and you've already read the <a href="http:rules.html">Rules</a> and <a href="http:future.html">Future</a> modules, you can look at the
<a href="http:gc.html">Garbage Collection</a> and <a href="http:api.html">API</a> modules next.</p> </td> <td class="code"> <div class="highlight"><pre></pre></div> </td> </tr> <tr id="section-6"> <td class="docs"> <div class="pilwrap"> <a class="pilcrow" href="#section-6">&#182;</a> </div> <hr />
<p><strong>(c) 2012 <a href="http://braythwayt.com">Reg Braithwaite</a></strong> (<a href="http://twitter.com/raganwald">@raganwald</a>)</p>
<p>Cafe au Life is freely distributable under the terms of the <a href="http://en.wikipedia.org/wiki/MIT_License">MIT license</a>.</p>
<p>The annotated source code was generated directly from the <a href="https://github.com/raganwald/cafeaulife/blob/master/lib">original source</a> using <a href="http://jashkenas.github.com/docco/">Docco</a>.</p> </td> <td class="code"> <div class="highlight"><pre></pre></div> </td> </tr> </tbody> </table> </div> </body> </html>
Jump to Line
Something went wrong with that request. Please try again.