in reply to Using $a and $b from XS

The next trick is to get it to work with $a and $b. The following seems to work, but I'm not sure it isn't corrupting the stack. Any improvements? 
#! perl -slw
use strict;
use List::Util qw[ shuffle ];

use Inline C => 'DATA';

$^W = 0;

my $max = 120;
my @values = 1 .. $max;
my @values_mixed = shuffle( @values );
my @top = topN( 10, sub { $a <=> $b; }, \@values_mixed );
print "@top";

__END__
__C__

int callComp( SV* cmp, SV* a, SV* b ) {
    dSP;
    int rv;
    ENTER; 
    SAVETMPS; 

    GvSV(gv_fetchpv("main::a", TRUE, SVt_PV)) = a;
    GvSV(gv_fetchpv("main::b", TRUE, SVt_PV)) = b;
    
    PUSHMARK(SP);
    PUTBACK;

    if( call_sv( cmp, G_SCALAR|G_NOARGS ) != 1 )
        croak( "Bad comparator" );
    SPAGAIN;

    rv = POPi;

    PUTBACK; // << Was missing and is required!
    FREETMPS;LEAVE;
    return rv;
}

void topN( int n, SV* comp, AV*data ) {
    int *topN;
    int len = av_len( data );
    int i, j, k;

    Inline_Stack_Vars;
    Newz( 1, topN, n + 1, SV* );
    for( i = 0; i < n+1; i++ ) topN[ i ] = newSViv( 0 );
    
    for( i = 0; i <= len; i++ )    {
        SV* val = *av_fetch( data, i, 0 );
        for( j = 0; j < n; j++ ) {
            int cmp = callComp( comp, topN[ j ], val );
            if( cmp >= 0 ) continue;
            if( cmp < 0 ) {
                for( k = n; k > j; k-- ) topN[ k ] = topN[ k-1 ];
                topN[ j ] = val;
                break;
            }
        }
    }
    
    Inline_Stack_Reset;
    for( i = 0; i < n; i++ )
        Inline_Stack_Push( sv_2mortal( newSVsv( topN[ i ] ) ) );
    
    Safefree( topN );
    Inline_Stack_Done;
}

[download]

Replies are listed 'Best First'.
Re^2: Using $a and $b from XS
by BrowserUk (Patriarch) on Feb 06, 2005 at 05:01 UTC
    Any improvements?

    Only one. You can drop the first PUTBACK; as you aren't stacking any parameters. And it is quicker than passing via the stack. That is very noticable when using my linear search and shift. Will be less evident once your binary search works (it may be I broke that?).

    I'm thinking of trying to do the heap version also.

    I had hoped that we could drop the ENTER;SAVETMPS; and FREETMPS; LEAVE;, which I found I could do (ref:perlguts) with the working version of callComp(), when I was using smallish sets, but it breaks both (through memory leaks) with larger sets.

    I also tried to in-line the code from callComp() into the main routine--but the Inline_Stack_* macros and XS ones seem to make that impossible without moving over to using teh XS macros throughout. Which is probably what I will try next.

    What a way to program!:) Get something to work, and then move things around or comment them out and try it to see if it's required/in the right place or not.

    What with that; error messages that don't relate to the source;intermediate files that the error messages do relate to that change both their names and their directory names every time you changethe program; and the incompatibilty between the Inline_Stack_* macros and the XS macros that are required to write a callback that returns something.

    Shame really. If the Inline_Stack macros were a little more complete or compatible, the abilty to avoid perlguts/perlcall would be invaluable, but a denison of the Inline list reckons that things are unlikely to change anytime soon. For a hap'th of tar. :(

    Examine what is said, not who speaks.
    Silence betokens consent.
    Love the truth but pardon error.
[reply]
[d/l]
[select]
      I have adapted the solution for the binary search sort, and I also have one for a heap. Here are the two examples:

      The binary search case:

      Read more... (2 kB)

      The heap case:

      Read more... (3 kB)
[reply]
[d/l]
[select]

        On some quick, provisional testing, sort's avoidance of a callback for the 4 standard comparator variations means it still beats all our variants even when selecting a very small number from a large set, like 10 from 10,000. You have to move to something like 10 from 100,000 before the binary and heap versions start to look good:

        Read more... (2 kB)

        The other interesting thing from these results is that topN() which passes the comparator parameters via the stack runs quicker than the topNAB which does it via the globals!

        Switching topNbs() and topNheap() to using the stack gives these results:

        Read more... (3 kB)

        Which shows them faring much better by comparison with sort, but you still need to be forcing sort to sort a large number of values to see it.

        I think that four hardcoded comparator versions + a fifth with a callback would really make them shine--but that's for another day when I've slept.

        I guess what this proves is that you don't surpass many years of optimisations without effort :)

        Examine what is said, not who speaks.
        Silence betokens consent.
        Love the truth but pardon error.
[reply]
[d/l]
[select]

        Having got this to work reliably, it seems obvious that whilst Inline::C is convenient relative to XS, it has limitations and imposes overheads that make it less than ideal for the writing of this type of extension.

        Looking closely at the code for the callComp() function, whilst moving the callback into a separate sub allowed me to get something to work, the overhead it adds is skewing the results. This is especially true of the current implementation of the AB version which is fetching the globals $a and $b for every invocation. That could be fixed, but all my attempts to inline the callback code go nowhere.

        There is also a saving to be made by not creating a separate array of SV*s to hold the topNs and then later copying them to the stack. They could be written to and manipulated directly on the stack using EXTEND(SP,n) and ST(n). Or maybe using TARGS? but XS uses dSP; Inline C uses dXARGS; and TARGS requires dTARGS; all of which seem to conflict with one another.

        Maybe what is really needed is an Inline XS? The convenience of "Run, tweak. Run, tweak." with the "project management" taken care of, but without the mismatch between the C being converted XS being converted to C and their disparate environmental setups.

        I tried lifting the code for reduce() from List::Util as a model of XS done well and trying pursuade Inline C to manage it for me, but again, the environment that Inline C gives you does not work with the XS macros it uses.

        I said somwehere else, I feel a little like Pandora. I've resisted getting into XS till now, and I'm beginning to wish I had kept up that resistance. Inline C is seductive in it's simplicity of converting opcode intensive Perl code into fast running C, but it's limitations push you towards XS if you try to do something more than manipulated a few numbers or strings and the return a result. The need to call back to Perl, and Inline Cs apparent limitations in that area push you into another ballpark--and as I said in the other thread--it's a ballgame that I am not sure that I wish to be playing. It has complicated rules, a very sparse playbook and not much by way of a "noobie school"!

        Examine what is said, not who speaks.
        Silence betokens consent.
        Love the truth but pardon error.
[reply]
Re^2: Using $a and $b from XS
by dakkar (Hermit) on Feb 07, 2005 at 20:50 UTC
[reply]

      Any pointers as to how to discover the caller's package from XS/Inline::C?

      Update: Never mind. Just dropping the 'main::' part seems to work fine--so long as they don't embed a package statement into the comparator sub.

      Examine what is said, not who speaks.
      Silence betokens consent.
      Love the truth but pardon error.
[reply]

In Section Seekers of Perl Wisdom