Re^5: What is the most efficient way to see if a hash is empty?

I don't understand how you got to that conclusion. My benchmark (when modified to use scalar %hash shows that there is no O(number of buckets) operation. All it does is factor of 4 or 5 difference between empty and non-empty hashes. For me that doesn't look like a loop, but rather like a good optimization for the empty case.

(For the empty hash the format of scalar %hash differs from the "normal" case. Instead of "$count/$buckets" it's simply 0).

The number of buckets seems to be stored in the MAX field.

Comment on Re^5: What is the most efficient way to see if a hash is empty? Select or Download Code

Replies are listed 'Best First'.
Re^6: What is the most efficient way to see if a hash is empty? by ELISHEVA (Prior) on Apr 28, 2009 at 11:21 UTC
I got that because the more elements the bigger the difference in performance of empty and full hashes. If all we were doing was checking a member of a structure, why would there be any difference at all related to size? Wouldn't the difference between empty and full be simply the difference between one and two pointer de-references - one to get the allocated bucket count and one to get the used bucket count? I should think that would be at most 200%, not 400% and up. And that's assuming that the code involved in dying consumed only a fraction of the time consumed by fetching one or two variables. Best, beth	[reply]
Re^7: What is the most efficient way to see if a hash is empty? by BrowserUk (Patriarch) on Apr 28, 2009 at 12:23 UTC
See the diagrams for HVs at the bottom of PerlGuts Illustrated. MAX is the number of buckets; FILL is the number of those buckets in use; KEYS the number of keys in the hash. In the empty case ARRAY will be null (even though MAX will be minimum 7), hence the 0 returned for the empty case. I think that the differences in moritz' benchmark come about because die is an uncommonly slow opcode--essentially a long jump--which completely swamps the conditional test and so skews the timing beyond recognition. [0] Perl> for(2..6){ %a =(); %b = 1.."1e$_"; cmpthese -1, { A=>q[ for(1 .. 10000){ if( %a ){ 1; } } ], B=>q[ for(1 .. 10000){ unless( %b ){ 1; } } ] } };; Rate B A B 72.0/s -- -90% A 726/s 908% -- Rate B A B 72.6/s -- -90% A 736/s 914% -- Rate B A B 70.5/s -- -91% A 751/s 965% -- Rate B A B 69.5/s -- -91% A 759/s 992% -- Rate B A B 71.5/s -- -90% A 715/s 900% -- [0] Perl> for(2..6){ %a =(); %b = 1.."1e$_"; cmpthese -1, { A=>q[ for(1 .. 10000){ unless( %a ){ 1; } } ], B=>q[ for(1 .. 10000){ if( %b ){ 1; } } ] } };; Rate B A B 75.9/s -- -89% A 709/s 834% -- Rate B A B 73.7/s -- -90% A 730/s 890% -- Rate B A B 72.7/s -- -90% A 747/s 928% -- Rate B A B 71.5/s -- -90% A 725/s 914% -- Rate B A B 70.6/s -- -90% A 708/s 903% -- [download] The difference between empty and full hashes is remarkably consistant--if surprisingly high--regardless of the magnitude of the hash. Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error. "Science is about questioning the status quo. Questioning authority". In the absence of evidence, opinion is indistinguishable from prejudice. "Too many [] have been sedated by an oppressive environment of political correctness and risk aversion."	[reply] [d/l]