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: 

P:\test>topn -MAX=10000 -N=10
sort     :10000 9999 9998 9997 9996 9995 9994 9993 9992 9991
topN   @_:10000 9999 9998 9997 9996 9995 9994 9993 9992 9991
TopN   AB:10000 9999 9998 9997 9996 9995 9994 9993 9992 9991
topNbs AB:10000 9999 9998 9997 9996 9995 9994 9993 9992 9991
topNhp AB:9991 9992 9998 9994 9993 9999 10000 9995 9997 9996
  1 trial  of     sort [10 of 10000] ( 16.561ms total), 16.561/trial

  1 trial  of     topN [10 of 10000] (159.503ms total), 159.50/trial

  1 trial  of   topNAB [10 of 10000] (198.859ms total), 198.85/trial

  1 trial  of topNbsAB [10 of 10000] ( 20.988ms total), 20.988/trial

  1 trial  of topNhpAB [10 of 10000] ( 19.172ms total), 19.172/trial


P:\test>topn -MAX=100000 -N=10
sort     :100000 99999 99998 99997 99996 99995 99994 99993 99992 99991
topN   @_:100000 99999 99998 99997 99996 99995 99994 99993 99992 99991
TopN   AB:100000 99999 99998 99997 99996 99995 99994 99993 99992 99991
topNbs AB:100000 99999 99998 99997 99996 99995 99994 99993 99992 99991
topNhp AB:99991 99993 99992 99995 99994 99999 99998 99996 99997 100000
  1 trial  of     sort [10 of 100000] (228.633ms total), 228.63/trial

  1 trial  of     topN [10 of 100000] (   1.631s total), 1.631s/trial

  1 trial  of   topNAB [10 of 100000] (   1.859s total), 1.859s/trial

  1 trial  of topNbsAB [10 of 100000] (187.500ms total), 187.50/trial

  1 trial  of topNhpAB [10 of 100000] (203.125ms total), 203.12/trial

[download]

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: 

P:\test>topn -MAX=10000 -N=10
sort:10000 9999 9998 9997 9996 9995 9994 9993 9992 9991
topN@_:10000 9999 9998 9997 9996 9995 9994 9993 9992 9991
TopNAB:10000 9999 9998 9997 9996 9995 9994 9993 9992 9991
topNbs:10000 9999 9998 9997 9996 9995 9994 9993 9992 9991
topNhp:9991 9992 9994 9993 9995 9999 9996 10000 9998 9997
  1 trial  of     sort [10 of 10000] ( 15.625ms total), 15.625/trial

  1 trial  of     topN [10 of 10000] (156.250ms total), 156.25/trial

  1 trial  of   topNAB [10 of 10000] (203.125ms total), 203.12/trial

  1 trial  of   topNbs [10 of 10000] ( 15.625ms total), 15.625/trial

  1 trial  of topNheap [10 of 10000] ( 15.625ms total), 15.625/trial


P:\test>topn -MAX=100000 -N=10
sort:100000 99999 99998 99997 99996 99995 99994 99993 99992 99991
topN@_:100000 99999 99998 99997 99996 99995 99994 99993 99992 99991
TopNAB:100000 99999 99998 99997 99996 99995 99994 99993 99992 99991
topNbs:100000 99999 99998 99997 99996 99995 99994 99993 99992 99991
topNhp:99991 99992 99993 99994 99996 99997 100000 99995 99999 99998
  1 trial  of     sort [10 of 100000] (232.320ms total), 232.32/trial

  1 trial  of     topN [10 of 100000] (   1.638s total), 1.638s/trial

  1 trial  of   topNAB [10 of 100000] (   1.875s total), 1.875s/trial

  1 trial  of   topNbs [10 of 100000] (171.875ms total), 171.87/trial

  1 trial  of topNheap [10 of 100000] (171.875ms total), 171.87/trial


P:\test>topn -MAX=100000 -N=100
sort:100000 99999 99998 99997 99996 99995 99994 99993 99992 99991 9999
+0 99989 9
topN@_:100000 99999 99998 99997 99996 99995 99994 99993 99992 99991 99
+990 99989
TopNAB:100000 99999 99998 99997 99996 99995 99994 99993 99992 99991 99
+990 99989
topNbs:100000 99999 99998 99997 99996 99995 99994 99993 99992 99991 99
+990 99989
topNhp:99901 99902 99904 99905 99903 99908 99911 99909 99907 99912 999
+06 99910
  1 trial  of     sort [100 of 100000] (229.722ms total), 229.72/trial

  1 trial  of     topN [100 of 100000] (  16.505s total), 16.505/trial

  1 trial  of   topNAB [100 of 100000] (  18.922s total), 18.922/trial

  1 trial  of   topNbs [100 of 100000] (171.875ms total), 171.87/trial

  1 trial  of topNheap [100 of 100000] (187.500ms total), 187.50/trial

[download]

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.

In reply to Re^4: Using $a and $b from XS by BrowserUk
in thread Using $a and $b from XS by tall_man

Title:
Use:  <p> text here (a paragraph) </p>
and:  <code> code here </code>
to format your post, it's "PerlMonks-approved HTML":


  • Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!
  • Titles consisting of a single word are discouraged, and in most cases are disallowed outright.
  • Read Where should I post X? if you're not absolutely sure you're posting in the right place.
  • Please read these before you post! —
  • Posts may use any of the Perl Monks Approved HTML tags:
    a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr
  • You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)
            For:     Use:
    & &amp;
    < &lt;
    > &gt;
    [ &#91;
    ] &#93;
  • Link using PerlMonks shortcuts! What shortcuts can I use for linking?
  • See Writeup Formatting Tips and other pages linked from there for more info.