5 ms·

Maybe I'm not familiar enough with Perl's implementation of "Hash", but if it's what I expect a "Hash" to be, access time is constant. What kind of data struct

Maybe I'm not familiar enough with Perl's implementation of "Hash", but if it's what I expect a "Hash" to be, access time is constant. What kind of data structure was actually in play there?

bane 12y ago
Hashes end up O(n) not O(k) in worst case scenarios. Arrays are guaranteed O(k). But that's also a simplistic view of how they work. Hashes, by necessity are far more complex than arrays. As you use them, there's lots more overhead involved that can cause things like cache misses, memory doubling when growing, rehashing etc. More importantly, hashes need to store both the key and value pair. Arrays just need to allocate memory and user pointer arithmetic to offset from the array start location to arrive at each index. If you think of an Array as just a Hash with numbers for the keys, Arrays "store" the keys basically for free. While even a hash with integers for the keys has to store 4 bytes for each key (on 32-bit implementations). When hashes hit some utilization percentage, Perl (and any sane language) constructs a new, larger hash, then moves all the keys and values over (requiring all the keys to be rehashed again). When Perl lists get need to grow, a new array is constructed and all the pointers from the old one are copied over to the same indexes in the new one, no rehashing is needed and no values need to be copied. Destroying the old array and returning it to memory is also easier and faster than destroying the old hash. Hashes are also much more aggressive in resizing. I believe Perl Arrays resize only once they're 100% consumed, but hashes, in order to prevent collisions, have to resize once they hit something like 50% utilization, and they grow by doubling their space leaving lots of unused entries in the hash (I could be wrong on the exact details, but the ideas is the same). Here's the illustrations of Perl's datatypes. It really clears up lots of mysteries about how Perl works internally. http://www.cpan.org/modules/by-module/LWP/GAAS/illguts-0.09.pdf http://www.cpan.org/modules/by-module/LWP/GAAS/illguts-0.09.... The relevant portions are "AV" and "HV". I haven't read this in years, but at one point I had large chunks of it memorized and could hand count the number of bytes in memory I expected a Perl datastructure to take up and be fairly accurate with it. For sake of comparison it's useful to run the following code. An Array version for($i=0;$i<1000000;$i++) { $av[$i]=$i; } system("pause"); And a Hash version for($i=0;$i<1000000;$i++) { $av{$i}=$i; } system("pause"); and check the memory usage for both. On my system, the first one consumes about 35MB of memory. The second one takes about 216MB of memory and is a hair slower. Now suppose each entry in each structure pointed to another array or hash respectively each with a million entries, and each of those in turn did the same. The memory growth of the array version is going to be much slower than the hash version. This holds true for most languages, they implement their arrays, lists and hashes similarly and have similar issues for all of them.
- zak_mc_kracken 12y ago
  Thanks for the clarification. It's pretty appalling for Perl, though, and I don't agree with your claim that this holds true for most languages. A lot of languages have specialized structures for arrays and on the JVM, there is even close to no penalty for using ArrayList over a regular array (it's actually recommended for a bunch of reasons). There is really no excuse for taking so long to populate a hash table (as long as the hashcode implementation is reasonable), especially if the indices are integers.
  - bane 12y ago
    If I understand how Java implements the ArrayList, yeah, there's not much more overhead vs. an Array. I don't have the time right now, but I'd be interested if you could whip up a quick simple profile like I did above for various generic Java collections like Map<T,T> and HashMap<T,T> and observe the time and memory consumption for each. I'd guess that the various Hash-like collections in Java will display a similar memory consumption to Perl's.
  - bane 12y ago
    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.

Maybe I'm not familiar enough with Perl's implementation of "Hash", but if it's what I expect a "Hash" to be, access time is constant. What kind of data structure was actually in play there?

bane 12y ago

Hashes end up O(n) not O(k) in worst case scenarios. Arrays are guaranteed O(k). But that's also a simplistic view of how they work. Hashes, by necessity are far more complex than arrays. As you use them, there's lots more overhead involved that can cause things like cache misses, memory doubling when growing, rehashing etc. More importantly, hashes need to store both the key and value pair. Arrays just need to allocate memory and user pointer arithmetic to offset from the array start location to arrive at each index. If you think of an Array as just a Hash with numbers for the keys, Arrays "store" the keys basically for free. While even a hash with integers for the keys has to store 4 bytes for each key (on 32-bit implementations). When hashes hit some utilization percentage, Perl (and any sane language) constructs a new, larger hash, then moves all the keys and values over (requiring all the keys to be rehashed again). When Perl lists get need to grow, a new array is constructed and all the pointers from the old one are copied over to the same indexes in the new one, no rehashing is needed and no values need to be copied. Destroying the old array and returning it to memory is also easier and faster than destroying the old hash. Hashes are also much more aggressive in resizing. I believe Perl Arrays resize only once they're 100% consumed, but hashes, in order to prevent collisions, have to resize once they hit something like 50% utilization, and they grow by doubling their space leaving lots of unused entries in the hash (I could be wrong on the exact details, but the ideas is the same). Here's the illustrations of Perl's datatypes. It really clears up lots of mysteries about how Perl works internally. http://www.cpan.org/modules/by-module/LWP/GAAS/illguts-0.09.pdf http://www.cpan.org/modules/by-module/LWP/GAAS/illguts-0.09.... The relevant portions are "AV" and "HV". I haven't read this in years, but at one point I had large chunks of it memorized and could hand count the number of bytes in memory I expected a Perl datastructure to take up and be fairly accurate with it. For sake of comparison it's useful to run the following code. An Array version for($i=0;$i<1000000;$i++) { $av[$i]=$i; } system("pause"); And a Hash version for($i=0;$i<1000000;$i++) { $av{$i}=$i; } system("pause"); and check the memory usage for both. On my system, the first one consumes about 35MB of memory. The second one takes about 216MB of memory and is a hair slower. Now suppose each entry in each structure pointed to another array or hash respectively each with a million entries, and each of those in turn did the same. The memory growth of the array version is going to be much slower than the hash version. This holds true for most languages, they implement their arrays, lists and hashes similarly and have similar issues for all of them.

zak_mc_kracken 12y ago
Thanks for the clarification. It's pretty appalling for Perl, though, and I don't agree with your claim that this holds true for most languages. A lot of languages have specialized structures for arrays and on the JVM, there is even close to no penalty for using ArrayList over a regular array (it's actually recommended for a bunch of reasons). There is really no excuse for taking so long to populate a hash table (as long as the hashcode implementation is reasonable), especially if the indices are integers.
- bane 12y ago
  If I understand how Java implements the ArrayList, yeah, there's not much more overhead vs. an Array. I don't have the time right now, but I'd be interested if you could whip up a quick simple profile like I did above for various generic Java collections like Map<T,T> and HashMap<T,T> and observe the time and memory consumption for each. I'd guess that the various Hash-like collections in Java will display a similar memory consumption to Perl's.
- bane 12y ago
  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.