Beefy Boxes and Bandwidth Generously Provided by pair Networks
We don't bite newbies here... much

precalculating hash keys in XS slower?

by patcat88 (Deacon)
on Mar 28, 2011 at 14:41 UTC ( #895931=perlquestion: print w/replies, xml ) Need Help??
patcat88 has asked for the wisdom of the Perl Monks concerning the following question:

I've been thinking of how to speed up XS code, and saw many hv functions take a "hash number". Its 99% of the time zero in every example I've seen. Your supposed to use the "PERL_HASH" macro to calculate the hash number. The only example I have found of PERL_HASH being used anywhere was here

I've been having problems figuring out if its faster or SLOWER to use precalculated hashes. I wrote a test library to time the difference. The Time::HiRes time() benchmarking says caching the key hashes is faster (get was 0.95s, getKC was 0.89s). My C profiler (DevPartner 8) says no key caching is faster (get=5.81us per run, getKC=5.89us per run). Nytprof says no key caching is faster (get is 516ms, getKC is 531ms).

I did my tests on Windows XP ActivePerl 5.10 build 1003 compiled with VS2003.

here is XHVKC.xs

#define PERL_NO_GET_CONTEXT #include "EXTERN.h" #include "perl.h" #include "XSUB.h" #include "ppport.h" typedef struct { const char * key; unsigned long hash; const signed long klen; } hvCacheKeyStruct; typedef struct { hvCacheKeyStruct jiugsdh1; hvCacheKeyStruct iusidfsd2; hvCacheKeyStruct ihfsdgsfg3; hvCacheKeyStruct sudfyf4; hvCacheKeyStruct sfyuihldfss5; hvCacheKeyStruct iuodafohsd6; hvCacheKeyStruct kjsdjdfsj7; hvCacheKeyStruct layer1; hvCacheKeyStruct layer2; hvCacheKeyStruct layer3; } hvCacheStruct; #define HVCKSINIT(keyname) {#keyname, 0, sizeof(#keyname)-1 } static hvCacheStruct hvCache = { HVCKSINIT(jiugsdh1), HVCKSINIT(iusidfsd2), HVCKSINIT(ihfsdgsfg3), HVCKSINIT(sudfyf4), HVCKSINIT(sfyuihldfss5), HVCKSINIT(iuodafohsd6), HVCKSINIT(kjsdjdfsj7), HVCKSINIT(layer1), HVCKSINIT(layer2), HVCKSINIT(layer3) }; #undef HVCKSINIT #define HVKC_KEY(x) (hvCache.x.key) #define HVKC_KLEN(x) (hvCache.x.klen) #define HVKC_HASH(x) (hvCache.x.hash) #define HVKC_ARR_KEY(x) ((((hvCacheKeyStruct*)&(hvCache))+(x))->key) #define HVKC_ARR_KLEN(x) ((((hvCacheKeyStruct*)&(hvCache))+(x))->klen) #define HVKC_ARR_HASH(x) ((((hvCacheKeyStruct*)&(hvCache))+(x))->hash) #define hvkc_hv_fetch(hv, key, klen, lval, hash) + \ ((SV**) hv_common_key_len((hv), (key), (klen), (lval) \ ? (HV_FETCH_JUST_SV | HV_FETCH_LVALUE) \ : HV_FETCH_JUST_SV, NULL, (hash))) #define hvkc_hv_fetch_kc(hv, key, lval) + \ ((SV**) hv_common_key_len((hv), (HVKC_KEY(key)), (HVKC_KLEN(key)), (lv +al) \ ? (HV_FETCH_JUST_SV | HV_FETCH_LVALUE) \ : HV_FETCH_JUST_SV, NULL, (HVKC_HASH(key)))) void initializeHVCache(pTHX) { unsigned long i; const unsigned long arraylength = sizeof(hvCacheStruct)/sizeof(hvC +acheKeyStruct); for(i=0; i<arraylength; i++){ printf("initializeHVCache b4 %s hash=%u klen=%u\n", (((hvCacheKeyStruct*)&(hvCache))+i)->key, (((hvCacheKeyStruct*)&(hvCache))+i)->hash, (((hvCacheKeyStruct*)&(hvCache))+i)->klen ); PERL_HASH( ((((hvCacheKeyStruct*)&(hvCache))+i)->hash), ((((hvCacheKeyStruct*)&(hvCache))+i)->key), ((((hvCacheKeyStruct*)&(hvCache))+i)->klen) ); printf("initializeHVCache after %s hash=%u klen=%u\n", (((hvCacheKeyStruct*)&(hvCache))+i)->key, (((hvCacheKeyStruct*)&(hvCache))+i)->hash, (((hvCacheKeyStruct*)&(hvCache))+i)->klen ); } } MODULE = XHVKC PACKAGE = XHVKC BOOT: initializeHVCache(aTHX); void get(self, num) SV * self unsigned long num PREINIT: void * voidPtr = 0; char * finalKeyName; unsigned long finalKeyNameLen; CODE: if (SvROK((HV*)self) && SvTYPE(SvRV((HV*)self))==SVt_PVHV) self = SvRV((HV*)self); else Perl_croak(aTHX_ "%s: %s is not a hash reference", "XHVKC::get", "self"); #define SWITCHMACRO(num,key) case (num): finalKeyName = #key; finalKey +NameLen = sizeof(#key)-1; break; switch(num){ SWITCHMACRO(1,jiugsdh1) SWITCHMACRO(2,iusidfsd2) SWITCHMACRO(3,ihfsdgsfg3) SWITCHMACRO(4,sudfyf4) SWITCHMACRO(5,sfyuihldfss5) SWITCHMACRO(6,iuodafohsd6) SWITCHMACRO(7,kjsdjdfsj7) #undef SWITCHMACRO default: printf("huh?"); exit(1); } (SV **)voidPtr = hvkc_hv_fetch((HV *)self, "layer1", sizeof("layer +1")-1, 0,0); if(voidPtr){ (SV *)voidPtr = *(SV **)voidPtr; if (SvROK((SV *)voidPtr)){ (SV *)voidPtr = SvRV((SV *)voidPtr); if (SvTYPE((SV *)voidPtr)==SVt_PVHV) { (SV **)voidPtr = hvkc_hv_fetch((HV *)voidPtr, "layer2" +, sizeof("layer2")-1,0,0); if(voidPtr) { (SV *)voidPtr = *(SV **)voidPtr; if (SvROK((SV *)voidPtr)){ (SV *)voidPtr = SvRV((SV *)voidPtr); if (SvTYPE((SV *)voidPtr)==SVt_PVHV) { (SV **)voidPtr = hvkc_hv_fetch((HV *)voidP +tr, "layer3", sizeof("layer3")-1,0,0); if(voidPtr) { (SV *)voidPtr = *(SV **)voidPtr; if (SvROK((SV *)voidPtr)){ (SV *)voidPtr = SvRV((SV *)voidPtr +); if (SvTYPE((SV *)voidPtr)==SVt_PVH +V) { (SV **)voidPtr = hvkc_hv_fetch +((HV *)voidPtr, finalKeyName, finalKeyNameLen,0,0); if(voidPtr) { voidPtr = (void *)SvIV(*(S +V **)voidPtr); } //else stays null } else {voidPtr = NULL;} } else {voidPtr = NULL;} } //else stays null } else {voidPtr = NULL;} } else {voidPtr = NULL;} } //else stays null } else {voidPtr = NULL;} } else {voidPtr = NULL;} } //else stays null if(voidPtr != (void *)999) { printf("wrong number at end of hash tree"); exit(1); } void getKC(self, num) SV * self unsigned long num PREINIT: void * voidPtr = 0; CODE: if (SvROK((HV*)self) && SvTYPE(SvRV((HV*)self))==SVt_PVHV) self = SvRV((HV*)self); else Perl_croak(aTHX_ "%s: %s is not a hash reference", "XHVKC::get", "self"); (SV **)voidPtr = hvkc_hv_fetch_kc((HV *)self, layer1,0); if(voidPtr){ (SV *)voidPtr = *(SV **)voidPtr; if (SvROK((SV *)voidPtr)){ (SV *)voidPtr = SvRV((SV *)voidPtr); if (SvTYPE((SV *)voidPtr)==SVt_PVHV) { (SV **)voidPtr = hvkc_hv_fetch_kc((HV *)voidPtr, layer +2,0); if(voidPtr) { (SV *)voidPtr = *(SV **)voidPtr; if (SvROK((SV *)voidPtr)){ (SV *)voidPtr = SvRV((SV *)voidPtr); if (SvTYPE((SV *)voidPtr)==SVt_PVHV) { (SV **)voidPtr = hvkc_hv_fetch_kc((HV *)vo +idPtr, layer3,0); if(voidPtr) { (SV *)voidPtr = *(SV **)voidPtr; if (SvROK((SV *)voidPtr)){ (SV *)voidPtr = SvRV((SV *)voidPtr +); if (SvTYPE((SV *)voidPtr)==SVt_PVH +V) { num -= 1; (SV **)voidPtr = hvkc_hv_fetch +((HV *)voidPtr, HVKC_ARR_KEY(num), HVKC_ARR_KLEN(num), 0, HVKC_ARR_HA +SH(num)); if(voidPtr) { voidPtr = (void *)SvIV(*(S +V **)voidPtr); } //else stays null } else {voidPtr = NULL;} } else {voidPtr = NULL;} } //else stays null } else {voidPtr = NULL;} } else {voidPtr = NULL;} } //else stays null } else {voidPtr = NULL;} } else {voidPtr = NULL;} } //else stays null if(voidPtr != (void *)999) { printf("wrong number at end of hash tree"); exit(1); }

here is

package XHVKC; use strict; use warnings; require Exporter; our @ISA = qw(Exporter); # Items to export into callers namespace by default. Note: do not expo +rt # names by default without a very good reason. Use EXPORT_OK instead. # Do not simply export all your public functions/methods/constants. # This allows declaration use XHVKC ':all'; # If you do not need this, moving things directly into @EXPORT or @EXP +ORT_OK # will save memory. our %EXPORT_TAGS = ( 'all' => [ qw( ) ] ); our @EXPORT_OK = ( @{ $EXPORT_TAGS{'all'} } ); our @EXPORT = qw( ); our $VERSION = '0.01'; require XSLoader; XSLoader::load('XHVKC', $VERSION); sub new { my $href = { 'layer1' => { 'layer2' => { 'layer3' => { 'jiugsdh1' => 999, 'iusidfsd2' => 999, 'ihfsdgsfg3' => 999, 'sudfyf4' => 999, 'sfyuihldfss5' => 999, 'iuodafohsd6' => 999, 'kjsdjdfsj7' => 999 } } } }; bless $href ; return $href ; } # Preloaded methods go here. 1; __END__

here is the, it may or may not apply to you, I've disabled a few compiler optimizations to enable step through debugging in VS

use 5.010000; use ExtUtils::MakeMaker; # See lib/ExtUtils/ for details of how to influence # the contents of the Makefile that is written. use Config qw(%Config); my $ccflags = $Config{'ccflags'}; warn $ccflags."\n"; $ccflags =~ s/O1/Od/; $ccflags =~ s/-DNDEBUG//; warn $ccflags."\n"; WriteMakefile( NAME => 'XHVKC', VERSION_FROM => 'lib/', # finds $VERSION PREREQ_PM => {}, # e.g., Module::Name => 1.1 ($] >= 5.005 ? ## Add these new keywords supported since 5.005 (ABSTRACT_FROM => 'lib/', # retrieve abstract from modu +le AUTHOR => 'A. U. Thor <a.u.thor@a.galaxy.far.far.away>' +) : ()), LIBS => [''], # e.g., '-lm' DEFINE => '', # e.g., '-DHAVE_SOMETHING' INC => '-I.', # e.g., '-I. -I/usr/include/other' CCFLAGS => $ccflags, OPTIMIZE => ' ', XSOPT => ' -nolinenumbers ' # Un-comment this if you add C files to link with later: # OBJECT => '$(O_FILES)', # link all the C files too );

the test script
#!/usr/bin/perl -w use XHVKC; use Time::HiRes qw( time ); $o = new XHVKC; $time = time; for(0..300000){ for (int(rand 6)+1) {$o->get($_);} } print "time was ".(time-$time)."\n"; $time = time; for(0..300000){ for (int(rand 6)+1) {$o->getKC($_);} } print "time was ".(time-$time)."\n";

Replies are listed 'Best First'.
Re: precalculating hash keys in XS slower?
by sundialsvc4 (Abbot) on Mar 28, 2011 at 16:22 UTC

    Pardon me that I do not have the time right now to study your code in detail.   (P.S. I would, however, “club ya,” as a former co-worker would put it, for using a variable name like voidPtr ...)

    In my experience, the speed with which a hash-key is calculated makes precious little difference at all.   What matters is the quality of the search attempt that results from using it, all things considered.   The number of hash-buckets, the distribution of key values within the table (in actual, observed practice), and the probability of a virtual memory page-fault, are all things that I would call “genuine” considerations.   The hash-algorithm is an important consideration in this overall picture, but it is only one of them, and a small one at that.   The number of nanoseconds required to compute it is, by and large, irrelevant (IMHO) given the larger context.   To the (very limited) extent that the actual hash-algorithm does influence anything, it is wiser to spend a little more time (if indeed you must...) producing a “better” result, than to spend less time producing an inferior one.

    JM2CW.   Nothing more or less.

Log In?

What's my password?
Create A New User
Node Status?
node history
Node Type: perlquestion [id://895931]
Approved by marto
[robby_dobby]: I attended a couple conferences (both in India). Left me with a renewed enthusiasm to do more, only to see it disappear in a few days!
[LanX]: Then come to YAPC EU in Amsterdam ...
[robby_dobby]: LanX: But that's in Africa! More like YAPC::Africa
choroba fears Amsterdam might fill him with enthusiasm to do nothing
[robby_dobby]: Uff, too expensive :-(
[LanX]: ... I found YAPC EU more entertaining (and international )than YAPC NA
[robby_dobby]: What's the site for YAPC::EU?
[LanX]: Robby Dobby no IIRC Sinai is already part of Asia
[robby_dobby]: page for yapceu is out of date by 2 years
[robby_dobby]: LanX: Sharm-el-Sheikh is in Egypt

How do I use this? | Other CB clients
Other Users?
Others lurking in the Monastery: (12)
As of 2017-04-24 15:57 GMT
Find Nodes?
    Voting Booth?
    I'm a fool:

    Results (442 votes). Check out past polls.