Scala Vector operations aren't “Effectively Constant” time

It's not really the correct kind of argument. Landau notation is for analyzing asymptotic behaviour of functions; this makes them fit as sets of functions for many purposes in theoretical compsi, but it's simply the wrong approach for practical, "in the field" comparison of implemented algorithms. It only has some merit there to state... well, asymptotic behaviour, like the complexity of a hash-table lookup or deleting an arbitrary element of a vector.

To argue that this is act of pedantry is to argue that any form of canoncial notation to describe the essential nature of algorithms is itself pedantry. It's to suggest bigO notation itself is pedantry and by extension so is it's defense.

In the face of this, I'd say, "If you don't like it, don't use it. But many people do find it useful and it's corrosive in the extreme to demand the right to redefine it for what amounts to marketing purposes." Scala's got a bunch of actors in it's community that do this; and it's frustrating when you're trying to evaluate the ecosystem.

The asymptotic boundaries of algorithms ARE theoretical tools that can be misleading. For example, how many people incorrectly suggest that quicksort is asymptotically faster than merge sort? It's not.

But the response to this should not be to vaguely redefine the terms. The response to this should be to quantify the implementation's docs with real metrics.

They're not all effectively constant though. I can say that effectively all web pages render within 100 seconds and thus web page rendering is O(1), but it's not true because "between visually instantaneous and 100 seconds" is not effectively constant.

In another example, 1 nanosecond and 1 millisecond, separated by six orders of magnitude, are both effectively instant to a human... at least, as long as it's only happening once. Start looping on that and the differences rapidly become, ah, effective.

The root problem here is that pragmatic measures don't fit in math and math doesn't fit in pragmatic measures, and you need to at least be careful not to equivocate back and forth. But there's nothing wrong with either one; you just need to know where you stand. You can't help it anyhow; we are not capable of dealing with the universe with mathematical precision everywhere, we lack the computational power to do so, assuming it is even theoretically possible.

The 32-way tree operations have asymptomic complexity 6 * C_1 * log(n) = C_2 * log(n)

Operations on a balanced binary tree have asymptotic complexity C_3 * log(n) = 6 * C_4 * log(n).

The only difference between the two data structures is the actual values of the constants.

I think the Scala people have a valid point that logarithmic complexity may be as good (or nearly as good) as constant-time in practice. The precise way the claim is formulated is wrong and abuses big-O analysis.

A more correct argument is to choose a practical upper bound on log(n). E.g. maybe 64. Then multiply that by the constant factor (not playing any tricks with splitting out 6 *). If that number is always good enough if practice, then you don't need to worry about your operation being logarithmic.

Another example is Donald Knuth who claims in TAOCP, section 4.3.3 "How fast can we multiply", that multiplication algorithms are effectively linear. Quote: "For all practical purposes we can assume that [...] the Schönhage-Strassen multiplication technique will have a running time linearly proportional to n. [...] The practical problem of fast multiplication is therefore solved, except for improvements in the constant factor."

This really stuck out to me.

http://www.ilikebigbits.com/blog/2014/4/21/the-myth-of-ram-p...

Relevant quote:

> The amount of information that can fit within a sphere with radius r can be calculated using the Bekenstein bound, which says that the amount of information that can be contained by a sphere is directly proportional to the radius and mass: N ∝ r·m. So how massive can a sphere get? Well, what is the most dense thing in existence? A black hole! It turns out that the mass of a black hole is directly proportional to its radius: m ∝ r. This means that the amount of information that can fit inside a sphere of radius r is N ∝ r². And so we come to the conclusion that the amount of information contained in a sphere is bounded by the area of that sphere - not the volume!

> In short: if you try to squeeze too much L1 cache onto your CPU it will eventually collapse into a black hole, and that would make it awkward to get the results of the computation back to the user.

But honestly I find all of these arguments equally pedantic.

People often forget Big Oh is a tool just like any other tool. It's useful for estimating number of X, whether X is cpu instructions, cache miss, disk read or whatever. When it stops being a good estimate (whether it's because your real world N is too small for growth rate to dominate, or stuff you're counting are not unit-cost comparable, or you're not even counting the right things in the first place), just stop using it and count cycles on a benchmark instead.

So "O(Q)" means "there exists some X such that for all accesses of items in a structure of size N at any index it will always take time less than X multiplied by the expression Q, which is expressed in terms of N". O(1) is "constant time", and does not mean things take one instruction: it means the expression does not depend on N. There is no O(1000): that is the same as O(1); and if an operation takes randomly either 10 or 1000 cycles, it still is O(1) as X is 1000: both 10 and 1000 are bounded by 1000 multiplied by 1.

Time complexity is thereby a measure of how scalable something is, not how long it will take. An operation that is linear might beat one that is logarithmic at small values of N, but eventually you will have an input large enough that the logarithmic one is not just faster but will always be faster as the constant multipliers can no longer compensate the bounds for the one underlying expression being swamped by the other one.

The constant time constraint is true for simple memory access on a computer running a single process (which I only add as a constraint as the entire theoretically framework breaks otherwise), even if some accesses take a thousand times longer than other ones: there is a slowest possible time past which it will not be slower. No matter how large the array gets, it isn't going to get slower, even though it is super fast for extremely small arrays that fit entirely in some small amount of cache.

Of course, it might not be true if memory is backed by a file and that file is on network storage, and the remote file is stored in a linked list ;P, but that isn't the situation with cache: the controller doesn't even keep a resizable data structure for cache lookups. If you plotted a graph of the pefromance of lookups vs. the size of the array, once you got noticeably past the size of the cache the line would stop growing, and the entire thing would fit under a flat line at some constant X.

There is a fiction here, and that is that we can think about these issues at all in the world of a computer, which has a limited amount of storage (which means there exists some I past which it is no longer possible to even access elements as we cannot allocate an array that large); but it isn't due to cache misses and has nothing to do with the kind of predictable real-time constraints you describe: those are constant multipliers on the complexity. That is when you enter the world of physics, which is arguably more interesting.

Wouldn't the 6 in O(((n^1000)^n)^6) be a non-constant factor that makes a big difference in asymptotic performance though?

Scala has illuminated the author to a pedantic dissonance in academia: in this case, that true asymptotic analyses should be using O(logn) instead of O(1) for random memory access.

Hence why algorithms like Hoare's quicksort are so fast, they actually are Theta(nlogn) in practice because linear memory access looks like O(1) on modern machines.

(but again pedantically it is probably still O(logn) from gate depth of multiplexing/demultiplexing the architecture's pointer size.)

Edit: Remembering that O((logn)^2) = O(logn), I suppose the author is probably correct.

This rationale ad absurdum means we can call an in-memory linear search "effectively constant" because we have an upper-bound of 2^32 or 2^64, depending on processor architecture.

Yes, log32 is very nice. Even log2 is pretty nice though, and we don't call that "effectively constant", because we already have a much more precise and well defined term for it - "logarithmic" - which the docs also use: http://docs.scala-lang.org/overviews/collections/performance...

You might be able to tell me with a straight face that labeling log32 "effectively constant" and log2 "logarithmic" is "correct enough". But can you tell me with that same straight face, that labeling it "Log32" (or even just "Log") isn't just as correct, more informative, and less confusing?

Notably Vector index access takes 4,260,000 ns for a vector with 1,048,576 elements instead of measured 0 ns for native arrays. is about +4 ns extra per element and hints at the whole data set still fitting into L2 cache.

If the process ends up accessing more working memory than fits into L2 (32 or 64 MB or so) and lookups aren't nicely bundled together, the overhead will approach about +80 ns per element access. Or +0.08 seconds per million element accesses.

It does seem unlikely that every element access would end up causing a cache miss since I'd expect lookups to happen close together, but this can be significant for intense workloads such as OLAP.

Hash tables are usually considered to have constant time lookup, but of course in practice they have to deal with collisions. I don't think it's unreasonable to say that Scala's vector lookups are "effectively" constant time, because they are.