symbolize 0.1.0.2 → 0.1.0.3
raw patch · 4 files changed
+28/−15 lines, 4 filesdep +containersPVP ok
version bump matches the API change (PVP)
Dependencies added: containers
API changes (from Hackage documentation)
Files
- CHANGELOG.md +4/−0
- src/Symbolize.hs +16/−9
- symbolize.cabal +4/−1
- test/suite/SymbolizeTest.hs +4/−5
CHANGELOG.md view
@@ -8,6 +8,10 @@ ## Unreleased +- Switch from `HashMap ShortText (Weak Symbol)` to `Map ShortText (Weak Symbol)` for the `textTosymbol` part of the global symbol table. Potentially slightly slower, but HashDoS-resistant. + (Note that the `symbolToText :: HashMap Word -> ShortText` is unaffected as its keys are not user-created and guaranteed unique.)+- Remove NOINLINE for lookup as it is now a proper IO function.+ ## 0.1.0.1 / 0.1.0.2 - 2023-11-24 Fixes in the README and package description only, for better rendering on Hackage.
src/Symbolize.hs view
@@ -111,6 +111,8 @@ import Data.Function ((&)) import Data.HashMap.Strict (HashMap) import qualified Data.HashMap.Strict as HashMap+import Data.Map.Strict (Map)+import qualified Data.Map.Strict as Map import Data.Hashable (Hashable (..)) import Data.IORef (IORef) import qualified Data.IORef as IORef@@ -219,6 +221,12 @@ -- but you can use `globalSymbolTable` to get a handle to it and use its `Show` instance for introspection. -- -- `globalSymbolTableSize` can similarly be used to get the current size of the table.+--+-- Current implementation details (these might change even between PVP-compatible versions):+-- +-- - A (containers) `Map` is used for mapping text -> symbol. This has O(log2(n)) lookup time, but is resistent to HashDoS attacks.+-- - A (unordered-containers) `HashMap` is used for mapping symbol -> text. This has O(log16(n)) lookup time. +-- Because symbols are unique and their values are not user-generated, there is no danger of HashDoS here. data GlobalSymbolTable = GlobalSymbolTable { next :: !(MVar Word), mappings :: !(IORef SymbolTableMappings)@@ -247,12 +255,12 @@ <> " }" data SymbolTableMappings = SymbolTableMappings- { textToSymbols :: !(HashMap ShortText (Weak Symbol)),+ { textToSymbols :: !(Map ShortText (Weak Symbol)), symbolsToText :: !(HashMap Word ShortText) } -- | Unintern a symbol, returning its textual value.--- Takes O(log16 n) time to look up the matching textual value, where n is the number of symbols currently in the table.+-- Takes O(log16(n)) time to look up the matching textual value, where n is the number of symbols currently in the table. -- -- Afterwards, the textual value is converted to the desired type s. See `Textual` for the type-specific time complexity. --@@ -279,7 +287,7 @@ -- -- Returns `Nothing` if no such symbol currently exists. ----- Takes O(log16 n) time, where n is the number of symbols currently in the table.+-- Takes O(log2(n)) time, where n is the number of symbols currently in the table. -- -- Runs concurrently with any other operation on the symbol table, without any atomic memory barriers. --@@ -289,17 +297,16 @@ let !text' = toShortText text table <- globalSymbolTable mappings <- IORef.readIORef (mappings table)- let maybeWeak = mappings & textToSymbols & HashMap.lookup text'+ let maybeWeak = mappings & textToSymbols & Map.lookup text' case maybeWeak of Nothing -> pure Nothing Just weak -> do Weak.deRefWeak weak-{-# NOINLINE lookup #-} -- | Intern a string-like value. -- -- First converts s to a `ShortText` (if it isn't already one). See `Textual` for the type-specific time complexity of this.--- Then, takes O(log16 n) time to look up the matching symbol and insert it if it did not exist yet (where n is the number of symbols currently in the table).+-- Then, takes O(log2(n)) time to look up the matching symbol and insert it if it did not exist yet (where n is the number of symbols currently in the table). -- -- Any concurrent calls to (the critical section in) `intern` are synchronized. intern :: (Textual s) => s -> Symbol@@ -322,7 +329,7 @@ let !mappings2 = SymbolTableMappings { symbolsToText = HashMap.insert idx text' symbolsToText,- textToSymbols = HashMap.insert text' weakSymbol textToSymbols+ textToSymbols = Map.insert text' weakSymbol textToSymbols } IORef.atomicWriteIORef (mappings globalSymbolTable') mappings2 @@ -349,7 +356,7 @@ -- SAFETY: We need all calls to globalSymbolTable' to use the same thunk, so NOINLINE. System.IO.Unsafe.unsafePerformIO $ do nextRef <- MVar.newMVar 0 -- IORef.newIORef 0- mappingsRef <- IORef.newIORef (SymbolTableMappings HashMap.empty HashMap.empty)+ mappingsRef <- IORef.newIORef (SymbolTableMappings Map.empty HashMap.empty) return (GlobalSymbolTable nextRef mappingsRef) {-# NOINLINE globalSymbolTable' #-} @@ -374,6 +381,6 @@ Just text -> SymbolTableMappings { symbolsToText = HashMap.delete idx symbolsToText,- textToSymbols = HashMap.delete text textToSymbols+ textToSymbols = Map.delete text textToSymbols } {-# NOINLINE finalizer #-}
symbolize.cabal view
@@ -5,7 +5,7 @@ -- see: https://github.com/sol/hpack name: symbolize-version: 0.1.0.2+version: 0.1.0.3 synopsis: Efficient global Symbol table, with Garbage Collection. description: Symbols, also known as Atoms or Interned Strings, are a common technique to reduce memory usage and improve performance when using many small strings.@@ -58,6 +58,7 @@ build-depends: base >=4.7 && <5 , bytestring >=0.11.0 && <0.12+ , containers >=0.6.0 && <0.7 , deepseq >=1.4.0 && <1.5 , hashable >=1.4.0 && <1.5 , text >=2.0 && <2.2@@ -85,6 +86,7 @@ build-depends: base >=4.7 && <5 , bytestring >=0.11.0 && <0.12+ , containers >=0.6.0 && <0.7 , deepseq >=1.4.0 && <1.5 , doctest-parallel , hashable >=1.4.0 && <1.5@@ -118,6 +120,7 @@ async , base >=4.7 && <5 , bytestring >=0.11.0 && <0.12+ , containers >=0.6.0 && <0.7 , deepseq >=1.4.0 && <1.5 , hashable >=1.4.0 && <1.5 , hedgehog
test/suite/SymbolizeTest.hs view
@@ -1,17 +1,16 @@+{-# OPTIONS_GHC -Wno-missing-export-lists #-} module SymbolizeTest where --- import qualified System.Mem- import qualified Control.Concurrent.Async import Control.Monad.IO.Class (liftIO) import qualified Data.Hashable-import Data.Text (Text)+-- import Data.Text (Text) import Hedgehog import qualified Hedgehog.Gen as Gen import qualified Hedgehog.Range as Range import qualified Symbolize-import qualified System.Mem-import Test.Tasty.HUnit+-- import qualified System.Mem+-- import Test.Tasty.HUnit hprop_symbolTableIsIdempotent :: Property hprop_symbolTableIsIdempotent = withTests 1000 $ property $ do