string-interner

Fixed

• Fixed off-by-one bug in serde support. #91

Improvements

• Improve documentation about custom hashing. #90
• Add notification about unchecked resolution for BufferBackend. #92
• Updated dependencies. #100 #101
• Specify Rust MSRV to be 1.65. #101

• Update hashbrown dependency from version 0.9 to version 0.11.

• Add shrink_to_fit method to StringInterner via backend. (#36)

• Add support more than 4G of interned strings with StringBackend. (#37)

• Remove S: Symbol trait bound from interner backends.

• Remove S: Symbol trait bound from Clone impl for StringBackend.

• Reworked the memory and allocation tests

  • Run them via cargo test -- --test-threads 1

• CI now tests the whole build for windows, linux (ubuntu) and macos.

• Add cargo-audit and cargo-outdated checks to CI pipeline.

• Remove no longer needed jemalloc dev-dependency.

• Ensure cloned StringInterner can still look up the same symbols. #34 (Thanks @alamb)
  • This requires BuildHasher: Clone trait bound for StringInterner's Clone impl.

• The BucketBackend now implements Send + Sync.
• Implemented some minor internal improvements.
• Update dependencies:
  • hashbrown 0.8 -> 0.9
  • cfg-if 0.1 -> 1.0

• Make DefaultBackend generic over its symbol type.
  • This simplifies type ascription of string interners that do not use the default symbol type.
    • E.g. StringInterner<usize> is now possible to write (again).
• Add backends crate feature.
  • Enabled by default.
  • Disable this if you do not use any of the backends provided by the string-interner crate.

• Add Symbol implementation for usize.

• Add new StringBackend that is optimized for memory allocations and footprint.
  • Use it if your memory constraints are most important to you.

Special thanks to Ten0 for help with this release!

• Remove usage of unsafe in Symbol::try_from_usize methods.
• Remove no longer correct unsafe impls for Send and Sync for StringInterner.
• Add new crate feature more-inline that puts more #[inline] on public methods.
  • The new more-inline crate feature is enabled by default. If you want to turn it off use --no-default-features.
  • Enabling more-inline also enables hashbrown/more-inline.
• Remove &B: IntoIter trait bound from Clone impl of StringInterner

Thanks a lot (again) to CAD97 who is the vanguard of the technical improvements in this release with their blog post.

• Significantly improved StringInterner's memory consumption independend from the used internment backend.
• Significantly improved StringInterner's throughput for interning strings.
• Change the Backend trait:
  • intern is no longer unsafe
  • intern returns S (symbol type) instead of (InternedStr, S)
  • same as above for intern_static
  • add unsafe fn resolve_unchecked which does the same as resolve but explicitely without bounds checking
• No longer export backend::InternedStr type
• Make hashbrown a mandatory dependency. Note: We depend on it for the moment for its raw_entry API that has not yet been stabilized for Rust. Also benchmarks show that it is 20-30% faster than Rust's hashmap implementation.
• Benchmarks now show performance when using FxBuildHasher as build hasher.

• Allow to intern &'static str using get_or_intern_static API.
  • This is a common use case and more efficient since the interner can skip some allocations in this special case.
• Fix bug in SymbolU16 and SymbolU32 that instantiating them with values greater or equal to u16::MAX or u32::MAX respectively caused them to panic instead of returning None.
  • Special thanks to Ten0 for reporting the issue!
• Add a bunch of additional unit tests to further solifidy the implementation.

Special thanks to CAD97 who motivated me to craft this release through their blog post "String interners in Rust". Also I want to thank matklad who wrote a nice blog post that inspired the design of the new BucketBackend for StringInterner.

• Implement pluggable backends for StringInterner. Uses the new BucketBackend by default which results in significant performance boosts and lower memory consumption as well as fewer overall memory allocations.

  This makes it possible for dependencies to alter the behavior of internment. The string-interner crate comes with 2 predefined backends:

  1. SimpleBackend: Which is how the StringInterner of previous versions worked by default. It performs one allocation per interned string.
  2. BucketBackend: Tries to minimize memory allocations and packs interned strings densely. This is the new default behavior for this crate.

• Due to the above introduction of backends some APIs have been removed:

  • reserve
  • capacity
  • the entire iter module
    • Note: Simple iteration through the StringInterer's interned strings and their symbols is still possible if the used backend supports iteration.
  • resolve_unchecked: Has no replacement, yet but might be reintroduced in future versions again.
  • shrink_to_fit: The API design was never really a good fit for interners.

• Remove Ord trait bound from Symbol trait
  • Also change Symbol::from_usize(usize) -> Self to Symbol::try_from_usize(usize) -> Option<Self>
• Minor performance improvements for DefaultSymbol::try_from_usize
• Put all iterator types into the iter sub module
• Put all symbol types into the symbol sub module
• Add new symbol types:
  • SymbolU16: 16-bit wide symbol
  • SymbolU32: 32-bit wide symbol (default)
  • SymbolUsize: same size as usize
• Various internal improvements and reorganizations

• Make it possible to use this crate in no_std environments
  • Use the new hashbrown crate feature together with no_std
• Rename Sym to DefaultSymbol
• Add IntoIterator impl for &StringInterner
• Add some #[inline] annotations which improve performance for queries
• Various internal improvements (uses Pin self-referentials now)

• CRITICAL fix use after free bug in StringInterner::clone()
• implement std::iter::Extend for StringInterner
• Sym::from_usize now avoids using unsafe code
• optimize FromIterator impl of StringInterner
• move to Rust 2018 edition

Thanks YOSHIOKA Takuma for implementing this release.

release of version 0.7.0

• changed license from MIT to MIT/APACHE2.0
• removed generic impl of Symbol for types that are From<usize> and Into<usize>
• removed StringInterner::clear API since its usage breaks invariants
• added StringInterner::{capacity, reserve} APIs
• introduced a new default symbol type Sym that is a thin wrapper around NonZeroU32 (idea by [koute][gh-user-koute])
• made DefaultStringInterner a type alias for the new StringInterner<Sym>
• added convenient FromIterator impl to StringInterner<S: Sym>
• dev
  • rewrote all unit tests (serde tests are still missing)
  • entirely refactored benchmark framework
  • added html_root_url to crate root

Thanks [matklad][gh-user-madklad] for suggestions and impulses

• CRITICAL: fix use after free bug in StringInterner::clone implementation.

• fixed a bug that StringInterner's Send impl didn't respect its generic HashBuilder parameter. Fixes GitHub [issue #4][gh-issue-4].

• added shrink_to_fit public method to StringInterner - (by artemshein)

• fixed a bug that inserting non-owning string types (e.g. str) was broken due to dangling pointers (Thanks to artemshein for fixing it!)

• added optional serde serialization and deserialization support
• more efficient and generic PartialEq implementation for StringInterner
• made StringInterner generic over BuildHasher to allow for custom hashers

• added IntoIterator trait implementation for StringInterner
• greatly simplified iterator code

• removed restrictive constraint for Unsigned for Symbol

• added Send and Sync to InternalStrRef to make StringInterner itself Send and Sync