On adapting discrimination to Rust

[tapeinosyne]

Having previously drafted a library for generic discrimination in Rust, I can probably offer some comments.

(I will edit this later. Meanwhile, you may want to skim my comment on r/rust – although it is not very detailed when it comes to actual implementation choices.

To begin with, a note: the performance of order discriminators is primarily determined by the speed of the sorting routine used for the base order (NatO in the paper), and by how much overhead you incur when applying that sorting routine with a given ordering relation; analogously, equivalence discriminators are more or less dependent on the data structure that backs the grouping operation.

In more concrete terms, the half-bucket, half-radix sorting routine presented in the paper works well for illustrative purposes, but I failed to achieve reasonable perfomance when sorting types with relatively complex ordering relations. I would recommend starting directly with a real radix sort on Natural, and defer sorting of all fixed-size types to it. With regard to overhead caused by orderings, my ideas are still fairly nebulous and remain unimplemented (as I planned to work on them during the upcoming holidays), so it is perhaps too early to offer sound advice.

[pthariensflame]

Thanks for the interesting words! I’m definitely planning on making the underlying implementation of Natural “swappable,” so that different basic sorts can be applied to different use cases.

I have hopes that by piggy-backing on DoubleEndedIterator I‘ll get some flattening-based performance gains, but that awaits benchmarking, which in turn awaits this library being in a more complete state.

Is your attempt anywhere online? If so, I could try to merge ideas in from it.