Beefy Boxes and Bandwidth Generously Provided by pair Networks
"be consistent"
 
PerlMonks  

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 http://cpansearch.perl.org/src/DOY/Moose-1.9902-TRIAL/mop.c

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 XHVKC.pm

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 makefile.pl, 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/MakeMaker.pm 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/XHVKC.pm', # finds $VERSION PREREQ_PM => {}, # e.g., Module::Name => 1.1 ($] >= 5.005 ? ## Add these new keywords supported since 5.005 (ABSTRACT_FROM => 'lib/XHVKC.pm', # 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";

Comment on precalculating hash keys in XS slower?
Select or Download Code
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?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: perlquestion [id://895931]
Approved by marto
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others having an uproarious good time at the Monastery: (12)
As of 2014-10-21 13:40 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    For retirement, I am banking on:










    Results (103 votes), past polls