Schlemiel the Painter's algorithm: Difference between revisions

Revision as of 16:33, 21 February 2014

Revision as of 18:36, 22 February 2014

Line 1:

{{afd-mergeto|#REDIRECT [[Joel Spolsky|#Schlemiel the Painter's algorithm|21]] February{{R from Merge}} {{R 2014|date=Februaryto 2014Section}}

{{Distinguish|Painter's algorithm}}

In software development, a '''Schlemiel the Painter's algorithm''' (or '''Schlemiel the Painter algorithm''')<!-- Spolsky uses it both with and without the possessive 's --> is a method that is inefficient because the programmer has overlooked some fundamental issues at the very [[High and low level|lowest levels]] of [[software design]]. The term was coined in 2001 by software engineer and essayist [[Joel Spolsky]].

The algorithm is not to be confused with the [[Painter's algorithm]] of image compositing, as the two are completely unrelated.

__TOC__

==Spolsky's analogy==

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 to which Spolsky was drawing an analogy was the poor programming practice of repeated [[concatenation]] of [[C (programming language)|C]]-style [[Null character|null]]-terminated character arrays (that is, [[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 ''Schlemiel 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" />

Spolsky's essays have been cited as examples of clear writing "about their insular world in a way that wins the respect of their colleagues and the attention of outsiders."<ref>{{citation|last=Rosenberg|first=Scott|title=The Shlemiel way of software|date=December 9, 2004|url=http://dir.salon.com/story/tech/feature/2004/12/09/spolsky/|publisher=salon.com}}.</ref>

==Spolsky's example==

The programming practice that Spolsky used to make his point was repeated concatenation of null-terminated character arrays ("strings").<ref name="basics" />

The first step in every implementation of the [[C standard library|standard C library]] function for concatenating strings is determining the length of the first string by checking each character in the array, starting from the beginning, to see if it is the terminating [[null character]]. Next, the second string is copied to the end of the first, effectively concatenating the two. At the end of the concatenation, the length of the combined string is discarded upon return to the calling code.

In Spolsky's example, the "Schlemiels" occur when multiple strings are concatenated together:

# <code>[[strcat]]( buffer, "John" ); &nbsp;&nbsp; </code>/* Here, the string "John" is appended to the buffer */

# <code>strcat( buffer, "Paul" ); &nbsp;&nbsp; </code>/* Now the string "Paul" is appended to ''that'' */

# <code>strcat( buffer, "George" );&nbsp; </code>/* ... and "George" is appended to ''that'' */

# <code>strcat( buffer, "Ringo" ); &nbsp; </code>/* ... and "Ringo" is appended to ''that'' */

After "Paul" has been appended to "John", the length of "JohnPaul" (or, more precisely, the position of the terminating null character) is known within the [[Scope (programming)|scope]] of <code>strcat()</code> but is discarded upon its return to the point after Paul and before George. Afterwards, when <code>strcat()</code> is told to append "George" to "JohnPaul", <code>strcat()</code> starts at the very first character of the array ("J") all over again just to find the terminating null character. Each subsequent call to <code>strcat()</code> has to compute the length again before concatenating another name to the <code>buffer</code>.

Analogous to Schlemiel not carrying the paint-bucket (or the string's length) with him, all the subsequent <code>strcat()</code>s have to "walk" the length of the string again to determine where the second string should be copied. As more data is added to <code>buffer</code> with each call to <code>strcat()</code>, that terminating null character also gets farther away from the beginning, meaning subsequent calls are increasingly slow—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 its 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 ==

{{reflist}}

[[Category:Software engineering terminology]]

[[Category:Software development philosophies]]