5 releases (3 breaking)

0.4.0 Nov 17, 2021
0.3.0 Nov 13, 2021
0.2.0 Nov 5, 2021
0.1.1 Oct 31, 2021
0.1.0 Oct 30, 2021

#44 in Memory management

Download history 30/week @ 2021-10-28 21/week @ 2021-11-04 28/week @ 2021-11-11 13/week @ 2021-11-18

92 downloads per month

MPL-2.0 license

93KB
1.5K SLoC

hybrid-rc - Thread-safe hybrid reference counting pointers

Crates.io Documentation License Build Status Test Coverage

Usage

  1. Add the following to your Cargo.toml:
[dependencies]
hybrid-rc = "0.4.0"
  1. Read the crate documentation

Functionality

The hybrid-rc crate provides generic types HybridRc<T, State> and Weak<T> for reference counting pointers.

It is loosely based on the algorithm described in "Biased reference counting: minimizing atomic operations in garbage collection" by Jiho Choi et. al. but adapted to Rust's type system and its lack of a managed runtime environment.

The switching between atomic and non-atomic reference counting is managed through the type system:

  • HybridRc<T, Local> (type aliased as Rc): very fast but only usable on one thread.
  • HybridRc<T, Shared> (type aliased as Arc): slower but universally usable.

Instances of both variants are convertible into each other. Especially, an Rc can always be converted into an Arc using HybridRc::to_shared(&rc) or .into(). An Arc on the other hand can only be converted into an Rc using HybridRc::to_local(&arc) or .try_into() if no other thread has Rcs for the same value.

Tasks

  • All stable Rc/Arc functionality implemented
    • new()
    • as_ptr()
    • get_mut()
    • get_mut_unchecked()
    • make_mut()
    • into_raw()
    • from_raw()
    • pin()
    • try_unwrap()
    • weak_count()
    • strong_count()
    • [in|de]crement_strong_count()
    • ptr_eq()
    • downcast()
    • impl AsRef
    • impl Borrow
    • impl Clone
    • impl Debug
    • impl Default
    • impl Deref
    • impl Display
    • impl Drop
    • impl From<&[T]>
    • impl From<&str>
    • impl From<String>
    • impl From<Box<T>>
    • impl From<Cow<'a, T>
    • impl From<T>
    • impl From<Vec<T>>
    • impl FromIterator
      • Specialization for TrustedLen
    • impl Into<Waker>
    • impl Hash
    • impl Ord
    • impl PartialEq, impl Eq
    • impl PartialOrd
    • impl Pointer
    • deref(), borrow(), as_ref()
    • Weak pointers (downgrade(), upgrade())
  • Conversion between local and shared HybridRcs
    • to_shared(), to_local()
    • impl From, impl TryFrom
  • Convenience type aliases
  • Unsized coercion
    • Upcasting to HybridRc<dyn Any, _> with From
    • Converting from HybridRc<[T; N], _> to HybridRc<[T], _> with From
  • Minimize memory overhead

Performance

Rc::clone() and Arc::clone() as well as Rc::drop() and Arc::drop() run in virtually the same time as their standard library counterparts.

Weak references are modeled after std::sync::Weak and thus always use atomic operations. Weak::clone() and upgrading to an Arc perform slightly slower than their standard library counterparts. Weak::upgrade_local() is about 15 % slower than Weak::upgrade().

Rc::to_shared() is essentially as expensive as Arc::clone(), while Arc::to_local() is about as expensive as Weak::upgrade().

The memory overhead for each allocation is about twice as high than for the standard library counterparts to accomodate for the additional reference counter and the owner thread id (on x86_64 that amounts to 32 bytes per allocation). The pointer objects themselves are as big as NonNull<T>.

Examplary benchmarks

Benchmarks executed on an Intel Core i7-4790K. YMMV.

std::rc::Rc HybridRc<T, Local> HybridRc<T, Shared> std::sync::Arc
clone() 1.5 ns 1.5 ns 5.0 ns 5.0 ns
drop() 1.5 ns 1.6 ns 4.6 ns 6.3 ns
to_local() 8.2 ns
to_shared() 5.0 ns
downgrade() 1.5 ns 8.0 ns 8.0 ns 7.8 ns
upgrade*() 1.6 ns 9.4 ns 8.2 ns 8.0 ns

no_std Support

This crate provides limited support for no_std environments. In this mode Arc::to_local() and Weak::upgrade_local() only succeed if no Rc exists on any thread, as threads cannot be reliably identified without std.

To enable no_std mode, disable the default enabled std feature in Cargo.toml. A global allocator is required.

Supported Rust versions

The minimum supported Rust toolchain version is Rust 1.51.0.

The minimum supported Rust toolchain version for no_std support is Rust 1.56.0.

Stability

This crate follows semantic versioning with the additional promise that below 1.0.0 backwards-incompatible changes will not be introduced with only a patch-level version number change.

License

Licensed under Mozilla Public License, Version 2.0 (LICENSE or https://www.mozilla.org/en-US/MPL/2.0/).

Contribution

Unless you explicitly state otherwise, any contribution intentionally submitted for inclusion in the work by you, shall be licensed as above including compatibility with secondary licenses, as defined by the MPL.

No runtime deps