In perl.git, the branch blead has been updated <http://perl5.git.perl.org/perl.git/commitdiff/32dfa2a7022d23efefa78556ec78725b0d2d4373?hp=12733a0391a05c17c34b642aa1694e0d482f3df6>
- Log ----------------------------------------------------------------- commit 32dfa2a7022d23efefa78556ec78725b0d2d4373 Author: Yves Orton <[email protected]> Date: Sat Mar 1 17:31:53 2014 +0100 Preallocate HvAUX() structures for large bucket arrays The assumption is that the time/space tradeoff of not allocating the HvAUX() structure goes away for a large bucket array where the size of the allocated buffer is much larger than the nonallocated HvAUX() "extension". This should make keys() and each() on larger hashes faster, but still preserve the essence of the original space conservation, where the assumption is a lot of small hash based objects which will never be traversed. M hv.c M hv.h commit bea177f3c4412e3250a860c64abed7595ae6373a Author: Yves Orton <[email protected]> Date: Sat Mar 1 15:49:28 2014 +0100 Split out part of hv_auxinit() so it can be reused Changes nothing except that it introduces hv_auxinit_interal() which does part of the job of hv_auxinit(), so that we can call it from somewhere else in the next commit. M embed.fnc M embed.h M hv.c M proto.h ----------------------------------------------------------------------- Summary of changes: embed.fnc | 1 + embed.h | 1 + hv.c | 91 ++++++++++++++++++++++++++++++++++++++++++--------------------- hv.h | 10 +++++++ proto.h | 5 ++++ 5 files changed, 78 insertions(+), 30 deletions(-) diff --git a/embed.fnc b/embed.fnc index 1e96cbc..c85d219 100644 --- a/embed.fnc +++ b/embed.fnc @@ -1840,6 +1840,7 @@ sR |HEK* |share_hek_flags|NN const char *str|I32 len|U32 hash|int flags rs |void |hv_notallowed |int flags|NN const char *key|I32 klen|NN const char *msg in |U32|ptr_hash|PTRV u s |struct xpvhv_aux*|hv_auxinit|NN HV *hv +sn |struct xpvhv_aux*|hv_auxinit_internal|NN struct xpvhv_aux *iter sM |SV* |hv_delete_common|NULLOK HV *hv|NULLOK SV *keysv \ |NULLOK const char *key|STRLEN klen|int k_flags|I32 d_flags \ |U32 hash diff --git a/embed.h b/embed.h index facb415..824d294 100644 --- a/embed.h +++ b/embed.h @@ -1413,6 +1413,7 @@ #define hfreeentries(a) S_hfreeentries(aTHX_ a) #define hsplit(a,b,c) S_hsplit(aTHX_ a,b,c) #define hv_auxinit(a) S_hv_auxinit(aTHX_ a) +#define hv_auxinit_internal S_hv_auxinit_internal #define hv_delete_common(a,b,c,d,e,f,g) S_hv_delete_common(aTHX_ a,b,c,d,e,f,g) #define hv_free_ent_ret(a,b) S_hv_free_ent_ret(aTHX_ a,b) #define hv_magic_check S_hv_magic_check diff --git a/hv.c b/hv.c index 9d80659..ef686ab 100644 --- a/hv.c +++ b/hv.c @@ -1162,6 +1162,7 @@ S_hv_delete_common(pTHX_ HV *hv, SV *keysv, const char *key, STRLEN klen, return NULL; } + STATIC void S_hsplit(pTHX_ HV *hv, STRLEN const oldsize, STRLEN newsize) { @@ -1170,18 +1171,25 @@ S_hsplit(pTHX_ HV *hv, STRLEN const oldsize, STRLEN newsize) char *a = (char*) HvARRAY(hv); HE **aep; - PERL_ARGS_ASSERT_HSPLIT; + bool do_aux= ( + /* already have an HvAUX(hv) so we have to move it */ + SvOOK(hv) || + /* no HvAUX() but array we are going to allocate is large enough + * there is no point in saving the space for the iterator, and + * speeds up later traversals. */ + ( ( hv != PL_strtab ) && ( newsize >= PERL_HV_ALLOC_AUX_SIZE ) ) + ); - /*PerlIO_printf(PerlIO_stderr(), "hsplit called for %p which had %d\n", - (void*)hv, (int) oldsize);*/ + PERL_ARGS_ASSERT_HSPLIT; PL_nomemok = TRUE; Renew(a, PERL_HV_ARRAY_ALLOC_BYTES(newsize) - + (SvOOK(hv) ? sizeof(struct xpvhv_aux) : 0), char); + + (do_aux ? sizeof(struct xpvhv_aux) : 0), char); + PL_nomemok = FALSE; if (!a) { - PL_nomemok = FALSE; return; } + #ifdef PERL_HASH_RANDOMIZE_KEYS /* the idea of this is that we create a "random" value by hashing the address of * the array, we then use the low bit to decide if we insert at the top, or insert @@ -1194,29 +1202,46 @@ S_hsplit(pTHX_ HV *hv, STRLEN const oldsize, STRLEN newsize) PL_hash_rand_bits = ROTL_UV(PL_hash_rand_bits,1); } #endif - - if (SvOOK(hv)) { + HvARRAY(hv) = (HE**) a; + HvMAX(hv) = newsize - 1; + /* before we zero the newly added memory, we + * need to deal with the aux struct that may be there + * or have been allocated by us*/ + if (do_aux) { struct xpvhv_aux *const dest = (struct xpvhv_aux*) &a[newsize * sizeof(HE*)]; - Move(&a[oldsize * sizeof(HE*)], dest, 1, struct xpvhv_aux); - /* we reset the iterator's xhv_rand as well, so they get a totally new ordering */ + if (SvOOK(hv)) { + /* alread have an aux, copy the old one in place. */ + Move(&a[oldsize * sizeof(HE*)], dest, 1, struct xpvhv_aux); + /* we reset the iterator's xhv_rand as well, so they get a totally new ordering */ +#ifdef PERL_HASH_RANDOMIZE_KEYS + dest->xhv_rand = (U32)PL_hash_rand_bits; +#endif + /* For now, just reset the lazy fill counter. + It would be possible to update the counter in the code below + instead. */ + dest->xhv_fill_lazy = 0; + } else { + /* no existing aux structure, but we allocated space for one + * so intialize it properly. This unrolls hv_auxinit() a bit, + * since we have to do the realloc anyway. */ + /* first we set the iterator's xhv_rand so it can be copied into lastrand below */ #ifdef PERL_HASH_RANDOMIZE_KEYS - dest->xhv_rand = (U32)PL_hash_rand_bits; + dest->xhv_rand = (U32)PL_hash_rand_bits; #endif - /* For now, just reset the lazy fill counter. - It would be possible to update the counter in the code below - instead. */ - dest->xhv_fill_lazy = 0; + /* this is the "non realloc" part of the hv_auxinit() */ + (void)hv_auxinit_internal(dest); + /* Turn on the OOK flag */ + SvOOK_on(hv); + } } - - PL_nomemok = FALSE; + /* now we can safely clear the second half */ Zero(&a[oldsize * sizeof(HE*)], (newsize-oldsize) * sizeof(HE*), char); /* zero 2nd half*/ - HvMAX(hv) = --newsize; - HvARRAY(hv) = (HE**) a; if (!HvTOTALKEYS(hv)) /* skip rest if no entries */ return; + newsize--; aep = (HE**)a; do { HE **oentry = aep + i; @@ -1938,6 +1963,23 @@ PERL_STATIC_INLINE U32 S_ptr_hash(PTRV u) { return (U32)u; } +static struct xpvhv_aux* +S_hv_auxinit_internal(struct xpvhv_aux *iter) { + PERL_ARGS_ASSERT_HV_AUXINIT_INTERNAL; + iter->xhv_riter = -1; /* HvRITER(hv) = -1 */ + iter->xhv_eiter = NULL; /* HvEITER(hv) = NULL */ +#ifdef PERL_HASH_RANDOMIZE_KEYS + iter->xhv_last_rand = iter->xhv_rand; +#endif + iter->xhv_fill_lazy = 0; + iter->xhv_name_u.xhvnameu_name = 0; + iter->xhv_name_count = 0; + iter->xhv_backreferences = 0; + iter->xhv_mro_meta = NULL; + iter->xhv_aux_flags = 0; + return iter; +} + static struct xpvhv_aux* S_hv_auxinit(pTHX_ HV *hv) { @@ -1971,18 +2013,7 @@ S_hv_auxinit(pTHX_ HV *hv) { iter = HvAUX(hv); } - iter->xhv_riter = -1; /* HvRITER(hv) = -1 */ - iter->xhv_eiter = NULL; /* HvEITER(hv) = NULL */ -#ifdef PERL_HASH_RANDOMIZE_KEYS - iter->xhv_last_rand = iter->xhv_rand; -#endif - iter->xhv_fill_lazy = 0; - iter->xhv_name_u.xhvnameu_name = 0; - iter->xhv_name_count = 0; - iter->xhv_backreferences = 0; - iter->xhv_mro_meta = NULL; - iter->xhv_aux_flags = 0; - return iter; + return hv_auxinit_internal(iter); } /* diff --git a/hv.h b/hv.h index 5b52f98..8ff1d14 100644 --- a/hv.h +++ b/hv.h @@ -238,6 +238,16 @@ C<SV*>. */ #define PERL_HASH_DEFAULT_HvMAX 7 +/* HvMAX(hv)+1 is >= to this we preallocate the HvAUX() struct during hsplit() + * The assumption being that we are using so much space anyway we might + * as well allocate the extra bytes and speed up later keys() + * or each() operations. We don't do this to small hashes as we assume + * that a) it will be easy/fast to resize them to add the iterator, and b) that + * many of them will be objects which won't be traversed. Larger hashes however + * will take longer to extend, and the size of the aux struct is swamped by the + * overall length of the bucket array. + * */ +#define PERL_HV_ALLOC_AUX_SIZE (1 << 9) /* these hash entry flags ride on hent_klen (for use only in magic/tied HVs) */ #define HEf_SVKEY -2 /* hent_key is an SV* */ diff --git a/proto.h b/proto.h index 9b33013..b4f22dd 100644 --- a/proto.h +++ b/proto.h @@ -5863,6 +5863,11 @@ STATIC struct xpvhv_aux* S_hv_auxinit(pTHX_ HV *hv) #define PERL_ARGS_ASSERT_HV_AUXINIT \ assert(hv) +STATIC struct xpvhv_aux* S_hv_auxinit_internal(struct xpvhv_aux *iter) + __attribute__nonnull__(1); +#define PERL_ARGS_ASSERT_HV_AUXINIT_INTERNAL \ + assert(iter) + STATIC SV* S_hv_delete_common(pTHX_ HV *hv, SV *keysv, const char *key, STRLEN klen, int k_flags, I32 d_flags, U32 hash); STATIC SV* S_hv_free_ent_ret(pTHX_ HV *hv, HE *entry) __attribute__nonnull__(pTHX_1) -- Perl5 Master Repository
