bytestring-trie 0.2.7 → 0.2.7.1
raw patch · 5 files changed
+85/−32 lines, 5 filesdep ~basePVP ok
version bump matches the API change (PVP)
Dependency ranges changed: base
API changes (from Hackage documentation)
Files
- CHANGELOG +3/−0
- bytestring-trie.cabal +5/−4
- dev/Bench/Regression.hs +18/−11
- dev/Test/Main.hs +2/−2
- src/Data/Trie/Internal.hs +57/−15
CHANGELOG view
@@ -1,3 +1,6 @@+0.2.7.1 (2022-08-28):+ * Technical Debt:+ - Updated for GHC 9.4 0.2.7 (2022-03-14): * Added: - Instances: Eq1, Ord, Ord1, IsList, Show1, Read, Read1, NFData.
bytestring-trie.cabal view
@@ -6,11 +6,11 @@ -- <https://github.com/haskell/cabal/issues/4899> ------------------------------------------------------------------- wren gayle romano <wren@cpan.org> ~ 2022.03.05+-- wren gayle romano <wren@cpan.org> ~ 2022.08.28 ---------------------------------------------------------------- Name: bytestring-trie-Version: 0.2.7+Version: 0.2.7.1 Build-Type: Simple Stability: provisional Homepage: https://wrengr.org/software/hackage.html@@ -57,7 +57,8 @@ GHC ==8.8.4, GHC ==8.10.3, GHC ==9.0.1,- GHC ==9.2.1+ GHC ==9.2.4,+ GHC ==9.4.1 -- These are the versions of our dependencies which ship with the -- above. Alas, we can't merge this with the above because cabal -- files only have full-line comments, not end-of-line comments.@@ -93,7 +94,7 @@ -- we verified (for GHC 7.4.1). We no longer maintain CI tests -- that far back, but they still seem to work according to Hackage: -- <https://matrix.hackage.haskell.org/#/package/bytestring-lexing>- Build-Depends: base >= 4.5 && < 4.17+ Build-Depends: base >= 4.5 && < 4.18 , bytestring >= 0.9.2 && < 0.12 , binary >= 0.5.1 && < 0.11 , deepseq >= 1.2 && < 1.5
dev/Bench/Regression.hs view
@@ -2,7 +2,7 @@ {-# LANGUAGE CPP, BangPatterns #-} ------------------------------------------------------------------- ~ 2022.03.12+-- ~ 2022.04.03 -- | -- Module : Bench.Regression -- Copyright : 2008--2022 wren romano@@ -94,20 +94,27 @@ #endif ------------------------------------------------------------------- Hopefully the @fmap Sum@ will be rewritten into 'coerce'. Though--- we may want to do that explicitly... bgroup_Foldable :: BenchmarkE (T.Trie Int) bgroup_Foldable = bgroupE "Foldable"- [ benchE "fold" $ C.nf--- FIXME: the version using @(. fmap Sum)@ is monstrously slower--- than the version using 'coerce'. On the one hand that makes--- sense, but on the other hand it means we really should provide--- rewrite rules for our Functor instance.+ -- BUG: For these two 'fold' tests, whichever one we put first+ -- runs much more slowly than the one we put second! Thus, there's+ -- some sort of bug in how 'C.env' is forcing things. And adding+ -- calls to 'Control.Exception.evaluate' and 'Control.DeepSeq.rnf'+ -- doesn't help any. So for now we just put a nonce test first+ -- to do whatever forcing is necessary.+ [ benchE "IGNORE_THIS" $ C.nf (F.fold . fmap Sum)+ -- Before adding rewrite rules for the 'Functor' type class, the+ -- test using @(.)@ used to run monstrously slower than the version+ -- using @(.#)@; indicating that those rewrites didn't automatically+ -- come for free. Since defining our own rewrite rules, the two+ -- versions seem about the same and it varies which one comes out+ -- faster. Marking 'fold' as INLINE (instead of INLINABLE) causes+ -- the @(.)@ variant to be closer to 'foldMap' than to the+ -- 'fold' @(.#)@ variant.+ , benchE "fold(.)" $ C.nf (F.fold . fmap Sum) #if MIN_VERSION_base(4,7,0)- (F.fold .# fmap Sum)-#else- (F.fold . fmap Sum)+ , benchE "fold(.#)" $ C.nf (F.fold .# fmap Sum) #endif , benchE "foldMap" $ C.nf (F.foldMap Sum) #if MIN_VERSION_base(4,13,0)
dev/Test/Main.hs view
@@ -18,8 +18,8 @@ ---------------------------------------------------------------- module Main (main) where -#if !(MIN_VERSION_base(4,13,0))--- [GHC 8.8.1]: This guard is just to avoid an \"unused import\" warning.+#if !(MIN_VERSION_base(4,11,0))+-- [GHC 8.4.1]: This guard is just to avoid an \"unused import\" warning. import Shared.BaseCompat #endif import Test.Utils
src/Data/Trie/Internal.hs view
@@ -17,7 +17,7 @@ {-# LANGUAGE Trustworthy #-} #endif --------------------------------------------------------------- ~ 2022.03.13+-- ~ 2022.04.03 -- | -- Module : Data.Trie.Internal -- Copyright : 2008--2022 wren romano@@ -151,6 +151,10 @@ #if __GLASGOW_HASKELL__ >= 708 import qualified GHC.Exts (IsList(..)) #endif+#if MIN_VERSION_base(4,7,0)+-- [GHC 7.8.1]: "Data.Coerce" added to base.+import Data.Coerce (coerce)+#endif ------------------------------------------------------------ ------------------------------------------------------------@@ -315,6 +319,14 @@ -- Prefix/Mask should be deterministic regardless of insertion order -- TODO: prove this is so. +-- [Note:Closure] aka: Local 'go' functions and capturing+-- ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~+-- Copied from 'IntMap': Care must be taken when using 'go' function+-- which captures an argument. Sometimes (for example when the+-- argument is passed to a data constructor, as in insert), GHC+-- heap-allocates more than necessary. Therefore C-- code must be+-- checked for increased allocation when creating and modifying+-- such functions. {----------------------------------------------------------- -- Smart constructors@@ -723,7 +735,7 @@ {- -- TODO: do we want/need these?-#if __GLASGOW_HASKELL__+#ifdef __GLASGOW_HASKELL__ instance Data.Data.Data (Trie a) where ... -- See 'IntMap' for how to do this without sacrificing abstraction. #endif@@ -738,25 +750,39 @@ -- Instances: Functor -----------------------------------------------------------} --- TODO: IntMap floats the definition of 'fmap' out of the instance--- so that it can provide rewrite rules (for @map f . map g@ and--- for @map coerce@). Should we do the same? instance Functor Trie where- fmap f = go- where- go Empty = Empty- go (Arc k Nothing t) = Arc k Nothing (go t)- go (Arc k (Just v) t) = Arc k (Just (f v)) (go t)- go (Branch p m l r) = Branch p m (go l) (go r)-#if __GLASGOW_HASKELL__+ {-# INLINE fmap #-}+ fmap = fmapTrie+#ifdef __GLASGOW_HASKELL__ -- Non-default definition since 0.2.7- -- Avoiding closure over @v@ because that's what IntMap does.+ -- Leaving this definition inline and avoiding closure over @v@+ -- because that's what 'IntMap' does. _ <$ Empty = Empty v <$ (Arc k Nothing t) = Arc k Nothing (v <$ t) v <$ (Arc k (Just _) t) = Arc k (Just v) (v <$ t) v <$ (Branch p m l r) = Branch p m (v <$ l) (v <$ r) #endif +-- | Implementation of 'fmap', floated out so that we can give it rewrite rules.+fmapTrie :: (a -> b) -> Trie a -> Trie b+fmapTrie f = go+ where+ go Empty = Empty+ go (Arc k Nothing t) = Arc k Nothing (go t)+ go (Arc k (Just v) t) = Arc k (Just (f v)) (go t)+ go (Branch p m l r) = Branch p m (go l) (go r)+#ifdef __GLASGOW_HASKELL__+{-# NOINLINE [1] fmapTrie #-}+{-# RULES+"fmapTrie/fmapTrie" forall f g xs .+ fmapTrie f (fmapTrie g xs) = fmapTrie (f . g) xs+ #-}+-- 'IntMap' doesn't bother giving a rule for 'id'; so I guess we won't either.+#if MIN_VERSION_base(4,7,0)+{-# RULES "fmapTrie/coerce" fmapTrie coerce = coerce #-}+#endif+#endif+ -- TODO: strict version of fmap. Is there a canonical name\/class for this yet? {-----------------------------------------------------------@@ -764,6 +790,8 @@ -----------------------------------------------------------} instance Traversable Trie where+ -- TODO: 'IntMap' marks this INLINE and floats out an INLINE+ -- top-level definition; no rules though, afaict. traverse f = go where go Empty = pure Empty@@ -905,6 +933,7 @@ #else mappend = mergeBy $ \x y -> Just (x `mappend` y) #endif+ -- TODO: Can we improve `mconcat` over the default? {-----------------------------------------------------------@@ -1305,7 +1334,11 @@ -- before being inlined. instance Foldable Trie where- {-# INLINABLE fold #-}+ -- TODO: 'IntMap' marks 'fold' as INLINABLE; however, that seems+ -- to introduce a bit of slowdown with respect to 'foldMap'+ -- (which goes away when marked INLINE instead); so we should+ -- do more to discern which inlinement is preferable.+ {-# INLINE fold #-} fold = go where go Empty = mempty@@ -1422,7 +1455,7 @@ {- -- TODO: need to move these definitions here... -- TODO: may want to give a specialized implementation of 'member' then- {-# INLINE elem #-}+ {-# INLINE elem #-} -- TODO: 'IntMap' uses INLINABLE with a local definition; rather than INLINE with the top-level definition... Also, that TLD remarks to see [Note:Closure] elem = member -} -- TODO: why does IntMap define these two specially, rather than using foldl' or foldl1' ?@@ -1692,6 +1725,10 @@ -- Query functions (just recurse) -----------------------------------------------------------} +-- TODO: All the lookup-like functions for 'IntMap' remark to see+-- [Note:Closure]; so we should double check our 'lookupBy_' adheres+-- to that performance guideline.+ -- | Generic function to find a value (if it exists) and the subtrie -- rooted at the prefix. The first function argument is called if and -- only if a node is exactly reachable by the query; if no node is@@ -2262,6 +2299,11 @@ -- TODO: should verify that all of these are now free of the quadratic -- slowdown from reconstructing keys. They should be, but just to -- verify that some new quadratic hasn't accidentally crept in...++-- TODO: Maybe we should follow 'IntMap' and separate out NOINLINE+-- versions of these functions which construct a specialized View+-- type, vs INLINE wrappers that convert the View into the+-- Maybe/pair/etc. -- | Return the lexicographically smallest 'ByteString' and the -- value it's mapped to; or 'Nothing' for the empty trie. When one