Understood. The reason for my reluctance to do things one at a time is because I saw the effects of doing a C to perl callback for the comparator. Just calling the comparator (without actually using it's return value) drops my topN() routine from first, to second last place in the benchmark.

[ 1:01:43.25] P:\test>427029 -MAX=100 -N=10

10 from 100 (1 seconds)
100|99|98|97|96|95|94|93|92|91
         Rate    Ari    Buk     LR  BukLR   perl      C
Ari     464/s     --   -74%   -83%   -93%   -98%   -99%
Buk    1768/s   281%     --   -35%   -74%   -93%   -97%
LR     2731/s   488%    54%     --   -60%   -89%   -95%
BukLR  6876/s  1381%   289%   152%     --   -72%   -88%
perl  24678/s  5217%  1296%   804%   259%     --   -57%
C     57443/s 12276%  3149%  2004%   735%   133%     --

[ 1:02:07.47] P:\test>427029 -MAX=100 -N=10

10 from 100 (1 seconds)
100|99|98|97|96|95|94|93|92|91
         Rate   Ari     C   Buk    LR BukLR  perl
Ari     477/s    --  -32%  -72%  -79%  -92%  -98%
C       703/s   47%    --  -59%  -69%  -88%  -97%
Buk    1729/s  262%  146%    --  -24%  -71%  -93%
LR     2266/s  375%  222%   31%    --  -61%  -91%
BukLR  5881/s 1132%  737%  240%  159%    --  -77%
perl  25039/s 5146% 3463% 1348% 1005%  326%    --
[download]

There may be some fat that could be trimmed as I put the callback code in a separate C function (per the examples) in order to isolate all the stack manipulations.

That could probably be inlined with care, but I also tried calling a dummy C-function and it is very clear that it is the callback to perl, not the call to the C function that is chewing all the time. Once you get into the C code, it's better to stay and do as much work as possible in one go.

That said, I guess you could alway do the batching within the wrapping code also, which would make sense.

Out of curiousity, was your comparator of the {$a <=> $b} type, or did you pass parameters to it? It seems as if we could tap into sort's efficient comparator speed if we could use $a and $b from C code. Generic comparisons might be easier that way.

Out of curiousity, was your comparator of the {$a <=> $b} type, or did you pass parameters to it?

I haven't worked out how to set $a and $b yet. This was the C wrapper function I used for calling the comparator.

int callComp( SV* cmp, int a, int b ) {
    int count, rv;
    dSP; ENTER; SAVETMPS; 
    PUSHMARK(SP);
    XPUSHs( sv_2mortal( newSViv( a ) ) );
    XPUSHs( sv_2mortal( newSViv( b ) ) );
    PUTBACK; 
    if( ( count = call_sv( cmp, G_SCALAR ) ) != 1 ) 
        croak( "Bad comparator" );
    SPAGAIN; 
    rv = POPi;
    FREETMPS; LEAVE;
}
[download]

That said, I am not sure how much difference it would make to the performance? You get the best performance from sort when you don't actually do anything in the comparator sub, which allows perl to completely skip the setting of parameters and the callback to perl.

But I think that the decision that allows perl to do that is embedded deep within the parser, a very specific special case, not something that could easily be transferred to extensions. I don't think it uses the hints mechanism?

That's what I suggested that when the programmer codes @s = sort{$a<=>$b} @u;, the interpreter effectively reads that as @s = sortNumericAscending @u; and sort{$bcmp$a} is effectively translated to 'sortAlphaDescending'.

Indeed, in the latest versions, @s = reverse sort @u; is also interpreted as 'sortAlphaDescending', but I don't think there is any easy way to apply that type of reinterpretation to extensions.

Actually, I think that 4 named variants would be cleaner both from the point of view of understandability: topN() or Ngreatest() doesn't make a great deal of sense in the case of wanting the N lowest values; and efficiency: avoiding the conditional code to decide which way we are ordering.

To fit in with the existing naming conventions of List::Util, they should probably be called: maxN(), minN(), maxNstr() & minNstr(). I don't really like the "defaulting" of min() and max() to numeric--which is the opposite to sort--or the "ommision" of 'num' from the names, but that's what now exists, and consistancy would be a good thing.

---

Examine what is said, not who speaks.

Silence betokens consent.

Love the truth but pardon error.