Hacker News Reader

Comment by GuB-42 | Hacker News Reader

About big-O constant, I came to the realization that in the real world, constant time is actually a log at best, but more likely a cube root.

The simple idea is that the most basic thing, that is reading the number "n" depends on the number of digits, so that's a log.

But in most algorithms, the "n" refers to the size of a data set. This set is usually stored in some kind of memory, and memory is a physical array of little cells in 3D space. Accessing that cell means travelling through the array, with a time to reach it proportional to its distance, and since capacity increases with the cube of the distance, the time it takes to get the data is proportional to the cube root of n.

The conclusion, to me, is that when complexity gets down to less than a cube root, mathematical abstractions start to break down and you need to consider the actual machine, in particular its cache architecture.

View on HN

No, memory reads do not depend on the address distance, unless you create a list.

Ordinary memory is not a list. It's a flat space read in O(1).

In theory. In practice there are multiple levels of cache, and cached reads will be much, much faster than main memory reads.

So if your entire data structure lives in cache and you repeatedly loop through it, it's going to be processed much more quickly than a bigger and more spread-out structure.

There's also paging, and alloc/dealloc to consider, and maybe garbage collection.

By the time you include all of that big-O estimates can become wildly misleading generalisations, unless your n is always >a million or so.

For small n it can be way off.

For any big enough memory the speed of the memory reads will depend on address distance, at least due to the finite propagation speed of the data that is read.

Sequential reads from adjacent cells will be pipelined, so they can have a throughput that does not depend on the distance in address, but the latency to start another sequential read stream from a different address must depend on the address, for very big memories, e.g. of rack size, where the propagation from a corner of the rack to the other corner takes a long time in comparison with the memory clock.

They mean physical distance, not "address distance".

And in the general case, memory reads do depend on distance. Hence:

> In practice there are multiple levels of cache, and cached reads will be much, much faster than main memory reads.

This is why we have the cache levels in the first place. And the hierarchy continues: L1, L2, RAM, block of spinning rust in the closet, "the cloud" somewhere... There is only so much storage you can fit close to core! More = physically bigger = physically further away.

Sure, within a level might feel like constant time. But that's because the optimal case for that level is slowed down to match the suboptimal cases. The step discontinuities in access time are caused by our inability to engineer a system to manage this tradeoff continuously, not a fundamental law.

Cache is not fast because it's physically close to the core. Well okay, closeness does matter but it doesn't matter as much as the fact that cache is static, i.e. it's (effectively) made of flip-flops.

If you build a computer with DRAM 10 cm away from the CPU and static RAM 50 cm away, access times for the static RAM will still be much lower than access times for the DRAM.

Why don't we just build all RAM as static? Because it's more expensive per bit, it uses more energy, and it requires a great deal more silicon area.

When we are talking about galactic algorithms we have long since left the realm of things that might fit on one computer. Some of these algorithms are only starting to become faster on n so large that we have trouble fitting the data in this solar system. At those scales the distinction between the type of RAM is irrelevant. At that point "how long to read memory address X" is pretty much the same as "how long does light take to reach X" which is pretty much "how far to X" which scales with a cube root. (Well, probably a square root if we look at physical limits for weird reasons)

My understanding is that in the limit (i.e. before you create a black hole), information density actually scales with surface area, not volume, so square root. And then of course at that kind of density, you'd have to account for time dilation as well...

"Information density" is a ratio, i.e. the ratio between the amount of information and the length, area or volume in which it is stored, so it does not "scale".

The amount of information at high enough amounts scales with the volume in which it is stored.

Because of the need to be able to reach the cells that store information, the density of information is normally high in 2 directions an low in the 3rd direction.

This is why it is useful to distinguish between the density of information per area, which is determined by things like the size of a magnetic head or the resolution of a photolithographic process, and the density of information per volume, which is determined by the density of information per area and by some kind of layer thickness, which is usually determined by mechanical considerations, e.g. to ensure enough strength for a tape or a disk or an integrated circuit package.

Like I have said, at high enough amounts of information you reach an almost constant information density per volume, like in a rack full with HDDs or in a magnetic tape robotic library.

Yes, misspoken. Anyway, not that I'm an expert here but my understanding is that at maximum density, information in a region does not scale with the volume in which it is stored; it scales with the surface area of the event horizon it creates (at least for a Schwarzschild black hole). Is that incorrect?

The amount of information you are talking about is quite a bit lower than the amount I'm talking about. Big O is about limits, so if we're going to bring physical limitations into play to say there's some limit to density, you'd might as well go all the way. It's not limit as n -> 10^18; it's limit as n->infinity. You can't keep adding information and still get cubic scaling.

Some of the computation models (including the ones in some of the OpenAI papers in question) avoid this particular concern by working in a multi-tape Turing machine model. One might quibble about the energy cost of moving an entire infinite tape (because it’s multi-tape and, for bounded communication code, the heads need to stay near each other), but the machines really are local in a fairly strong sense.

Reply on news.ycombinator.com