No, it's O(1). Time complexity is about how the execution time grows with the size of the input, not the size of the program. In this case, each of those lambdas is a piece of the program text; the size of the jump table is therefore a constant for any particular program. The time complexity here is the time taken for one jump through the table as a function of the number of jumps, and clearly that's a constant also.
In fact, it would still be a constant if the 'case' were implemented as a chain of 'if's. Time complexity, since it concerns asymptotic growth of runtime as a function of input size, is not the correct notion to invoke here. You're just interested in performance in the ordinary sense: you want your program to run as fast as reasonably possible, and you know that a chain of 'if's leaves something to be desired in that regard.
Fair enough. But let's look at the array-of-closures implementation again. Assuming that the number of jumps made through one of these tables, once you've created it, is much larger than the number of times you have to create a table, it's a perfectly workable implementation.
I think your second point is more substantive. I too have come to the conclusion that coroutines were an unfortunate omission from the CL spec.
I stand by my claim. The size of the jump table of N entries takes O(N) time to construct at runtime. This construction cannot be done at compile time if the lexical environment must be accessible. A linear chain of N if-expressions constitutes an O(N) dispatch at runtime as well.
The point of a jump table is to compile N branches, laying them out in memory at addresses known at compile-time, and allowing a fixed jump to occur during program execution, equivalent to incrementing a program counter by some static amount. This cannot be done portably in ANSI Common Lisp.
The best you can do is construct a binary tree of IF branches to achieve O(log N) time.
You cannot construct the vector of N function entries without first constructing the vector (can be done at compile time), without second constructing N closures representing the code you’d jump to (must be done at runtime to capture the lexical environment), and without third populating the vector (must be done at runtime since the data being populated has been constructed at runtime).
Once the jump table is constructed, the actually vector dereference and call is O(1), but that’s beside the point if each invocation requires linear construction.
The number of possible inputs is proportional to the size of the table (i.e., number of entries) for which it can discriminate. It may be that the input is an integer N of unbounded length (say, K bits), which means that the time complexity is O(2^K) = O(N) > O(1).
If you don’t believe me, please show me how you would implement this.
> Once the jump table is constructed, the actually vector dereference and call is O(1), but that’s beside the point if each invocation requires linear construction.
Not necessarily. What matters is the ratio of calls through the table to the number of times the table is constructed. If that ratio is bounded, for any size input, then you have a point. My response is simply that programs for which such bounds exist are relatively rare in practice; the common case is that such a table will be called through many more times than it is constructed, and furthermore that the ratio of calls to constructions will increase without bound as the size of the input increases. Then the fraction of time that the program spends constructing the tables asymptotically approaches zero.
Admittedly, this argument is of little comfort if you're actually writing a program that constructs many such tables, only to call through each a small (and bounded) number of times. But the force of that fact as a criticism of a language has to take into account the likelihood of needing to write such a program in the first place.
> I too have come to the conclusion that coroutines were an unfortunate omission from the CL spec.
There was no consensus on multiprocessing at the time of standardization and language support was very uncommon.
But still it’s weird: coroutines were over 20 years old by then, and newer ideas like the condition system and CLOS were included. And while nowadays the CL runtime is considered small, at the time it was criticized for being too large.
Coroutines are not quite threads, but then, they don't require a scheduler. They're also not quite firstclass continuations, but then, they're simpler to implement, simpler to use, and don't have the same implications for the rest of the language and implementation design. Still, they can do some of the things you might otherwise use threads or firstclass continuations for; and as reikonomusha points out, those things can be quite difficult to do otherwise in a clean way.
I'm sure some of the implementors (though not Symbolics, of course) would have been unenthusiastic about their inclusion, but still I wish it had been done.
Coroutines and first-class continuations make the implementation of non-local transfer of control much more complicated.
Their inclusion would have made staples like unwind-protect, conditions, and underlying them try/catch, much more difficult to implement, if not nearly impossible to get right.
I personally think that those language features are worth it and that this particular trade-off was well made.
I think it’s pretty obvious what the GP means, and quibbling about big-O notation changes the argument. The GP didn’t really mean “it’s impossible to build an n-branch case which captures the lexical scope and operates in constant time” because you can do that in any language. The GP means “it’s impossible to build an n-branch case which captures the lexical scope where the time taken to choose a branch doesn’t depend (modulo Professor caches) on the number of branches.
Therefore to reply as if the GP were making a statement about O-notation is to reply to a point which was not made.
What GP means is slightly fiddly to define formally as you need to formalise the jump operation that processors can do in constant time, but informally I think it’s completely obvious what this means. It’s also obvious you can do this in C (with the extension that lets you make jump tables) or assembly for basically any modern ISA, so I think it is reasonable to complain that you can’t do it in CL.
> The GP means “it’s impossible to build an n-branch case which captures the lexical scope where the time taken to choose a branch doesn’t depend (modulo processor caches) on the number of branches.
But the array-of-closures implementation satisfies that requirement! reikonomusha's objection to that proposal is that even though the time for one branch is constant, there is a setup time dependent on the number of branches. This is true. The essence of my reply is that it is, however, unlikely to matter much in practice, because the whole thing still runs in amortized constant time [0] per jump.
If you're doing something that's really so performance-sensitive that amortized constant time per operation isn't good enough for you, then you're probably going to have to work in C or assembler, because any higher-level language — even C++ — will have constructs with linear setup times (consider 'make-array' in CL, or 'std::vector' in C++).
> It’s also obvious you can do this in C (with the extension that lets you make jump tables)
Complaining that CL is deficient because a nonstandard extension exists in some other language that allows you to do something, or that you can do it in assembler, seems like a rather weak criticism. Besides, this seems to me more like a quality-of-implementation issue: as reikonomusha mentioned, it's entirely possible for a CL compiler to compile 'case' into a jump table, given reasonable constraints on the case values. I don't know which ones do this, if any, but it seems like the kind of thing the SBCL maintainers could be persuaded to do if someone had a clear need for it.
In fact, it would still be a constant if the 'case' were implemented as a chain of 'if's. Time complexity, since it concerns asymptotic growth of runtime as a function of input size, is not the correct notion to invoke here. You're just interested in performance in the ordinary sense: you want your program to run as fast as reasonably possible, and you know that a chain of 'if's leaves something to be desired in that regard.
Fair enough. But let's look at the array-of-closures implementation again. Assuming that the number of jumps made through one of these tables, once you've created it, is much larger than the number of times you have to create a table, it's a perfectly workable implementation.
I think your second point is more substantive. I too have come to the conclusion that coroutines were an unfortunate omission from the CL spec.