1. Tim Day
  2. lru_cache

Commits

Tim Day  committed e6cbfe7

Minor update to article

  • Participants
  • Parent commits 04389f1
  • Branches default

Comments (0)

Files changed (3)

File article/lru.html

View file
 <meta name="originator" content="TeX4ht (http://www.cse.ohio-state.edu/~gurari/TeX4ht/)" /> 
 <!-- html,xhtml --> 
 <meta name="src" content="lru.tex" /> 
-<meta name="date" content="2011-10-03 14:30:00" /> 
+<meta name="date" content="2012-05-19 00:44:00" /> 
 <link rel="stylesheet" type="text/css" href="lru.css" /> 
 </head><body 
 >
 <h2 class="titleHead">LRU cache implementation in C++</h2>
 <div class="author" ><span 
 class="cmsy-10x-x-120">Š</span><span 
-class="pncr7t-x-x-120">2010-2011 Tim Day</span>
+class="pncr7t-x-x-120">2010-2012 Tim Day</span>
 <br /> <span 
 class="pncr7t-x-x-120">timday@timday.com</span>
 <br />  <a 
    <h3 class="sectionHead"><span class="titlemark">1    </span> <a 
  id="x1-20001"></a>Document history</h3>
      <ul class="itemize1">
+     <li class="itemize">May 2012: Minor typo fixed in text.
+     </li>
      <li class="itemize">October 2011: Updated for C++0x; added templating to permit use
      of both hash-based &#8220;unordered&#8221; maps and conventional tree-based
      maps. Updated performance results.
                                                                      
 
                                                                      
-<!--l. 65--><p class="noindent" >
+<!--l. 66--><p class="noindent" >
 </p>
    <h3 class="sectionHead"><span class="titlemark">2    </span> <a 
  id="x1-30002"></a>Source code licensing</h3>
-<!--l. 67--><p class="noindent" >While the general aim of this document is to provide its audience with
+<!--l. 68--><p class="noindent" >While the general aim of this document is to provide its audience with
 enough information to implement their own LRU-caching classes, readers
 are welcome to cut-and-paste the code listings in this document under the
 terms of the Internet Systems Consortium (ISC) license (an OSI-approved
 code in this document, and added as a comment in any code copied directly
 from it:
 </p>
-   <!--l. 74-->
+   <!--l. 75-->
 <div class="lstlisting" id="listing-1"><span class="label"><a 
  id="x1-3001r1"></a></span><span 
 class="pcrr7t-x-x-80">Copyright</span><span 
 class="pcrr7t-x-x-80">SOFTWARE</span><span 
 class="pcrr7t-x-x-80">.</span>
    </div>
-<!--l. 90--><p class="indent" >   Readers simply looking for templated LRU cache code for instant usage
+<!--l. 91--><p class="indent" >   Readers simply looking for templated LRU cache code for instant usage
 may wish to turn straight to <a 
 href="#x1-8007r1">Listing&#x00A0;1</a> and the comments immediately
 preceding it.
-</p><!--l. 93--><p class="indent" >   The sources are also available from a Bitbucket-hosted <a 
+</p><!--l. 94--><p class="indent" >   The sources are also available from a Bitbucket-hosted <a 
 href="http://bitbucket.org/timday/lru_cache" >Mercurial
 repository</a>.
-</p><!--l. 95--><p class="noindent" >
+</p><!--l. 96--><p class="noindent" >
 </p>
    <h3 class="sectionHead"><span class="titlemark">3    </span> <a 
  id="x1-40003"></a>The problem</h3>
-<!--l. 97--><p class="noindent" >The need for caching behaviour sometimes arises during system development.
+<!--l. 98--><p class="noindent" >The need for caching behaviour sometimes arises during system development.
 Generally the desire is to preserve some expensive-to-obtain results so they
 can be reused &#8220;for free&#8221; without repeating the expensive operation in future.
 Typically the expense arises because a complex calculation is needed to
 class="pcrr7t-x-x-109">std::map</span>), with the key being the input to the expensive function and the
 value being the result. This is often referred to as &#8220;memoisation&#8221; of a
 function.
-</p><!--l. 108--><p class="indent" >   However, for most applications, this approach would quickly consume too
+</p><!--l. 109--><p class="indent" >   However, for most applications, this approach would quickly consume too
 much memory to be of any practical value. The memory consumption issue
 can be addressed by limiting the maximum number of items stored in the
 cache or, if the items have a variable size, limiting the aggregate total stored.
 to make way for a new record by deleting the record in the cache
 which was &#8220;least recently used&#8221;. This is called an LRU replacement
 strategy.
-</p><!--l. 123--><p class="indent" >   Despite the general utility of a LRU-replacement cache component, one is
+</p><!--l. 124--><p class="indent" >   Despite the general utility of a LRU-replacement cache component, one is
 not provided as such in C++&#8217;s Standard Library or in the well known Boost
 libraries. However, it is reasonably easy logic to construct using either library
 as a basis.
-</p><!--l. 127--><p class="noindent" >
+</p><!--l. 128--><p class="noindent" >
 </p>
    <h3 class="sectionHead"><span class="titlemark">4    </span> <a 
  id="x1-50004"></a>Implementations</h3>
-<!--l. 129--><p class="noindent" >The following two sections describe possible implementations, both of them
+<!--l. 130--><p class="noindent" >The following two sections describe possible implementations, both of them
 providing caching up to a limited number of records of a function with
 signature <span 
-class="pcrr7t-x-x-109">V f(K)</span>), where <span 
+class="pcrr7t-x-x-109">V f(K)</span>, where <span 
 class="pcrr7t-x-x-109">K </span>and <span 
 class="pcrr7t-x-x-109">V </span>are the &#8220;key type&#8221; and the &#8220;value type&#8221;.
 The only real difference in the API to either implementation is that the
 than a function pointer, providing slightly more flexibility through
 compatibility with <span 
 class="pcrr7t-x-x-109">boost::bind</span>.
-</p><!--l. 138--><p class="indent" >   The code presented has been tested on g++ 4.4.5. The <span 
+</p><!--l. 139--><p class="indent" >   The code presented has been tested on g++ 4.4.5. The <span 
 class="pcrr7t-x-x-109">-std=c++0x </span>option
 is required in order to use the <span 
 class="pcrr7t-x-x-109">std::unordered</span><span 
 Library, and variadic template arguments are also used to bypass some
 templated-template issues associated with the different type arguments to
 the tree-based and hash-based container types.
-</p><!--l. 144--><p class="indent" >   For brevity the code explanations below will generally refer to the
+</p><!--l. 145--><p class="indent" >   For brevity the code explanations below will generally refer to the
 <span 
 class="pcrr7t-x-x-109">std::map </span>and <span 
 class="pcrr7t-x-x-109">boost::bimaps::set</span><span 
 class="pcrr7t-x-x-109">boost::bimaps::set</span><span 
 class="pcrr7t-x-x-109">_of</span>, hashability and equality
 testing in the case of the unordered variants).
-</p><!--l. 151--><p class="noindent" >
+</p><!--l. 152--><p class="noindent" >
 </p>
                                                                      
 
                                                                      
    <h3 class="sectionHead"><span class="titlemark">5    </span> <a 
  id="x1-60005"></a>Standard Library based LRU-cache</h3>
-<!--l. 154--><p class="noindent" >
+<!--l. 155--><p class="noindent" >
 </p>
    <h4 class="subsectionHead"><span class="titlemark">5.1    </span> <a 
  id="x1-70005.1"></a>Design</h4>
-<!--l. 155--><p class="noindent" >Users of the C++ Standard Library needing an LRU-replacement cache
+<!--l. 156--><p class="noindent" >Users of the C++ Standard Library needing an LRU-replacement cache
 generally gravitate towards <span 
 class="pcrr7t-x-x-109">std::map </span>or <span 
 class="pcrr7t-x-x-109">std::unordered</span><span 
 class="cmr-10x-x-109">(1)</span>
 access complexity). The problem then is how to implement the eviction
 strategy.
-</p><!--l. 159--><p class="indent" >   The most obvious naive solution is to use an </p><!--l. 160-->
+</p><!--l. 160--><p class="indent" >   The most obvious naive solution is to use an </p><!--l. 161-->
 <div class="lstlisting" id="listing-2"><span class="label"><a 
  id="x1-7001r1"></a></span><span 
 class="pcrr7t-">&#x00A0;</span><span 
 class="pcrr7t-">&#x00A0;</span><span 
 class="pcrr7t-">&#x003E;</span>
    </div>
-<!--l. 164--><p class="indent" >   The <span 
+<!--l. 165--><p class="indent" >   The <span 
 class="pcrr7t-x-x-109">timestamp</span><span 
 class="pcrr7t-x-x-109">_t </span>holds a scalar quantity, the ordering of which indicates
 when the value was last accessed relative to other values; typically some sort
 class="cmmi-10x-x-109">n</span><span 
 class="cmr-10x-x-109">) </span>search over all the records to determine the oldest
 one.
-</p><!--l. 172--><p class="indent" >   As a solution to eviction being expensive, it might be tempting to
-implement the cache as a </p><!--l. 173-->
+</p><!--l. 173--><p class="indent" >   As a solution to eviction being expensive, it might be tempting to
+implement the cache as a </p><!--l. 174-->
 <div class="lstlisting" id="listing-3"><span class="label"><a 
  id="x1-7002r1"></a></span><span 
 class="pcrr7t-">&#x00A0;</span><span 
 class="pcrr7t-">&#x00A0;</span><span 
 class="pcrr7t-">&#x003E;</span>
    </div>
-<!--l. 176--><p class="indent" >   Moving any item accessed to the tail of the list (a cheap operation for
+<!--l. 177--><p class="indent" >   Moving any item accessed to the tail of the list (a cheap operation for
 lists), ensures the least-recently-used item can trivially be obtained (for
 erasure) at the list head by <span 
 class="pcrr7t-x-x-109">begin()</span>. However, this just moves the problem
 class="cmmi-10x-x-109">n</span><span 
 class="cmr-10x-x-109">) </span>search simply to look up
 a key in the cache.
-</p><!--l. 181--><p class="indent" >   While either naive solution can be got to work (and may well be a
+</p><!--l. 182--><p class="indent" >   While either naive solution can be got to work (and may well be a
 simple pragmatic solution to caching a few tens of items) certainly
 neither can be considered scalable or efficient due to the <span 
 class="cmmi-10x-x-109">O</span><span 
 class="cmr-10x-x-109">) </span>behaviour
 associated with either identifying eviction targets or accessing values by
 key.
-</p><!--l. 185--><p class="indent" >   However, it is possible to implement an LRU-replacement cache with
+</p><!--l. 186--><p class="indent" >   However, it is possible to implement an LRU-replacement cache with
 efficient eviction <span 
-class="pncri7t-x-x-109">and </span>access using a pair of maps: </p><!--l. 187-->
+class="pncri7t-x-x-109">and </span>access using a pair of maps: </p><!--l. 188-->
                                                                      
 
                                                                      
 class="pcrr7t-">key_to_value_type</span><span 
 class="pcrr7t-">;</span>
    </div>
-<!--l. 194--><p class="indent" >   On accessing <span 
+<!--l. 195--><p class="indent" >   On accessing <span 
 class="pcrr7t-x-x-109">key</span><span 
 class="pcrr7t-x-x-109">_to</span><span 
 class="pcrr7t-x-x-109">_value </span>by a key, we obtain access to both the value
 class="pcrr7t-x-x-109">_to</span><span 
 class="pcrr7t-x-x-109">_key </span>provides the key to the record
 which must be erased.
-</p><!--l. 199--><p class="indent" >   However, this can actually be optimised slightly: </p><!--l. 200-->
+</p><!--l. 200--><p class="indent" >   However, this can actually be optimised slightly: </p><!--l. 201-->
 <div class="lstlisting" id="listing-5"><span class="label"><a 
  id="x1-7008r1"></a></span><span 
 class="pcrr7t-">&#x00A0;</span><span 
 class="pcrr7t-">key_to_value_type</span><span 
 class="pcrr7t-">;</span>
    </div>
-<!--l. 207--><p class="indent" >   This has the slight advantage that updating the timestamp on a record
+<!--l. 208--><p class="indent" >   This has the slight advantage that updating the timestamp on a record
 access avoids an keyed lookup into <span 
 class="pcrr7t-x-x-109">timestamp</span><span 
 class="pcrr7t-x-x-109">_to</span><span 
 class="pcrr7t-x-x-109">_key</span>, replacing it with a
 (presumably more efficient) direct iterator access.
-</p><!--l. 210--><p class="indent" >   Pedants will observe that further slight improvement would also have
+</p><!--l. 211--><p class="indent" >   Pedants will observe that further slight improvement would also have
 the <span 
 class="pcrr7t-x-x-109">timestamp</span><span 
 class="pcrr7t-x-x-109">_to</span><span 
 following a cache miss is likely to be hugely more expensive than any
 keyed access. Therefore this second optimisation is not considered
 further.
-</p><!--l. 222--><p class="indent" >   In fact there <span 
+</p><!--l. 223--><p class="indent" >   In fact there <span 
 class="pncri7t-x-x-109">is </span>one final powerful optimisation possible. The only
 operations actually done on <span 
 class="pcrr7t-x-x-109">timestamp</span><span 
 previous testing the author has found list-and-map implementations
 to be almost twice as fast as a version (not shown) using a pair of
 maps.
-</p><!--l. 231--><p class="indent" >   Finally, before showing the complete implementation, there is one
+</p><!--l. 232--><p class="indent" >   Finally, before showing the complete implementation, there is one
 other detail to consider: it would seem to be desirable to template the
 cache class code on the underlying container type used (<span 
 class="pcrr7t-x-x-109">std::map </span>or
 and value types. Generalising the code to support overriding of the default
 comparator (or the unordered map type equivalent) or allocators is left as an
 exercise for the reader.
-</p><!--l. 243--><p class="noindent" >
+</p><!--l. 244--><p class="noindent" >
 </p>
    <h4 class="subsectionHead"><span class="titlemark">5.2    </span> <a 
  id="x1-80005.2"></a>Implementation</h4>
-<!--l. 245--><p class="noindent" >See <a 
+<!--l. 246--><p class="noindent" >See <a 
 href="#x1-8007r1">Listing&#x00A0;1</a> for a complete example using the pair of containers
-</p><!--l. 246-->
+</p><!--l. 247-->
 <div class="lstlisting" id="listing-6"><span class="label"><a 
  id="x1-8001r1"></a></span><span 
 class="pcrr7t-">&#x00A0;</span><span 
 class="pcrr7t-">key_to_value_type</span><span 
 class="pcrr7t-">;</span>
    </div>
-<!--l. 252--><p class="indent" >   where MAP is expected to be one of <span 
+<!--l. 253--><p class="indent" >   where MAP is expected to be one of <span 
 class="pcrr7t-x-x-109">std::map </span>or <span 
 class="pcrr7t-x-x-109">std::unordered</span><span 
 class="pcrr7t-x-x-109">_map</span>;
 for example an LRU cache from <span 
 class="pcrr7t-x-x-109">std::string </span>to <span 
 class="pcrr7t-x-x-109">std::string </span>using
-hashing would be declared as </p><!--l. 254-->
+hashing would be declared as </p><!--l. 255-->
 <div class="lstlisting" id="listing-7"><span class="label"><a 
  id="x1-8005r1"></a></span><span 
 class="pcrr7t-">&#x00A0;</span><span 
 class="pcrr7t-">unordered_map</span><span 
 class="pcrr7t-">&#x003E;</span>
    </div>
-<!--l. 257--><p class="indent" >   while an int-keyed cache of Foo objects using the &#8220;classic&#8221; <span 
+<!--l. 258--><p class="indent" >   while an int-keyed cache of Foo objects using the &#8220;classic&#8221; <span 
 class="pcrr7t-x-x-109">std::map</span>
-would be declared as </p><!--l. 258-->
+would be declared as </p><!--l. 259-->
 <div class="lstlisting" id="listing-8"><span class="label"><a 
  id="x1-8006r1"></a></span><span 
 class="pcrr7t-">&#x00A0;</span><span 
 class="pcrr7t-">map</span><span 
 class="pcrr7t-">&#x003E;</span>
    </div>
-<!--l. 261--><p class="indent" >   Note that use of a reference counted smart-pointer for heap-allocated
+<!--l. 262--><p class="indent" >   Note that use of a reference counted smart-pointer for heap-allocated
 value types is strongly advised as the very nature of caches easily leads to
 situations where value object ownership must be considered shared
 between the cache and a client which has retrieved the value from the
 cache.
 </p>
-   <!--l. 265--><div class="lstinputlisting">
+   <!--l. 266--><div class="lstinputlisting">
 <a 
  id="x1-8007r1"></a>
 <a 
 
                                                                      
    </div>
-<!--l. 267--><p class="indent" >   Readers interested in the performance impact of choosing <span 
+<!--l. 268--><p class="indent" >   Readers interested in the performance impact of choosing <span 
 class="pcrr7t-x-x-109">std::map </span>vs.
 <span 
 class="pcrr7t-x-x-109">std::unordered</span><span 
 class="pcrr7t-x-x-109">_map </span>will find some results in <a 
 href="#x1-140007.2">subsection&#x00A0;7.2</a>.
-</p><!--l. 270--><p class="noindent" >
+</p><!--l. 271--><p class="noindent" >
 </p>
    <h3 class="sectionHead"><span class="titlemark">6    </span> <a 
  id="x1-90006"></a>Boost bimap-based LRU-cache</h3>
-<!--l. 273--><p class="noindent" >
+<!--l. 274--><p class="noindent" >
 </p>
    <h4 class="subsectionHead"><span class="titlemark">6.1    </span> <a 
  id="x1-100006.1"></a>Design</h4>
-<!--l. 274--><p class="noindent" >Assuming usage of the <a 
+<!--l. 275--><p class="noindent" >Assuming usage of the <a 
 href="http://www.boost.org/" >boost C++ libraries</a> is an option, <a 
 href="http://www.boost.org/doc/libs/1_42_0/libs/bimap/doc/html/index.html" ><span 
 class="pcrr7t-x-x-109">boost::bimap</span></a>
 required, and much of the complication of the standard-library version
 described in <a 
 href="#x1-60005">section&#x00A0;5</a> can be avoided.
-</p><!--l. 284--><p class="indent" >   As with the standard library based implementation above, it is not
+</p><!--l. 285--><p class="indent" >   As with the standard library based implementation above, it is not
 actually necessary to record timestamps explicitly and it suffices for the
 access-history view of the bimap to be a <span 
 class="pcrr7t-x-x-109">list</span><span 
 class="pcrr7t-x-x-109">bimap </span>inserts new records at the
 tail of the list view, and records can be efficiently relocated there on
 access.
-</p><!--l. 290--><p class="indent" >   There are several ways in which the boost::bimap container to be used
-might be instantiated. The most obvious one is </p><!--l. 292-->
+</p><!--l. 291--><p class="indent" >   There are several ways in which the boost::bimap container to be used
+might be instantiated. The most obvious one is </p><!--l. 293-->
 <div class="lstlisting" id="listing-9"><span class="label"><a 
  id="x1-10001r1"></a></span><span 
 class="pcrr7t-">&#x00A0;</span><span 
 class="pcrr7t-">container_type</span><span 
 class="pcrr7t-">;</span>
    </div>
-<!--l. 298--><p class="indent" >   with the left view providing the key-to-value semantics, and the ordering
+<!--l. 299--><p class="indent" >   with the left view providing the key-to-value semantics, and the ordering
 on the right view used to maintain a record of the key-value-pair access
 history. Replacing the <span 
 class="pcrr7t-x-x-109">set</span><span 
 class="pcrr7t-x-x-109">_set</span><span 
 class="pcrr7t-x-x-109">_of </span>to use hashing
 instead of trees is another choice.
-</p><!--l. 302--><p class="indent" >   However, there also exists the possibility of declaring </p><!--l. 303-->
+</p><!--l. 303--><p class="indent" >   However, there also exists the possibility of declaring </p><!--l. 304-->
 <div class="lstlisting" id="listing-10"><span class="label"><a 
  id="x1-10005r1"></a></span><span 
 class="pcrr7t-">&#x00A0;</span><span 
 
                                                                      
    </div>
-<!--l. 310--><p class="indent" >   with the cached value stored using bimap&#8217;s support for &#8220;additional
+<!--l. 311--><p class="indent" >   with the cached value stored using bimap&#8217;s support for &#8220;additional
 information&#8221; and <span 
 class="pcrr7t-x-x-109">dummy</span><span 
 class="pcrr7t-x-x-109">_type </span>never storing a meaningful value. In the past
 without <span 
 class="pcrr7t-x-x-109">with</span><span 
 class="pcrr7t-x-x-109">_info </span>is considered further here.
-</p><!--l. 317--><p class="noindent" >
+</p><!--l. 318--><p class="noindent" >
 </p>
    <h4 class="subsectionHead"><span class="titlemark">6.2    </span> <a 
  id="x1-110006.2"></a>Implementation</h4>
-<!--l. 319--><p class="noindent" >See <a 
+<!--l. 320--><p class="noindent" >See <a 
 href="#x1-11002r2">Listing&#x00A0;2</a> for a complete implementation. This is similar to the standard
 library-based version in that it is templated on the key view template to
 be used which is expected be one of <span 
 <span 
 class="pcrr7t-x-x-109">std::string </span>to <span 
 class="pcrr7t-x-x-109">std::string </span>using hashing would be declared as
-</p><!--l. 323-->
+</p><!--l. 324-->
 <div class="lstlisting" id="listing-11"><span class="label"><a 
  id="x1-11001r1"></a></span><span 
 class="pcrr7t-">&#x00A0;</span><span 
 class="pcrr7t-">unordered_set_of</span><span 
 class="pcrr7t-">&#x003E;</span>
    </div>
-   <!--l. 327--><div class="lstinputlisting">
+   <!--l. 328--><div class="lstinputlisting">
 <a 
  id="x1-11002r2"></a>
 <a 
 class="pcrb7t-">#</span><span 
 class="pcrb7t-">endif</span>
    </div>
-<!--l. 329--><p class="indent" >   See <a 
+<!--l. 330--><p class="indent" >   See <a 
 href="#x1-140007.2">subsection&#x00A0;7.2</a> for some comparative performance testing between
 the tree and hash based versions, and between bimap-based caches and
 conventional standard library map based caches.
-</p><!--l. 332--><p class="noindent" >
+</p><!--l. 333--><p class="noindent" >
 </p>
    <h3 class="sectionHead"><span class="titlemark">7    </span> <a 
  id="x1-120007"></a>Testing</h3>
-<!--l. 334--><p class="noindent" >Both test codes below make use of the header <a 
+<!--l. 335--><p class="noindent" >Both test codes below make use of the header <a 
 href="#x1-12003r3">Listing&#x00A0;3</a> which brings
 together both standard library and boost bimap based implementations and
-defines some helper types. This permits, for example </p><!--l. 337-->
+defines some helper types. This permits, for example </p><!--l. 338-->
 <div class="lstlisting" id="listing-12"><span class="label"><a 
  id="x1-12001r1"></a></span><span 
 class="pcrr7t-">&#x00A0;</span><span 
 
                                                                      
    </div>
-<!--l. 340--><p class="indent" >   to be written </p><!--l. 341-->
+<!--l. 341--><p class="indent" >   to be written </p><!--l. 342-->
 <div class="lstlisting" id="listing-13"><span class="label"><a 
  id="x1-12002r1"></a></span><span 
 class="pcrr7t-">&#x00A0;</span><span 
 class="pcrr7t-">&#x003E;::</span><span 
 class="pcrr7t-">type</span>
    </div>
-   <!--l. 345--><div class="lstinputlisting">
+   <!--l. 346--><div class="lstinputlisting">
 <a 
  id="x1-12003r3"></a>
 <a 
 class="pcrb7t-">#</span><span 
 class="pcrb7t-">endif</span>
    </div>
-<!--l. 347--><p class="noindent" >
+<!--l. 348--><p class="noindent" >
 </p>
    <h4 class="subsectionHead"><span class="titlemark">7.1    </span> <a 
  id="x1-130007.1"></a>Unit test</h4>
-<!--l. 349--><p class="noindent" ><a 
+<!--l. 350--><p class="noindent" ><a 
 href="#x1-13001r4">Listing&#x00A0;4</a> contains templated <span 
 class="pcrr7t-x-x-109">boost::test </span>code to exercise all four cache
 implementations and check basic behaviour is as expected.
 </p>
-   <!--l. 352--><div class="lstinputlisting">
+   <!--l. 353--><div class="lstinputlisting">
 <a 
  id="x1-13001r4"></a>
 <a 
  id="x1-13091r89"></a></span><span 
 class="pcrr7t-">}</span>
    </div>
-<!--l. 354--><p class="noindent" >
+<!--l. 355--><p class="noindent" >
 </p>
    <h4 class="subsectionHead"><span class="titlemark">7.2    </span> <a 
  id="x1-140007.2"></a>Performance testing</h4>
-<!--l. 357--><p class="noindent" ><a 
+<!--l. 358--><p class="noindent" ><a 
 href="#x1-14004r5">Listing&#x00A0;5</a> contains test code to examine the performance of all four cache
 implementations. It makes use of a timer utility class which is provided in
 <a 
 href="#x1-21001r6">Listing&#x00A0;6</a> (NB this makes use of the TR1 &#8220;chrono&#8221; addition to the standard
 library).
-</p><!--l. 361--><p class="indent" >   In order to test only pure cache performance, a trivial operation is used
+</p><!--l. 362--><p class="indent" >   In order to test only pure cache performance, a trivial operation is used
 for the cached function. The code tests a 1024 element capacity cache with a
 series of random accesses over a smaller or larger range. When the the load
 is less than or equal to <span 
 to be a miss, and in the <span 
 class="cmr-10x-x-109">200% </span>load case, on average half of all accesses should
 miss.
-</p><!--l. 373--><p class="indent" >   Two key-value types are tested: </p>
+</p><!--l. 374--><p class="indent" >   Two key-value types are tested: </p>
      <ul class="itemize1">
      <li class="itemize"><span 
 class="pcrr7t-x-x-109">int </span>to  <span 
      <span 
 class="pcrr7t-x-x-109">wchar</span><span 
 class="pcrr7t-x-x-109">_t</span>), with the cached function simply being the string length.</li></ul>
-<!--l. 380--><p class="indent" >   <a 
+<!--l. 381--><p class="indent" >   <a 
 href="#x1-140021">Table&#x00A0;1</a> and <a 
 href="#x1-140032">Table&#x00A0;2</a> shows performance results obtained on a 2.66GHz
 Intel Q9450 Core2 running Debian Squeeze (32bit) when compiled with
-</p><!--l. 381-->
+</p><!--l. 382-->
 <div class="lstlisting" id="listing-14"><span class="label"><a 
  id="x1-14001r1"></a></span><span 
 class="pcrr7t-">&#x00A0;</span><span 
 class="pcrr7t-">-</span><span 
 class="pcrr7t-">lboost_unit_test_framework</span>
    </div>
-<!--l. 384--><p class="indent" >   Software versions are g++ 4.4.5, boost 1.42.
+<!--l. 385--><p class="indent" >   Software versions are g++ 4.4.5, boost 1.42.
 </p>
    <div class="table">
                                                                      
 
                                                                      
-<!--l. 386--><p class="indent" >   <a 
+<!--l. 387--><p class="indent" >   <a 
  id="x1-140021"></a></p><hr class="float" /><div class="float" 
 >
                                                                      
                                                                      
 
                                                                      
-<!--l. 402--><p class="indent" >   <a 
+<!--l. 403--><p class="indent" >   <a 
  id="x1-140032"></a><a 
  id="x1-14004r5"></a><a 
  id="x1-21001r6"></a></p><hr class="float" /><div class="float" 
                                                                      
    </div><hr class="endfloat" />
    </div>
-<!--l. 418--><p class="indent" >   The main conclusions which can be drawn from these results are:
+<!--l. 419--><p class="indent" >   The main conclusions which can be drawn from these results are:
 </p>
      <ul class="itemize1">
      <li class="itemize">Performance   differences   between   hash-based   and   tree-based
      boost  implementation  performs  better  under  heavy  load  (high
      proportion of cache misses), but this is not actually true over all
      results obtained.</li></ul>
-<!--l. 428--><p class="noindent" >Of course these results should not be taken as a substitute for readers carrying
+<!--l. 429--><p class="noindent" >Of course these results should not be taken as a substitute for readers carrying
 out performance testing on their own systems using realistic test cases
 relevant to their own usage.
 </p>
-   <!--l. 431--><div class="lstinputlisting">
+   <!--l. 432--><div class="lstinputlisting">
 <a 
  id="x1-14005"></a>
 <br />
    </div>
    <h3 class="sectionHead"><span class="titlemark">8    </span> <a 
  id="x1-150008"></a>Variations</h3>
-<!--l. 435--><p class="noindent" >There are numerous ways in which basic caching behaviour can be extended.
+<!--l. 436--><p class="noindent" >There are numerous ways in which basic caching behaviour can be extended.
 Here are a few suggestions.
                                                                      
 
                                                                      
-</p><!--l. 438--><p class="noindent" >
+</p><!--l. 439--><p class="noindent" >
 </p>
    <h4 class="subsectionHead"><span class="titlemark">8.1    </span> <a 
  id="x1-160008.1"></a>Definition of &#8220;capacity&#8221;</h4>
-<!--l. 440--><p class="noindent" >In many applications for caches, it is required to define the cache capacity
+<!--l. 441--><p class="noindent" >In many applications for caches, it is required to define the cache capacity
 not simply as a maximum number of cached elements, but rather in terms of
 the total of some measure on the elements. For example, a utility for
 browsing a collection of image files might include a cache of loaded
 consumed by cached objects could be controlled and the number of
 images cached automatically adjusted in response to the aggregate
 size.
-</p><!--l. 453--><p class="indent" >   Implementation of such a cache is left as an exercise for the reader. Hint:
+</p><!--l. 454--><p class="indent" >   Implementation of such a cache is left as an exercise for the reader. Hint:
 It will be necessary to provide some mechanism (another function object?) for
 determining the capacity consumed by each stored record, to track the
 aggregate total currently cached, and to call the <span 
 class="pcrr7t-x-x-109">evict() </span>method within a
 loop to possibly free up multiple elements in order to make sufficient space
 for insertion of a single large elements.
-</p><!--l. 460--><p class="noindent" >
+</p><!--l. 461--><p class="noindent" >
 </p>
    <h4 class="subsectionHead"><span class="titlemark">8.2    </span> <a 
  id="x1-170008.2"></a>Thread safety</h4>
-<!--l. 462--><p class="noindent" >It should be obvious how to trivially make a cache implementation
+<!--l. 463--><p class="noindent" >It should be obvious how to trivially make a cache implementation
 thread-safe by addition of a suitable mutex as a member and locking it for
 the scope of the access operation. Bear in mind that caches can easily become
 a serialisation bottleneck because, unlike simpler containers with no state
                                                                      
 
                                                                      
-</p><!--l. 476--><p class="indent" >   In some cases the best solution might be for multiple threads to each
+</p><!--l. 477--><p class="indent" >   In some cases the best solution might be for multiple threads to each
 maintain their own independent cache: the inefficiency introduced by
 duplication of some cache-miss calculations must be weighed against the
 overheads introduced by sharing a cache between multiple threads.
-</p><!--l. 480--><p class="noindent" >
+</p><!--l. 481--><p class="noindent" >
 </p>
    <h4 class="subsectionHead"><span class="titlemark">8.3    </span> <a 
  id="x1-180008.3"></a>Compressed stored values</h4>
-<!--l. 482--><p class="noindent" >Depending on the nature of the stored result values in the cache, it may be
+<!--l. 483--><p class="noindent" >Depending on the nature of the stored result values in the cache, it may be
 possible to reduce the amount of memory used by the cache (or, more usefully,
 cache more records in the same amount of memory) by compressing the
 result values. Storing a value in the cache will incur a compression overhead,
 to obtain the value then it may be worth the expense to obtain an
 overall improvement in system performance through a better cache hit
 rate.
-</p><!--l. 491--><p class="indent" >   A further refinement might be two levels of caching; one holding
+</p><!--l. 492--><p class="indent" >   A further refinement might be two levels of caching; one holding
 compressed values, and a smaller one holding the most recent decompressed
 values in anticipation of near-term reuse.
-</p><!--l. 495--><p class="indent" >   See also <a 
+</p><!--l. 496--><p class="indent" >   See also <a 
 href="http://www.boost.org/doc/libs/1_42_0/libs/flyweight/doc/index.html" ><span 
 class="pcrr7t-x-x-109">boost::flyweight</span></a>, which may be of use as a cache-size
 reducer in situations where many records in the cache actually hold the
 same value (this would imply the cached function is &#8220;many-to-one&#8221; in
 character).
-</p><!--l. 500--><p class="noindent" >
+</p><!--l. 501--><p class="noindent" >
 </p>
    <h4 class="subsectionHead"><span class="titlemark">8.4    </span> <a 
  id="x1-190008.4"></a>Alternative strategies to LRU</h4>
-<!--l. 502--><p class="noindent" >For some specialist use cases, alternative strategies might be appropriate.
+<!--l. 503--><p class="noindent" >For some specialist use cases, alternative strategies might be appropriate.
 For example, a most-recently-used (MRU) replacement strategy evicts the
 record most recently added to the cache; this might be relevant where cached
 results generated earliest in the lifetime of a program are most likely to be
                                                                      
 
                                                                      
-</p><!--l. 513--><p class="noindent" >
+</p><!--l. 514--><p class="noindent" >
 </p>
    <h4 class="subsectionHead"><span class="titlemark">8.5    </span> <a 
  id="x1-200008.5"></a>Pooling</h4>
-<!--l. 515--><p class="noindent" >Consider a fully populated cache, which should be considered to be the
+<!--l. 516--><p class="noindent" >Consider a fully populated cache, which should be considered to be the
 normal state for caches after they have been in existence for some time.
 Cache misses result in the deletion of an evicted stored result value,
 followed by the immediate creation of a new one. If the value type is
 particularly expensive to create there may be a potential optimisation in
 recycling evicted values through a simple object pool for more efficient
 reuse.
-</p><!--l. 525--><p class="noindent" >
+</p><!--l. 526--><p class="noindent" >
 </p>
    <h3 class="sectionHead"><span class="titlemark">A    </span> <a 
  id="x1-21000A"></a>Timer utility class</h3>
-<!--l. 526--><p class="noindent" ><a 
+<!--l. 527--><p class="noindent" ><a 
 href="#x1-21001r6">Listing&#x00A0;6</a> contains the timer utility class used by the performance testing
 code in <a 
-href="#x1-14004r5">Listing&#x00A0;5</a>. </p><!--l. 527--><div class="lstinputlisting">
+href="#x1-14004r5">Listing&#x00A0;5</a>. </p><!--l. 528--><div class="lstinputlisting">
 <a 
  id="x1-21001r6"></a>
 <a 

File article/lru.pdf

Binary file modified.

File test/makefile

View file
 #  OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.            #
 ##############################################################################
 
-all:		lru_test lru_perf # lru.pdf # lru.html
+all:		lru_test lru_perf
 
 CACHE_HEADERS=$(wildcard ../include/*cache*.h)