Re^2: Bidirectional lookup algorithm? (poor XS solution)

That line below your signature is somewhat enigmatic:

The code present a class:BiMap, which supports the following methods: 7 ) { strncpy( (char*)( iHash script for RAD and testing), and a brief description. , CLEAN_AFTER_BUILD =used, newSize ); for( i = 0; i = pair; bm--1

I've tried setting up a bidirectional hash using XS code. It makes both key and values into keys and misuses the IV slot of SV of a hash entry to store the pointer to the crossover hash key.

However, the benchmarks are disappointing:

use blib;
use Hash::Bidirectional;
use Benchmark qw(cmpthese);
use Devel::Size qw(total_size);

use strict;
use warnings;

my $hn = {};
my $hb = bless {}, 'Hash::Bidirectional';

my $i = 0;
for ( 'aaaaz' .. 'zzzzz') {
    $i++;
    $hn->{$_} = $i;   # - normal hash
    $hn->{$i} = $_;   # /
    $hb->pair($_,$i); # - bidirectional hash
}
print "size normal hash: ", total_size($hn),"\n";
print "size bi_dir hash: ", total_size($hb),"\n";

cmpthese( 10000000, {
    normal => sub { $hn->{$hn->{shmem}} },
    bi_dir => sub { $hb->get($hb->get('shmem')) },
});
__END__
size normal hash: 3025679168
size bi_dir hash: 2360323536
            Rate bi_dir normal
bi_dir 2801120/s     --   -62%
normal 7407407/s   164%     --
[download]

Improvement of 22% in memory and more than double time for lookup? Why? Is it due to method call/XS overhead? XS code below.

#include "EXTERN.h"
#include "perl.h"
#include "XSUB.h"
#include "perlapi.h"
#include "ppport.h"

HE * get_entry(HE * he, U32 hash) {
    HE *entry = he;
    for(; entry; entry = HeNEXT(entry)) {
        if (HeHASH(entry) != hash){
            continue;
        }
    }
    if (!entry) entry = he;
    return entry;
}

MODULE = Hash::Bidirectional            PACKAGE = Hash::Bidirectional

char * pair(HV *hv, char *key, SV *value)
CODE:
    SV **key_ptr;
    SV **value_ptr;
    char *v = SvPVbyte_nolen(value);
    U32 hash = 0;
    HE *ventry;
    HE *kentry;
    SV *ksv;
    SV *vsv;
    
    /* store key as key */
    PERL_HASH(hash, key, strlen(key));
    ksv = newSViv((IV) &key);
    key_ptr = hv_store(hv, key, strlen(key), ksv, hash);
    kentry = get_entry((HvARRAY(hv))[hash & (I32) HvMAX(hv)],hash);

    /* store value as key */
    hash = 0;
    PERL_HASH(hash, v, strlen(v));
    vsv = newSViv((IV) &v);
    value_ptr = hv_store(hv, v, strlen(v), vsv, hash);
    ventry = get_entry((HvARRAY(hv))[hash & (I32) HvMAX(hv)],hash);

    /* set pointers of each */
    sv_setiv(ksv,(IV)HeKEY(ventry));
    sv_setiv(vsv,(IV)HeKEY(kentry));
    RETVAL = v;
OUTPUT:
    RETVAL

char * get(HV *hv, char *key)
CODE:
    HE *entry;
    U32 hash;

    PERL_HASH(hash, key, strlen(key));
    entry = get_entry((HvARRAY(hv))[hash & (I32) HvMAX(hv)],hash);
    RETVAL= (char*) SvIVX(HeVAL(entry));
OUTPUT:
    RETVAL
[download]

perl -le'print map{pack c,($-++?1:13)+ord}split//,ESEL'

Comment on Re^2: Bidirectional lookup algorithm? (poor XS solution) Select or Download Code

Replies are listed 'Best First'.
Re^3: Bidirectional lookup algorithm? (poor XS solution) by BrowserUk (Patriarch) on Jan 11, 2015 at 21:48 UTC
That line below your signature is somewhat enigmatic: It's an automatic appending of a collection of random snippets from the body of the post. It happens quite often when I post here. I try to remember to check for them and remove them; but sometimes I forget. I'm told (by the PMDevs) that it is due to the browser I use -- Opera -- but the fact that it never happens on any other site I use makes me think it is more to do with PM than Opera; but its always easier to blame someone else's tools than fix your own code. more than double time for lookup? Why? Is it due to method call/XS overhead? I would assume so. Any XS code is always going to be at a disadvantage compared to built-ins; that's inevitable. Which means you really have to parr everything down to even begin to compete. With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday' 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. Agile (and TDD) debunked	[reply]
Re^4: Bidirectional lookup algorithm? (poor XS solution) by Anonymous Monk on Jan 11, 2015 at 23:00 UTC
I'm told (by the PMDevs) that it is due to the browser I use -- Opera -- but the fact that it never happens on any other site I use makes me think it is more to do with PM than Opera; but its always easier to blame someone else's tools than fix your own code. :) do you got any js in your free nodelet? I've been using perlmonks since 2001 and this appending of random snippets hasn't happened to me, but then I don't use opera :/	[reply]
Re^5: Bidirectional lookup algorithm? (poor XS solution) by BrowserUk (Patriarch) on Jan 12, 2015 at 00:22 UTC
:) do you got any js in your free nodelet? What's a "free nodelet"? :) Seems I do have one, and there was some js there; though it only seemed to be loading some 3rd party js; not actually executing it. (Not sure how, why or when it got there.) But in any case, I don't have the free nodelet enable either on the frontpage or anywhere else, so it seems unlikely that is the cause. I have seen the effect -- random crap at the end of the post -- on 2 or 3 nodes by other people, but I don't remember who, or which nodes. But they might well have also been Opera users. It really is weird, in that it has persisted across several new versions of Opera -- which if it is an Opera bug, you'd think it would have been caught and dealt with by now -- and has never occurred anywhere else than this site. (Notice the bar 'li' after my sig. I didn't type it, it was there as soon as the "Comment on" TEXTAREA was displayed. And it isn't in my template. (Update: And now I've hit "Create" and "update" once, its been joined by the link test from my footer.) (Update again: And after hitting "update" to add the line above, its been joined by the text: 'free nodelet') With the rise and rise of 'Social' network sites: 'Computers are making people easier to use everyday' 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. Agile (and TDD) debunked	[reply]