Programming As If Performance Mattered 615
Junks Jerzey writes "Saw the essay 'Programming as if Performance Mattered', by James Hague, mentioned at the Lambda the Ultimate programming language weblog. This is the first modern and sensible spin on how optimization has changed over the years. The big 'gotcha' in the middle caught me by surprise. An inspiring read." Hague begins: "Are particular performance problems perennial? Can we never escape them? This essay is an attempt to look at things from a different point of view, to put performance into proper perspective."
speed/easy coding (Score:2, Interesting)
Really? How about the server side of things?
Shameless bragging: Why don't you take a look at my page to get a whole new view on peformance?
Funny thing about performance (Score:5, Interesting)
Performance gains occur at the hardware level. Any tendency to optimize prematurely ought to be avoided, at least until after v1.0 ships.
Re:Funny thing about performance (Score:2, Interesting)
Do you code all your own algorithms?
I think... (Score:2, Interesting)
Make the common case fast (Score:2, Interesting)
Sheesh!
Don't agree (Score:5, Interesting)
The thing is, in real life applications, playing with a Targa file is not the same as service critical, 300 users, number crunching, data handling systems, where a small performance improvement must be multiplied by the number of users/uses, by many many hours of operation and by years in service to understand its true impact.
Just now I'm working on an econometric model for the Panama Canal (they're trying to make it bigger and need to figure out if it's worth the effort/investment) and playing with over 300 variables and 100 parameters to simulate dozens of different scenarios can make any server beg for more cycles, and any user beg for a crystal ball.
Performance is relative (Score:5, Interesting)
Ok, it's not bad for a a language like Erlang, but it's not exactly fast.
The big point here for the author is "it's fast enough". Lots of micro- (and macro-) optimizations are done when it turns out they aren't needed. And writing in a high level language you're comfortable in is important, if it'll do the job. This is a good point.
On the other hand, even a fairly naive implementation in something like C or C++ (and perhaps Java) would probably have acheived the goal without having to make 5 optimization passes (and noticable time examining behavior).
And even today, optimizations often do matter. I'm working on code that does pretty hard-real-time processing on multiple threads and keeps them synchronized while communicating with the outside world. A mis-chosen image filter or copy algorithm can seriously trash the rest of the system (not overlapping DMA's, inconvenient ordering of operations, etc). The biggest trick is knowing _where_ they will matter, and generally writing not-horrible-performance (but very readable) code as a matter of course as a starting point.
Disclaimer: I was a hard-core ASM & C programmer who for years beta-tested 680x0 compilers by critiquing their optimizers.
But in some cases performance counts (Score:2, Interesting)
Optimizations also have significant effect in software designed to perform complex computations, such as scheduling.
Also, the trend of ignoring performance considerations with the claim that modern hardware makes optimizations obselete is precisely what leads to the trend, particularly among Microsoft software, for the software to become significantly slower with each revision.
Re:the software taketh what the hardware giveth. (Score:2, Interesting)
Have a look at some of the PC demos that boot from DOS and take over the machine (eg. www.scene.org) and tell me that they aren't just as amazing.
Why aren't optimized algorithms best practices? (Score:3, Interesting)
This, of course, has already begun with many frequently used algorithms like sorting or hashing being made part of the language core libraries, but more than that, it seems that duplicating effort occurs much more often than simply that.
This is one instance where Microsoft has really come through. Their COM architecture allows for inter-language reuse of library code. By releasing a library which is binary compatible across different languages, as well as backwards compatible with itself (v2.0 supports v1.9), the COM object architecture takes much of the weight of programming difficult and repetitive tasks out of the hands of programmers and into the hands of library maintainers.
This kind of separation of job function allows library programmers the luxury of focusing on optimizing the library. It also allows the client programmer the luxury of ignoring that optimization and focusing on improving the speed and stability of his own program by improving the general structure of the system rather than the low level mundanities.
Large libraries like Java's and
Re:Funny thing about performance (Score:5, Interesting)
That's not the only reason. Programmers usually get to use fast machines with lots of RAM and diskspace, and often end up writing programs that need everything they have.
Back in the DOS days, I worked on a project that had a better way of doing things. We had one machine with reasonable speed as the testbed. It wasn't well optimized as we didn't expect our customers to know how to do that and the programs we were writing didn't need expanded or extended memory. If what you wrote wouldn't run on that machine, it didn't matter how well it worked on your machine, you had to tweak it to use less memory.
Optimizations are a varied lot (Score:3, Interesting)
If you're code must process a large amount of data, look for ways of designing your program so that you serially process the data. Don't try to bring large amounts of data from a database or data file all at once if you don't have too. Once you are no longer able to contain the data in physical memory, and the program starts using 'virtual' memory, things slow down real fast. I've seen architects forget about this, which is why I'm writing this reminder.
On the other hand I've worked on a C++ project where, in a certain segment of the code, it was necessary to write our own container class to replace one of the std: classes, for performance on the SPARC architecture. Using the std: container would cause the subroutines to nest deeply enough to so that the cpu registers needed to be written out out to slower memory. The effect was enough to be quite noticeable in the app.
With today's processors, to optimize for speed, you have to think about memory utilization, since running within cache is noticably faster than from main memory. Things are not as clear cut, so far as speed optimization goes, as they once were.
Performance oriented coding in real life... (Score:1, Interesting)
A few points that come to mind... (Score:2, Interesting)
- Decoding a RLE data buffer is short of impressive as a benchmark. RLE was designed as a simple and specific (generally inefficient) compression approach for age-old hardware (i.e. 8MHz, not 333MHz as the base system used here).
How about JPEG or PNG ?
- The author actually spent several iterations optimizing this Erlang code. And these optimizations required handling special cases. (So performance eventually did matter to the author?) Now, would a 'first throw' implementation in C/C++ have been written faster while immediately performing better than the Erlang version? (simpler code)
- I agree that the compiled/interpreted code performance matters less and less, because processors are so much more powerful. For instance, the processing for RLE decompression should in any case be negligible wrt the memory or disk i/o involved.
What is becoming increasingly important, however, is the data structures and algorithms that are used. In this perspective, C++ still shines, thanks to the flexibility that its algorithms and containers library provides.
C++ offers both a high level of abstraction (working with containers), and provides the ability to convert to a different implementation strategy with ease - if and when profiling demonstrates a need.
For large system and library development, the strong static typing of C++ is also a real plus (it doesn't matter to me it is faster than dynamic typing or not).
I totally agree that performance should not be a concern during program implementation (other than avoiding 'unnecessary pessimization', which involves the KISS principle and knowledge of language idioms). Optimization should only be performed where the need for a speed-up has been demonstrated.
Other than saying "wow this interpreted language runs damn fast on current hardware", this article does a poor job at making any relevant point.
radix omnia malorum prematurae optimisatia est -- Donald Knuth
Throw hardware at it. (Score:2, Interesting)
When to optimize (Score:2, Interesting)
What this achieves for me, is that I can look at the program as a whole, and _then_ identify where the problem areas are - most likely not where I thought they were... Even if the first version takes 5 minutes to run (as my first attempt at a depth-first tree search did), it works passably, and is often easier to optimize than trying to optimize each function as I write it.
Might not work for everyone, but I like coding this way
Fragility of the decoder (Score:4, Interesting)
And, sure enough, there's a known, exploitable buffer overflow in Microsoft's RLE image decoder.
Re:Throw hardware at it. (Score:5, Interesting)
I don't know. Clean, elegant, functional code is beautiful. If you're ever going to have to work on it again, I think it's better for it to be clean and optimized.
Also depends on the size of the app. With a small app, what excuse do you have for not optimizing? Wouldn't take that long. With a big project? Depends on your work environment.
The bosses will never know if its optimal or not. If you tell them you've maxed out the server, they just think you write big badass code. A lot of times though, there isn't time to thoroughly bug check a big app (That what users are for, eh?), more less optimize it.
uhh.. yeah (Score:3, Interesting)
back in the day, i discovered a really great trick... you might represent it as something like...
boolean a;
a = 1 - a;
this is a zillion times more efficient than if(a == 1) a = 0; else a = 1;
it is also about the same as a |= 1; if you were going to use bitwise functions.
OK. Great.
Re:Article puts it all in perspective (Score:2, Interesting)
How is this fair? He completely and utterly changed the entire assignment on you forcing you to throw all of your work away. And gave you one week for it!?
apt-get and emerge are two totally different implementations of the same idea. Changing the environment on you may have taught you a lesson about how optimizing eliminates robustness, but if the last professor encouraged you to try MMX/SIMD instructions then you were totally right to tie yourself to the x86.
I would've kicked that moron's ass.
Re:Managed environments (Score:5, Interesting)
The reason I made that statement was because just last week I was at Redmond for an interview for internship at Microsoft, and I was interviewed by the team that was trying to prevent just this sort of thing from happening.
The idea was to design heuristics-enabled compilers that would effectively detect any "bad-code" and help make managed code and pseudo-managed code the norm, or convert existing code into managed code.
I did not say that I was using a programming language that had such protections, merely that such programming languages have their own advantages. I was interviewed for creating compilers, linkers and OS-level protection that did not allow those troublesome things to exist - not use them - and hence my justification
That said, you may knowingly or unknowingly use a language designed for bad programmers even when you program C or C++ in upcoming versions of compilers that insist on managed code - they may just wrap up your code in a nice wrapper to prevent mishaps and hand it over to the linker after having taken care of your holes.
I don't know about Erlang but... (Score:3, Interesting)
The Squeak [squeak.org] VM is a great example of this. The whole thing is written in Squeak itself. Running a Smalltalk VM this way is painfully slow, but a Smalltalk->C translator generates the code that will be compiled and used as the actual, runtime VM (which can support a whole host of things, including raster and vector graphics, sound, MP3 audio and MPEG video!).
Re:One thing new programmers often miss (Score:5, Interesting)
Other things that can help are doing your own memory management at times (i.e. freelists) since that will be faster than malloc/new, and will have less memory overhead. Also, design your storage to your data. If you know you'll allocate up to 64K of an item, and the item is small, allocate an array of 64K of them and maintain a freelist. This will use a lot less memory than dynamically allocating each item and will result in better locality.
I write code in the embedded space, where memory usage and performance are both equally important. Usually getting the last ounce of performance out of the compiler doesn't make much difference.
A good real-world example is that I replaced the malloc code provided by a popular embedded OS with DLMalloc, which glibc is based. The dlmalloc code is *much* more complicated, and the code path is much longer, but due to much better algorithms, operations that took an hour with the old simple malloc dropped down to 3 minutes. It went from exponential to linear time.
-Aaron
http://www.javaperformancetuning.com/ (Score:3, Interesting)
But if you haven't heard of it http://www.javaperformancetuning.com/ [javaperfor...tuning.com] is a good source of performance tips for java
For some things, enough hasn't ever been enough (Score:2, Interesting)
However, as available processing power increases, some tasks change. Many technologies follow a trajectory that starts at "unthinkable" then move to "if you have special hardware" and then move gradually to software. Often along the way, features and computational complexity are added that keep a technology barely in reach (of both HW and SW implementations). It can be many many years before some technologies settle into a stage where they can be comfortably supported in SW at acceptable performance.
Examples include: sound (which started with clicks and beeps and moved through to multichannel 3D audio), graphics, games (text-based to ever-more-complex 3D) and video codecs (simple RLE moving to ridiculously complex stuff like the H.264 codec). In games, for example, there are often preference panels controlling which features should be disabled for performance reasons. This seems evidence that the authors/publishers feel they can't count on their customers having enough power to run the games without cutting features to gain performance.
I think for those applications where processing power trails needs and desires of customers and where optimization can make up the difference, developers will need to optimize or be eaten by the competition. In my experience, in things like codec and graphics development, you can get many-times performance increases over solid but poorly optimized implementations (sometimes even when you're just feeding HW).
I think those gains can be critical.
Re:me too... (Score:5, Interesting)
Some (very old) BASIC interpreters used to parse each source line each time it was executed.
Doing it that way saved memory (no intermediate code to store).
So true... (Score:3, Interesting)
One of the most dangerous things (optimization-wise) in C++, I've found is the temporary-creation problem. You have to be insanely careful to avoid creating temporaries to get any sort of reasonable performance... (or maybe I just need a better compiler than GNU GCC?)
Not quite sure why you would consider them dangerous, but they are Turing Complete (i.e. they are a compile-time language all of their own). Which some people have used to create this [oonumerics.org]. It looks almost as fast as Fortran, but the syntax is a lot more complex than just A*B for a matrix-multiplication.
Re:Asymptotic performance (Score:2, Interesting)
When I started my Ph.D. work, I came into a project doing compiler stuff in functional languages. There was a home-brew lexer that my adviser had written, that did 2d "array" lookups by scanning all the way through a list of lists. We thought it was broken, as it never finished. I changed it to use real arrays, and got it down to taking a matter of minutes. Merely using a O(n^2) implementation rather than O(n^4)
Morale: It's the O-factors that will kill you. Optimizing anything but that is a waste of time until you have seen the profiling data. And even the O-factors are irrelevant in code that's not going to be executed often or that is outside of high-performance areas.
I still catch myself trying to avoid single instruction improvements in handling of, say, user dialog actions. But the user and window system together probably took over a second already to cause the action, so doing a bit of extra CPU work to be clearer or safer is The Right Thing.
Re:Managed environments (Score:2, Interesting)
I've come to the belief that sending out machine-code packages is flawed, because you don't really know what the target platform is going to look like.
Example: can the processor support SIMD instructions? This can make a _HUGE_ performance difference in some applications. I would argue that if you are shipping a binary, you just wouldn't know.
Example: Code optimized for a Pentium III did not run as fast on a Pentium IV. Why? The pipeline changed and this had an effect on the way the compiler should schedule instructions.
Summary: You want the binding between program -> machine code to be as late as you can push it. This doesn't mean I advocate source distrubition since those have their own issues (see Gentoo). But an easily translatable representation like Microsoft's ILM or Java's ByteCode seems to be the solution. This is a classic versioning problem, do you want every app to deal with it? Or deal with it once at the OS level?
Not to mention having really stupid loaders causes other problems down the pipleline. Was this code compiled for thread-saftey? How about with debug information?
But back to performance, low-level efficiency matters. But how much it matters depends on the application. Thinking in terms in processing large amounts of data. Obviously you want to touch it as few times as possible: therefore O(log n) is bettern then O(n), better then O(n^2). But to get good performance: BE CACHE FRIENDLY. Make sure you access data in an array, so that if you access the same data again, you access it soon, and if you look at one element you are likely to look at one of it's neighbors.
This will keep your code running well today, and will allow future hardware to process it faster (assuming new machines use the same type of memory hierarchy only bigger). This does mean prefering indexing tricks into the array over pointers. And yes, linked lists are your enemies.
Anything else, it is going to be a wash. The first thing that researchers of some new language find out is how to get rid of 80% of the inefficiencies that make it slower than C.
In sum, concentrate more on the algorithms. Be cache friendly. Program in a language that you enjoy. And leave the pissing contest between who's language (and therefore their unit) is fundamentally faster to people who have nothing better to do.
engineering (Score:3, Interesting)
A lot of this discussion here is either crap, a rehash or was covered in Engineering 101.
Basically, you have some requirements for the product, and you optimise according to those requirements. Performance is just one variable (time to market, scalability, reliability, security, usability, cost, etc - are the many others).
The requirements for a product in a fast moving market entry company are less about performance and more about rollout ASAP.
The requirements for the same product two years later may be to improve performance to achieve scalability requirements.
If you're writing some sort of overnight build or batch application: whether it takes an extra hour or not may not matter, because it has a 12 hour window to run in.
If you're writing an order processing system, then performance and end-to-end turn around to will be vitaly important, but you won't focus on the assembly, you'll focus on the algorithms, design and architecture.
If you're writing a compression or encryption module: you probably will work on the assembly.
All of the above cases, before you optimise anything: you profile and understand how the optimisation is going to pay back in real terms.
In my experience, you cannot prescribe any of this: you need to take it on case by case basis because every product and circumstance is different.
Re:me too... (Score:1, Interesting)
Vantive stores VB for Application data in a set size blob on the server. Max size 64k. Go over that, and it won't save.
Of course you could always refactor the blocks to move things out, but when you're working 70 hour days under the gun to "get-it-done-now-however" you just substitute a variable or two and damn the consequences.
Re:The question I always ask is (Score:3, Interesting)
So throwing more hardware at Windows doesn't solve its performance problems ? So the parent poster was right ?
So what's your point ?
In any case, the main usability problem with Windows XP isn't slowness - it's the thousand faces of madness within ! I mean the stupid popups that keep on harassing me ! "Do you want to clean the desktop ?" No, I want to work with the app I just started ! Why is there "never bother me again" -button on the darn popup ?!?
I've only used XP on school, so I admit that my skills are propably lacking, and that a more skillfull person could propably turn all of these annoyances off. Still, it is not fun having those popups disturb me all the time, ut us not funny having the stupid operating system and Office programs hide half their menus, and it is NOT funny having that idiotic paperclip jumping up and offering useless "advice" all the time !
Sorry about the rant, but I had to get that off my chest. Feel free to mod flamebait/offtopic/troll/whatever.
Coding while blind (Score:5, Interesting)
In software, the biggest problem is lack of performance directives. POSIX pthreads is one of the biggest offenders here. Best performance practices in pthreads are based on how common implementations work. POSIX allows implementations that would cause major performance problems for so called best pthread programming practices. Example, POSIX allows pthread_cond_signal implementations to wake all waiting threads, not just one. There are programs that depend on pthread_cond_signal to wake only one thread for performance in order to avoid "thundering herd" problems. So while standards allow portability of correct programs, whey do not necessarily allow portability of performance.
We need explicit performance directives.
Re:Performance is relative (Score:1, Interesting)
Optimising the algorithm is certainly the best way to speed it up but his apparent belief that C programmers would have trouble using the same optimisations is truly bizarre. In truth C programmers probably wouldn't bother because they'd have stopped earlier, doing less work for a similar final speed, reaping the benefit of making it 'just fast enough'. I know I made little effort to optimise image readers even on ancient 16Mhz PC's, the naive, readable C++ was fast enough.
If it had anything useful to say about micro-optimisation (and when not to bother) it would be useful, but that's not really mentioned in the article, just an invention in the slashdot preamble.
Re:What annoys me (Score:2, Interesting)
Re:me too... (Score:3, Interesting)
Some (very old) BASIC interpreters used to parse each source line each time it was executed.
One time (around 1985 IIRC), I read an article in the local computer club's magazine. The author had written a BASIC program (GW-BASIC I think) to "shorten" BASIC programs. It would:
The source code that went along with the article looked like it was used on itself (very terse).
With the machines you had back then, it probably made a difference.
De-commenting (Score:4, Interesting)
Each byte of that 640K was precious, so it was common practice to "de-comment" the code before release; remove all comments, reduce whitespace, move multiple statements onto a single line, possibly shorten variable names. You could gain a substantial (for the time) amount of memory that way. You also dynamically imported/destroyed functions.
I regularly debugged client systems with "de-commented" APL; if you could read that, you could read anything!
Re:Performance tuning. (Score:2, Interesting)
All your optimizations are wrong. (Score:5, Interesting)
Real opimizations come before you right your program. Take for example that loop that you removed an instruction or two from. Say it is a searching an array. and looks like:
There are two things wrong. One you cal strlen repetitively. Strlen() is theta(n) So you have a loop that executes n times at a cost of n . n*n=n^2. That's one of the slowest algorithms around. Maybe your compiler is smart enough to see that x is not being modified and will to a s=strlen(x); then compare against X for you, but probably not.
The other thing is when searching an array, try to give it structure. If your array contains sorted characters, then you can find it in log _2 (n). Of course, of you sort by frequency (most commonly accessed at the top) then your n^2 loop *might* do better.
The article is right: constant-time operations (type checking, etc) are asymtotically infitessimal in algorithms. The article's real problem is that it is n, but on a 2d image (x*y)=n you can't do any better. Note that it is not n^2, (though it makes a square picture) because you're operating on pixels. So that will be your unit of measure - NOT time.
Which is my 2nd point. Don't measure in time or instructions. Measure in OPERATIONS. Operations are not instructions or lines of code. An Operation is everytime you have to look at a unit. It is a logical unit of cost. Hardware can be changed out. We know that hardware (performance) doubles every 18 months. The constant-time instructions will get smaller. (Also clocks per cycle are irrelevant as well). But your loops will remain the biggest part of your program.
With that, here's a crash course in CS:
To learn more, take a datastructures class at your local university. Please review Calculus II before doing that though.
Re:me too... (Score:2, Interesting)
The Vic20/C64 basic allowed you to merge program lines using a semicolon. This took 1 byte less per merged line, and did indeed run somewhat faster. Since the Vic20 had only 2.3K usable without tricks this was a big deal.
Of course, anyone inflexible enough to carry that through to a C++/C/Cobol project shouldn't be programming.
Re:Quick, go get Fortran 95. (Score:1, Interesting)
Like C++, F95 has opaque types and function (and operator) overloading, and "pointers". These offer all the same merits and demerits as in C++.
Many F95 compilers do not check runtime array bounds, and none do by default. And when they do, the executable slows noticeably. Nobody ships F95-based apps or runs production code with array bounds checking turned on. It just isn't done.
F95 bugs are at least as common as in C/C++, simply because the language's programming idiom does not routinely check return status variables, much less trap exceptions. Maybe that's not the fault of the language, but idioms count just as much as syntax.
I agree that F95 is almost certainly superior to most/all other languages if you need to manipulate arrays. F95's compilers also produce better optimized code than the others (aside from C/C++). That's simply where the priorities of its users lies.
But since most users of F95 attempt a different kind of programming task, with its own characteristic set of bugs, it's not meaningful to compare the subtleties of F95's floating-point exceptions with C++'s null pointers.
Finally, perhaps the reason that "computer science" often underestimates F95 is that there are no books written on the language for computer scientists. Fortran terminology was coined in 1955 and NEVER updated. Rather than use common terms like "record" or "procedure", fortran persists in promulgating its own antiquated argot.
Until fortran "gets with the program", it will remain a language that only an engineer could love.
Randy
Re:Funny thing about performance (Score:3, Interesting)
VIC20 BASIC: Tokens mattered (Score:4, Interesting)
Junior High did not have computers yet. I finally convinced my family to get me a computer if I paid half. With my budget, that meant a VIC20 for under $100. The VIC20 had 4KB of RAM. You could buy a 16KB expansion, but I could not afford it.
The language was the same as the PET, so I tried to run my existing programs. They ran. I tried to modify them, save, and run them, and they would not work, even if the change was to remove code. I finally tried changing all the commands to "tokens" to shorten them. IIRC, a token was the first 2 characters of a command and an underscore. Since most of the commands were 4 letters, this saved quite a few characters. I also renamed all my variables to shorten them. Then I saved and the program ran. Yeah!
Then I made another change, and the problem reappeared.
I decided that:
10 The program loaded as written to the tape. (Hard drive? Floppy disk? Never heard of them.)
20 If the program fit in memory, it would run.
30 When the program was loaded for editing, all tokens were expanded to the full command.
40 The program was saved as text, except...
50 If the tokenized version of a command was encountered, then it was saved as the token. I never figured out if they were saved as the 2 Hex number, the dollar sign and the number, or the 3-character shorthand "token" I typed.
60 GOTO 10 (and see if it runs.)
So every time I wanted to modify the longer programs, I had to change every command to the "token" format. (About half of my programs were under the 4KB limit, about half could be "fixed" using this technique, and a few were large enough that I never got them working again.) Any changes to the longer programs required 20 minutes of "tokenizing" the commands before saving it. That killed much of the fun of programming. (Today I get upset if a build takes longer than a game of Solitaire, but "getting upset" means deciding to fix the build process.)
Commodore bought BASIC from MS, and then modified it, so I do not know who to blame for the hours I wasted on this, but Commodore is gone and MS continues to take the fun out of computers, so I blame MS.
---
My next venture into computers was the C64. They had "Sprites". Half of the code in my games was controlling the graphics, and this improvement to the platform made that code obsolete. For the challenge, I upgraded one game to use Sprites. They took much of the fun out of it, and (IIRC) you were limited to 4 of them, so you had to play games (pun intended) to write PacMan. (4 Ghosts and PacMan required 5 Sprites. The dots and cherries would be handled without Sprites. It was easy to write a 3-ghost PacMan game, and really difficult to write a 4-ghost game.)
Since the C64s at school did not have tape drives, my old programs had to be typed in, if I had a printout from elemetary school (no printer at home.) I already stated that I was lazy, so they are gone. Well, I still have the tapes, but they are 2 decades old, and my PC does not have a tape drive anyway.
Re:This is backward thinking with no vision (Score:1, Interesting)
You're a bit too early to be making that kind of statement. Try again in 15-20 years. Computers are still THAT far behind the processing/memory capabilities of a human.