This is a live mirror of the Perl 5 development currently hosted at https://github.com/perl/perl5
Upgrade to Memoize 0.66.
authorJarkko Hietaniemi <jhi@iki.fi>
Wed, 12 Sep 2001 17:41:49 +0000 (17:41 +0000)
committerJarkko Hietaniemi <jhi@iki.fi>
Wed, 12 Sep 2001 17:41:49 +0000 (17:41 +0000)
p4raw-id: //depot/perl@12006

lib/Memoize.pm
lib/Memoize/AnyDBM_File.pm
lib/Memoize/Expire.pm
lib/Memoize/README
lib/Memoize/TODO
lib/Memoize/t/expire_module_t.t
lib/Memoize/t/speed.t

index 219a0ff..6907400 100644 (file)
@@ -8,10 +8,10 @@
 # same terms as Perl itself.  If in doubt, 
 # write to mjd-perl-memoize+@plover.com for a license.
 #
-# Version 0.65 beta $Revision: 1.17 $ $Date: 2000/10/24 04:33:49 $
+# Version 0.66 $Revision: 1.18 $ $Date: 2001/06/24 17:16:47 $
 
 package Memoize;
-$VERSION = '0.65';
+$VERSION = '0.66';
 
 # Compile-time constants
 sub SCALAR () { 0 } 
@@ -390,7 +390,7 @@ Options include:
 `Memoizing' a function makes it faster by trading space for time.  It
 does this by caching the return values of the function in a table.
 If you call the function again with the same arguments, C<memoize>
-jmups in and gives you the value out of the table, instead of letting
+jumps in and gives you the value out of the table, instead of letting
 the function compute the value all over again.
 
 Here is an extreme example.  Consider the Fibonacci sequence, defined
@@ -551,13 +551,13 @@ might look like this:
          $hash{B} ||= 2;
          $hash{C} ||= 7;
 
-         join($;, $a, map ($_ => $hash{$_}) sort keys %hash);
+         join(',', $a, map ($_ => $hash{$_}) sort keys %hash);
        }
 
 Each of the argument lists above comes out of the C<normalize_f>
 function looking exactly the same, like this:
 
-       OUCH^\B^\2^\C^\7
+       OUCH,B,2,C,7
 
 You would tell C<Memoize> to use this normalizer this way:
 
@@ -569,28 +569,28 @@ that it computed for one argument list and return it as the result of
 calling the function with the other argument list, even if the
 argument lists look different.
 
-The default normalizer just concatenates the arguments with C<$;> in
-between.  This always works correctly for functions with only one
-string argument, and also when the arguments never contain C<$;>
-(which is normally character #28, control-\.  )  However, it can
-confuse certain argument lists:
+The default normalizer just concatenates the arguments with character
+28 in between.  (In ASCII, this is called FS or control-\.)  This
+always works correctly for functions with only one string argument,
+and also when the arguments never contain character 28.  However, it
+can confuse certain argument lists:
 
        normalizer("a\034", "b")
        normalizer("a", "\034b")
        normalizer("a\034\034b")
 
-for example.  
+for example.
 
 Since hash keys are strings, the default normalizer will not
 distinguish between C<undef> and the empty string.  It also won't work
-when the function's arguments are references.  For example, consider
-function C<g> which gets two arguments: A number, and a reference to
+when the function's arguments are references.  For example, consider a
+function C<g> which gets two arguments: A number, and a reference to
 an array of numbers:
 
        g(13, [1,2,3,4,5,6,7]);
 
 The default normalizer will turn this into something like
-C<"13\024ARRAY(0x436c1f)">.  That would be all right, except that a
+C<"13\034ARRAY(0x436c1f)">.  That would be all right, except that a
 subsequent array of numbers might be stored at a different location
 even though it contains the same data.  If this happens, C<Memoize>
 will think that the arguments are different, even though they are
@@ -615,7 +615,7 @@ returns a value which depends on the current hour of the day:
          return $line;
        }
 
-At 10:23, this function generates the tenth line of a data file; at
+At 10:23, this function generates the 10th line of a data file; at
 3:45 PM it generates the 15th line instead.  By default, C<Memoize>
 will only see the $problem_type argument.  To fix this, include the
 current hour in the normalizer:
@@ -635,7 +635,7 @@ Normally, C<Memoize> caches your function's return values into an
 ordinary Perl hash variable.  However, you might like to have the
 values cached on the disk, so that they persist from one run of your
 program to the next, or you might like to associate some other
-interesting semantics with the cached values.  
+interesting semantics with the cached values.
 
 There's a slight complication under the hood of C<Memoize>: There are
 actually I<two> caches, one for scalar values and one for list values.
@@ -650,7 +650,7 @@ the following four strings:
        MEMORY
        FAULT
        MERGE
-        HASH                                                           
+        HASH
 
 or else it must be a reference to a list whose first element is one of
 these four strings, such as C<[HASH, arguments...]>.
@@ -677,7 +677,7 @@ complete details about C<tie>.
 
 A typical example is:
 
-        use DB_File; 
+        use DB_File;
         tie my %cache => 'DB_File', $filename, O_RDWR|O_CREAT, 0666;
         memoize 'function', SCALAR_CACHE => [HASH => \%cache];
 
@@ -695,14 +695,14 @@ because all its results have been precomputed.
 This option is B<strongly deprecated> and will be removed
 in the B<next> release of C<Memoize>.  Use the C<HASH> option instead.
 
-        memoize ... [TIE, ARGS...]
+        memoize ... [TIE, PACKAGE, ARGS...]
 
 is merely a shortcut for
 
-        tie my %cache, ARGS...;
+        require PACKAGE;
+        tie my %cache, PACKAGE, ARGS...;
         memoize ... [HASH => \%cache];
 
-
 =item C<FAULT>
 
 C<FAULT> means that you never expect to call the function in scalar
@@ -737,12 +737,12 @@ caches the list C<(3)> in the list cache.  The third call doesn't call
 the real C<pi> function; it gets the value from the scalar cache.
 
 Obviously, the second call to C<pi> is a waste of time, and storing
-its return value is a waste of space.  Specifying C<LIST_CACHE
-=E<gt> MERGE> will make C<memoize> use the same cache for scalar and
-list context return values, so that the second call uses the scalar
-cache that was populated by the first call.  C<pi> ends up being
-cvalled only once, and both subsequent calls return C<3> from the
-cache, regardless of the calling context.
+its return value is a waste of space.  Specifying C<LIST_CACHE =E<gt>
+MERGE> will make C<memoize> use the same cache for scalar and list
+context return values, so that the second call uses the scalar cache
+that was populated by the first call.  C<pi> ends up being called only
+once, and both subsequent calls return C<3> from the cache, regardless
+of the calling context.
 
 Another use for C<MERGE> is when you want both kinds of return values
 stored in the same disk file; this saves you from having to deal with
@@ -783,8 +783,6 @@ without synchronizing the database.  So what you can do instead is
 
     $SIG{INT} = sub { unmemoize 'function' };
 
-Thanks to Jonathan Roy for discovering a use for C<unmemoize>.
-
 C<unmemoize> accepts a reference to, or the name of a previously
 memoized function, and undoes whatever it did to provide the memoized
 version in the first place, including making the name refer to the
@@ -797,7 +795,7 @@ croaks.
 =head2 C<flush_cache>
 
 C<flush_cache(function)> will flush out the caches, discarding I<all>
-the cached data.  The argument may be a funciton name or a reference
+the cached data.  The argument may be a function name or a reference
 to a function.  For finer control over when data is discarded or
 expired, see the documentation for C<Memoize::Expire>, included in
 this package.
@@ -809,7 +807,7 @@ method, this will cause a run-time error.
 An alternative approach to cache flushing is to use the C<HASH> option
 (see above) to request that C<Memoize> use a particular hash variable
 as its cache.  Then you can examine or modify the hash at any time in
-any way you desire.
+any way you desire.  You may flush the cache by using C<%hash = ()>. 
 
 =head1 CAVEATS
 
@@ -955,6 +953,9 @@ function (or when your program exits):
 Include the `nstore' option to have the C<Storable> database written
 in `network order'.  (See L<Storable> for more details about this.)
 
+The C<flush_cache()> function will raise a run-time error unless the
+tied package provides a C<CLEAR> method.
+
 =head1 EXPIRATION SUPPORT
 
 See Memoize::Expire, which is a plug-in module that adds expiration
@@ -968,21 +969,21 @@ is available on CPAN as Memoize::ExpireLRU.
 
 The test suite is much better, but always needs improvement.
 
-There used to be some problem with the way C<goto &f> works under
-threaded Perl, because of the lexical scoping of C<@_>.  This is a bug
-in Perl, and until it is resolved, Memoize won't work with these
-Perls.  This is probably still the case, although I have not been able
-to try it out.  If you encounter this problem, you can fix it by
-chopping the source code a little.  Find the comment in the source
-code that says C<--- THREADED PERL COMMENT---> and comment out the
-active line and uncomment the commented one.  Then try it again.
+There is some problem with the way C<goto &f> works under threaded
+Perl, perhaps because of the lexical scoping of C<@_>.  This is a bug
+in Perl, and until it is resolved, memoized functions will see a
+slightly different C<caller()> and will perform a little more slowly
+on threaded perls than unthreaded perls.
 
 Here's a bug that isn't my fault: Some versions of C<DB_File> won't
 let you store data under a key of length 0.  That means that if you
 have a function C<f> which you memoized and the cache is in a
 C<DB_File> database, then the value of C<f()> (C<f> called with no
 arguments) will not be memoized.  Let us all breathe deeply and repeat
-this mantra: ``Gosh, Keith, that sure was a stupid thing to do.''
+this mantra: ``Gosh, Keith, that sure was a stupid thing to do.''  If
+this is a big problem, you can write a tied hash class which is a
+front-end to C<DB_File> that prepends <x> to every key before storing
+it.
 
 =head1 MAILING LIST
 
@@ -1000,33 +1001,40 @@ memoization and about the internals of Memoize that appeared in The
 Perl Journal, issue #13.  (This article is also included in the
 Memoize distribution as `article.html'.)
 
+My upcoming book will discuss memoization (and many other fascinating
+topics) in tremendous detail.  It will be published by Morgan Kaufmann
+in 2002, possibly under the title I<Perl Advanced Techniques
+Handbook>.  It will also be available on-line for free.  For more
+information, visit http://perl.plover.com/book/ .
+
 To join a mailing list for announcements about C<Memoize>, send an
 empty message to C<mjd-perl-memoize-request@plover.com>.  This mailing
 list is for announcements only and has extremely low traffic---about
-four messages per year.
+two messages per year.
 
 =head1 COPYRIGHT AND LICENSE
 
 Copyright 1998, 1999, 2000, 2001  by Mark Jason Dominus
 
 This library is free software; you may redistribute it and/or modify
-it under the same terms as Perl itself. 
+it under the same terms as Perl itself.
 
 =head1 THANK YOU
 
 Many thanks to Jonathan Roy for bug reports and suggestions, to
 Michael Schwern for other bug reports and patches, to Mike Cariaso for
 helping me to figure out the Right Thing to Do About Expiration, to
-Joshua Gerth, Joshua Chamas, Jonathan Roy, Mark D. Anderson, and
-Andrew Johnson for more suggestions about expiration, to Brent Powers
-for the Memoize::ExpireLRU module, to Ariel Scolnicov for delightful
-messages about the Fibonacci function, to Dion Almaer for
+Joshua Gerth, Joshua Chamas, Jonathan Roy (again), Mark D. Anderson,
+and Andrew Johnson for more suggestions about expiration, to Brent
+Powers for the Memoize::ExpireLRU module, to Ariel Scolnicov for
+delightful messages about the Fibonacci function, to Dion Almaer for
 thought-provoking suggestions about the default normalizer, to Walt
 Mankowski and Kurt Starsinic for much help investigating problems
 under threaded Perl, to Alex Dudkevich for reporting the bug in
 prototyped functions and for checking my patch, to Tony Bass for many
-helpful suggestions, to Philippe Verdret for enlightening discussion
-of Hook::PrePostCall, to Nat Torkington for advice I ignored, to Chris
+helpful suggestions, to Jonathan Roy (again) for finding a use for
+C<unmemoize()>, to Philippe Verdret for enlightening discussion of
+C<Hook::PrePostCall>, to Nat Torkington for advice I ignored, to Chris
 Nandor for portability advice, to Randal Schwartz for suggesting the
 'C<flush_cache> function, and to Jenda Krynicky for being a light in
 the world.
@@ -1034,4 +1042,5 @@ the world.
 Special thanks to Jarkko Hietaniemi, the 5.8.0 pumpking, for including
 this module in the core and for his patient and helpful guidance
 during the integration process.
+
 =cut
index 89ef0e1..91f9609 100644 (file)
@@ -19,6 +19,8 @@ my $verbose = 1;
 my $mod;
 for $mod (@ISA) {
 #  (my $truemod = $mod) =~ s/^Memoize:://;
+#  my $file = "$mod.pm";
+#  $file =~ s{::}{/}g;
   if (eval "require $mod") {
     print STDERR "AnyDBM_File => Selected $mod.\n" if $Verbose;
     @ISA = ($mod);     # if we leave @ISA alone, warnings abound
index 517ce34..8bd5999 100644 (file)
@@ -3,7 +3,7 @@ package Memoize::Expire;
 # require 5.00556;
 use Carp;
 $DEBUG = 0;
-$VERSION = '0.65';
+$VERSION = '0.66';
 
 # This package will implement expiration by prepending a fixed-length header
 # to the font of the cached data.  The format of the header will be:
@@ -18,6 +18,13 @@ sub _header_size () { length(_header_fmt) }
 #         TIE => [Memoize::Expire, LIFETIME => sec, NUM_USES => n,
 #                 TIE => [...] ]
 
+BEGIN {
+  eval {require Time::HiRes};
+  unless ($@) {
+    Time::HiRes->import('time');
+  }
+}
+
 sub TIEHASH {
   my ($package, %args) = @_;
   my %cache;
@@ -54,7 +61,7 @@ sub STORE {
 sub FETCH {
   $DEBUG and print STDERR " >> Fetch cached value for $_[1]\n";
   my ($data, $last_access, $expire_time, $num_uses_left) = _get_item($_[0]{C}{$_[1]});
-  $DEBUG and print STDERR " >>   (ttl: ", ($expire_time-time), ", nuses: $num_uses_left)\n";
+  $DEBUG and print STDERR " >>   (ttl: ", ($expire_time-time()), ", nuses: $num_uses_left)\n";
   $num_uses_left--;
   $last_access = time;
   _set_header(@_, $data, $last_access, $expire_time, $num_uses_left);
@@ -113,8 +120,6 @@ sub _get_header  {
 
 1;
 
-# Below is the stub of documentation for your module. You better edit it!
-
 =head1 NAME 
 
 Memoize::Expire - Plug-in module for automatic expiration of memoized values
@@ -123,7 +128,7 @@ Memoize::Expire - Plug-in module for automatic expiration of memoized values
 
   use Memoize;
   use Memoize::Expire;
-  tie my %cache => 'Memoize::Expire', 
+  tie my %cache => 'Memoize::Expire',
                     LIFETIME => $lifetime,    # In seconds
                     NUM_USES => $n_uses;
 
@@ -224,6 +229,11 @@ STORE
 Given a function argument and the corresponding function value, store
 them into the cache.
 
+=item
+CLEAR
+
+(Optional.)  Flush the cache completely.
+
 =back
 
 The user who wants the memoization cache to be expired according to
@@ -262,7 +272,7 @@ cache item after ten seconds.
 
        sub TIEHASH {
          my ($package, %args) = @_;
-          my $cache = $args{$HASH} || {};
+          my $cache = $args{HASH} || {};
          bless $cache => $package;
        }
 
@@ -299,7 +309,7 @@ entirely absent or was older than ten seconds.
 You should always support a C<HASH> argument to C<TIEHASH> that ties
 the underlying cache so that the user can specify that the cache is
 also persistent or that it has some other interesting semantics.  The
-example above demonstrates how to do this, as does C<Memozie::Expire>.
+example above demonstrates how to do this, as does C<Memoize::Expire>.
 
 Another sample module, C<Memoize::Saves>, is included with this
 package.  It implements a policy that allows you to specify that
@@ -326,7 +336,7 @@ This module is experimental, and may contain bugs.  Please report bugs
 to the address below.
 
 Number-of-uses is stored as a 16-bit unsigned integer, so can't exceed
-65535.  
+65535.
 
 Because of clock granularity, expiration times may occur up to one
 second sooner than you expect.  For example, suppose you store a value
@@ -334,9 +344,8 @@ with a lifetime of ten seconds, and you store it at 12:00:00.998 on a
 certain day.  Memoize will look at the clock and see 12:00:00.  Then
 9.01 seconds later, at 12:00:10.008 you try to read it back.  Memoize
 will look at the clock and see 12:00:10 and conclude that the value
-has expired.  Solution: Build an expiration policy module that uses
-Time::HiRes to examine a clock with better granularity.  Contributions
-are welcome.  Send them to:
+has expired.  This will probably not occur if if you have
+C<Time::HiRes> installed.
 
 =head1 AUTHOR
 
@@ -356,6 +365,6 @@ http://www.plover.com/~mjd/perl/Memoize/  (for news and updates)
 I maintain a mailing list on which I occasionally announce new
 versions of Memoize.  The list is for announcements only, not
 discussion.  To join, send an empty message to
-mjd-perl-memoize-request@Plover.com.  
+mjd-perl-memoize-request@Plover.com.
 
 =cut
index 011c4bf..b7abb5f 100644 (file)
@@ -1,7 +1,7 @@
 
 Name:          Memoize
 What:          Transparently speed up functions by caching return values.
-Version:       0.65
+Version:       0.66
 Author:                Mark-Jason Dominus (mjd-perl-memoize+@plover.com)
 
 ################################################################
@@ -25,6 +25,19 @@ If not, please send me a report that mentions which tests failed.
 The address is: mjd-perl-memoize+@plover.com.
 
 ################################################################
+What's new since 0.65:
+
+Test changes only.  
+
+        0.62 was the fist version that would be distributed with Perl.
+        I got so absorbed in integrating it that I wrote some tests
+        that used Time::HiRes.  I knew this was safe because
+        Time::HiRes is also distributed with the same versions of
+        Perl.  I totally forgot that some people will get the module
+        off of CPAN without Perl and they may not have TIme::HiRes.
+        Sorry!
+
+################################################################
 What's new since 0.62:
 
 
index fad3262..5968612 100644 (file)
@@ -1,4 +1,4 @@
-# Version 0.05 alpha $Revision: 1.5 $ $Date: 1999/09/17 14:57:55 $
+# Version 0.05 alpha $Revision: 1.6 $ $Date: 2001/06/24 17:11:26 $
 
 =head1 TO DO
 
@@ -336,10 +336,10 @@ same analysis and make the same adjustments to the hash.  If the
 normalizer could make the adjustments and save the changes in @_, you
 wouldn't have to do it twice. 
 
-=item*
+=item *
 20010623 Add CLEAR methods to tied hash modules.
 
-=item*
+=item *
 20010623 You get a warning if you try to use DB_File as LIST_CACHE,
 because it won't store lists.  But if you use it as the underlying
 cache with an expiration manager in the middle, no warning---the
index 7032f65..3cc3de1 100644 (file)
@@ -2,7 +2,15 @@
 
 use lib '..';
 use Memoize;
-use Time::HiRes 'time';
+BEGIN {
+  eval {require Time::HiRes};
+  if ($@ || $ENV{SLOW}) {
+#    $SLOW_TESTS = 1;
+  } else {
+    'Time::HiRes'->import('time');
+  }
+}
+
 my $DEBUG = 0;
 
 my $n = 0;
@@ -48,7 +56,7 @@ sub now {
   time;
 }
 
-tie my %cache => 'Memoize::Expire', LIFETIME => 8;
+tie my %cache => 'Memoize::Expire', LIFETIME => 10;
 memoize 'now',
     SCALAR_CACHE => [HASH => \%cache ],
     LIST_CACHE => 'FAULT'
@@ -64,42 +72,42 @@ for (1,2,3) {
   ++$n;
   print "not " unless close_enough($when{$_}, time());
   print "ok $n\n";
-  sleep 3 if $_ < 3;
+  sleep 4 if $_ < 3;
   $DEBUG and print "# ", time()-$t0, "\n";
 }
-# values will now expire at T=8, 11, 14
-# it is now T=6
+# values will now expire at T=10, 14, 18
+# it is now T=8
 
-# T+6
+# T+8
 for (1,2,3) {
   $again{$_} = now($_); # Should be the same as before, because of memoization
 }
 
-# T+6
+# T+8
 foreach (1,2,3) {
   ++$n;
   print "not " unless close_enough($when{$_}, $again{$_});
   print "ok $n\n";
 }
 
-wait_until(9.5);  # now(1) expires
+wait_until(12);  # now(1) expires
 print "not " unless close_enough(time, $again{1} = now(1));
 ++$n; print "ok $n\n";
 
-# T+9.5
+# T+12
 foreach (2,3) {                        # Should not have expired yet.
   ++$n;
   print "not " unless close_enough(scalar(now($_)), $again{$_});
   print "ok $n\n";
 }
 
-wait_until(12.5);  # now(2) expires
+wait_until(16);  # now(2) expires
 
-# T+12.5
+# T+16
 print "not " unless close_enough(time, $again{2} = now(2));
 ++$n; print "ok $n\n";
 
-# T+12.5
+# T+16
 foreach (1,3) {  # 1 is good again because it was recomputed after it expired
   ++$n;
   print "not " unless close_enough(scalar(now($_)), $again{$_});
index ef30a81..6d21906 100755 (executable)
@@ -12,15 +12,27 @@ $| = 1;
 # If we don't say anything, maybe nobody will notice.
 # print STDERR "\nWarning: I'm testing the speedup.  This might take up to thirty seconds.\n                    ";
 
+my $COARSE_TIME = 1;
+
+sub times_to_time { my ($u) = times; $u; }
+if ($^O eq 'riscos') {
+  eval {require Time::HiRes; *my_time = \&Time::HiRes::time };
+  if ($@) { *my_time = sub { time }; $COARSE_TIME = 1 }
+} else {
+  *my_time = \&times_to_time;
+}
+
 
 print "1..6\n";
 
+
+
 # This next test finds an example that takes a long time to run, then
 # checks to make sure that the run is actually speeded up by memoization.
 # In some sense, this is the most essential correctness test in the package.  
 #
 # We do this by running the fib() function with successfily larger
-# arguments until we find one that tales at leasrtt $LONG_RUN seconds
+# arguments until we find one that tales at least $LONG_RUN seconds
 # to execute.  Then we memoize fib() and run the same call cagain.  If
 # it doesn't produce the same test in less than one-tenth the time,
 # something is seriously wrong.