Re^9: Using $a and $b from XS

I still get a weird result when I reverse the $a and $b in the comparator. Now it's:

-1 0 0 0 7
[download]

Oh well, I think I'll keep the comparison caller in a separate subroutine for simplicity and maintainability anyway.

A similar mechanism should work for the heap sort version.

Actually, I don't need to do the same thing for the heap. All I need to do is call makeHeap on the first N items. That's O(N); building up the heap item-by-item is O(NlogN).

I'm thinking that this is good enough to go ahead with. If I implement the four simple cases (maxN, minN, maxNstr, minNstr) as you suggested, and also a user-supplied comparator, that will be fine.

We've been giving perl's sort an unfair advantage against our homemade comparator. I tried a benchmark against a call it didn't know how to optimize, { ($a < $b) ? -1 : (($a > $b) ? 1:0) }, and our partial sorts do better in many cases (5 in 1000, 5 in 10,000 etc.).

Comment on Re^9: Using $a and $b from XS Select or Download Code

Replies are listed 'Best First'.
Re^10: Using $a and $b from XS by BrowserUk (Patriarch) on Feb 08, 2005 at 04:16 UTC
I still get a weird result when I reverse the $a and $b in the comparator. Sorry, I'm lost as to which version of what you are referring to? My C; your C; my Perl? In the C code I posted back two levels, it only worked for {$b<=>$a} because that's all the algorithm in topNbs handled? If you are indicating something else, then I'll need a heavier cluebat :) Actually, I don't need to do the same thing for the heap. Then why havie I been faffing around fixing the topNbs() algorithm then? :) I've only been using the topNbs for testing, because the heap version never worked on my system. Your compiler apparently allows vaiable declarations at places other than the top of the block (ala C++), but my doesn't--or maybe could if I applied the appropriate switches. <pI was more interested in trying to make one algorithm work as best I could re: building the return list and calling the comparator and the topNbs algorithm is simpler to work with than the heap for testing. It also beats out the heap for all but the very largest of subsets--greater than 10,000 from memory. It would appear that the saving gained by the heap from moving less elements around is, considerably offset by the complexity of the algorithm. Inserts to the binary chop may move more elements, but they do so in a very tight, optimisable loop. You have to be moving a large number to outweight the cost of the heap algorithm. We've been giving perl's sort an unfair advantage against our homemade comparator. I tried a benchmark against a call it didn't know how to optimize, { ($a < $b) ? -1 : (($a > $b) ? 1:0) }, and our partial sorts do better in many cases (5 in 1000, 5 in 10,000 etc.). I would say that was artificially giving sort a disadvantage. It does know how to optimise the four basic cases, and in those cases it has the advantage once the subset gets to above ~ 10% of the set. It's only with very small subsets of large lists that we win--if we have to call the comparator and it doesn't. That said. I also tested a version of topNbs that didn't call the comparator at all. And again, probably due to my lack of proficiency in XS, in all but a few extreme cases, very small subsets from very large lists, sort n slice wins most times. sort has had a lot of clever people, over many years adding to it's optimisation, and I've been doing XS for 4 days! I'm currently attempting to work at from the other end, by starting with the code for reduce from List::Util.xs. I've succeeded in getting that to build and function correctly from within the Inline::C framework. I intend to first test to see if doing through Inline::C adds any noticable overhead to the performance by comparing my version directly with the XS built version. Assuming that any overhead is minimal, then I'll try and insert the topNbs code into that and see how is performs relative to the other two versions (separate callComp() and inlined-call_sv()). If it works better--and it probably will as I can already see several things it does in a simpler, more efficient way than I am doing. I'm still doing the aliasing to $a & $b all wrong. In fact, I'm not aliasing at all and I am stomping on any existing values $a and $b might have in the calling code--ie. Not doing the equivalent of `local $a, $b;`. There is a lot going on in reduce() that I do not understand, but maybe by the time I do, I'll be in a better position? Examine what is said, not who speaks. Silence betokens consent. Love the truth but pardon error.	[reply] [d/l]

Replies are listed 'Best First'.

Re^10: Using $a and $b from XS
by BrowserUk (Patriarch) on Feb 08, 2005 at 04:16 UTC

I still get a weird result when I reverse the $a and $b in the comparator.

Sorry, I'm lost as to which version of what you are referring to? My C; your C; my Perl?

In the C code I posted back two levels, it only worked for {$b<=>$a} because that's all the algorithm in topNbs handled? If you are indicating something else, then I'll need a heavier cluebat :)

Actually, I don't need to do the same thing for the heap.

Then why havie I been faffing around fixing the topNbs() algorithm then? :)

I've only been using the topNbs for testing, because the heap version never worked on my system. Your compiler apparently allows vaiable declarations at places other than the top of the block (ala C++), but my doesn't--or maybe could if I applied the appropriate switches. <pI was more interested in trying to make one algorithm work as best I could re: building the return list and calling the comparator and the topNbs algorithm is simpler to work with than the heap for testing.

It also beats out the heap for all but the very largest of subsets--greater than 10,000 from memory. It would appear that the saving gained by the heap from moving less elements around is, considerably offset by the complexity of the algorithm. Inserts to the binary chop may move more elements, but they do so in a very tight, optimisable loop. You have to be moving a large number to outweight the cost of the heap algorithm.

We've been giving perl's sort an unfair advantage against our homemade comparator. I tried a benchmark against a call it didn't know how to optimize, { ($a < $b) ? -1 : (($a > $b) ? 1:0) }, and our partial sorts do better in many cases (5 in 1000, 5 in 10,000 etc.).

I would say that was artificially giving sort a disadvantage. It does know how to optimise the four basic cases, and in those cases it has the advantage once the subset gets to above ~ 10% of the set. It's only with very small subsets of large lists that we win--if we have to call the comparator and it doesn't.

That said. I also tested a version of topNbs that didn't call the comparator at all. And again, probably due to my lack of proficiency in XS, in all but a few extreme cases, very small subsets from very large lists, sort n slice wins most times.

sort has had a lot of clever people, over many years adding to it's optimisation, and I've been doing XS for 4 days!

I'm currently attempting to work at from the other end, by starting with the code for reduce from List::Util.xs. I've succeeded in getting that to build and function correctly from within the Inline::C framework.

I intend to first test to see if doing through Inline::C adds any noticable overhead to the performance by comparing my version directly with the XS built version. Assuming that any overhead is minimal, then I'll try and insert the topNbs code into that and see how is performs relative to the other two versions (separate callComp() and inlined-call_sv()).

If it works better--and it probably will as I can already see several things it does in a simpler, more efficient way than I am doing. I'm still doing the aliasing to $a & $b all wrong. In fact, I'm not aliasing at all and I am stomping on any existing values $a and $b might have in the calling code--ie. Not doing the equivalent of local $a, $b;.

There is a lot going on in reduce() that I do not understand, but maybe by the time I do, I'll be in a better position?

Examine what is said, not who speaks.

Silence betokens consent.

Love the truth but pardon error.

[reply]
[d/l]