www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.bugs - [Issue 11644] New: EvictingStrategy.LRU for std.functional.memoize

reply d-bugmail puremagic.com writes:
https://d.puremagic.com/issues/show_bug.cgi?id=11644

           Summary: EvictingStrategy.LRU for std.functional.memoize
           Product: D
           Version: D2
          Platform: All
        OS/Version: All
            Status: NEW
          Severity: enhancement
          Priority: P2
         Component: Phobos
        AssignedTo: nobody puremagic.com
        ReportedBy: bearophile_hugs eml.cc


--- Comment #0 from bearophile_hugs eml.cc 2013-11-29 12:10:15 PST ---
In DMD 2.065alpha this is the function std.functional.memoize:

ReturnType!fun memoize(alias fun, uint maxSize =
(uint).max)(ParameterTypeTuple!fun args); 

Where:
The maxSize parameter is a cutoff for the cache size. If upon a miss the length
of the hash table is found to be maxSize, the table is simply cleared. 



In Python3+ library there is something similar, but I find its strategy a
little more useful:

http://docs.python.org/3/library/functools.html#functools.lru_cache

  functools.lru_cache(maxsize=128, typed=False)
    Decorator to wrap a function with a memoizing callable that saves up to the
maxsize most recent calls. It can save time when an expensive or I/O bound
function is periodically called with the same arguments.

    Since a dictionary is used to cache results, the positional and keyword
arguments to the function must be hashable.

    If maxsize is set to None, the LRU feature is disabled and the cache can
grow without bound. The LRU feature performs best when maxsize is a
power-of-two.

    If typed is set to True, function arguments of different types will be
cached separately. For example, f(3) and f(3.0) will be treated as distinct
calls with distinct results.

    To help measure the effectiveness of the cache and tune the maxsize
parameter, the wrapped function is instrumented with a cache_info() function
that returns a named tuple showing hits, misses, maxsize and currsize. In a
multi-threaded environment, the hits and misses are approximate.

    The decorator also provides a cache_clear() function for clearing or
invalidating the cache.

    The original underlying function is accessible through the __wrapped__
attribute. This is useful for introspection, for bypassing the cache, or for
rewrapping the function with a different cache.

    An LRU (least recently used) cache works best when the most recent calls
are the best predictors of upcoming calls (for example, the most popular
articles on a news server tend to change each day). The cache’s size limit
assures that the cache does not grow without bound on long-running processes
such as web servers.



The cache_info() is useful, but what's more useful is having a LRU strategy
instead of just clearing the cache. So I suggest to add an enum argument to
specify a different strategy:

ReturnType!fun memoize(alias fun, uint maxSize = (uint).max, EvictingStrategy
strategy=EvictingStrategy.clear)(ParameterTypeTuple!fun args); 


enum EvictingStrategy { clear, LRU }

-- 
Configure issuemail: https://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Nov 29 2013
parent d-bugmail puremagic.com writes:
https://d.puremagic.com/issues/show_bug.cgi?id=11644



--- Comment #1 from bearophile_hugs eml.cc 2013-11-29 12:38:15 PST ---
A simpler strategy is the random replacement (but currently the low-level API
of associative arrays doesn't allow to extract a random bucket):

enum EvictingStrategy { clearAll, LRU, random }

-- 
Configure issuemail: https://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Nov 29 2013