Thanks for the link, now I got my answer. However, now a more serious question is raised.
According to perldata, the denominator of that fraction is the number of units of momery, perl has allocated for your hash, and more interestingly, the denominator is always a number of 2's power.
This algorithm of allocating memory really worries me, because it indicates, that it intends to waste more memory, when your hash gets bigger, because whenever you used up the memory been already allocated, perl would just double it.
I can understand the thought behind this algorithm, one is thinking, okay, I already gave you a big piece of memory, but it is still not big enough for you, instead of wasting time to give you all those small pieces, let's just double the memory I gave you.
I can understand this is a space vs. time thing, and I have no problem with that, but I still feel this algorithm is way too rough. there must be other more delicate/fine solutions.
| [reply] |
Hashes are known to be innefiicient uses of memory. Thats the tradeoff you get for speed.
One thing I did recently discover is that a nearly full hash will tend to have its elements in some kind of well defined order.
For example if you do letter frequency analysis of a large document because you think this might be fun for cryptography you end up with a hash %frequencies which contains most of the ASCII character set from 32 to 127 and they are also in nearly alphabetical order that is keys %frequencies produces a list ... 'A', 'B', 'C', 'D' ...
Dingus
Enter any 47-digit prime number to continue.
| [reply] |
You are right, given the appropriate frame of reference ;-)))
Old OSs actually gave you the memory you requested.
In modern, sane operating systems, allocating memory is not the same as occupying it. If you do char* m=malloc(10*1204*1024), you are telling the OS (OK, the C library, which could do some magic, but the result is the same) that you want a megabyte added to your address space. So the OS (for example) adds a couple of lines to your process' page table, and you have your address space. When then you do c[200]=0, the OS tries to access the memory, gets a page fault, remembers that it has to actually give you that memory, and creates a page (a single page, mind, usually in the order of 4KB) to store your data in, attaching it to the appropriate entry in the page table. Now you are occupying memory. 4KB of it ;-)
So the space occupied is less than the space allocated. Given that most of the time is spent in the allocation phase (you have to keep track of the memory at the OS, library and probably application levels), always doubling the memory allocated to a growing container insures an "amortized linear time" complexity (meaning that it's linear in the mean, but sometimes it is slower (alloc), sometimes faster (write)).
--
dakkar - Mobilis in mobile
| [reply]
[d/l]
[select] |