Here is my final incarnation of the comparator caller "function" plus a version of topNbs() that uses it.

By re-writing the PUSHMARK() macro, I managed to squeeze the calling of the via-$A$B comparator into another macro and avoid (the little) overhead that imposed.

I've also done away with the separate SV** topN; and associated memory allocation and freeing by building the return list directly on the stack.

If your going to adapt your topNheap(), note the order and positioning of the large group of XS macros--they are critical.

#define MYPUSHMARK(p) \
    ( *PL_markstack_ptr = ( ++PL_markstack_ptr == PL_markstack_max ) \
    ? ( markstack_grow(), (p) - PL_stack_base ) \
    : ( (p) - PL_stack_base ) )

#define CMP( callback, aa, bb )  ( \
    ( GvSV( a ) = ( aa ) ), \
    ( GvSV( b ) = ( bb ) ), \
    ( MYPUSHMARK(SP) ), \
    ( call_sv( callback, G_SCALAR|G_NOARGS ) ), \
    ( SPAGAIN ), \
    ( POPi ) \
)

void topNbsAB( int n, SV *cmp, AV*data ) {                           
    int i, k;                                                    
    int left, right;                                                 
    int len = av_len( data );                                        
                                                                     
    GV* a = gv_fetchpv( "main::a", TRUE, SVt_PV );
    GV* b = gv_fetchpv( "main::b", TRUE, SVt_PV );                   
                                                                     
    dSP; dMARK; dAX;
    POPMARK;
    POPs; POPs; POPs;
    EXTEND( SP, n );
    PUSHMARK( SP );
        
    for( i = 0; i < n; i++ ) {
       PUSHs( newSViv( 0 ) );                                        
    }                                                                
    PUTBACK;
    
    for( i = 0; i <= len; i++ ) {                                    
        SV *val = *av_fetch( data, i, 0 );                           
        if( CMP( cmp, val, ST( n-1 ) ) < 0 ) continue;      
                                                                     
        left = 0;                                                    
        right = n;                                              
        while (left < right) {                                       
           int middle = ( left + right ) >> 1;                       
           if( CMP( cmp, val, ST( middle ) ) <= 0 ) {       
              left = middle + 1;                                     
           } else {                                                  
              right = middle;                                        
           }                                                         
        }                                                            
        for( k = n; k >= left; k-- ) ST( k ) = ST( k - 1 );      
        ST( left ) = val;                                            
    }
    XSRETURN( n );                                                   
}
[download]

The upshot in my tests is that whilst using $a and $b is quicker than passing via the stack for small numbers of callbacks, as that number grows, the extra cost of lookup of globals (in the comparator sub itself) overtakes the saving of stacking the parameters in the C code.

Once again, when you move above about 1% N of T, sort starts to win by not having to call the comparator at all.

I'd be really interested to see what a real XS programmer would make of the above?