Friday, January 23, 2009


There is this annoyingly widespread perception among programmers that C is magically faster than anything else. In one sense this is true - if you have a program in some other language which is faster than the C equivalent, you can turn it into an identical C program, since C allows you to write assembly code inline. This isn't a very useful thing to actually do, however. In practice, C has to give up on a lot of performance, for a few reasons.

  1. Pernicious overallocation: When allocating memory, you either have to have complicated code to grow buffers on the fly, or allocate as much as you could ever possibly need up front. In C, the latter is almost always chosen, for simplicity's sake. This leads to programs taking up more memory than they really need to.
  2. Terrible string support: Or to be more precise, nonexistent. C strings have two major problems. First, null-terminated strings are slow - to get the length of a string, you have to read through the entire thing! They also makes it unreasonably difficult to apply certain loop optimizations to strings. Second, having strings as plain arrays means that you can't make immutable strings, which in turn means that every time you pass a string to code you don't control, the safe thing to do is make a copy of it. (See 1.)
  3. Pointers: In a nutshell, the problem here is that it's difficult (maybe impossible?) for the compiler to get complete data about what pointers go with what memory, and that hides a lot of optimizations from the compiler. A lot of work has been put into pointer analysis, and they've accomplished some pretty amazing stuff, but at the end of the day, it's still not a solved problem.
Why is it such a problem when stuff gets hidden from the compiler? C is as fast as it is for two reasons. The first is that, being a lower-level language, it allows people to write more low-level code. The second is that, after a few decades of improvement, it has really really good optimizing compilers. For a language that depends on compiler as much as C does, it's essential that the language not get in the compiler's way.

There's more I want to write about this, but I also kind of want to sleep. >_>

1 comment:

Kiriska said...

I don't blame you. I'd want to go to sleep after writing that too~.