Emil Ernerfeldt writes about performance, optimization, and low-level programming, including hash tables and memory access.
HN mostly links his "Myth of RAM" essay, which argues memory access time grows with the square root of data size, and commenters find it insightful.
There's an interesting argument based on physics on why memory access is O(sqrt(N)):
http://www.ilikebigbits.com/blog/2014/4/21/the-myth-of-ram-part-i
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…
No answer is complete without getting into fundamental physics, information theory, and blackholes: https://www.ilikebigbits.com/2014_04_21_myth_of_ram_1.html
TL;DR: Time complexity of memory access scales O(√N), not O(1), where N is your data set size. This applies even without hitting theoretical information density limits, whatever your best process size and latency. For optimal performance on any particular task you'll always need to consider locality of your working data set, i.e. memory hierarchy, caching, etc. And to be clear, the implication is that temporal and spatial locality are fundamentally related.
Yes, some cache levels have lower intrinsic latency than others, but at scale (even at-home, DIY, toy project scales these days) it's simpler to think of that as a consequence of space-time physics, not a property of manufacturing processes, packaging techniques, or algorithms. This is liberating in the sense that you can predict and design against both today's and tomorrow's systems without fixating on specific technology or benchmarks.
There was a decent article exploring the timing between memory accesses, and when they started taking longer b/c you hit L2 cache, L3 cache, main RAM, swap, etc., and eventually showed how if you really graphed the access times, the overarching "curve" they followed was square/cube root¹; that is, real world hardware obeys the laws of physics.
My googling dug up [1], but I'm not sure if that's it or not.
My university schooling was pretty straightforward about memory access not being O(1). We also went over adding two numbers together (also not O(1)), but these are just generally elided for brevity's sake; I don't think most of us want to start worrying/optimizing for CPU caches prior to it being a thing that perf testing says we need to worry about.
> 16/32 bit pointers for small arrays?
It's not about the size of the array, it's about the location in memory. If you're storing an index, then sure, knock yourself out.
[1]: http://www.ilikebigbits.com/2014_04_21_myth_of_ram_1.html
¹I'm a software engineer, not a physicist.
> https://johnresig.com/blog/web-workers/
Sorry, I should have said "JS doesn't support shared memory parallelism for all intents and purposes, so memory sharing concerns are a moot point".
> https://softwareengineering.stackexchange.com/questions/2455...
This supports my point; not sure why you're posting this...
> http://www.ilikebigbits.com/blog/2015/12/6/the-fastest-code-...
This is also congruent with my points; if this is meant to be contradiction, you'll have to clarify.
> http://www.ilikebigbits.com/blog/2015/12/6/the-fastest-code-...
I'm not spending any more of my time skimming these mysterious links; this is a very straightforward question and you've evaded it several times and then referred me to an 8 kiloword document. What gives?
No, it will never level off.
You'll always eventually expand past the limits of whatever storage you're using. It's clearly impossible to build totally unlimited storage with constant access time, and you'll always eventually need larger storage (to disk, to other machines, to other data centres, etc), at the cost of speed.
Take a look at [part two](http://www.ilikebigbits.com/blog/2014/4/28/the-myth-of-ram-part-ii), where he runs through this in more concrete depth to back his claims up. The theoretical physical limit for accessing N bits of data is O(sqrt(n)), no matter how you do it, just from the speed of light.
It's counter-intuitive, but this really is true in the general case, not only in the regions shown on that graph.
> JS is not parallelized
https://johnresig.com/blog/web-workers/
https://ponyfoo.com/articles/understanding-javascript-async-await
> Python is also compiled to a bytecode before interpretation; were still don't call it a compiled language.
https://softwareengineering.stackexchange.com/questions/24558/is-python-interpreted-or-compiled
> macros aren't significantly faster
> you can always precompile your abstraction on program load at the expense of slower start times
http://www.ilikebigbits.com/blog/2015/12/6/the-fastest-code-is-the-code-that-never-runs
> How can I ask it what type a function returns or what types it's arguments should take?
http://www.braveclojure.com/core-functions-in-depth/