www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - Memoize and other optimization.

reply David <d dav1d.de> writes:
I have this code:


struct CubeSideData {
     float[3][4] positions; // 3*4, it's a cube!
     float[3] normal;
}

immutable CubeSideData[6] CUBE_VERTICES = [...]


Vertex[] simple_block(Side side, byte[2][4] texture_slice) pure {
     return simple_block(side, texture_slice, nslice);
}

Vertex[] simple_block(Side side, byte[2][4] texture_slice) pure {
     CubeSideData cbsd = CUBE_VERTICES[side];

     float[3][6] positions = to_triangles(cbsd.positions);
     byte[2][6] texcoords = to_triangles(texture_slice);
     byte[2][6] mask;
     if(mask_slice == nslice) {
         mask = texcoords;
     } else {
         mask = to_triangles(mask_slice);
     }

     Vertex[] data;

     foreach(i; 0..6) {
         data ~= Vertex(positions[i][0], positions[i][1], positions[i][2],
                        cbsd.normal[0], cbsd.normal[1], cbsd.normal[2],
                        texcoords[i][0], texcoords[i][1],
                        mask[i][0], mask[i][1],
                        0, 0);
     }

     return data;
}


Is using std.functional.memoize useful for that function, or is the 
lookup slower? This isn't calculation intensive but has quite a few 
array lookups.

Is there an approximate value how expensive an AA-lookup is (something I 
can compare with)?

PS:/ I just noticed that I wanted to optimize "arr ~= …". Better using a 
static array or std.array.appender with reserve?
Aug 16 2012
parent reply "bearophile" <bearophileHUGS lycos.com> writes:
David:

 Is using std.functional.memoize useful for that function, or is 
 the lookup slower?
This is hard to tell, in general you have to write two versions of your code, and time them.
 PS:/ I just noticed that I wanted to optimize "arr ~= …". 
 Better using a static array or std.array.appender with reserve?
A static array, where usable, is faster because it has no resize costs. appender is supposed to be faster than ~= if you are appending a lot, but unfortunately this is not always true, and you have to time again. Bye, bearophile
Aug 16 2012
parent reply David <d dav1d.de> writes:
Am 17.08.2012 02:09, schrieb bearophile:
 David:

 Is using std.functional.memoize useful for that function, or is the
 lookup slower?
This is hard to tell, in general you have to write two versions of your code, and time them.
I though there is a rule of thumb how many array lookups equal an AA lookup, so I'll time it.
 PS:/ I just noticed that I wanted to optimize "arr ~= …". Better using
 a static array or std.array.appender with reserve?
A static array, where usable, is faster because it has no resize costs. appender is supposed to be faster than ~= if you are appending a lot, but unfortunately this is not always true, and you have to time again.
So I'll go with a static array, thanks for your answer.
Aug 17 2012
parent reply David <d dav1d.de> writes:
Am 17.08.2012 11:45, schrieb David:
 Am 17.08.2012 02:09, schrieb bearophile:
 David:

 Is using std.functional.memoize useful for that function, or is the
 lookup slower?
This is hard to tell, in general you have to write two versions of your code, and time them.
I though there is a rule of thumb how many array lookups equal an AA lookup, so I'll time it.
For anyone interested: Memoize No memoize (3000 runs with std.datetime.benchmark) 0.000401645 - 0.00666028
Aug 17 2012
parent reply Philippe Sigaud <philippe.sigaud gmail.com> writes:
On Fri, Aug 17, 2012 at 4:27 PM, David <d dav1d.de> wrote:
 Am 17.08.2012 11:45, schrieb David:
 For anyone interested:

 Memoize       No memoize (3000 runs with std.datetime.benchmark)
 0.000401645 - 0.00666028
I'm quite interested with these results, as I'm also trying to memoize some code instead of recomputing everything. So in your case it's a direct *15 times faster, right?
Aug 20 2012
parent David <d dav1d.de> writes:
Am 20.08.2012 15:26, schrieb Philippe Sigaud:
 On Fri, Aug 17, 2012 at 4:27 PM, David <d dav1d.de> wrote:
 Am 17.08.2012 11:45, schrieb David:
 For anyone interested:

 Memoize       No memoize (3000 runs with std.datetime.benchmark)
 0.000401645 - 0.00666028
I'm quite interested with these results, as I'm also trying to memoize some code instead of recomputing everything. So in your case it's a direct *15 times faster, right?
Yes, 16.5 times, but I passed a maxSize of 16 (the function can only produce 16 different results), not sure which impact that has.
Aug 20 2012