www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.bugs - [Issue 8743] New: Add support for memoizing class methods

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

           Summary: Add support for memoizing class methods
           Product: D
           Version: D2
          Platform: All
        OS/Version: All
            Status: NEW
          Severity: enhancement
          Priority: P2
         Component: Phobos
        AssignedTo: nobody puremagic.com
        ReportedBy: andrej.mitrovich gmail.com


--- Comment #0 from Andrej Mitrovic <andrej.mitrovich gmail.com> 2012-10-01
12:33:24 PDT ---
This was asked for here:
http://stackoverflow.com/questions/12677498/how-do-i-use-std-functional-memoize-inside-a-class

There could be use-cases for this even though methods usually depend on
internal class state. Perhaps if the method was  pure it would be safe to use
it. Anyway I have an experimental implementation: 

module test;

import std.stdio;
import std.traits;
import std.typecons;
import std.datetime;

template isClassStruct(alias fun)
{
    enum bool isClassStruct = (is(fun == class) || is(fun == struct));
}

mixin template memoize(alias fun, uint maxSize = uint.max)
    if (isClassStruct!(__traits(parent, fun)))
{
    ReturnType!fun opCall(ParameterTypeTuple!fun args)
    {
        static ReturnType!fun[Tuple!(typeof(args))] memo;
        auto t = tuple(args);
        auto p = t in memo;
        if (p) return *p;
        static if (maxSize != uint.max)
        {
            if (memo.length >= maxSize) memo = null;
        }

        mixin("auto r = this." ~ __traits(identifier, fun) ~ "(args);");
        memo[t] = r;
        return r;
    }    
}

class A 
{
    int slowFunc(int a, int b) 
    { 
        int result;
        foreach (_; 0 .. 1024)
        {
            result += a;
            result += b;
        }
        return result;
    }

    mixin memoize!slowFunc fastFunc;
}

enum CallCount = 2048;

void main() 
{
    A a = new A;

    auto sw1 = StopWatch(AutoStart.yes);
    foreach (x; 0 .. CallCount)
    {
        a.slowFunc(100, 100);  // 11232 usecs
    }
    sw1.stop();
    writeln(sw1.peek.usecs);

    auto sw2 = StopWatch(AutoStart.yes);
    foreach (x; 0 .. CallCount)
    {
        a.fastFunc(100, 100);  // 302 usecs
    }
    sw2.stop();
    writeln(sw2.peek.usecs);
}

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Oct 01 2012
next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=8743



--- Comment #1 from Andrej Mitrovic <andrej.mitrovich gmail.com> 2012-10-01
13:19:45 PDT ---
Here's another one that has rehashing ability: http://dpaste.dzfl.pl/abb6086f

But it comes with a runtime cost of a boolean check. I'd love to be able to
make rehash a compile-time parameter, but I can't seem to make opCall work with
it. Even if it did work I'd have to figure out a way to store the hash outside
of the template since each template instance has it's own internal hash.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Oct 01 2012
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=8743



--- Comment #2 from Andrej Mitrovic <andrej.mitrovich gmail.com> 2012-10-01
13:23:08 PDT ---
Ahh, I've got it! Templates have their own scope, so the hash can go outside:

http://dpaste.dzfl.pl/4ba280c7

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Oct 01 2012
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=8743


bearophile_hugs eml.cc changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |bearophile_hugs eml.cc


--- Comment #3 from bearophile_hugs eml.cc 2012-10-01 14:00:29 PDT ---
(In reply to comment #2)

 Ahh, I've got it! Templates have their own scope, so the hash can go outside:
 
 http://dpaste.dzfl.pl/4ba280c7


I suggest to put a copy of it in Bugzilla (as attach or just pasting it here),
so it's readable even if dpaste is down, or it deletes this paste, etc.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Oct 01 2012
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=8743



--- Comment #4 from bearophile_hugs eml.cc 2012-10-01 14:03:50 PDT ---
void rehash() { memo = null; }

Maybe do you mean something like this?

void rehash() { memo.rehash; }
void clear() { memo = null; }

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Oct 01 2012
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=8743



--- Comment #5 from Andrej Mitrovic <andrej.mitrovich gmail.com> 2012-10-02
02:25:42 PDT ---
(In reply to comment #4)

 void rehash() { memo = null; }
 
 Maybe do you mean something like this?
 
 void rehash() { memo.rehash; }
 void clear() { memo = null; }


Absolutely. I've used the wrong term here. Here's the snippet:

module test;

import std.stdio;
import std.traits;
import std.typecons;
import std.datetime;

template isClassStruct(alias fun)
{
    enum bool isClassStruct = (is(fun == class) || is(fun == struct));
}

mixin template memoize(alias fun, uint maxSize = uint.max)
    if (isClassStruct!(__traits(parent, fun)))
{
    ReturnType!fun[Tuple!(ParameterTypeTuple!fun)] memo;

    void rehash() { memo.rehash(); }
    void clear() { memo = null; }

    ReturnType!fun opCall(ParameterTypeTuple!fun args)
    {
        auto t = tuple(args);
        auto p = t in memo;
        if (p) return *p;
        static if (maxSize != uint.max)
        {
            if (memo.length >= maxSize) memo = null;
        }

        mixin("auto r = this." ~ __traits(identifier, fun) ~ "(args);");
        memo[t] = r;
        return r;
    }
}

class A 
{
    int field;

    int slowFunc(int a, int b) 
    { 
        int result;
        foreach (_; 0 .. 1024)
        {
            result += a;
            result += b;
        }
        return result + field;
    }

    mixin memoize!slowFunc fastFunc;
}

enum CallCount = 2048;

void main() 
{
    A a = new A;

    int z = a.fastFunc(100, 100);
    writeln(z);
    a.field = 50;
    a.fastFunc.clear();
    z = a.fastFunc(100, 100);
    writeln(z);
}

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Oct 02 2012
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=8743



--- Comment #6 from bearophile_hugs eml.cc 2012-10-02 02:54:21 PDT ---
(In reply to comment #5)


     enum bool isClassStruct = (is(fun == class) || is(fun == struct));


No need for extra parentheses:

enum bool isClassStruct = is(fun == class) || is(fun == struct);




     void rehash() { memo.rehash(); }


I think () aren't needed, even with -property.



     int slowFunc(int a, int b)


If the arguments are constant it doesn't work:
int slowFunc(in int a, in int b)



     mixin memoize!slowFunc fastFunc;


This mixin template is useful. A disadvantage is that it doesn't follow the API
(usage) of the Phobos memoize. So maybe it needs a different name, like
memoizeMethod, or something.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Oct 02 2012
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=8743



--- Comment #7 from Andrej Mitrovic <andrej.mitrovich gmail.com> 2012-10-02
03:05:48 PDT ---
(In reply to comment #6)

 If the arguments are constant it doesn't work:
 int slowFunc(in int a, in int b)


Seems to be a new bug related to Tuple: Issue 8746

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Oct 02 2012
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=8743



--- Comment #8 from Andrej Mitrovic <andrej.mitrovich gmail.com> 2012-10-02
03:08:44 PDT ---
(In reply to comment #6)

 This mixin template is useful. A disadvantage is that it doesn't follow the API
 (usage) of the Phobos memoize. So maybe it needs a different name, like
 memoizeMethod, or something.


Yes. I couldn't make it have the same syntax because of the requirement of the
`this` reference.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Oct 02 2012
prev sibling next sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=8743



--- Comment #9 from Andrej Mitrovic <andrej.mitrovich gmail.com> 2012-10-02
03:12:47 PDT ---
(In reply to comment #8)

 (In reply to comment #6)

 This mixin template is useful. A disadvantage is that it doesn't follow the API
 (usage) of the Phobos memoize. So maybe it needs a different name, like
 memoizeMethod, or something.


 
 Yes. I couldn't make it have the same syntax because of the requirement of the
 `this` reference.


Also I'm unsure about recursive calls. Existing memoize allows you to
recursively call a memoized function.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Oct 02 2012
prev sibling parent d-bugmail puremagic.com writes:
http://d.puremagic.com/issues/show_bug.cgi?id=8743



--- Comment #10 from Andrej Mitrovic <andrej.mitrovich gmail.com> 2012-10-02
03:17:42 PDT ---
(In reply to comment #9)

 (In reply to comment #8)

 (In reply to comment #6)

 This mixin template is useful. A disadvantage is that it doesn't follow the API
 (usage) of the Phobos memoize. So maybe it needs a different name, like
 memoizeMethod, or something.


 
 Yes. I couldn't make it have the same syntax because of the requirement of the
 `this` reference.


 
 Also I'm unsure about recursive calls.


And I think I've uncovered yet another bug:

class A 
{
    int slowFunc(int a, int b) 
    { 
        int result;

        /* Error: function expected before (), not mixin memoize!(slowFunc)
fastFunc; */
        if (a > 1)
            return fastFunc(a-1, b);

        return result;
    }

    mixin memoize!slowFunc fastFunc;
}

If I replace 'return fastFunc(a-1, b);' with 'return this.fastFunc(a-1, b)' it
works.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
Oct 02 2012