float CT stringification

[Fawzi Mohamed]

On 2008-06-05 12:31:45 +0200, bearophile <bearophileHUGS at 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);
> }