Schlemiel the Painter's algorithm: Difference between revisions

Revision as of 16:50, 14 May 2009

Revision as of 20:54, 13 June 2009

Line 25:

By the end of the first invocation of <code>strcat()</code> the length of <code>buffer</code> will be known but not preserved upon return to the point just after step 1 and just before step 2. Subsequent calls to <code>strcat()</code> have to compute that length again before concatenating another name to the <code>buffer</code>.

As such, and analogous to SchmielSchlemiel's not carrying the paint-bucket with him, all the subsequent <code>strcat()</code>s have to again "walk" the length of the string to determine where the second string should be copied. As more data is added to it, the string in <code>buffer</code> also gets longer with each call to <code>strcat()</code>, and with increasing length, the determination of that length takes longer, which means that subsequent calls are increasingly slower. Just as "Schlemiel's" path to his bucket keeps getting longer.

The problems illustrated by Spolsky's example remain hidden to a programmer with little or no knowledge of the underlying principles and functions, which every higher-level language and library will still be using even when the low-level manipulation is not immediately obvious at the higher level. "Some of the biggest mistakes people make even at the highest architectural levels come from having a weak or broken understanding of a few simple things at the very lowest levels."<ref name="basics" />