primitive-sort 0.1.2.1 → 0.1.2.2
raw patch · 5 files changed
+95/−76 lines, 5 filesdep −ghc-primdep ~basedep ~contiguous
Dependencies removed: ghc-prim
Dependency ranges changed: base, contiguous
Files
- CHANGELOG.md +5/−0
- bench/Main.hs +71/−53
- primitive-sort.cabal +18/−19
- src/Data/Primitive/Sort.hs +1/−3
- test/Main.hs +0/−1
CHANGELOG.md view
@@ -1,5 +1,10 @@ # Revision history for primitive-sort +## 0.1.2.2 -- 2024-02-02++* Replace imports of `GHC.Prim` with `GHC.Exts` so that the dependency+ on ghc-prim can be dropped.+ ## 0.1.2.1 -- 2024-02-01 * Updated package metadata.
bench/Main.hs view
@@ -1,48 +1,48 @@ {-# LANGUAGE BangPatterns #-} {-# LANGUAGE RankNTypes #-} {-# LANGUAGE ScopedTypeVariables #-}-{-# LANGUAGE MagicHash #-} {-# LANGUAGE TypeApplications #-} -import Gauge.Main -import Type.Reflection (typeRep,TypeRep)-import Data.Primitive (ByteArray(..),PrimArray(..),Prim)-import Control.Monad.ST (ST,runST)+import Control.Monad.ST (ST, runST) import Data.Int-import Data.Word-import System.Random (mkStdGen,randoms,Random)-import GHC.Prim (proxy#, Proxy#)-import qualified GHC.OldList as L+import Data.Primitive (ByteArray (..), Prim, PrimArray (..)) import qualified Data.Primitive as P import qualified Data.Primitive.Sort import qualified GHC.Exts as E+import qualified GHC.OldList as L+import Gauge.Main+import System.Random (Random, mkStdGen, randoms)+import Type.Reflection (TypeRep, typeRep) main :: IO ()-main = defaultMain- [ bgroup "contiguous"- [ benchType (typeRep :: TypeRep Int8) (primArrayToByteArray . sortInt8 . byteArrayToPrimArray)- , benchType (typeRep :: TypeRep Word) (primArrayToByteArray . sortWord . byteArrayToPrimArray)- ]- , bgroup "tagged-unique"- [ bench "mini" (whnf (\(k,v) -> evalPair (Data.Primitive.Sort.sortUniqueTagged k v)) (sizedInts Mini, sizedInts Mini))- , bench "tiny" (whnf (\(k,v) -> evalPair (Data.Primitive.Sort.sortUniqueTagged k v)) (sizedInts Tiny, sizedInts Tiny))- , bench "small" (whnf (\(k,v) -> evalPair (Data.Primitive.Sort.sortUniqueTagged k v)) (sizedInts Small, sizedInts Small))+main =+ defaultMain+ [ bgroup+ "contiguous"+ [ benchType (typeRep :: TypeRep Int8) (primArrayToByteArray . sortInt8 . byteArrayToPrimArray)+ , benchType (typeRep :: TypeRep Word) (primArrayToByteArray . sortWord . byteArrayToPrimArray)+ ]+ , bgroup+ "tagged-unique"+ [ bench "mini" (whnf (\(k, v) -> evalPair (Data.Primitive.Sort.sortUniqueTagged k v)) (sizedInts Mini, sizedInts Mini))+ , bench "tiny" (whnf (\(k, v) -> evalPair (Data.Primitive.Sort.sortUniqueTagged k v)) (sizedInts Tiny, sizedInts Tiny))+ , bench "small" (whnf (\(k, v) -> evalPair (Data.Primitive.Sort.sortUniqueTagged k v)) (sizedInts Small, sizedInts Small))+ ] ]- ] -- It is useful to have this here with inlining disabled because it -- makes it easy to inspect Core to see if GHC's specialization is -- working like we expect it to. sortInt8 :: PrimArray Int8 -> PrimArray Int8-{-# noinline sortInt8 #-}+{-# NOINLINE sortInt8 #-} sortInt8 !x = Data.Primitive.Sort.sort @Int8 x sortWord :: PrimArray Word -> PrimArray Word-{-# noinline sortWord #-}+{-# NOINLINE sortWord #-} sortWord !x = Data.Primitive.Sort.sort @Word x evalPair :: (PrimArray a, PrimArray b) -> ()-evalPair (!_,!_) = ()+evalPair (!_, !_) = () primArrayToByteArray :: PrimArray a -> ByteArray primArrayToByteArray (PrimArray x) = ByteArray x@@ -51,16 +51,16 @@ byteArrayToPrimArray (ByteArray x) = PrimArray x data Size = Mini | Tiny | Small | Medium | Large | Gigantic- deriving (Enum,Bounded)+ deriving (Enum, Bounded) data Arrangement = Unsorted | Presorted | Reversed- deriving (Enum,Bounded)+ deriving (Enum, Bounded) allSizes :: [Size]-allSizes = [minBound..maxBound]+allSizes = [minBound .. maxBound] allArrangements :: [Arrangement]-allArrangements = [minBound..maxBound]+allArrangements = [minBound .. maxBound] showSize :: Size -> String showSize x = case x of@@ -89,7 +89,7 @@ Large -> intsLarge Gigantic -> intsGigantic -intsMini,intsTiny,intsSmall,intsMedium,intsLarge,intsGigantic :: PrimArray Int+intsMini, intsTiny, intsSmall, intsMedium, intsLarge, intsGigantic :: PrimArray Int intsMini = E.fromList (L.take 10 (randoms (mkStdGen 23) :: [Int])) intsTiny = E.fromList (L.take 100 (randoms (mkStdGen 87) :: [Int])) intsSmall = E.fromList (L.take 1000 (randoms (mkStdGen 19) :: [Int]))@@ -103,49 +103,68 @@ Presorted -> "presorted" Reversed -> "reversed" -buildArrangement :: (Prim a, Num a, Random a, Enum a, Bounded a)- => Arrangement -> TypeRep a -> Int -> ByteArray+buildArrangement ::+ (Prim a, Num a, Random a, Enum a, Bounded a) =>+ Arrangement ->+ TypeRep a ->+ Int ->+ ByteArray buildArrangement x = case x of Unsorted -> unsorted Presorted -> presorted Reversed -> reversed -benchType :: (Prim a, Num a, Random a, Enum a, Bounded a)- => TypeRep a -> (ByteArray -> ByteArray) -> Benchmark-benchType rep sort = bgroup- (show rep)- (map (\arrange -> benchArrangement rep arrange sort) allArrangements)+benchType ::+ (Prim a, Num a, Random a, Enum a, Bounded a) =>+ TypeRep a ->+ (ByteArray -> ByteArray) ->+ Benchmark+benchType rep sort =+ bgroup+ (show rep)+ (map (\arrange -> benchArrangement rep arrange sort) allArrangements) -benchArrangement :: (Prim a, Num a, Random a, Enum a, Bounded a)- => TypeRep a -> Arrangement -> (ByteArray -> ByteArray) -> Benchmark-benchArrangement rep arrange sort = bgroup- (showArrangement arrange)- (map (\sz -> let arr = buildArrangement arrange rep (numSize sz) in benchSize arr sz sort) allSizes)+benchArrangement ::+ (Prim a, Num a, Random a, Enum a, Bounded a) =>+ TypeRep a ->+ Arrangement ->+ (ByteArray -> ByteArray) ->+ Benchmark+benchArrangement rep arrange sort =+ bgroup+ (showArrangement arrange)+ (map (\sz -> let arr = buildArrangement arrange rep (numSize sz) in benchSize arr sz sort) allSizes) benchSize :: ByteArray -> Size -> (ByteArray -> ByteArray) -> Benchmark benchSize arr sz sort = bench (showSize sz) (whnf sort arr) unsorted :: forall a. (Prim a, Random a) => TypeRep a -> Int -> ByteArray-unsorted typ n = byteArrayFromList- (L.take n (randoms (mkStdGen 42) :: [a]))+unsorted _typ n =+ byteArrayFromList+ (L.take n (randoms (mkStdGen 42) :: [a])) presorted :: forall a. (Prim a, Num a, Enum a, Bounded a) => TypeRep a -> Int -> ByteArray-presorted typ n = byteArrayFromList- (L.take n (iterate (+1) (minBound :: a)))--reversed :: forall a. (Prim a, Num a, Enum a, Bounded a)- => TypeRep a -> Int -> ByteArray-reversed typ n = byteArrayFromList- (L.take n (iterate (subtract 1) (maxBound :: a)))-+presorted _typ n =+ byteArrayFromList+ (L.take n (iterate (+ 1) (minBound :: a))) +reversed ::+ forall a.+ (Prim a, Num a, Enum a, Bounded a) =>+ TypeRep a ->+ Int ->+ ByteArray+reversed _typ n =+ byteArrayFromList+ (L.take n (iterate (subtract 1) (maxBound :: a))) -byteArrayFromList :: Prim a => [a] -> ByteArray+byteArrayFromList :: (Prim a) => [a] -> ByteArray byteArrayFromList xs = byteArrayFromListN (L.length xs) xs -byteArrayFromListN :: forall a. Prim a => Int -> [a] -> ByteArray-byteArrayFromListN len vs = runST run where+byteArrayFromListN :: forall a. (Prim a) => Int -> [a] -> ByteArray+byteArrayFromListN len vs = runST run+ where run :: forall s. ST s ByteArray run = do arr <- P.newByteArray (len * P.sizeOf (undefined :: a))@@ -157,4 +176,3 @@ go as (ix + 1) go vs 0 P.unsafeFreezeByteArray arr-
primitive-sort.cabal view
@@ -1,6 +1,6 @@ cabal-version: 2.2 name: primitive-sort-version: 0.1.2.1+version: 0.1.2.2 synopsis: Sort primitive arrays description: This library provides a stable sorting algorithm for primitive arrays.@@ -21,22 +21,24 @@ CHANGELOG.md README.md +common build-settings+ default-language: Haskell2010+ ghc-options: -O2 -Wall -Wunused-packages+ library- hs-source-dirs: src- exposed-modules: Data.Primitive.Sort+ import: build-settings+ hs-source-dirs: src+ exposed-modules: Data.Primitive.Sort build-depends: , base >=0.4.9 && <5 , contiguous >=0.6 && <0.7- , ghc-prim >=0.9.1 && <0.10 , primitive >=0.6.4 && <0.10 - ghc-options: -O2 -Wall- default-language: Haskell2010- test-suite test- type: exitcode-stdio-1.0- hs-source-dirs: test- main-is: Main.hs+ import: build-settings+ type: exitcode-stdio-1.0+ hs-source-dirs: test+ main-is: Main.hs build-depends: , base , containers@@ -50,24 +52,21 @@ , tasty-quickcheck , tasty-smallcheck - ghc-options: -threaded -rtsopts -O2 -with-rtsopts=-N1- default-language: Haskell2010+ ghc-options: -threaded -rtsopts -with-rtsopts=-N1 benchmark bench- type: exitcode-stdio-1.0+ import: build-settings+ type: exitcode-stdio-1.0 build-depends: , base- , contiguous , gauge >=0.2.5- , ghc-prim , primitive , primitive-sort , random - ghc-options: -threaded -rtsopts -O2 -with-rtsopts=-N1- default-language: Haskell2010- hs-source-dirs: bench- main-is: Main.hs+ ghc-options: -threaded -rtsopts -with-rtsopts=-N1+ hs-source-dirs: bench+ main-is: Main.hs source-repository head type: git
src/Data/Primitive/Sort.hs view
@@ -21,15 +21,13 @@ , sortUniqueTaggedMutable ) where -import Control.Applicative import Control.Monad.ST import Data.Int import Data.Primitive (MutablePrimArray, Prim, PrimArray) import Data.Primitive.Contiguous (Contiguous, ContiguousU, Element, Mutable) import qualified Data.Primitive.Contiguous as C import Data.Word-import GHC.Int (Int (..))-import GHC.Prim+import GHC.Exts -- | Sort an immutable array. Duplicate elements are preserved. sort ::
test/Main.hs view
@@ -15,7 +15,6 @@ import Test.Tasty.QuickCheck as QC import Test.Tasty.SmallCheck as SC -import Control.Applicative (liftA2) import Control.Exception (Exception, toException) import Control.Monad.ST (ST, runST) import Data.Int