Lambda the Ultimate

inactiveTopic Guido van Rossum: An Optimization Anecdote
started 4/5/2002; 6:33:10 AM - last post 4/11/2002; 7:17:54 AM
Ehud Lamm - Guido van Rossum: An Optimization Anecdote  blueArrow
4/5/2002; 6:33:10 AM (reads: 2410, responses: 4)
Guido van Rossum: An Optimization Anecdote
If you are fond of high level languages you find yourself all too often irritated by naive remarks about the speed and size of programs. Common misconceptions include confusing executable size and space efficiency, premature optimization, and misunderstanding of modern computing architecture (RISC, cache efficiency, branch predication etc.) Often these are the result of not knowing what a compiler does, and how optimizations work. Sometimes people used to lower level language like C assume that the compiler simply translates source statements into equivalent blocks of machine code.

On top of this many programmers exaggerate the importance of efficiency. They'll go to amazing lengths to eliminate one source statement (often declaring a constant value), making the code less readable - while writing code that will be executed once or twice on fairly small data sets.

So we often simply tell people to forget about speed (or space) and let the compiler worry about it. Optimize only if measurement and profiling shows your code is problematic. If we are honest we emphasize using good algorithms and data structures, since they have the largest impact on speed and space. All the while we know deep down that this is not the whole truth. Sometimes small source level changes can have quite a large impact on speed.

A language designer/implementor is often the one most qualified to discuss such isues.

Posted to Python by Ehud Lamm on 4/5/02; 6:40:35 AM

Adam Vandenberg - Re: Guido van Rossum: An Optimization Anecdote  blueArrow
4/5/2002; 9:36:46 PM (reads: 934, responses: 0)
One place where optimization is as much myth as science is in game programming. Lots of game programmers cut their teeth on 8 or 16-bit boxes, where doing certain things in a particular way with assembly code bought you A WHOLE LOT.

Even up to DOS game programming with Mode 13h there are a lot of well known optimizations.

These days, though, C/C++ compilers are really darn good at generating machine code. I've heard that at least some game devs don't have much of a Computer Science grounding, having come into it as a hobby. It turns out that while the graphics code may be optimized well, many games use algorithms for other things (think AI processing) that have inappropriate orders of execution. Say, doing 2 linear searches per frame over some array instead of using a hash table.

James Hague - Re: Guido van Rossum: An Optimization Anecdote  blueArrow
4/8/2002; 8:57:44 AM (reads: 872, responses: 0)
I agree that there is a lot of myth regarding optimization among newbie game programmers. But you need to be careful: it's still pretty easy to beat most C/C++ compilers with hand-assembled code (for large, non-trivial functions). I know, I know, people don't want it to be true (myself included), but that doesn't change things. And it also doesn't mean that there's much _point_ in writing faster code on that kind of level, except in extreme circumstances. That processors have gotten so much faster is a larger factor than improvements in compiler optimization.

What struck me most about Guido's optimization example is it's triviality. It's interesting from a "what goes on under the hood in the the Python interpreter" point of view, and as a programming problem, but it's not likely that converting a list of integers into a string is a bottleneck in any kind of real application. And as such it does more to encourage pointless micro-optimization than discourage it.

Luke Gorrie - Re: Guido van Rossum: An Optimization Anecdote  blueArrow
4/9/2002; 7:18:36 AM (reads: 841, responses: 0)
Actually James - a very similar problem caused a real bottleneck in part of our SSL-offload appliance (, in a modest way.

I wrote some code in the command-line interface that accumulated output messages with string appends, and since Erlang strings are lists of numbers this takes quadratic time. This worked fine on all the cases that were initially tested or expected (in the back of my mind).

But (of course) over time the status messages got bigger and more numerous. Eventually we got a bug report saying that when you dump the full configuration of hundreds of servers it takes a long time - tens of seconds, IIRC. Since this work was being done by the same processor that is handling traffic, and traffic handling is CPU-bound, this wasn't a trivial problem.

It took a bit of prodding from colleagues and measuring before I believed that it was the string appends at fault, but indeed it was. So we applied standard erlang idiom: switched from appends to consing up a list-of-strings, then flattening it at the end. (I think of that as trading speed against prettiness of debug printouts.) This made it roughly O(N) and the problem was easily solved.

So that's my similarly trivial anecdote, which tells the other side of the story: when constant factors (like loops in C vs Erlang/Python) aren't important, but growth rates are (even though you mightn't expect them to be).

But I guess this is a case of "normal code that was first written really badly" rather than "inner loop code optimized to lightning speed" :-)

Ehud Lamm - Re: Guido van Rossum: An Optimization Anecdote  blueArrow
4/11/2002; 7:17:54 AM (reads: 782, responses: 0)
Want more speed? Get better hardware.