Coding Horror: The Sad Tragedy of Micro-Optimization Theater

http://www.codinghorror.com/blog/archives/001218.html

by twampss • 17 years ago

20 29 17 years ago

Jeff is not quite on the ball with his reference to the "Shlemiel" algorithm.

Joel originally described the "Shlemiel" case when referring to strings in C not having a length stored in them, and needing to use strlen to walk the string to find the length. The Shlemiel problem comes up when you use strcat in a loop, since each strcat call needs to recalculate the length of the loop, which takes longer as the string gets longer.

The problem with concatenating strings is not a length issue, but a memory issue. In order to concatenate a string in C# or C++ using built in string classes, the location to store the new resulting string has to be allocated and the two strings have to copied into this new location. The allocation does not take up a trivial amount of time, and reallocating memory over and over again for each time you concatenate a string is bad practice. There is still a bit of "Shlemiel" since you have to keep copying your existing string, which takes a larger amount of time as the string gets longer, but you have to take in consideration the allocation, which wasn't present in the original problem that the "Shlemiel" story described.

cconstantine2• 17 years ago

Memory allocation is something that is typically O(1), or O(log(n)). The constants attached are fairly large, but doing lots of allocations/deallocations isn't a BigO issue.

The schlemiel problem still exists when doing '+=' in a loop. Each copy requires some code to walk the length of both sides of the operator, same as strlen in Joel's example. The loop is an O(n^2) operation, even if it has a smaller constant on it than a memcpy(src, dest, strlen(src)).

It's "Schlemiel", but with different constants attached. For big enough N the O(1) or O(log(n)) of the allocations lose importance making the entire thing O(n^2) just like "Schlemiel".

tptacek5• 17 years ago

So we may be saying the same thing, but, he didn't say allocation was N log N --- and allocation/deallocation is really expensive; it's consistently on the top of profiles of programs I work on.

jcl• 17 years ago

The reference is entirely valid. Both Jeff and Joel are using the joke allegorically; Joel uses it to describe an algorithm that counts the length of the first part of the string over and over, while Jeff uses it to describe an algorithm that copies the first part of the string over and over. (The joke itself is an old one, not original with Joel.)

daleharvey3• 17 years ago

am I just being slow or has he completely missed the point of avoiding concatenation in loops, concatenating small strings inside loops is fine, its tiny cost, but concatenating the results of those 100000 iterations is completely different

cconstantine2• 17 years ago

The Schlemiel problem is a BigO problem. BigO is really only useful analysis if your N is large enough. If you always work with data sets that are small (and have confidence that they will remain small) there is no point in doing BigO analysis or worrying about bad things like O(N^2).

daleharvey3• 17 years ago

I wasnt talking about the length of the iterations but what the result of them is, he is just concatenating tiny strings, then apparently throwing the result away, if he used the first example in an iteration of 100000 then I dont think the results would be negligible.

jonknee• 17 years ago

Is Jeff really making HTML strings in his methods? Aren't there template systems for .NET?

johns• 17 years ago

Yes, but they get very ugly when you have a lot of control structures. Jeff prefers to move these into code, see here: http://twitter.com/codinghorror/statuses/1154609179

pseale• 17 years ago

Jeff is presumably choosing to build his reusable HTML widgets in functions, which is one valid way to do things.

Here's a good overview of all options available to ASP.NET MVC: http://www.lostechies.com/blogs/jimmy_bogard/archive/2009/01...

aditya• 17 years ago

Can anyone explain what he means by "writing better code"?

It seems like he sets up a straw man string concatenation problem and then tears it down in a pointless argument.

olavk2• 17 years ago

I would guess that better code means more readable and maintable code.

jerf2• 17 years ago

Well, the real fastest thing to do is stream your page out by arranging it such that you don't have to construct it out of order, so you never "concatenate" strings at all, simply shipping the page out to the socket with each chunk, except with a small I/O buffer before shipping it out on the socket. Not only will this take less time in all but very pathological cases by avoiding string concatenation penalties, it'll also end up getting the page to the user sooner so they can progressively render it.

But hardly any web framework I've ever used will even permit this, all insisting on being handed one big string to ship out to the user. Sigh.

tptacek5• 17 years ago

You mean like, Rails helpers and "concat"?

jerf2• 17 years ago

Beats me, I've never used Rails. I did qualify it with "I've used" and "hardly any". I've used a number, but nobody's come even close to using them all.

raganwald• 17 years ago

Meaning "no true framework":http://en.wikipedia.org/wiki/No_true_Scotsman allows you to stream results out piecemeal.

ezmobius• 17 years ago

nope, rails will still buffer up the whole template render before it sends it down the socket. I think he means progressive rendering directly to a socket rather then buffering it before shipping.

coliveira• 17 years ago

In the examples that he gives, the main burden is in creating objects, not in concatenating strings. As long as there are just a small number of += operations, the ratio between object creation and concatenation remains similar and there will be no big difference in the long run.

newt0311• 17 years ago

OT: This is why I keep wishing that languages would grow up when it came to strings and use better optimized big-O data structures like ropes instead and save everybody a lot of headache.

dominik• 17 years ago

I'm unclear what point Jeff had in mind...

A micro-summary to illustrate:

1. I love strings.

2. You don't want to concatenate strings in (large) loops.

3. You already knew that, at least if you're a decent programmer.

4. Analysis of various methods of concatenating strings in loops.

5. Reveal that the methods don't matter.

6. It's bad to worry about micro-optimizations like the best way to concatenate strings in a loop.

7. Just avoid obvious mistakes like concatenating strings in loops.

8. Otherwise, don't worry about micro-optimization. Instead, focus on your real goal: writing better code.

Maybe it's me, but this article felt disjointed.

Coding Horror: The Sad Tragedy of Micro-Optimization Theater

Related Stories