> Assembly language isn't even the lowest level ... maybe the machine has microcode
Yup. Microops. Your x86 processor doesn't run x86 instructions; it dynamically translates (and caches) them into a small RISC like instruction set which can vary even in different chip models from the same vendor.
X86 is just a convenient "intermediate language". And by convenient, I mean a lot of software exists that runs on it.
But I've got to ask. The biggest things that the STL has that I miss in in Linq.Net are well defined complexity guarantees and exception guarantees.
If I call Count on a pseudo container that wraps a random access container will it perform better than one based on a fwd container? And will it be able to make that optimisation at compile time?
Good question! Complexity guarantees have always been a bit messy for lazy evaluation. I'm not offering an excuse for Linq to objects, just general information. Everything just creates a wrapper, and the behavior of that wrapper depends on what's inside it and so forth.
For instance, consider "r = Range(1, n); r.SelectMany(x=>r.Take(1<<x)).Where(x=>x==1)" -- no Linq operator takes exponential time, but each element of this composition takes exponential steps to compute (1, 2, 4, 8, ...).
That said, I'll do what I can to make sure that the performance characteristics are, at least, predictable.
As for optimizations, I looking at how much we can preserve. Generally, aggregations are always O(N), but we can optimize special cases, such as zero-argument count. Filtering is amenable to bidirectional traversal only, as we need to skip an indeterminate number of elements.