Crate hybrid_rc

Thread-safe hybrid reference counting pointers

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 type HybridRc<T, State> provides thread-safe shared ownership of a value of type T allocated on the heap, just like std::sync::Arc<T> does. The main difference is that one thread at a time can use non-atomic reference counting for better performance. That means that HybridRc is especially suited for workloads where one thread accesses the shared value significantly more often than others.

There a two variants of HybridRc:

• 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. The thread holding Rcs to a value is called the “owner thread”. Once all Rcs are dropped, the shared value becomes ownerless again.

HybridRc is designed as a drop-in replacement for std::sync::Arc and std::rc::Rc, so except for the conversion functionality outlined above the usage is similar to these and other smart pointers.

Thread Safety

HybridRc uses two separate reference counters - one modified non-atomically and one using atomic operations - and keeps track of a owner thread that is allowed to modify the “local” reference counter. This means that it is thread-safe, while one thread is exempted from the disadvantage of atomic operations being more expensive than ordinary memory accesses.

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.

[dependencies]
hybrid-rc = { version = "…", default-features = false }

Examples

Multiple threads need a reference to a shared value while one thread needs to clone references to the value significantly more often than the others.

use hybrid_rc::{Rc, Arc};
use std::thread;
use std::sync::mpsc::channel;

let local = Rc::new(SomeComplexType::new());
let (sender, receiver) = channel();

// Spawn of threads for multiple expensive computations
for i in 1..=4 {
	let sender = sender.clone();
	let shared = Rc::to_shared(&local);
	thread::spawn(move || {
		sender.send(expensive_computation(shared, i));
	});
}

// Do something that needs single-thread reference counting
for i in 1..=1000 {
	do_something(local.clone(), i);
}

// Collect expensive computation results
for i in 1..=4 {
	println!("{:?}", receiver.recv().unwrap());
}

A library wants to give library consumers flexibility for multithreading but also internally have the performance of std::rc::Rc for e.g. a complex tree structure that is mutated on the main thread.

use hybrid_rc::Rc;
use std::thread;

let reference = get_local_hybridrc_from_some_library();
let shared = Rc::to_shared(&reference);

// do the work in another thread
let worker = thread::spawn(move || {
	do_something(&*shared);
});

// Do something useful with the library

worker.join()?;

Modules

state

Marker types for the states of a HybridRc

Structs

HybridRc

A hybrid reference-counting pointer.

Weak

Weak<T> represents a non-owning reference to a value managed by a HybridRc<T, _>. The value is accessed by calling upgrade() or upgrade_local() on Weak.

Enums

UpgradeError

An enumeration of possible errors when upgrading a Weak.

Type Definitions

Arc

Type alias for a shared reference counting pointer.

Rc

Type alias for a local reference counting pointer.