Schlemiel the Painter's algorithm: Difference between revisions

Revision as of 07:59, 11 May 2008

Revision as of 08:05, 11 May 2008

Line 87:

</source>

Our newThe ''stringcat'' function is basicallythe same as the sametraditional ''strcat'', itexcept justthat it returns the-new-end-of-the-destination-string insteadwhich ofmay the-start-of-the-destination-string...then Sobe what?passed Well soto the '''next time'''invocation we callof ''stringcat'', we caneliminating passthe itoverhead of repeatedly finding the-end-of-the-destination-string, so ''stringcat'' doesn't have to waste time finding it. Pretty clever huh!

NowThe lets write afollowing test harness toexcersises examinethe new ''stringcat'''s (hopefully improved) performancefunction.

<source lang="c">

Line 96:

final int BUFFER_SIZE = 1024*1024;

char word[] = "word";

char nextWord[] = ", word";

char buffer[BUFFER_SIZE] = "";

char *last = buffer+BUFFER_SIZE-strlen(word)-strlen(", "); // <-- Do this once!

char *endOfBuffer = stringcat(buffer, word); // <-- Do this once!

while( endOfBuffer < last ) { // <-- 15 billion times cheaper

endOfBuffer = strcat(endOfBuffer, wordnextWord); // <-- 30 billion times cheaper

}

}