Schlemiel the Painter's algorithm: Difference between revisions

Revision as of 04:50, 9 January 2010

Revision as of 19:00, 9 January 2010

Line 6:

Spolsky used a [[Yiddish]] joke to illustrate a certain poor programming practice. In the joke, Schlemiel (also rendered Shlemiel) has a job painting the dotted lines down the middle of a road. Each day, Schlemiel paints less than he painted the day before. When he is asked why, Schlemiel complains that it is because each day he gets farther away from the paint can.<ref name="basics">{{citation|last=Spolsky|first=Joel|title=Back to Basics|date=December 11, 2001|series=Joel on Software|url=http://www.joelonsoftware.com/articles/fog0000000319.html|publisher=joelonsoftware.com}}.</ref>

The inefficiency Spolsky was drawing an analogy tothat refers to the poor programming practice of repeated [[concatenation]] of [[C (programming language)|C]]-style [[Null character|null]]-terminated character arrays (in general computing parlance, these are known as "[[String (computer science)|strings]]") in which the position of the destination string has to be recomputed from the beginning of the string each time because it is not carried over from a previous concatenation.

Spolsky condemned such inefficiencies as typical for programmers who had not been taught basic programming techniques before they began programming using higher level languages: "Generations of graduates are descending on us and creating ''Shlemiel The Painter algorithms'' right and left and they don't even realize it, since they fundamentally have no idea that strings are, at a very deep level, difficult."<ref name="basics" />

Line 27:

Analogous to Schlemiel's not carrying the paint-bucket (or the string's length) 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 <code>buffer</code>, that terminating null character also gets farther away from the beginning with each call to <code>strcat()</code>, meaning more checks must be taken to find that character and subsequent calls are increasingly slower&mdash;just as "Schlemiel's" path to his bucket keeps getting longer.

The problems illustrated by Spolsky's example are not noticed by a programmer who is using a high level language and has little or no knowledge of theits underlying principles and functions. "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" />

== References ==