primitive-sort: Sort primitive arrays

[ bsd3, library, software ] [ Propose Tags ] [ Report a vulnerability ]

This library provides a stable sorting algorithm for primitive arrays. The algorithm currently uses mergesort on large chunks and switches to insertion sort on small chunks. There are also novel improvements to increase the performance if the input array is already mostly sorted.

[Skip to Readme]

Modules

[Index] [Quick Jump]

Data
- Primitive
  - Data.Primitive.Sort

Downloads

primitive-sort-0.1.2.4.tar.gz [browse] (Cabal source package)
Package description (as included in the package)

Maintainer's Corner

Package maintainers

andrewthad, l3c_amartin

For package maintainers and hackage trustees

edit package information

Candidates

0.1.2.3

Versions [RSS]	0.1.0.0, 0.1.1.0, 0.1.2.0, 0.1.2.1, 0.1.2.2, 0.1.2.3, 0.1.2.4
Change log	CHANGELOG.md
Dependencies	base (>=0.4.16 && <5), contiguous (>=0.6 && <0.7), primitive (>=0.6.4 && <0.10) [details]
Tested with	ghc ==9.4.8 \|\| ==9.6.3 \|\| ==9.8.1
License	BSD-3-Clause
Copyright	2018 Andrew Martin
Author	Andrew Martin
Maintainer	amartin@layer3com.com
Category	software
Home page	https://github.com/byteverse/primitive-sort
Bug tracker	https://github.com/byteverse/primitive-sort/issues
Source repo	head: git clone git://github.com/byteverse/primitive-sort.git
Uploaded	by l3c_amartin at 2024-02-07T17:02:59Z
Distributions
Reverse Dependencies	1 direct, 3 indirect [details]
Downloads	1389 total (13 in the last 30 days)
Rating	(no votes yet) [estimated by Bayesian average]
Your Rating	λ λ λ
Status	Docs available [build log] Last success reported on 2024-02-07 [all 1 reports]

Readme for primitive-sort-0.1.2.4

[back to package description]

primitive-sort

Sorting of contiguous data structures. Implementation uses mergesort and switches to insertion sort once the arrays are small. Some of the benchmark results on a Intel Xeon CPU E3-1505M v5 2.80GHz (GHC 8.10.4):

contiguous/Int8/unsorted/mini      time  91.59 ns  
contiguous/Int8/unsorted/tiny      time  1.236 μs  
contiguous/Int8/unsorted/small     time  40.68 μs  
contiguous/Int8/unsorted/medium    time  614.1 μs  
contiguous/Int8/unsorted/large     time  6.580 ms  
contiguous/Int8/unsorted/gigantic  time  68.16 ms

Results may vary across processors, but you observe results that are 10x slower, it's probably an issue with the compiler, and please open an issue.

GHC Specialization Problems

Sadly, the most permissive signature for sort causes GHC's specialization to break. This permissive signature is:

sort :: (Contiguous arr, Element arr a, Ord a) => arr a -> arr a

And the less permissive variant used by this library is:

sort :: (Prim a, Ord a) => PrimArray a -> PrimArray a

The latter works nicely with SPECIALIZE and INLINEABLE, but the former does not work at all with these. The issue is believed to be related to the use of an associated constraint type Element, which introduced coercions that might confuse the specializer. However, this has not been confirmed.