It's interesting that all your calculations are about the memory footprint of these data structures, which in my experience, have very, very little impact on the performance of a big application. Need more memory? Just buy it or allocate it at startup. Problem solved.
I really wish more of the scaling problems I encounter on a daily basis were memory footprint related, but the reality is that they never are.
The real problem that was plaguing Perl in the example posted above was the runtime cost of operations which, in any reasonable library or language, should be constant but is apparently linear in Perl.
Well, strangely enough memory allocation/deallocation takes time. The fewer bytes you shuffle around, the less time memory operations consume. On some systems, once you start exceeding physical memory, you end up in swap space, which slows things down even further. Once you run out of every possible place you can stash something, your run-time effectively grows to infinity because your process has crashed.
So if your data is consuming 32gb of memory, and all 32gb have to meander their way into a register and back out, assuming a mov operation takes 1 CPU cycle. You've effectively had to move 64gb of data.
On a machine with 64-bit word length that's ~537 million cycles to move in and 537 million cycles to mov out or about 1 billion CPU cycles.
That may not sound like a lot, but nobody just moves things into or out of a register. Let's say you're doing some kind of multiplication. That's 3 cycles per mul * 537 million = 1.6 billion CPU cycles.
And now you're at 2.6 billion CPU cycles just to do something like "multiply each of half a billion numbers by some number" (assuming all the data fits in memory). Again, on a Ghz + machine that may not sound like a huge number, but hopefully you can see that the number start adding up quickly and I'm just calculating out a trivial operation of effectively 3 ASM operations.
One big mistake people make is assuming pointer dereferencing is "free". But all that dereferencing takes time as well. The pointer has to be moved into a register, read, then that memory location has to be moved into memory and then you might be able to do something to it.
Or take something like the example given in Perl. In theory a hash lookup can be O(k) if you're lucky. But that discounts the time it takes to run the hash function on the key, mov pointers around, lookup values, move more memory addresses around, search memory for a free spot to malloc (and if you're out and have to swap to disk, there goes a couple billion cycles waiting for that to happen)....etc. etc. etc. Oh, your hash is 50% utilized, let's wait while a new hash object is malloc'd that's twice the size of your current one, and every k->v pair is rehashed and inserted into the new hash, then the old hash is destroyed.
In the middle of all this, your OS is moving the entire execution stack all over the place as it context switches through the hundred processes that you have running so each can get a chance to do what they do. So while your process may only "need" a 20 or 30 billion CPU cycles, it takes 2000 or 3000 billion CPU cycles for it to get all those.
I'm oversimplifying, modern CPUs are much smarter these days and make some thing likes context switching less expensive, but the point still stands. If you're trying to compute something on lots of memory, it will take lots of time. Trying to fit your problem data into a more compact form might take less time if you run the numbers and figure out the cycle cost...which practically nobody who graduated school in the last 10 years knows how to do.
The next biggest thing you can do is algorithmic. You can often literally take a problem that will run until the universe grows cold, and turn it into a problem that can finish in a few minutes with a solid understanding of algorithms.
I'm continuously amazed at how relatively small datasets (small by way of the power of the machines we have today), and problems that should be quick single machine problems, get turned into entire racks full of machines running night and day. We've gotten really good at interconnecting machines to do useful things, but really stupid about how to get even a fraction of the performance potential out of an individual machine.
I really wish more of the scaling problems I encounter on a daily basis were memory footprint related, but the reality is that they never are.
The real problem that was plaguing Perl in the example posted above was the runtime cost of operations which, in any reasonable library or language, should be constant but is apparently linear in Perl.