www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - float CT stringification

reply bearophile <bearophileHUGS lycos.com> writes:
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);
}
Jun 05 2008
next sibling parent reply Fawzi Mohamed <fmohamed mac.com> writes:
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);
 }

Jun 05 2008
parent reply bearophile <bearophileHUGS lycos.com> writes:
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
Jun 05 2008
next sibling parent reply Fawzi Mohamed <fmohamed mac.com> writes:
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
Jun 05 2008
parent Fawzi Mohamed <fmohamed mac.com> writes:
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...
Jun 05 2008
prev sibling parent reply BCS <ao pathlink.com> writes:
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...
 

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
Jun 05 2008
parent bearophile <bearophileHUGS lycos.com> writes:
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
Jun 05 2008
prev sibling parent reply "Jarrett Billingsley" <kb3ctd2 yahoo.com> writes:
"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); ...
Jun 05 2008
next sibling parent bearophile <bearophileHUGS lycos.com> writes:
Jarrett Billingsley:
 const f = 1.2345;
 pragma(msg, f.stringof);

It works, thank you :-) Bye, bearophile
Jun 05 2008
prev sibling parent Chris Wright <dhasenan gmail.com> writes:
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; }
Jun 05 2008