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

[Anonymous Monk]

Devel::Peek and a quick perusal of the sources seems back up the idea that its a lookup

C:\> perl -MDevel::Peek -e"Dump { }
SV = RV(0x183cfc8) at 0x226074
  REFCNT = 1
  FLAGS = (TEMP,ROK)
  RV = 0x225f84
  SV = PVHV(0x22b504) at 0x225f84
    REFCNT = 1
    FLAGS = (SHAREKEYS)
    IV = 0         <<<------------------------------------------
    NV = 0
    ARRAY = 0x0
    KEYS = 0       <<<------------------------------------------
    FILL = 0
    MAX = 7
    RITER = -1
    EITER = 0x0

C:\>perl -MDevel::Peek -e"Dump { 1..10 }
SV = RV(0x183cfc8) at 0x182f4f4
  REFCNT = 1
  FLAGS = (TEMP,ROK)
  RV = 0x225f94
  SV = PVHV(0x22b514) at 0x225f94
    REFCNT = 1
    FLAGS = (SHAREKEYS)
    IV = 5         <<<------------------------------------------
    NV = 0
    ARRAY = 0x1825554  (0:3, 1:5)
    hash quality = 150.0%
    KEYS = 5       <<<------------------------------------------
    FILL = 5
    MAX = 7
    RITER = -1
    EITER = 0x0
    Elt "1" HASH = 0x806b80c9
    SV = IV(0x1828ce0) at 0x226084
      REFCNT = 1
      FLAGS = (IOK,pIOK)
      IV = 2
    Elt "3" HASH = 0xa400c7f3
    SV = IV(0x1828d04) at 0x2260b4
      REFCNT = 1
      FLAGS = (IOK,pIOK)
      IV = 4
    Elt "7" HASH = 0xecc9d984
    SV = IV(0x1828d14) at 0x2260f0
      REFCNT = 1
      FLAGS = (IOK,pIOK)
      IV = 8

[ELISHEVA]

Thanks for the links to Perl source code and the dump.

Key counts being stored would be consistent with BrowserUk's observations that there seems to be little difference between scalar keys on an empty and full hash. But scalar(%h) is returning counts of used and allocated buckets, not key counts.

Given moritz's observations of a significant difference in empty and non-empty hashes for %h and the lack of an obvious dump field to store bucket counts in Devel::Peek output, I would think that %h is doing some sort of looping and is O(number of buckets).

Best, beth

[moritz]

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.

[ELISHEVA]

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

[Anonymous Monk]

hv.h

281 /* the number of keys (including any placeholers) */
282 #define XHvTOTALKEYS(xhv)       ((xhv)->xhv_keys)

289 #define HvKEYS(hv)              HvUSEDKEYS(hv)
290 #define HvUSEDKEYS(hv)          (HvTOTALKEYS(hv) - HvPLACEHOLDERS_
+get(hv))


293 #define HvPLACEHOLDERS_get(hv)  (SvMAGIC(hv) ? Perl_hv_placeholder
+s_get(aTHX_ (const HV *)hv) : 0)

hv.c

2536 I32
2537 Perl_hv_placeholders_get(pTHX_ const HV *hv)
2538 {
2539     dVAR;
2540     MAGIC * const mg = mg_find((const SV *)hv, PERL_MAGIC_rhash);
2541 
2542     PERL_ARGS_ASSERT_HV_PLACEHOLDERS_GET;
2543 
2544     return mg ? mg->mg_len : 0;
2545 }

mg.c

411 MAGIC*
412 Perl_mg_find(pTHX_ const SV *sv, int type)
413 {
414     PERL_UNUSED_CONTEXT;
415     if (sv) {
416         MAGIC *mg;
417         for (mg = SvMAGIC(sv); mg; mg = mg->mg_moremagic) {
418             if (mg->mg_type == type)
419                 return mg;
420         }
421     }
422     return NULL;
423 }