Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

Already on GitHub? Sign in to your account

[TODO] add method FixedStringArray.sort() #384

Open
fperrad opened this Issue Dec 4, 2009 · 4 comments

Comments

Projects
None yet
3 participants
Contributor

fperrad commented Dec 4, 2009

Add the method sort in the FixedStringArray PMC.

Currently, the method sort is only implemented in FixedPMCArray (and inherited by ResizablePMCArray).

This method uses the C function Parrot_quicksort (in src/utils.c) which handles only PMC and not STRING.

Originally http://trac.parrot.org/parrot/ticket/1356

Contributor

jkeenan commented Sep 18, 2010

Can anyone take this ticket on? Should we?

Contributor

jkeenan commented May 21, 2011

Replying to jkeenan:

Can anyone take this ticket on? Should we?

I repeat the question.

Contributor

Whiteknight commented May 22, 2011

I suspect that we would like this kind of functionality, if we can find a good way to inherit it between all our array types. Or, better yet, if we could find an intelligent and non-wasteful way to combine our array types, and implement a single sort routine. In any case, I feel like all our array types should either have built-in sort functionality or an easy way to access it.

On another side note, because the Parrot_quicksort routine calls nested runloops to call the comparison routines, there is a very real possibility that an implementation in PIR could be faster than the current implementation in C. I'll play with that as a possible alternative.

Contributor

Whiteknight commented May 27, 2011

I have a preliminary finding that is quite interesting. I implemented a Quicksort routine in winxed for sorting ResizablePMCArrays. My quicksort is about 20% faster than the built-in sort method when a custom comparison routine is used. When the built-in C-level comparisons are used, the current method is 80% faster than the winxed version. I suspect the difference here is that the current method has optimizations for NCI PMCs to invoke them without PCC. When a custom comparison sort is used, as I suspect it would be for most HLL applications, the current version is significantly slower than a version written in pure PIR.

My recommendation, and I am looking for feedback, is this: I would like to deprecate and remove the sort method from the various array types where it is present. In exchange, I would like to provide a pure-PIR version in the standard library. This sort library would not be a built-in method (although it could always be injected as such at runtime), but would be able to be used by all array and array-like types, including types which do not inherit from Parrot's current array types.

If this sounds like an attractive trade-off, I will get the process started. If not, we can search for alternatives.

@ghost ghost assigned Whiteknight May 9, 2012

@Whiteknight Whiteknight removed their assignment Mar 7, 2015

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment