[lorenzhs]

That's a common misunderstanding of what "Big-O" is, but rephrased as "the models used for algorithm analysis assume very simple machines that don't represent actual computers all that well" your point is very valid. There's a whole lot of things that our computers do that aren't accounted for in the RAM model (which is most commonly used when analysing sequential algorithms). Memory hierarchies are a big one (the external memory model accounts for a two-level hierarchy, and can be used to reason about cache usage or external memory ("out-of-core")), but other things such as branch (mis-)predictions or virtual memory translation (TLB) are rarely accounted for. That's what the field of Algorithm Engineering is about: designing algorithms that have good worst case guarantees ("Big-O") but that are also really fast when implemented on real-world hardware. (Given the publication list on your website, you probably know all this, but I wanted to expand on it for others)

[Certhas]

There is the idea that you should treat memory access as an O(N^.5) operation:

https://github.com/emilk/ram_bench

I am not sure if any serious academic work has been built on this model, but it's a nice short hand.

[gnramires]

This is somewhat universal. (Some physical insights)

Naively, to achieve optimal access time, you can pack your memory within a sphere of radius R, and R=O(N^(1/3)).

But, for large R you start having cooling problems. If each memory element needs some power P to operate, then the total power consumption is P×N = O(R^3). But your area is only 4pi R^2, so the power flow per unit area is O(R)=O(N^(1/3)). So if it has large radius, and it has limited thermal conductivity, your memory will melt (since temperature ~ power flow^(1/3) (Plank's law)).

The threshold for stable temperatures at any radius is memory access as O(N^(1/2)).

This analysis is valid for general computing and circuits, but since computers are usually modeled as memory machines I think that's sufficient (?).

Obs: Why, or how, is the human brain roughly spherical then? Because we have a very effective (water based) cooling system. Still, if it got large enough, and you admit limited flow rates of water and such, cooling eventually would be limiting. If you immediately thought of elephants, so did I, and this may be linked to their fantastic large ears:

https://asknature.org/strategy/large-ears-aid-cooling/

I love how everything is connected.

Obs2: Yes this is related to the Bekenstein bound, but much more relevant of course (because existing RAM is almost thermally limited and you need black hole densities to achieve bekenstein bound). The memories we use are organized in (mostly) flat packages.

[Certhas]

The true spherical cow model of circuits.

I do wonder though if this is really the mechanism behind the observed N^.5 law. As you allude to with Bekenstein, just because there is an eventual physical limit doesn't mean the structure of real hardware mirrors it.

Also, we are not limited to dissipation to transport heat away...

[lorenzhs]

Well the problem with that is "this is a curve that roughly fits the data" is a bad way to go about constructing a model. It's a useful and neat observation, but that doesn't make it a good model. It might model random accesses to memory reasonably well (such as traversing a linked list, the example used there), but it doesn't model a scan over an array well. That doesn't make for a useful model. In contrast, the external memory model assumes a fast internal memory of size M (e.g., cache), which can be accessed in constant time, and a slow external memory of infinite size (e.g., RAM) which can only be accessed in blocks of size B (e.g., a cache line). Then you count how many blocks the algorithm needs to read or write. Now, scanning an array of size N takes O(N/B) I/Os, whereas scanning a linked list of the same size takes O(N) I/Os. The complexity of sorting is O(N/B log(N/B)/log(M/B)) I/Os. This models the same behaviour in a much cleaner way, applies equally to all levels of the memory hierarchy (you can also view RAM as the internal memory and a hard disk/SSD as the external memory), and is widely used in what you called "serious academic work" :) See also https://en.wikipedia.org/wiki/External_memory_algorithm

Furthermore, the introduction in the article you linked misunderstands Big-O notation so incredibly fundamentally that I don't think the author has done their background reading on machine models and Big-O notation.

[Certhas]

It is not obvious that a two level model is a cleaner way to think about todays memory access, which has 4-5 levels of caches before you even hit possibly NUMA RAM, then an SSD, then a HDD and then maybe big datasets that can only be accessed over the network.

But then, I am a physicist, not an engineer, so to me starting from empirical observations is actually a very good way to construct a model.

[lorenzhs]

Well you can apply it to any pair of (adjacent) levels of the memory hierarchy. But the main problem with the square root model is that it only models random access time, but not when they are incurred and when data is already in cache. (There are also 2-3 levels of caches, no architecture that I’m aware of has more than 3, maybe 4 if you count the CPU registers but their allocation is usually fixed at compile time)

[naasking]

> I am not sure if any serious academic work has been built on this model, but it's a nice short hand.

Not that nmodel specifically, but cache-oblivious data structures are specifically designed to scale well in a hierarchical cache model, no matter the cache block size. So they scale excellently across L1 cache all the way down to hard disk.