Okay, so I did a version of this in Java.
And a regular old int[] consumes a little over 12MB.
int [] a = new int[1000000];
for(int i=0;i<1000000;i++){a[i] = i;}
An Integer array of a million entries like this consumes a little over 42MB.
Integer [] a = new Integer[1000000];
for(int i=0;i<1000000;i++){a[i] = i;}
And an ArraList<Integer> consumes around 35MB (a bit surprising)
ArrayList<Integer> a = new ArrayList();
for(int i=0;i<1000000;i++){ a.add(i); }
A HashMap consumes about 77MB.
HashMap<Integer,Integer> a = new HashMap();
for(int i=0;i<1000000;i++){ a.put(i,i); }
A Java process on my machine, doing nothing at all except spinning a loop consumes about 8.5MB.
- Java ints are 32-bit or 4-bytes. Theoretically then, An array of a million ints is just 41,000,000 or 4,000,000 bytes or just under 4MB. As we can see in my test, 4MB + the size of the JVM running is just about 12MB, or pretty much what's expected.
- An array of a million Integers is actually an array of 64-bit pointers pointing to a 32-bit int, with some other overhead. I've read that an Integer object consumes about 16-bytes total. So a million of those is 15.6MB + 8.5MB = 24.1MB. The actual memory consumption is 42MB, so I'm off by about half, I'm not sure where exactly, but there's probably some kind of extra references to something I'm missing or some kind of JVM house cleaning I'm not thinking about.
- An ArrayList appears to be a nice abstraction on an Array (O(1) adds, get, etc.) It probably has some logic to do the Perl thing and just has some logic to build bigger arrays as more stuff is added. So there's probably some kind of internal penalty when they're exceeded.
But at any rate, I wouldn't expect the memory consumption to be all that different from an array of Integers. And the test shows it to actually be a little tiny bit less at 35MB.
- Now we come to a HashMap. A HashMap is basically a list of key->value pairs. This means that for an entry in the HashMap we need something like (I'm probably wrong in the specific details, but this is a useful thought experiment)
key (8-bytes for pointer to 16-byte Integer) + 8-byte pointer to the value = 32-bytes
value (8-byte pointer to a 16-byte Integer)
So a k->v pair is 56bytes.
1 million of those is about 55MB + 8.5MB = 63.5MB.
BUT, hashes don't consume space linearly as they grow. Many hash function will double the size of the hash once it passes some consumption metric, maybe 50%.
Thus we have potentially 1,000,000 completely empty HashMap entries. Which look like this.
empty key (8-byte pointer to NULL)
value (8-byte pointer to NULL)
or 16-bytes doing nothing in particular 1,000,000 empty entries (50% of the total hash size) ~ 16MB
for a total of 63.5MB + 16MB = 79.5MB. Our actual is 77MB so we're within spitting distance.
So if you consider that Perl's version of this test is 35MB for the Array version, which is on the order of what Java was providing we're pretty good. While the Perl Hash version took up 216MB vs. 77MB -- which is not too surprising as Perl's dynamic typing objects take up lots of memory under the hood.