http://d.puremagic.com/issues/show_bug.cgi?id=4438
--- Comment #4 from bearophile_h...@eml.cc 2011-04-14 17:25:38 PDT --- A different case of missed inlining. In the following code isValidMove() is not inlined by DMD 2.052 (with -O -inline -release), despite this function contains no loop and no throws. Removing the "ref" for the board array in the isValidMove() signature changes nothing. The runtime is 12.6 seconds, the alternative version of the knightsTour() function with manually inlined isValidMove() (currently commented out below) runs in 8.0 seconds. My tests show that GCC -O3 is able to inline similar code written in C. // Code adapted from: // http://en.literateprograms.org/The_Knight's_Tour_(C)?oldid=14704 import core.stdc.stdio: printf; template TypeTuple(T...) { alias T TypeTuple; } bool isValidMove(int N)(ref int[N][N] board, int xpos, int ypos, int nmove) { if (xpos < 0 || xpos >= N || ypos < 0 || ypos >= N || (board[xpos][ypos] && board[xpos][ypos] < nmove)) return false; return true; } // run time: 12.6 seconds bool knightsTour(int N)(ref int[N][N] board, int xpos, int ypos, int nmove) { if (!isValidMove(board, xpos, ypos, nmove)) return false; board[xpos][ypos] = nmove; if (nmove == N * N) return true; alias TypeTuple!(+1, -2, -2, -1, -1, +2, +2, +1) spx; alias TypeTuple!(+2, +1, -1, +2, -2, +1, -1, -2) spy; static assert(spx.length == spy.length); bool ok = true; foreach (i, sx; spx) ok = ok && !knightsTour(board, xpos + sx, ypos + spy[i], nmove + 1); if (ok) { board[xpos][ypos] = N * N; return false; } return true; } /* // run time: 8.0 seconds bool knightsTour(int N)(ref int[N][N] board, int xpos, int ypos, int nmove) { // if is not valid move if (xpos < 0 || xpos >= N || ypos < 0 || ypos >= N || (board[xpos][ypos] && board[xpos][ypos] < nmove)) return false; board[xpos][ypos] = nmove; if (nmove == N * N) return true; alias TypeTuple!(+1, -2, -2, -1, -1, +2, +2, +1) spx; alias TypeTuple!(+2, +1, -1, +2, -2, +1, -1, -2) spy; static assert(spx.length == spy.length); bool ok = true; foreach (i, sx; spx) ok = ok && !knightsTour(board, xpos + sx, ypos + spy[i], nmove + 1); if (ok) { board[xpos][ypos] = N * N; return false; } return true; } */ void main() { enum int side = 8; enum int xpos = 0; enum int ypos = xpos; int[side][side] board; printf("Executing Knight's Tour...\n"); if (knightsTour(board, xpos, ypos, 1)) { printf("Solution found:\n"); foreach (ref row; board) { foreach (item; row) printf("%3d", item); printf("\n"); } } else printf("No solution found.\n"); } The first part of the assembly of knightsTour() shows the call to isValidMove(): _D4test20__T11knightsTourVk8Z11knightsTourFKG8G8iiiiZb comdat sub ESP,02Ch push EBX push EBP push ESI mov ESI,044h[ESP] push EDI mov 038h[ESP],EAX push ESI push dword ptr 048h[ESP] push dword ptr 048h[ESP] call near ptr _D4test20__T11isValidMoveVk8Z11isValidMoveFKG8G8iiiiZb xor AL,1 je L2D pop EDI ... -- Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email ------- You are receiving this mail because: -------