Supercow

Supercow is a versatile and low-overhead generalised reference, allowing to transparently work with owned or borrowed values, as well as shared-ownership types like Arc.

More information can be found in the documentation.

Status

Experimental. This crate is fairly well internally tested, but has not yet seen much serious use.

Contribution

Unless you explicitly state otherwise, any contribution intentionally submitted for inclusion in the work by you, as defined in the Apache-2.0 license, shall be dual licensed as above, without any additional terms or conditions.

lib.rs:

Supercow is Cow on steroids.

Supercow provides a mechanism for making APIs that accept or return very general references while maintaining very low overhead for usages not involving heavy-weight references (e.g, Arc). Though nominally similar to Cow in structure (and being named after it), Supercow does not require the containee to be Clone or ToOwned unless operations inherently depending on either are invoked.

Supercow allows you to

• Return values with ownership semantics decided at run-time;

• Write APIs that allow client code to manage its resources however it wants;

• Perform efficient copy-on-write and data sharing;

• Avoid cloning until absolutely necessary, even if the point at which it becomes necessary is determined dynamically.

Quick Start

Simple Types

In many cases, you can think of a Supercow as having only one lifetime parameter and one type parameter, corresponding to the lifetime and type of an immutable reference, i.e., Supercow<'a, Type> ⇒ &'a Type.

extern crate supercow;

use std::sync::Arc;
use supercow::Supercow;

// This takes a `Supercow`, so it can accept owned, borrowed, or shared
// values with the same API. The calls to it are annotated below.
//
// Normally a function like this would elide the lifetime and/or use an
// `Into` conversion, but here it is written out for clarity.
fn assert_is_forty_two<'a>(s: Supercow<'a, u32>) {
  // `Supercow` can be dereferenced just like a normal reference.
  assert_eq!(42, *s);
}

// Declare some data we want to reference.
let forty_two = 42u32;
// Make a Supercow referencing the above.
let mut a = Supercow::borrowed(&forty_two);
// It dereferences to the value of `forty_two`.
assert_is_forty_two(a.clone());             // borrowed
// And we can see that it actually still *points* to forty_two as well.
assert_eq!(&forty_two as *const u32, &*a as *const u32);

// Clone `a` so that `b` also points to `forty_two`.
let mut b = a.clone();
assert_is_forty_two(b.clone());             // borrowed
assert_eq!(&forty_two as *const u32, &*b as *const u32);

// `to_mut()` can be used to mutate `a` and `b` independently, taking
// ownership as needed.
*a.to_mut() += 2;
// Our immutable variable hasn't been changed...
assert_eq!(42, forty_two);
// ...but `a` now stores the new value...
assert_eq!(44, *a);
// ...and `b` still points to the unmodified variable.
assert_eq!(42, *b);
assert_eq!(&forty_two as *const u32, &*b as *const u32);

// And now we modify `b` as well, which as before affects nothing else.
*b.to_mut() = 56;
assert_eq!(44, *a);
assert_eq!(56, *b);
assert_eq!(42, forty_two);

// We can call `assert_is_forty_two` with an owned value as well.
assert_is_forty_two(Supercow::owned(42));   // owned

// We can also use `Arc` transparently.
let mut c = Supercow::shared(Arc::new(42));
assert_is_forty_two(c.clone());             // shared
*c.to_mut() += 1;
assert_eq!(43, *c);

Owned/Borrowed Types

Supercow can have different owned and borrowed types, for example String and str. In this case, the two are separate type parameters, with the owned one written first. (Both need to be listed explicitly since Supercow does not require the contained value to be ToOwned.)

extern crate supercow;

use std::sync::Arc;
use supercow::Supercow;

let hello: Supercow<String, str> = Supercow::borrowed("hello");
let mut hello_world = hello.clone();
hello_world.to_mut().push_str(" world");

assert_eq!(hello, "hello");
assert_eq!(hello_world, "hello world");

Accepting Supercow in an API

If you want to make an API taking Supercow values, the recommended approach is to accept anything that is Into<Supercow<YourType>>, which allows bare owned types and references to owned values to be accepted as well.

use std::sync::Arc;
use supercow::Supercow;

fn some_api_function<'a, T : Into<Supercow<'a,u32>>>
  (t: T) -> Supercow<'a,u32>
{
  let mut x = t.into();
  *x.to_mut() *= 2;
  x
}

fn main() {
  assert_eq!(42, *some_api_function(21));
  let twenty_one = 21;
  assert_eq!(42, *some_api_function(&twenty_one));
  assert_eq!(42, *some_api_function(Arc::new(21)));
}

Choosing the right variant

Supercow is extremely flexible as to how it internally stores and manages data. There are four variants provided by default: Supercow, NonSyncSupercow, InlineSupercow, and InlineNonSyncSupercow. Here is a quick reference on the trade-offs:

"Init" above specifically refers to initialisation with an owned value or shared reference. Supercows constructed with mundane references always construct extremely quickly.

The only difference between the NonSync variant and the default is that the default is to require the shared pointer type (e.g., Arc) to be Send and Sync (which thus prohibits using Rc), whereas NonSync does not and so allows Rc. Note that a side-effect of the default Send + Sync requirement is that the type of BORROWED also needs to be Send and Sync when using Arc as the shared reference type; if it is not Send and Sync, use NonSyncSupercow instead.

By default, Supercow boxes any owned value or shared reference. This makes the Deref implementation faster since it does not need to account for internal pointers, but more importantly, means that the Supercow does not need to reserve space for the owned and shared values, so the default Supercow is only one pointer wider than a bare reference.

The obvious problem with boxing values is that it makes construction of the Supercow slower, as one must pay for an allocation. If you want to avoid the allocation, you can use the Inline variants instead, which store the values inline inside the Supercow. (Note that if you are looking to eliminate allocation entirely, you will also need to tinker with the SHARED type, which by default has its own Box as well.) Note that this of course makes the Supercow much bigger; be particularly careful if you create a hierarchy of things containing InlineSupercows referencing each other, as each would effectively have space for the entire tree above it inline.

The default to box values was chosen on the grounds that it is generally easier to use, less likely to cause confusing problems, and in many cases the allocation doesn't affect performance:

• In either choice, creating a Supercow with a borrowed reference incurs no allocation. The boxed option will actually be slightly faster since it does not need to initialise as much memory and results in better locality due to being smaller.

• The value contained usually is reasonably expensive to construct anyway, or else there would be less incentive to pass it around as a reference when possible. In these cases, the extra allocation likely is a minor impact on performance.

• Overuse of boxed values results in a "uniform slowness" that can be identified reasonably easily, and results in a linear performance degradation relative to overuse. Overuse of InlineSupercows at best results in linear memory bloat, but if InlineSupercows reference structures containing other InlineSupercows, the result can even be exponential bloat to the structures. At best, this is a harder problem to track down; at worst, it can result in entirely non-obvious stack overflows.

Use Cases

More flexible Copy-on-Write

std::borrow::Cow only supports two modes of ownership: You either fully own the value, or only borrow it. Rc and Arc have the make_mut() method, which allows either total ownership or shared ownership. Supercow supports all three: owned, shared, and borrowed.

More flexible Copy-if-Needed

A major use of Cow in std is found on functions like OsStr::to_string_lossy(), which returns a borrowed view into itself if possible, or an owned string if it needed to change something. If the caller does not intend to do its own writing, this is more a "copy if needed" structure, and the fact that it requires the contained value to be ToOwned limits it to things that can be cloned.

Supercow only requires ToOwned if the caller actually intends to invoke functionality which requires cloning a borrowed value, so it can fit this use-case even for non-cloneable types.

Working around awkward lifetimes

This is the original case for which Supercow was designed.

Say you have an API with a sort of hierarchical structure of heavyweight resources, for example handles to a local database and tables within it. A natural representation may be to make the table handle hold a reference to the database handle.

struct Database;
impl Database {
  fn new() -> Self {
    // Computation...
    Database
  }
  fn close(self) -> bool {
    // E.g., it returns an error on failure or something
    true
  }
}
impl Drop for Database {
  fn drop(&mut self) {
    println!("Dropping database");
  }
}
struct Table<'a>(&'a Database);
impl<'a> Table<'a> {
  fn new(db: &'a Database) -> Self {
    // Computation...
    Table(db)
  }
}
impl<'a> Drop for Table<'a> {
  fn drop(&mut self) {
    println!("Dropping table");
    // Notify `self.db` about this
  }
}

We can use this quite easily:

fn main() {
  let db = Database::new();
  {
    let table1 = Table::new(&db);
    let table2 = Table::new(&db);
    do_stuff(&table1);
    // Etc
  }
  assert!(db.close());
}

fn do_stuff(table: &Table) {
  // Stuff
}

That is, until we want to hold the database and the tables in a struct.

struct Resources {
  db: Database,
  table: Table<'uhhh>, // Uh, what is the lifetime here?
}

There are several options here:

• Change the API to use Arcs or similar. This works, but adds overhead for clients that don't need it, and additionally removes from everybody the ability to statically know whether db.close() can be called.

• Force clients to resort to unsafety, such as OwningHandle. This sacrifices no performance and allows the stack-based client usage to be able to call db.close() easily, but makes things much more difficult for other clients.

• Take a Borrow type parameter. This works and is zero-overhead, but results in a proliferation of generics throughout the API and client code, and becomes especially problematic when the hierarchy is multiple such levels deep.

• Use Supercow to get the best of both worlds.

We can adapt and use the API like so:

use std::sync::Arc;

use supercow::Supercow;

struct Database;
impl Database {
  fn new() -> Self {
    // Computation...
    Database
  }
  fn close(self) -> bool {
    // E.g., it returns an error on failure or something
    true
  }
}
impl Drop for Database {
  fn drop(&mut self) {
    println!("Dropping database");
  }
}
struct Table<'a>(Supercow<'a, Database>);
impl<'a> Table<'a> {
  fn new<T : Into<Supercow<'a, Database>>>(db: T) -> Self {
    // Computation...
    Table(db.into())
  }
}
impl<'a> Drop for Table<'a> {
  fn drop(&mut self) {
    println!("Dropping table");
    // Notify `self.db` about this
  }
}

// The original stack-based code, unmodified

fn on_stack() {
  let db = Database::new();
  {
    let table1 = Table::new(&db);
    let table2 = Table::new(&db);
    do_stuff(&table1);
    // Etc
  }
  assert!(db.close());
}

// If we only wanted one Table and didn't care about ever getting the
// Database back, we don't even need a reference.
fn by_value() {
  let db = Database::new();
  let table = Table::new(db);
  do_stuff(&table);
}

// And we can declare our holds-everything struct by using `Arc`s to deal
// with ownership.
struct Resources {
  db: Arc<Database>,
  table: Table<'static>,
}
impl Resources {
  fn new() -> Self {
    let db = Arc::new(Database::new());
    let table = Table::new(db.clone());
    Resources { db: db, table: table }
  }

  fn close(self) -> bool {
    drop(self.table);
    Arc::try_unwrap(self.db).ok().unwrap().close()
  }
}

fn with_struct() {
  let res = Resources::new();
  do_stuff(&res.table);
  assert!(res.close());
}

fn do_stuff(table: &Table) {
  // Stuff
}

Conversions

To facilitate client API designs, Supercow converts (via From/Into) from a number of things. Unfortunately, due to trait coherence rules, this does not yet apply in all cases where one might hope. The currently available conversions are:

• The OWNED type into an owned Supercow. This applies without restriction.

• A reference to the OWNED type. References to a different BORROWED type are currently not convertible; Supercow::borrowed() will be needed to construct the Supercow explicitly.

• Rc<OWNED> and Arc<OWNED> for Supercows where OWNED and BORROWED are the exact same type, and where the Rc or Arc can be converted into SHARED via supercow::ext::SharedFrom. If OWNED and BORROWED are different types, Supercow::shared() will be needed to construct the Supercow explicitly.

Advanced

Variance

Supercow is covariant on its lifetime and all its type parameters, except for SHARED which is invariant. The default SHARED type for both Supercow and NonSyncSupercow uses the 'static lifetime, so simple Supercows are in general covariant.

use std::rc::Rc;

use supercow::Supercow;

fn assert_covariance<'a, 'b: 'a>(
  imm: Supercow<'b, u32>,
  bor: &'b Supercow<'b, u32>)
{
  let _imm_a: Supercow<'a, u32> = imm;
  let _bor_aa: &'a Supercow<'a, u32> = bor;
  let _bor_ab: &'a Supercow<'b, u32> = bor;
  // Invalid, since the external `&'b` reference is declared to live longer
  // than the internal `&'a` reference.
  // let _bor_ba: &'b Supercow<'a, u32> = bor;
}

Sync and Send

A Supercow is Sync and Send iff the types it contains, including the shared reference type, are.

use supercow::Supercow;

fn assert_sync_and_send<T : Sync + Send>(_: T) { }
fn main() {
  let s: Supercow<u32> = Supercow::owned(42);
  assert_sync_and_send(s);
}

Shared Reference Type

The third type parameter type to Supercow specifies the shared reference type.

The default is Box<DefaultFeatures<'static>>, which is a boxed trait object describing the features a shared reference type must have while allowing any such reference to be used without needing a generic type argument.

An alternate feature set can be found in NonSyncFeatures, which is also usable through the NonSyncSupercow typedef (which also makes it 'static). You can create custom feature traits in this style with supercow_features!.

It is perfectly legal to use a non-'static shared reference type. In fact, the original design for Supercow<'a> used DefaultFeatures<'a>. However, a non-'static lifetime makes the system harder to use, and if entangled with 'a on Supercow, makes the structure lifetime-invariant, which makes it much harder to treat as a reference.

Boxing the shared reference and putting it behind a trait object both add overhead, of course. If you wish, you can use a real reference type in the third parameter as long as you are OK with losing the flexibility the boxing would provide. For example,

use std::rc::Rc;

use supercow::Supercow;

let x: Supercow<u32, u32, Rc<u32>> = Supercow::shared(Rc::new(42u32));
println!("{}", *x);

Note that you may need to provide an identity supercow::ext::SharedFrom implementation if you have a custom reference type.

Storage Type

When in owned or shared mode, a Supercow needs someplace to store the OWNED or SHARED value itself. This can be customised with the fourth type parameter (STORAGE), and the OwnedStorage trait. Two strategies are provided by this crate:

• BoxedStorage puts everything behind Boxes. This has the advantage that the Supercow structure is only one pointer wider than a basic reference, and results in a faster Deref. The obvious drawback is that you pay for allocations on construction. This is the default with Supercow and NonSyncSupercow.

• InlineStorage uses an enum to store the values inline in the Supercow, thus incurring no allocation, but making the Supercow itself bigger. This is easily available via the InlineSupercow and InlineNonSyncSupercow types.

If you find some need, you can define custom storage types, though note that the trait is quite unsafe and somewhat subtle.

PTR type

The PTR type is used to consolidate the implementations of Supercow and Phantomcow; there is likely little, if any, use for ever using anything other than *const BORROWED or () here.

Performance Considerations

Construction Cost

Since it inherently moves certain decisions about ownership from compile-time to run-time, Supercow is obviously not as fast as using an owned value directly or a reference directly.

Constructing any kind of Supercow with a normal reference is very fast, only requiring a bit of internal memory initialisation besides setting the reference itself.

The default Supercow type boxes the owned type and double-boxes the shared type. This obviously dominates construction cost in those cases.

InlineSupercow eliminates one box layer. This means that constructing an owned instance is simply a move of the owned structure plus the common reference initialisation. Shared values still by default require one boxing level as well as virtual dispatch on certain operations; as described above, this property too can be dealt with by using a custom SHARED type.

Destruction Cost

Destroying a Supercow is roughly the same proportional cost of creating it.

Deref Cost

For the default Supercow type, the Deref is exactly equivalent to dereferencing an &&BORROWED.

For InlineSupercow, the implementation is a bit slower, comparable to std::borrow::Cow but with fewer memory accesses..

In all cases, the Deref implementation is not dependent on the ownership mode of the Supercow, and so is not affected by the shared reference type, most importantly, making no virtual function calls even under the default boxed shared reference type. However, the way it works could prevent LLVM optimisations from applying in particular circumstances.

For those wanting specifics, the function

// Substitute Cow with InlineSupercow for the other case.
// This takes references so that the destructor code is not intermingled.
fn add_two(a: &Cow<u32>, b: &Cow<u32>) -> u32 {
  **a + **b
}

results in the following on AMD64 with Rust 1.13.0:

 Cow                                Supercow
 cmp    DWORD PTR [rdi],0x1         mov    rcx,QWORD PTR [rdi]
 lea    rcx,[rdi+0x4]               xor    eax,eax
 cmovne rcx,QWORD PTR [rdi+0x8]     cmp    rcx,0x800
 cmp    DWORD PTR [rsi],0x1         cmovae rdi,rax
 lea    rax,[rsi+0x4]               mov    rdx,QWORD PTR [rsi]
 cmovne rax,QWORD PTR [rsi+0x8]     cmp    rdx,0x800
 mov    eax,DWORD PTR [rax]         cmovb  rax,rsi
 add    eax,DWORD PTR [rcx]         mov    eax,DWORD PTR [rax+rdx]
 ret                                add    eax,DWORD PTR [rdi+rcx]
                                    ret

The same code on ARM v7l and Rust 1.12.1:

 Cow                                Supercow
 push       {fp, lr}                ldr     r2, [r0]
 mov        r2, r0                  ldr     r3, [r1]
 ldr        r3, [r2, #4]!           cmp     r2, #2048
 ldr        ip, [r0]                addcc   r2, r2, r0
 mov        r0, r1                  cmp     r3, #2048
 ldr        lr, [r0, #4]!           addcc   r3, r3, r1
 ldr        r1, [r1]                ldr     r0, [r2]
 cmp        ip, #1                  ldr     r1, [r3]
 moveq      r3, r2                  add     r0, r1, r0
 cmp        r1, #1                  bx      lr
 ldr        r2, [r3]
 moveq      lr, r0
 ldr        r0, [lr]
 add        r0, r0, r2
 pop        {fp, pc}

If the default Supercow is used above instead of InlineSupercow, the function actually compiles to the same thing as one taking two &u32 arguments. (This is partially due to optimisations eliminating one level of indirection; if the optimiser did not do as much, it would be equivalent to taking two &&u32 arguments.)

to_mut Cost

Obtaining a Ref is substantially more expensive than Deref, as it must inspect the ownership mode of the Supercow and possibly move it into the owned mode. This will include a virtual call to the boxed shared reference if in shared mode when using the default Supercow shared reference type.

There is also cost in releasing the mutable reference, though insubstantial in comparison.

Memory Usage

The default Supercow is only one pointer wider than a mundane reference on Rust 1.13.0 and later. Earlier Rust versions have an extra word due to the drop flag.

use std::mem::size_of;

use supercow::Supercow;

// Determine the size of the drop flag including alignment padding.
// On Rust 0.13.0+, `dflag` will be zero.
struct DropFlag(*const ());
impl Drop for DropFlag { fn drop(&mut self) { } }
let dflag = size_of::<DropFlag>() - size_of::<*const ()>();

assert_eq!(size_of::<&'static u32>() + size_of::<*const ()>() + dflag,
           size_of::<Supercow<'static, u32>>());

assert_eq!(size_of::<&'static str>() + size_of::<*const ()>() + dflag,
           size_of::<Supercow<'static, String, str>>());

Of course, you also pay for heap space in this case when using owned or shared Supercows.

InlineSupercow can be quite large in comparison to a normal reference. You need to be particularly careful that structures you reference don't themselves contain InlineSupercows or you can end up with quadratically-sized or even exponentially-sized structures.

use std::mem;

use supercow::InlineSupercow;

// Define our structures
struct Big([u8;1024]);
struct A<'a>(InlineSupercow<'a, Big>);
struct B<'a>(InlineSupercow<'a, A<'a>>);
struct C<'a>(InlineSupercow<'a, B<'a>>);

// Now say an API consumer, etc, decides to use references
let big = Big([0u8;1024]);
let a = A((&big).into());
let b = B((&a).into());
let c = C((&b).into());

// Well, we've now allocated space for four `Big`s on the stack, despite
// only really needing one.
assert!(mem::size_of_val(&big) + mem::size_of_val(&a) +
        mem::size_of_val(&b) + mem::size_of_val(&c) >
        4 * mem::size_of::<Big>());

Other Notes

Using Supercow will not give your application apt-get-style Super Cow Powers.