I agree with everything you said (hence the winky hanging off of "theory"), except for this: > I find it unlikely that much insight can be gained from this for

I agree with everything you said (hence the winky hanging off of "theory"), except for this: > I find it unlikely that much insight can be gained from this for in-memory data structures. Reasons for my skepticism: First, better big O results usually come with some valuable insights that can be reapplied. Second, the tradeoffs in constant factors are really hard to predict. E.g. the extra CPU cycles may pay for themselves by increased cache coherency or better behaviour under multi-core contention. Hard things to even measure, let alone predict. ;) Third, besides caring about absolute speed, degradation is important in some cases -- an in-memory-only implementation that the OS decides to swap out to disk won't hit (as much of) a brick wall if/when that happens. Fourth -- although the extra complexity is prohibitive, MVCC tuned specifically for a specific data structure will almost certainly do way better on all kinds of metrics than a language/runtime-wide implementation. Appropriate for clojure? Not my call. Useful in general? Probably so.