Ticket #1356 (assigned RFC)

Opened 5 years ago

Last modified 4 years ago

[TODO] add method FixedStringArray.sort()

Reported by: fperrad Owned by: whiteknight
Priority: normal Milestone:
Component: core Version: master
Severity: medium Keywords:
Cc: Language:
Patch status: Platform: all

Description

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.

Change History

follow-up: ↓ 2   Changed 4 years ago by jkeenan

Can anyone take this ticket on? Should we?

in reply to: ↑ 1   Changed 4 years ago by jkeenan

Replying to jkeenan:

Can anyone take this ticket on? Should we?

I repeat the question.

  Changed 4 years ago by whiteknight

  • status changed from new to assigned
  • owner set to 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.

  Changed 4 years ago by whiteknight

  • version changed from 1.8.0 to master
  • type changed from todo to RFC

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.

Note: See TracTickets for help on using tickets.