fast-digits 0.2.1.0 → 0.3.0.0
raw patch · 7 files changed
+202/−105 lines, 7 filesdep +gaugedep −criterionPVP ok
version bump matches the API change (PVP)
Dependencies added: gauge
Dependencies removed: criterion
API changes (from Hackage documentation)
- Data.FastDigits.Internal: selectPower :: Word# -> (# Word#, Word# #)
- Data.FastDigits.Internal: selectPower' :: Word -> (Word, Word)
Files
- README.md +47/−0
- bench/Bench.hs +1/−1
- changelog.md +15/−0
- fast-digits.cabal +66/−44
- src-internal/Data/FastDigits/Internal.hs +53/−0
- src/Data/FastDigits.hs +20/−7
- src/Data/FastDigits/Internal.hs +0/−53
+ README.md view
@@ -0,0 +1,47 @@+# fast-digits [](https://travis-ci.org/Bodigrim/fast-digits) [](https://hackage.haskell.org/package/fast-digits) [](https://matrix.hackage.haskell.org/package/fast-digits) [](http://stackage.org/lts/package/fast-digits) [](http://stackage.org/nightly/package/fast-digits)++The fastest Haskell library to split integers into digits.+It is both asymptotically (O(n<sup>1.4</sup>) vs. O(n<sup>2</sup>))+and practically (2x-40x for typical inputs)+faster than [Data.Digits](https://hackage.haskell.org/package/digits).++Here are some benchmarks:++```+> cabal bench+shortInt/FastDigits base 2 mean 6.429 ms ( +- 465.7 μs )+shortInt/Data.Digits base 2 mean 50.08 ms ( +- 1.848 ms )++shortInt/FastDigits base 10 mean 4.288 ms ( +- 217.1 μs )+shortInt/Data.Digits base 10 mean 15.62 ms ( +- 540.1 μs )++shortInt/FastDigits base 10^5 mean 1.142 ms ( +- 50.09 μs )+shortInt/Data.Digits base 10^5 mean 3.962 ms ( +- 269.1 μs )++shortInt/FastDigits base 10^9 mean 963.8 μs ( +- 46.13 μs )+shortInt/Data.Digits base 10^9 mean 3.052 ms ( +- 238.5 μs )++mediumInt/FastDigits base 2 mean 1.213 ms ( +- 185.0 μs )+mediumInt/Data.Digits base 2 mean 12.41 ms ( +- 3.417 ms )++mediumInt/FastDigits base 10 mean 689.3 μs ( +- 32.43 μs )+mediumInt/Data.Digits base 10 mean 3.271 ms ( +- 137.3 μs )++mediumInt/FastDigits base 10^5 mean 220.1 μs ( +- 11.30 μs )+mediumInt/Data.Digits base 10^5 mean 711.1 μs ( +- 67.31 μs )++mediumInt/FastDigits base 10^9 mean 156.0 μs ( +- 9.115 μs )+mediumInt/Data.Digits base 10^9 mean 407.9 μs ( +- 19.58 μs )++longInt/FastDigits base 2 mean 3.515 ms ( +- 189.7 μs )+longInt/Data.Digits base 2 mean 183.2 ms ( +- 4.564 ms )++longInt/FastDigits base 10 mean 2.164 ms ( +- 134.7 μs )+longInt/Data.Digits base 10 mean 55.45 ms ( +- 946.7 μs )++longInt/FastDigits base 10^5 mean 1.467 ms ( +- 60.49 μs )+longInt/Data.Digits base 10^5 mean 11.09 ms ( +- 347.0 μs )++longInt/FastDigits base 10^9 mean 1.242 ms ( +- 52.92 μs )+longInt/Data.Digits base 10^9 mean 6.181 ms ( +- 226.1 μs )+```
bench/Bench.hs view
@@ -1,6 +1,6 @@ module Main where -import Criterion.Main+import Gauge.Main import qualified Data.Digits as D
+ changelog.md view
@@ -0,0 +1,15 @@+# 0.3.0.0++* Hide `Data.FastDigits.Internal`.++# 0.2.1.0++* Fix x32 build.++# 0.2.0.0++* Performance improvements.++# 0.1.0.0++* Initial release.
fast-digits.cabal view
@@ -1,53 +1,75 @@-name: fast-digits-version: 0.2.1.0-synopsis: The fast library for integer-to-digits conversion.-description: Convert an integer to digits and back.- Usually this library is twice as fast as "Data.Digits".- For small bases and long numbers it may be up to 40 times faster.-homepage: https://github.com/Bodigrim/fast-digits-license: GPL-3-license-file: LICENSE-author: Andrew Lelechenko-maintainer: andrew.lelechenko@gmail.com-category: Data-build-type: Simple-cabal-version: >=1.10+name: fast-digits+version: 0.3.0.0+license: GPL-3+license-file: LICENSE+maintainer: andrew.lelechenko@gmail.com+author: Andrew Lelechenko+homepage: https://github.com/Bodigrim/fast-digits+synopsis: Integer-to-digits conversion.+description:+ Convert an integer to digits and back.+ This library is both asymptotically (O(n^1.4) vs. O(n^2))+ and practically (2x-40x for typical inputs)+ faster than "Data.Digits".+category: Data+build-type: Simple+cabal-version: 2.0+extra-source-files:+ changelog.md+ README.md+tested-with:+ GHC ==7.10.3 GHC ==8.0.2 GHC ==8.2.2 GHC ==8.4.4 GHC ==8.6.5 GHC ==8.8.2 source-repository head- type: git+ type: git location: git://github.com/Bodigrim/fast-digits.git library- exposed-modules: Data.FastDigits- , Data.FastDigits.Internal- build-depends: base >=4.8 && < 5- , integer-gmp >=1.0- hs-source-dirs: src- default-language: Haskell2010- ghc-options: -Wall+ exposed-modules:+ Data.FastDigits+ hs-source-dirs: src+ default-language: Haskell2010+ ghc-options: -Wall+ build-depends:+ base >=4.8 && <5,+ integer-gmp >=1.0,+ fast-digits-internal +library fast-digits-internal+ exposed-modules:+ Data.FastDigits.Internal+ hs-source-dirs: src-internal+ default-language: Haskell2010+ ghc-options: -Wall+ build-depends:+ base >=4.8 && <5,+ integer-gmp >=1.0+ test-suite tests- type: exitcode-stdio-1.0- main-is: Tests.hs- build-depends: base- , tasty- , tasty-quickcheck- , tasty-smallcheck- , QuickCheck- , smallcheck- , digits- , fast-digits- hs-source-dirs: tests- default-language: Haskell2010- ghc-options: -Wall+ type: exitcode-stdio-1.0+ main-is: Tests.hs+ hs-source-dirs: tests+ default-language: Haskell2010+ ghc-options: -Wall+ build-depends:+ base,+ tasty,+ tasty-quickcheck,+ tasty-smallcheck,+ QuickCheck,+ smallcheck,+ digits,+ fast-digits,+ fast-digits-internal benchmark bench- type: exitcode-stdio-1.0- main-is: Bench.hs- hs-source-dirs: bench- build-depends: base- , criterion- , digits- , fast-digits- default-language: Haskell2010- ghc-options: -O2+ type: exitcode-stdio-1.0+ main-is: Bench.hs+ hs-source-dirs: bench+ default-language: Haskell2010+ ghc-options: -O2+ build-depends:+ base,+ digits,+ fast-digits,+ gauge
+ src-internal/Data/FastDigits/Internal.hs view
@@ -0,0 +1,53 @@+{-|+Module : Data.FastDigits.Internal+Copyright : (c) Andrew Lelechenko, 2015-2016+License : GPL-3+Maintainer : andrew.lelechenko@gmail.com+Stability : experimental++-}++{-# LANGUAGE CPP #-}+{-# LANGUAGE MagicHash #-}+{-# LANGUAGE UnboxedTuples #-}++{-# OPTIONS_GHC -fno-warn-type-defaults #-}+{-# OPTIONS_GHC -O2 #-}+{-# OPTIONS_GHC -optc-O3 #-}++module Data.FastDigits.Internal+ ( selectPower+ , selectPower'+ ) where++import GHC.Exts++#include "MachDeps.h"++-- | Take an integer base and return (pow, base^pow),+-- where base^pow <= maxBound and pow is as large as possible.+selectPower :: Word# -> (# Word#, Word# #)+#if WORD_SIZE_IN_BITS == 31+selectPower 2## = (# 31##, 2147483648## #)+#elif WORD_SIZE_IN_BITS == 32+selectPower 2## = (# 31##, 2147483648## #)+#else+selectPower 2## = (# 63##, 9223372036854775808## #)+#endif++selectPower base = go base+ where+ go pw = case timesWord2# pw pw of+ (# 0##, pw2 #)+ -> let (# n, pw2n #) = go pw2 in+ case timesWord2# pw pw2n of+ (# 0##, pw2n1 #) -> (#n `timesWord#` 2## `plusWord#` 1##, pw2n1 #)+ _ -> (# n `timesWord#` 2##, pw2n #)+ _ -> (# 1##, pw #)++-- | Take an integer base and return (pow, base^pow),+-- where base^pow <= maxBound and pow is as large as possible.+selectPower' :: Word -> (Word, Word)+selectPower' (W# base) = (W# power, W# poweredBase)+ where+ (# power, poweredBase #) = selectPower base
src/Data/FastDigits.hs view
@@ -1,16 +1,18 @@ {-| Module : Data.FastDigits-Description : The fast library for integer-to-digits conversion.-Copyright : (c) Andrew Lelechenko, 2015-2016+Description : Integer-to-digits conversion.+Copyright : (c) Andrew Lelechenko, 2015-2020 License : GPL-3 Maintainer : andrew.lelechenko@gmail.com Stability : experimental Convert an integer to digits and back.-Usually this library is twice as fast as "Data.Digits".-For small bases and long numbers it may be up to 40 times faster.+This library is both asymptotically (O(n^1.4) vs. O(n^2))+and practically (2x-40x for typical inputs)+faster than "Data.Digits". -} +{-# LANGUAGE BangPatterns #-} {-# LANGUAGE MagicHash #-} {-# LANGUAGE UnboxedTuples #-} @@ -82,15 +84,26 @@ else let (# fr, lr #) = digitsWordL base power r in fr ++ replicate (I# (unsafeCoerce# lr)) 0 ++ f q +padUpTo :: Int -> [Word] -> [Word]+padUpTo !n [] = replicate n 0+padUpTo !n (x : xs) = x : padUpTo (n - 1) xs+ -- | Return digits of a non-negative number in reverse order. digitsUnsigned :: Word -- ^ Precondition that base is ≥2 is not checked -> Natural -> [Word] digitsUnsigned (W# base) (NatS# n) = digitsWord base n-digitsUnsigned (W# base) (NatJ# n) = case power of- 1## -> digitsNatural base n- _ -> digitsNatural' base power poweredBase n+digitsUnsigned (W# base) (NatJ# n)+ | halfSize <- sizeofBigNat# n `iShiftRL#` 1#+ , isTrue# (halfSize ># 128#)+ = let pow = I# (word2Int# power *# halfSize) in+ let (nHi, nLo) = NatJ# n `quotRem` (NatS# poweredBase ^ (I# halfSize)) in+ padUpTo pow (digitsUnsigned (W# base) nLo) ++ digitsUnsigned (W# base) nHi+ | otherwise+ = case power of+ 1## -> digitsNatural base n+ _ -> digitsNatural' base power poweredBase n where (# power, poweredBase #) = selectPower base
− src/Data/FastDigits/Internal.hs
@@ -1,53 +0,0 @@-{-|-Module : Data.FastDigits.Internal-Copyright : (c) Andrew Lelechenko, 2015-2016-License : GPL-3-Maintainer : andrew.lelechenko@gmail.com-Stability : experimental---}--{-# LANGUAGE CPP #-}-{-# LANGUAGE MagicHash #-}-{-# LANGUAGE UnboxedTuples #-}--{-# OPTIONS_GHC -fno-warn-type-defaults #-}-{-# OPTIONS_GHC -O2 #-}-{-# OPTIONS_GHC -optc-O3 #-}--module Data.FastDigits.Internal- ( selectPower- , selectPower'- ) where--import GHC.Exts--#include "MachDeps.h"---- | Take an integer base and return (pow, base^pow),--- where base^pow <= maxBound and pow is as large as possible.-selectPower :: Word# -> (# Word#, Word# #)-#if WORD_SIZE_IN_BITS == 31-selectPower 2## = (# 31##, 2147483648## #)-#elif WORD_SIZE_IN_BITS == 32-selectPower 2## = (# 31##, 2147483648## #)-#else-selectPower 2## = (# 63##, 9223372036854775808## #)-#endif--selectPower base = go base- where- go pw = case timesWord2# pw pw of- (# 0##, pw2 #)- -> let (# n, pw2n #) = go pw2 in- case timesWord2# pw pw2n of- (# 0##, pw2n1 #) -> (#n `timesWord#` 2## `plusWord#` 1##, pw2n1 #)- _ -> (# n `timesWord#` 2##, pw2n #)- _ -> (# 1##, pw #)---- | Take an integer base and return (pow, base^pow),--- where base^pow <= maxBound and pow is as large as possible.-selectPower' :: Word -> (Word, Word)-selectPower' (W# base) = (W# power, W# poweredBase)- where- (# power, poweredBase #) = selectPower base