symbolize 1.0.0.0 → 1.0.0.1
raw patch · 4 files changed
+86/−25 lines, 4 files
Files
- CHANGELOG.md +3/−3
- README.md +33/−9
- src/Symbolize.hs +22/−3
- symbolize.cabal +28/−10
CHANGELOG.md view
@@ -8,9 +8,9 @@ ## 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.+## 1.0.0.1++- Minor documentation improvements ## 1.0.0.0 - 2025-02-17
README.md view
@@ -7,20 +7,44 @@ [API Documentation](https://hackage.haskell.org/package/symbolize/docs/Symbolize.html) + Symbols, also known as Atoms or Interned Strings, are a common technique-to reduce memory usage and improve performance when using many small strings.+to reduce memory usage and improve performance when using many small strings: -By storing a single copy of each encountered string in a global table and giving out indexes to that table,-it is possible to compare strings for equality in constant time, instead of linear (in string size) time.+A Symbol represents a string (any `Textual`, so String, Text, ShortText, ByteString, ShortByteString, etc.) -The main advantages of Symbolize over existing symbol table implementations are:+Just like `ShortText`, `ShortByteString` and `ByteArray`, a `Symbol` has an optimized memory representation,+directly wrapping a primitive `ByteArray#`. +Furthermore, a global symbol table keeps track of which values currently exist, ensuring we always deduplicate symbols.+This therefore allows us to:+- Check for equality between symbols in constant-time (using pointer equality)+- Calculate the hash in constant-time (using `StableName`)+- Keep the memory footprint of repeatedly-seen strings low.++This is very useful if you're frequently comparing strings+and the same strings might come up many times.+It also makes Symbol a great candidate for a key in e.g. a `HashMap` or `HashSet`.++The global symbol table is implemented using weak pointers,+which means that unused symbols will be garbage collected.+As such, you do not need to be concerned about memory leaks+(as is the case with many other symbol table implementations).++Symbols are considered 'the same' regardless of whether they originate+from a `String`, (lazy or strict, normal or short) `Data.Text`, (lazy or strict, normal or short) `Data.ByteString` etc.++The main advantages of Symbolize over other symbol table implementations are:+ - Garbage collection: Symbols which are no longer used are automatically cleaned up.-- `Symbol`s have a memory footprint of exactly 1 `Word` and are nicely unpacked by GHC.-- Support for any `Textual` type, including `String`, (strict and lazy) `Data.Text`, (strict and lazy) `Data.ByteString` etc.-- Thread-safe.-- Efficient: Calls to `lookup` and `unintern` are free of atomic memory barriers (and never have to wait on a concurrent thread running `intern`)-- Support for a maximum of 2^64 symbols at the same time (you'll probably run out of memory before that point).+- Support for any `Textual` type, including `String`, (strict and lazy) `Data.Text`, (strict and lazy) `Data.ByteString`, `ShortText`, `ShortByteString`, etc.+- Great memory usage:+ - `Symbol`s are simply a (lifted) wrapper around a `ByteArray#`, which is nicely unpacked by GHC.+ - The symbol table is an `IntMap` that contains weak pointers to these same `ByteArray#`s and their associated `StableName#`s+- Great performance:+ - `unintern` is a simple pointer-dereference+ - calls to `lookup` are free of atomic memory barriers (and never have to wait on a concurrent thread running `intern`)+- Thread-safe ## Basic usage
src/Symbolize.hs view
@@ -7,9 +7,28 @@ -- Symbols, also known as Atoms or Interned Strings, are a common technique -- to reduce memory usage and improve performance when using many small strings. ----- By storing a single copy of each encountered string in a global table and giving out pointers to the stored keys,--- it is possible to compare strings for equality in constant time, instead of linear (in string size) time.--- Furthermore, by using `StableName`, hashing of Symbols also takes constant-time, so `Symbol`s make great hashmap keys!.+-- A Symbol represents a string (any `Textual`, so String, Text, ShortText, ByteString, ShortByteString, etc.)+--+-- Just like `ShortText`, `ShortByteString` and `ByteArray`, a `Symbol` has an optimized memory representation,+-- directly wrapping a primitive `ByteArray#`.+--+-- Furthermore, a global symbol table keeps track of which values currently exist, ensuring we always deduplicate symbols.+-- This therefore allows us to:+-- - Check for equality between symbols in constant-time (using pointer equality)+-- - Calculate the hash in constant-time (using `StableName`)+-- - Keep the memory footprint of repeatedly-seen strings low.+--+-- This is very useful if you're frequently comparing strings+-- and the same strings might come up many times.+-- It also makes Symbol a great candidate for a key in e.g. a `HashMap` or `HashSet`.+--+-- The global symbol table is implemented using weak pointers,+-- which means that unused symbols will be garbage collected.+-- As such, you do not need to be concerned about memory leaks+-- (as is the case with many other symbol table implementations).+--+-- Symbols are considered 'the same' regardless of whether they originate+-- from a `String`, (lazy or strict, normal or short) `Data.Text`, (lazy or strict, normal or short) `Data.ByteString` etc. -- -- The main advantages of Symbolize over other symbol table implementations are: --
symbolize.cabal view
@@ -5,25 +5,41 @@ -- see: https://github.com/sol/hpack name: symbolize-version: 1.0.0.0+version: 1.0.0.1 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.+ to reduce memory usage and improve performance when using many small strings: .- By storing a single copy of each encountered string in a global table and giving out pointers to the stored keys,- it is possible to compare strings for equality in constant time, instead of linear (in string size) time.- Furthermore, by using `StableName`, hashing of Symbols also takes constant-time, so `Symbol`s make great hashmap keys!.+ A Symbol represents a string (any `Textual`, so String, Text, ShortText, ByteString, ShortByteString, etc.) .+ Just like `ShortText`, `ShortByteString` and `ByteArray`, a `Symbol` has an optimized memory representation,+ directly wrapping a primitive `ByteArray#`.+ .+ Furthermore, a global symbol table keeps track of which values currently exist, ensuring we always deduplicate symbols.+ This therefore allows us to:+ - Check for equality between symbols in constant-time (using pointer equality)+ - Calculate the hash in constant-time (using `StableName`)+ - Keep the memory footprint of repeatedly-seen strings low.+ .+ This is very useful if you're frequently comparing strings+ and the same strings might come up many times.+ It also makes Symbol a great candidate for a key in e.g. a `HashMap` or `HashSet`.+ .+ The global symbol table is implemented using weak pointers,+ which means that unused symbols will be garbage collected.+ As such, you do not need to be concerned about memory leaks+ (as is the case with many other symbol table implementations).+ . The main advantages of Symbolize over other symbol table implementations are: . - Garbage collection: Symbols which are no longer used are automatically cleaned up. - Support for any `Textual` type, including `String`, (strict and lazy) `Data.Text`, (strict and lazy) `Data.ByteString`, `ShortText`, `ShortByteString`, etc. - Great memory usage:- - `Symbol`s are simply a (lifted) wrapper around a `ByteArray#`, which is nicely unpacked by GHC.- - The symbol table is an `IntMap` that contains weak pointers to these same `ByteArray#`s and their associated `StableName#`s+ - `Symbol`s are simply a (lifted) wrapper around a `ByteArray#`, which is nicely unpacked by GHC.+ - The symbol table is an `IntMap` that contains weak pointers to these same `ByteArray#`s and their associated `StableName#`s - Great performance:- - `unintern` is a simple pointer-dereference- - calls to `lookup` are free of atomic memory barriers (and never have to wait on a concurrent thread running `intern`)+ - `unintern` is a simple pointer-dereference+ - calls to `lookup` are free of atomic memory barriers (and never have to wait on a concurrent thread running `intern`) - Thread-safe . Please see the full README below or on GitHub at <https://github.com/Qqwy/haskell-symbolize#readme>@@ -36,6 +52,8 @@ license: BSD-3-Clause license-file: LICENSE build-type: Simple+tested-with:+ GHC ==9.4.8 || ==9.6.6 || ==9.8.4 || ==9.10.1 extra-source-files: README.md CHANGELOG.md@@ -47,11 +65,11 @@ library exposed-modules: Symbolize- Symbolize.SymbolTable Symbolize.Textual other-modules: Symbolize.Accursed Symbolize.SipHash+ Symbolize.SymbolTable hs-source-dirs: src default-extensions: