#cow #generic #ref #borrow #generics

supercow

一种泛型方法,用于接受类似引用的通用值,而无需泛化泛型

1 个不稳定版本

使用旧的 Rust 2015

0.1.0 2016年12月15日

#2882Rust 模式

Download history 1191/week @ 2023-11-27 1298/week @ 2023-12-04 1319/week @ 2023-12-11 1156/week @ 2023-12-18 895/week @ 2023-12-25 988/week @ 2024-01-01 1352/week @ 2024-01-08 1700/week @ 2024-01-15 1577/week @ 2024-01-22 1578/week @ 2024-01-29 1725/week @ 2024-02-05 1413/week @ 2024-02-12 1289/week @ 2024-02-19 1516/week @ 2024-02-26 1749/week @ 2024-03-04 966/week @ 2024-03-11

5,689 每月下载量
127 包中使用(直接使用3个)

MIT/Apache

110KB
1.5K SLoC

Supercow

Supercow 是一个灵活且低开销的通用引用,允许透明地使用拥有或借用值,以及类似 Arc 的共享所有权类型。

更多信息可以在文档中找到。

状态

实验性。这个包内部测试得相当好,但还没有得到很多实际使用。

贡献

除非您明确声明,否则任何有意提交以包含在您的工作中的贡献,根据 Apache-2.0 许可证定义,应按上述方式双许可,而不附加任何额外条款或条件。


lib.rs:

Supercow 是增强版的 Cow

Supercow 提供了一种机制,使得 API 可以接受或返回非常通用的引用,同时对于不涉及重量级引用的使用保持非常低的开销(例如,Arc)。尽管在结构上与 Cow 类似(并且以它的名字命名),但 Supercow 不需要容器具有 CloneToOwned,除非操作本质上依赖于其中之一。

Supercow 允许您

  • 返回运行时决定所有权的值;

  • 编写允许客户端代码按其意愿管理其资源的 API;

  • 执行高效的写时复制和数据共享;

  • 在绝对必要时才进行克隆,即使必要的时间点是通过动态确定的。

快速入门

简单类型

在许多情况下,您可以认为 Supercow 只有一个生命周期参数和一个类型参数,对应于不可变引用的生存期和类型,即 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);

拥有/借用类型

Supercow 可以有不同的拥有和借用类型,例如 Stringstr。在这种情况下,这两个是独立的类型参数,拥有类型参数先写。(由于 Supercow 不要求包含的值是 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");

在API中接受 Supercow

如果您想创建一个接受 Supercow 值的API,建议的方法是接受任何是 Into<Supercow<YourType>> 的类型,这允许接受裸有的拥有类型和拥有值的引用。

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)));
}

选择正确的变体

Supercow 在内部存储和管理数据的方式上非常灵活。它提供了四种默认变体:SupercowNonSyncSupercowInlineSupercowInlineNonSyncSupercow。以下是关于权衡的快速参考

变体 Send+Sync? Rc? 大小 初始化 Deref
(默认) 非常快
非同步 非常快
内联
内联非同步

"初始化"以上特指使用拥有值或共享引用进行初始化。使用平凡引用构建的 Supercow 总是构建得非常快。

NonSync 变体与默认变体的唯一区别在于,默认情况下要求共享指针类型(例如,Arc)是 SendSync(因此禁止使用 Rc),而 NonSync 则不要求,因此允许使用 Rc。请注意,默认的 Send + Sync 要求的一个副作用是,当使用 Arc 作为共享引用类型时,BORROWED 的类型也需要是 SendSync;如果不是,请使用 NonSyncSupercow

默认情况下,Supercow 将任何拥有值或共享引用装箱。这使得 Deref 实现更快,因为它不需要考虑内部指针,但更重要的是,这意味着 Supercow 不需要为拥有值和共享值预留空间,因此默认的 Supercow 只比裸引用宽一个指针。

装箱值的一个明显问题是,它使得构建Supercow的速度变慢,因为必须为分配支付代价。如果您想避免分配,可以使用Inline变体,它将值内联存储在Supercow中。(注意,如果您想完全消除分配,您还需要调整默认具有自己的BoxSHARED类型。)请注意,这当然会使Supercow变得更大;如果您创建了一个包含相互引用的InlineSupercow的层次结构,则需要特别小心,因为每个都将为上面的整个树提供内联空间。

选择装箱值的原因是它通常更容易使用,不太可能引起令人困惑的问题,并且在许多情况下分配不会影响性能。

  • 在两种选择中,使用借用的引用创建Supercow不会产生分配。实际上,装箱选项将会稍微快一些,因为它不需要初始化太多内存,并且由于体积较小,因此具有更好的局部性。

  • 包含的值通常构建成本很高,否则就没有必要在可能的情况下将其作为引用传递。在这些情况下,额外的分配可能只会对性能产生轻微的影响。

  • 过度使用装箱值会导致一个相对较容易识别的“均匀的慢速”,并导致相对于过度使用呈线性性能下降。过度使用InlineSupercow最多会导致线性内存膨胀,但如果InlineSupercow引用包含其他InlineSupercow的结构,结果甚至可以是指数级膨胀。这最坏的情况是难以追踪的问题;在最坏的情况下,它可能导致完全不可见的栈溢出。

用例

更灵活的Copy-on-Write

std::borrow::Cow只支持两种所有权模式:要么完全拥有值,要么只借用它。RcArcmake_mut()方法,它允许完全所有权或共享所有权。Supercow支持所有三种:拥有、共享和借用。

更灵活的Copy-if-Needed

Cowstd中的主要用途之一是在像OsStr::to_string_lossy()这样的函数中,它如果可能,返回一个指向自身的借用视图,如果需要更改某些内容,则返回一个拥有字符串。如果调用者不打算进行自己的写入,这更像是一个“按需复制”结构,而要求包含的值是ToOwned的事实限制了它只能用于可克隆的事物。

Supercow只要求ToOwned,如果调用者实际上打算调用需要克隆借用值的函数,因此它可以适用于即使是不可克隆的类型。

解决棘手的生命周期问题

这是Supercow最初设计的用例。

比如说,您有一个具有某种层次结构的重资源API,例如本地数据库的句柄及其中的表。

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
  }
}

我们可以很容易地使用它


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
}

也就是说,直到我们想在结构中持有数据库和表。

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

这里有几种选择

  • 将API修改为使用Arc或类似的类型。这样做是有效的,但会增加不需要此功能的客户端的负担,并且还会从所有人那里剥夺了静态知道是否可以调用db.close()的能力。

  • 迫使客户端求助于不安全的方法,例如OwningHandle。这不会牺牲性能,并且允许基于堆栈的客户端能够轻松调用db.close(),但会使其他客户端变得更加困难。

  • 采用Borrow类型参数。这可以工作且无开销,但会导致API和客户端代码中泛型的泛滥,当层次结构有多个此类深度时,尤其成问题。

  • 使用Supercow以获得两全其美的效果。

我们可以这样适应和使用API

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
}

转换

为了促进客户端API的设计,Supercow可以通过From/Into从多种类型转换。遗憾的是,由于特例规则,这还不适用于所有可能希望的情况。目前可用的转换有

  • OWNED类型转换为拥有的Supercow。这没有限制。

  • OWNED类型的引用。对其他BORROWED类型的引用目前不可转换;需要Supercow::borrowed()来显式构建Supercow

  • 对于Rc<OWNED>Arc<OWNED>,其中OWNEDBORROWED是相同的类型,并且当RcArc可以通过supercow::ext::SharedFrom转换为SHARED时,用于构建Supercow。如果OWNEDBORROWED是不同类型,需要使用Supercow::shared()来显式构建Supercow

高级

变异性

Supercow在其生命周期和所有类型参数上是一致的,除了SHARED是不变的。默认的SHARED类型对于SupercowNonSyncSupercow都是使用'static生命周期,所以简单的Supercow通常是协变的。

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;
}

SyncSend

如果它包含的类型,包括共享引用类型,都是SyncSend,则SupercowSyncSend

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);
}

共享引用类型

第三种类型参数类型用于指定 Supercow 的共享引用类型。

默认值是 Box<DefaultFeatures<'static>>,这是一个描述共享引用类型必须拥有的特征的同时允许任何此类引用无需泛型类型参数即可使用的封装特质对象。

NonSyncFeatures 中可以找到另一种功能集,它也可以通过 NonSyncSupercow 类型别名(这也会使其成为 'static)使用。您可以使用 supercow_features! 创建这种风格的自定义特质。

使用非 'static 共享引用类型是合法的。实际上,Supercow<'a> 的原始设计使用了 DefaultFeatures<'a>。然而,非 'static 生命周期使得系统更难以使用,并且如果与 'a 上的 Supercow 混合,会使结构成为生命周期不变,这使得将其视为引用变得非常困难。

当然,封装共享引用并将其放在特质对象后面都会增加开销。如果您愿意,可以将第三参数用作真正的引用类型,只要您愿意放弃封装提供的灵活性。例如,

use std::rc::Rc;

use supercow::Supercow;

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

请注意,如果您有一个自定义引用类型,您可能需要提供一个身份 supercow::ext::SharedFrom 实现。

存储类型

在拥有或共享模式下,一个 Supercow 需要一个地方来存储其自身的 OWNEDSHARED 值。这可以通过第四个类型参数(STORAGE)和 OwnedStorage 特质进行自定义。此包提供了两种策略

  • BoxedStorage 将一切放在 Box 后面。这有一个优点,即 Supercow 结构体只比一个基本引用多一个指针,从而实现了更快的 Deref。明显的缺点是在构造时需要支付分配成本。这是 SupercowNonSyncSupercow 的默认设置。

  • InlineStorage 使用一个 enum 来在 Supercow 中内联存储值,因此不产生任何分配,但使 Supercow 本身更大。这可以通过 InlineSupercowInlineNonSyncSupercow 类型轻松实现。

如果您有需要,可以定义自定义存储类型,但请注意,该特质相当不安全且有些微妙。

PTR 类型

使用 PTR 类型来合并 SupercowPhantomcow 的实现;在这里,如果使用 *const BORROWED() 以外的任何类型,很可能没有或几乎没有用途。

性能考虑

构建成本

由于它将某些关于所有权的决策从编译时转移到运行时,Supercow 显然没有直接使用拥有值或直接使用引用那样快。

使用普通引用构建任何类型的 Supercow 非常快,除了设置引用本身外,只需进行一点内部内存初始化。

默认的 Supercow 类型将拥有类型装箱,并将共享类型双重装箱。这显然在那些情况下占主导地位的建设成本。

InlineSupercow 消除了一个盒层。这意味着构建一个拥有实例仅仅是拥有结构的移动加上公共引用初始化。共享值在默认情况下仍然需要一级装箱,以及某些操作上的虚函数分发;如上所述,此属性也可以通过使用自定义的 SHARED 类型来处理。

销毁成本

销毁一个 Supercow 的成本与创建它的成本大致相同。

Deref 成本

对于默认的 Supercow 类型,Deref 与解引用一个 &&BORROWED 完全相同。

对于 InlineSupercow,实现略慢,与 std::borrow::Cow 相当,但内存访问较少。

在所有情况下,Deref 实现不依赖于 Supercow 的所有权模式,因此不受共享引用类型的影响,最重要的是,即使在默认的装箱共享引用类型下也不会调用虚拟函数。然而,它的工作方式可能会阻止在特定情况下应用 LLVM 优化。

对于那些想要具体信息的人,函数

// 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
}

在 AMD64 上使用 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

相同的代码在 ARM v7l 和 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}

如果在上面的代码中使用默认的 Supercow 而不是 InlineSupercow,函数实际上编译成与接受两个 &u32 参数相同的结果。(这部分是因为优化消除了间接引用级别;如果优化器做得不那么多,它就相当于接受两个 &&u32 参数。)

to_mut 成本

获取一个 Ref 的成本比 Deref 高得多,因为它必须检查 Supercow 的所有权模式,并可能将其移动到拥有模式。这包括在默认的 Supercow 共享引用类型中使用共享模式时的装箱共享引用的虚拟调用。

释放可变引用也有成本,但相对较小。

内存使用

默认的 Supercow 在 Rust 1.13.0 及以后的版本中只比普通引用多一个指针。早期的 Rust 版本由于销毁标志而有一个额外的词。

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>>());

当然,当使用拥有或共享 Supercow 时,你还需要为堆空间付费。

与普通引用相比,InlineSupercow 可能相当大。你需要特别小心,确保你引用的结构本身不包含 InlineSupercow,否则你可能会得到二次方大小甚至指数级大小的结构。

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>());

其他注意事项

使用 Supercow 不会给你的应用程序带来类似 apt-get 风格的超级牛力量。

无运行时依赖