And I quote:
“Dude, if your examiners ever find out you were surprised that O(n) operations, like indexing into a list, were slow, your PhD is totally revoked! ;-P”
In light of yesterday’s post, this is a fair comment, but let’s put it in context, yes? (Fear not, gentle reader: ninjas have already been dispatched to deal with the commenter. And, I think the commenter was just teasing me… but, the ninjas will torture that fact out of him at some point or another, no doubt.)
The Transterpreter project has, from the start, been intended to be as simple as it can be in execution and implementation. Our primary goal is to create a portable runtime that can be easily ported to any architecture we encounter. Therefore, throughout the development of the runtime, we have consistently made semantically clear but often computationally expensive choices.
Our architecture is, generally speaking, easily optimized locally, and in some cases globally. However, optimizing sooner (rather than later) is a good way to be left with code that A) you don’t understand, or B) is potentially inflexible or inappropriate in light of later extension. In the long run, our goal is to support an evolving programming language; how do you design tools to support that? Guy Steel gave a brilliant talk on this at Indiana while I was there, and this short article on the Sun website touches on some of the issues involved. In short, the number of factors involved in supporting a growing and evolving programming language are many, and complex.
So, no, we weren’t surprised as such that indexing into a list was expensive. Rarely have I written code where the time/space difference between referencing into a linked list is significantly different than indexing into a vector. If anything surprised me, it was the immediate and obvious disparity between the two, and how (as a Scheme programmer) I often completely forget about the underlying performance concerns. Put another way, I am more often concerned with correctness than performance, or am writing code that A) is evolving rapidly and B) has limited application. Therefore, a list (which is, in a dynamically-typed language like Scheme) becomes a “universal type” that gives me flexibility and freedom to evolve interfaces quickly and without large changes to my core program logic.
In the end, you could argue that we should have known better from the start. However, you could also argue that we’ve used appropriate tools in appropriate ways to get us quite far into a project that otherwise might have become bogged down in details long ago. It is flexible, runs most everywhere, and while it did have a 60x speedup lying around, that speedup took … two, three hours of time to realize fully? This implies that our design was simple and clear enough that we could pluck that 60x off the tree as low-hanging fruit, and not a major architectural overhaul. While some of our local choices may have been naive, our global, or architectural choices have been, I think, sound.
