[TODO] add method FixedStringArray.sort()

[fperrad]

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.

[jkeenan]

Can anyone take this ticket on? Should we?

[jkeenan]

Replying to jkeenan:

Can anyone take this ticket on? Should we?

I repeat the question.

[whiteknight]

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.

[whiteknight]

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.