Memoization for compile time functions

Question

I'd like to lazily evaluate functions. Since calculating the return values are expensive, I have to use memoization, especially for the called subfunctions, otherwise the calculation's time complexity explodes exponentially. I need the results at compile time. (I am writing a library that provides various compile time templates based on the provided strings.) So in short, I need memoization during compile time.

std.functional.memoize does not work CT, so it's out of question. DMD and LDC is not clever enough to memoize pure functions, at least that's the result of my experiments for simple pure functions: The way I tested whether it caches the results:

Using simple arguments:

int sumN(int n) pure {
    int result = 0;
    for (int i = 0; i<=n; i++) result += i;
    return result;
}

void main() {
    enum sumMany =    sumN(2000000);
    enum sumMany2 =   sumN(2000000);
    writeln(sumMany, " ", sumMany2);
}

Using template arguments:

int sumN(int n)() pure {
    int result = 0;
    for (int i = 0; i<=n; i++) result += i;
    return result;
}

void main() {
    enum sumMany =    sumN!2000000;
    enum sumMany2 =   sumN!2000000;
    writeln(sumMany, " ", sumMany2);
}

Timing the compilation (calling sumN once vs twice):

time dmd -O -release -inline -boundscheck=off repeatpure.d

or

time ldc2 -O5 -release -inline -boundscheck=off repeatpure.d

The compilation time is always twice as long when I have both enums in the source code.

Is there any way to memoize CT functions?

score 5 · Accepted Answer · edited Mar 28 '16 at 03:49

5

Templates with all the same arguments should only be instantiated once, so what you want to do is make the result a constant value (enum in this case) inside the template itself.

Your template argument function would only be instantiated once, but it would be run for every time you did it. Make a helper function that is only run once:

template sumN(int n) {
    int helper() {
        int result = 0;
        for (int i = 0; i<=n; i++) result += i;
        return result;
    }

    // this is run once per unique argument group
    enum sumN = helper();
}

void main() {
    // so both of these now reference the same constant
    enum sumMany =    sumN!2000000;
    enum sumMany2 =   sumN!2000000;
    writeln(sumMany, " ", sumMany2);
}

It isn't exactly memoization but it might be good enough for what you need - notice the compile time is the same if you comment one of those sumMany.

edited Mar 28 '16 at 03:49

Max Alibaev

681
7
17

answered Mar 27 '16 at 18:53

Adam D. Ruppe

25,382
4
41
60

Exactly what I was looking for! Thanks! – Tamas Mar 27 '16 at 18:55
Some very important detail: helper() must be inside the template. int helper(int n) pure {...} outside the template & called from the template is just as slow as the other solutions. (Why??) – Tamas Apr 03 '16 at 18:30
Tamas: are you sure? It shouldn't make a difference and indeed doesn't when I try it here. – Adam D. Ruppe Apr 03 '16 at 19:06
I was wrong. Indeed, there's no difference. Thanks, and sorry for the noise! – Tamas Apr 03 '16 at 20:09

Memoization for compile time functions

1 Answers1