Metaprogramming in D is a really slow thing, there must be faster & simpler ways.
(I think there are simpler ways, using a scripting language to create D code before the compilation. I have created a Python templating system that seem to work well enough for C++).

I have written the following code to test compile time optimization regarding a small kernel convolution, the metaGenerated() is as fast as the hand written version. I show it here because it may be interesting to someone.

But currently the metaGenerated() doesn't work if the kernel2 contains floating point values. I think this problem can be solved with a compile time function/template like ToString that works on floating point values too, do you have it?

Bye,
bearophile


import std.stdio: put = writef, putr = writefln;
import std.metastrings: Format, ToString;
static import std.c.time;

double clock() {
    auto t = std.c.time.clock();
    if (t == -1)
        return 0.0;
    else
        return t/cast(double)std.c.time.CLOCKS_PER_SEC;
}

template Tuple(T...) {
    alias T Tuple;
}

template GenTerm(string m, string x, string y, int nr, int nc, int posx, int posy, ker...) {
    static if (ker[nc * posy + posx] == 0)
        const string GenTerm = "";
    else static if (ker[nc * posy + posx] == 1)
        const string GenTerm = Format!("%s[%s+%s][%s+%s] + ",
                                       m,
                                       x,
                                       ToString!(posx - (nc / 2)),
                                       y,
                                       ToString!(posy - (nr / 2)));
    else
        const string GenTerm = Format!("%s * %s[%s+%s][%s+%s] + ",
                                       ToString!(ker[nc * posy + posx]), //error if ker[] isn't integral
                                       m,
                                       x,
                                       ToString!(posx - (nc / 2)),
                                       y,
                                       ToString!(posy - (nr / 2)));
}

template GenConvolutionLine(string m, string x, string y, int nr, int nc, int posx, int posy, ker...) {
    static if (posx < nc)
        const string GenConvolutionLine = GenTerm!(m, x, y, nr, nc, posx, posy, ker) ~
                                          GenConvolutionLine!(m, x, y, nr, nc, posx+1, posy, ker);
    else
        const string GenConvolutionLine = "";
}

template GenConvolution(string m, string x, string y, int nr, int nc, int posy, ker...) {
    static if (posy < nr)
        const string GenConvolution = GenConvolutionLine!(m, x, y, nr, nc, 0, posy, ker) ~
                                      GenConvolution!(m, x, y, nr, nc, posy+1, ker);
    else
        const string GenConvolution = "0";
}

template Convolution(string m, string x, string y, int nc, ker...) {
    const string Convolution = GenConvolution!(m, x, y, ker.length / nc, nc, 0, ker);
}

// ------------------------------------------------------

void dynamic(float[][] inm, float[][] outm, float[] kern, int w, int h) {
    int height = inm.length;
    int width = inm[0].length;

    for (int x = 1; x < width - 1; ++x)
        for (int y = 1; y < height - 1; ++y) {
            float sum = 0.0;
            for (int i = 0; i < w; ++i)
                for (int j = 0; j < h; ++j)
	                sum += kern[j * w + i] * inm[x + i - w / 2][y + j - h / 2];
            outm[x - 1][y - 1] = sum;
        }
}

void handWritten(float[][] inm, float[][] outm) {
    int height = inm.length;
    int width = inm[0].length;

    for (int x = 1; x < width - 1; ++x)
        for (int y = 1; y < height - 1; ++y)
            outm[x - 1][y - 1] = inm[x+1][y] + inm[x-1][y] + inm[x][y-1] + inm[x][y+1] - 4 * inm[x][y];
}

void metaGenerated(kernel...)(float[][] inm, float[][] outm) {
    int height = inm.length;
    int width = inm[0].length;
    //pragma(msg, Convolution!("inm", "x", "y", 3, kernel)); // to see it

    for (int x = 1; x < width - 1; ++x)
        for (int y = 1; y < height - 1; ++y)
            mixin("outm[x - 1][y - 1] = " ~ Convolution!("inm", "x", "y", 3, kernel) ~ ";");
}

void main() {
    const int WIDTH = 200;
    const int HEIGHT = WIDTH;
    const int NLOOP = 500;

    auto data = new float[][](WIDTH, HEIGHT);
    auto output = new float[][](WIDTH-2, HEIGHT-2);

    for (int j; j < WIDTH; ++j)
        data[j][] = 1.5;

    auto t0 = clock();
    float[] kernel1 = [0, 1, 0, 1, -4, 1, 0, 1, 0];
    for (int i; i < NLOOP; ++i)
        dynamic(data, output, kernel1, 3, 3);

    auto t1 = clock();
    for (int i; i < NLOOP; ++i)
        handWritten(data, output);

    auto t2 = clock();
    alias Tuple!(0, 1, 0, 1, -4, 1, 0, 1, 0) kernel2;
    for (int i; i < NLOOP; ++i)
        metaGenerated!(kernel2)(data, output);

    auto t3 = clock();

    putr("Dynamic       : ", t1 - t0);
    putr("Hand written  : ", t2 - t1);
    putr("Meta-generated: ", t3 - t2);
}

On 2008-06-05 12:31:45 +0200, bearophile <bearophileHUGS@lycos.com> said:

> Metaprogramming in D is a really slow thing, there must be faster & simpler ways.
> (I think there are simpler ways, using a scripting language to create D code before the compilation. I have created a Python templating system that seem to work well enough for C++).
> 
> I have written the following code to test compile time optimization regarding a small kernel convolution, the metaGenerated() is as fast as the hand written version. I show it here because it may be interesting to someone.
> 
> But currently the metaGenerated() doesn't work if the kernel2 contains floating point values. I think this problem can be solved with a compile time function/template like ToString that works on floating point values too, do you have it?

I wrote an optimized convolution, but only for nearest neighbors in 2D and 3D.
I think that in principle one could generalize it (extending the x direction is straightforward, the other probably need some work).
Anyway I don't think that you really gain something by making the weight value compiletime, just the sparsity structure (number of variables) makes you gain something...

Fawzi

> 
> Bye,
> bearophile
> 
> 
> import std.stdio: put = writef, putr = writefln;
> import std.metastrings: Format, ToString;
> static import std.c.time;
> 
> double clock() {
>     auto t = std.c.time.clock();
>     if (t == -1)
>         return 0.0;
>     else
>         return t/cast(double)std.c.time.CLOCKS_PER_SEC;
> }
> 
> template Tuple(T...) {
>     alias T Tuple;
> }
> 
> template GenTerm(string m, string x, string y, int nr, int nc, int posx, int posy, ker...) {
>     static if (ker[nc * posy + posx] == 0)
>         const string GenTerm = "";
>     else static if (ker[nc * posy + posx] == 1)
>         const string GenTerm = Format!("%s[%s+%s][%s+%s] + ",
>                                        m,
>                                        x,
>                                        ToString!(posx - (nc / 2)),
>                                        y,
>                                        ToString!(posy - (nr / 2)));
>     else
>         const string GenTerm = Format!("%s * %s[%s+%s][%s+%s] + ",
>                                        ToString!(ker[nc * posy + posx]), //error if ker[] isn't integral
>                                        m,
>                                        x,
>                                        ToString!(posx - (nc / 2)),
>                                        y,
>                                        ToString!(posy - (nr / 2)));
> }
> 
> template GenConvolutionLine(string m, string x, string y, int nr, int nc, int posx, int posy, ker...) {
>     static if (posx < nc)
>         const string GenConvolutionLine = GenTerm!(m, x, y, nr, nc, posx, posy, ker) ~
>                                           GenConvolutionLine!(m, x, y, nr, nc, posx+1, posy, ker);
>     else
>         const string GenConvolutionLine = "";
> }
> 
> template GenConvolution(string m, string x, string y, int nr, int nc, int posy, ker...) {
>     static if (posy < nr)
>         const string GenConvolution = GenConvolutionLine!(m, x, y, nr, nc, 0, posy, ker) ~
>                                       GenConvolution!(m, x, y, nr, nc, posy+1, ker);
>     else
>         const string GenConvolution = "0";
> }
> 
> template Convolution(string m, string x, string y, int nc, ker...) {
>     const string Convolution = GenConvolution!(m, x, y, ker.length / nc, nc, 0, ker);
> }
> 
> // ------------------------------------------------------
> 
> void dynamic(float[][] inm, float[][] outm, float[] kern, int w, int h) {
>     int height = inm.length;
>     int width = inm[0].length;
> 
>     for (int x = 1; x < width - 1; ++x)
>         for (int y = 1; y < height - 1; ++y) {
>             float sum = 0.0;
>             for (int i = 0; i < w; ++i)
>                 for (int j = 0; j < h; ++j)
> 	                sum += kern[j * w + i] * inm[x + i - w / 2][y + j - h / 2];
>             outm[x - 1][y - 1] = sum;
>         }
> }
> 
> void handWritten(float[][] inm, float[][] outm) {
>     int height = inm.length;
>     int width = inm[0].length;
> 
>     for (int x = 1; x < width - 1; ++x)
>         for (int y = 1; y < height - 1; ++y)
>             outm[x - 1][y - 1] = inm[x+1][y] + inm[x-1][y] + inm[x][y-1] + inm[x][y+1] - 4 * inm[x][y];
> }
> 
> void metaGenerated(kernel...)(float[][] inm, float[][] outm) {
>     int height = inm.length;
>     int width = inm[0].length;
>     //pragma(msg, Convolution!("inm", "x", "y", 3, kernel)); // to see it
> 
>     for (int x = 1; x < width - 1; ++x)
>         for (int y = 1; y < height - 1; ++y)
>             mixin("outm[x - 1][y - 1] = " ~ Convolution!("inm", "x", "y", 3, kernel) ~ ";");
> }
> 
> void main() {
>     const int WIDTH = 200;
>     const int HEIGHT = WIDTH;
>     const int NLOOP = 500;
> 
>     auto data = new float[][](WIDTH, HEIGHT);
>     auto output = new float[][](WIDTH-2, HEIGHT-2);
> 
>     for (int j; j < WIDTH; ++j)
>         data[j][] = 1.5;
> 
>     auto t0 = clock();
>     float[] kernel1 = [0, 1, 0, 1, -4, 1, 0, 1, 0];
>     for (int i; i < NLOOP; ++i)
>         dynamic(data, output, kernel1, 3, 3);
> 
>     auto t1 = clock();
>     for (int i; i < NLOOP; ++i)
>         handWritten(data, output);
> 
>     auto t2 = clock();
>     alias Tuple!(0, 1, 0, 1, -4, 1, 0, 1, 0) kernel2;
>     for (int i; i < NLOOP; ++i)
>         metaGenerated!(kernel2)(data, output);
> 
>     auto t3 = clock();
> 
>     putr("Dynamic       : ", t1 - t0);
>     putr("Hand written  : ", t2 - t1);
>     putr("Meta-generated: ", t3 - t2);
> }

Fawzi Mohamed:
> I don't think that you really gain something by making the weight value compiletime, just the sparsity structure (number of variables) makes you gain something...

Right, the gain comes only from not doing the multiplication where the coefficient is 1, and not doing anything where it's zero.
Still, I'd like to have a CT toString(float).

Bye,
bearophile

On 2008-06-05 14:45:49 +0200, bearophile <bearophileHUGS@lycos.com> said:

> Fawzi Mohamed:
>> I don't think that you really gain something by making the
>> weight value compiletime, just the sparsity structure (number of
>> variables) makes you gain something...
> 
> Right, the gain comes only from not doing the multiplication where the coefficient is 1, and not doing anything where it's zero.
> Still, I'd like to have a CT toString(float).
> 
> Bye,
> bearophile

maybe, if nobody answers, you have to roll your own, and then you can contribute it back...
with
real frexp (real value, out int exp);

and then a bit per bit extraction of value using scalbn or ldexp, checking >=0, removing the bit and iterating... e even simpler multipy with 2**n_mantissa and cast to integer, and you should be able to do convert a float in two integers that you can then write out.
one should be careful and check that with denormalized numbers it still works

http://www.dsource.org/projects/tango/docs/current/tango.math.IEEE.html

On 2008-06-05 15:08:47 +0200, Fawzi Mohamed <fmohamed@mac.com> said:

> On 2008-06-05 14:45:49 +0200, bearophile <bearophileHUGS@lycos.com> said:
> 
>> Fawzi Mohamed:
>>> I don't think that you really gain something by making the
>>> weight value compiletime, just the sparsity structure (number of
>>> variables) makes you gain something...
>> 
>> Right, the gain comes only from not doing the multiplication where the coefficient is 1, and not doing anything where it's zero.
>> Still, I'd like to have a CT toString(float).
>> 
>> Bye,
>> bearophile
> 
> maybe, if nobody answers, you have to roll your own, and then you can contribute it back...
> with
> real frexp (real value, out int exp);
> 
> and then a bit per bit extraction of value using scalbn or ldexp, checking >=0, removing the bit and iterating... e even simpler multipy with 2**n_mantissa and cast to integer, and you should be able to do convert a float in two integers that you can then write out.
> one should be careful and check that with denormalized numbers it still works
> 
> http://www.dsource.org/projects/tango/docs/current/tango.math.IEEE.html

well at least the mantissa should be a long...

"bearophile" <bearophileHUGS@lycos.com> wrote in message news:g28fah$2i8d$1@digitalmars.com...
> Metaprogramming in D is a really slow thing, there must be faster &
> simpler ways.
> (I think there are simpler ways, using a scripting language to create D
> code before the compilation. I have created a Python templating system
> that seem to work well enough for C++).
>
> I have written the following code to test compile time optimization regarding a small kernel convolution, the metaGenerated() is as fast as the hand written version. I show it here because it may be interesting to someone.
>
> But currently the metaGenerated() doesn't work if the kernel2 contains floating point values. I think this problem can be solved with a compile time function/template like ToString that works on floating point values too, do you have it?

const f = 1.2345;
pragma(msg, f.stringof);


...

Jarrett Billingsley:
> const f = 1.2345;
> pragma(msg, f.stringof);

It works, thank you :-)

Bye,
bearophile

Jarrett Billingsley wrote:
> const f = 1.2345;
> pragma(msg, f.stringof);

Or if the float is a value in a CTFE function, and you know your value is in a certain range, you could use fixed precision rather more easily:

/// Returns string representation of a decimal value.
char[] toString (real r, uint decimals = 2)
{
	int top = cast(long) r;
	int bottom = cast(ulong) (r - top);
	for (int i = 0; i < decimals; i++) bottom *= 10;
	return toString (top) ~ "." ~ toString (bottom, decimals);
}

/// Returns string representation of an integer value, with
/// leading zeros to pad out to length.
char[] toString (ulong value, uint length)
{
	char[] str = toString (value);
	while (str.length < length) str = "0" ~ str;
	return str;
}

Reply to bearophile,

> Fawzi Mohamed:
> 
>> I don't think that you really gain something by making the weight
>> value compiletime, just the sparsity structure (number of variables)
>> makes you gain something...
>> 
> Right, the gain comes only from not doing the multiplication where the
> coefficient is 1, and not doing anything where it's zero.
> 
> Still, I'd like to have a CT toString(float).
> 
> Bye,
> bearophile

look for "fcvt" here http://www.dsource.org/projects/ddl/browser/trunk/meta/conv.d 

BCS:
> look for "fcvt" here http://www.dsource.org/projects/ddl/browser/trunk/meta/conv.d

Oh, that's fun code, thank you :-)

Bye,
bearophile