Archive for February 14, 2007

Wednesday, February 14, 2007

C Is the New Assembly

Daniel Jalkut (paraphrasing John Gruber):

He suggests that a typical developer will write everything in Ruby or Python, and then do performance testing. Anything that needs a speed-up can be redone in Objective-C. You know, that “slow” dynamic variant of C :)

This analysis is foreboding, because it’s exactly what programmers have always done when they switched to a higher level language. 10 years ago a programmer would be more likely to “switch to assembly” for a much-needed performance boost. Has it come to this?

Yes, it has. However, I’d like to add a few points. First, while in general it’s true that “scripting” languages are slow(er) and Objective-C is fast(er), this is not always the case. I suspect that common computations using lots of arrays, dictionaries, numbers, strings, etc. are faster in Python than in Objective-C/Cocoa due to less memory management and dispatch overhead. Likewise for text processing, since in the scripting languages the regex engine works directly with the native string type. Of course, Objective-C has the potential for very high performance if you drop below the object level or use Objective-C++.

Second, achieving better performance by recoding in Objective-C doesn’t work quite the same way as recoding parts of a C program in assembly. The difference is the bridge. A hybrid application must be developed with careful attention to bridging overhead, which can be a much bigger performance drain than the fact that the scripting language isn’t compiled down to native code. You must decide early on which areas of your application will use Objective-C objects and which will use scripting-language objects.

If you do everything with Objective-C objects, you can recode select objects in Objective-C to improve performance, but the ones coded in your scripting language (the majority) will be doing a lot of bridging, and you won’t be able to take full advantage of your scripting language because you’re limited to the Objective-C object model.

On the other hand, if you do everything with scripting-language objects you can avoid a lot of bridge overhead (within your own code—you increase the overhead when Cocoa needs to talk to your code), but it becomes more difficult to improve performance by recoding an object in Objective-C. Doing so will make that object locally faster but will add overhead due to the fact that the rest of your code now has to talk to this object via a proxy.

Regular Expression Performance

In this very well written article, Russ Cox explains why most current regular expression implementations have exponential running times for certain patterns, while Ken Thompson’s NFA implementation from the 1960s is linear for all inputs. Cox suggests that the NFA approach is compatible with modern regex features and that this is how regular expressions should be implemented. My hunch is that the current recursive backtracking implementations would be faster and use less memory for most real-world, non-pathological inputs and that they have better engineering characteristics, such as being easier to understand, debug, extend, and modify. Perhaps there are clever tricks that can be employed with the NFA implementation, but I suspect that this is an area where the theory is very nice but doesn’t lend itself to an efficient and modular implementation. Thus, I favor a hybrid approach where the simpler pathological patterns are dispatched to a Thompson NFA and the rest are handled in the normal way. (Via John Gruber.)