枚举变体大小过大导致的性能问题的解决方案

Question

我正在尝试使用以下表示构建树状数据结构Node：

use std::cmp::Ordering;
use std::fmt::Debug;
use std::sync::Arc;

const BRANCH_FACTOR: usize = 32;

#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord)]
enum Node<T> {
    Branch {
        children: [Option<Arc<Node<T>>>; BRANCH_FACTOR],
        len: usize,
    },
    RelaxedBranch {
        children: [Option<Arc<Node<T>>>; BRANCH_FACTOR],
        sizes: [Option<usize>; BRANCH_FACTOR],
        len: usize,
    },
    Leaf {
        elements: [Option<T>; BRANCH_FACTOR],
        len: usize,
    },
}

操场

枚举的变RelaxedBranch体很少使用，有时根本不使用。由于 Rust 中枚举的大小是由最大变体的大小定义的，因此RelaxedBranch总体上显着增加了内存占用Node。此枚举的较大尺寸会导致 20% 的性能下降，这在我的情况下是不可接受的。

作为枚举的替代方案，我决定尝试特征对象：

use std::cmp::Ordering;
use std::fmt::Debug;
use std::sync::Arc;

const BRANCH_FACTOR: usize = 32;

trait Node<T>: Debug + Clone + PartialEq + Eq + PartialOrd + Ord {}

#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord)]
struct Branch<T> {
    children: [Option<Arc<Node<T>>>; BRANCH_FACTOR],
    len: usize,
}

#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord)]
struct RelaxedBranch<T> {
    children: [Option<Arc<Node<T>>>; BRANCH_FACTOR],
    len: usize,
}

#[derive(Debug, Clone, PartialEq, Eq, PartialOrd, Ord)]
struct Leaf<T> {
    elements: [Option<T>; BRANCH_FACTOR],
    len: usize,
}

impl<T> Node<T> for Branch<T> {}
impl<T> Node<T> for RelaxedBranch<T> {}
impl<T> Node<T> for Leaf<T> {}

操场

我很快发现了一种称为特征对象安全性的东西:)这不允许用于特征对象的特征返回该Self类型的对象，这是我的情况，因为继承自Clone.

如何在没有枚举开销的情况下表示树节点？

Answer 1

您在这里不需要特征对象，因为您不需要它们提供的无限多态性。

Clippy告诉你该怎么做：

warning: large size difference between variants
  --> src/main.rs:13:5
   |
13 | /     RelaxedBranch {
14 | |         children: [Option<Arc<Node<T>>>; BRANCH_FACTOR],
15 | |         sizes: [Option<usize>; BRANCH_FACTOR],
16 | |         len: usize,
17 | |     },
   | |_____^
   |
   = note: #[warn(large_enum_variant)] on by default
help: consider boxing the large fields to reduce the total size of the enum
  --> src/main.rs:13:5
   |
13 | /     RelaxedBranch {
14 | |         children: [Option<Arc<Node<T>>>; BRANCH_FACTOR],
15 | |         sizes: [Option<usize>; BRANCH_FACTOR],
16 | |         len: usize,
17 | |     },
   | |_____^
   = help: for further information visit https://rust-lang-nursery.github.io/rust-clippy/v0.0.211/index.html#large_enum_variant

切换到

RelaxedBranch {
    children: Box<[Option<Arc<Node<T>>>; BRANCH_FACTOR]>,
    sizes: Box<[Option<usize>; BRANCH_FACTOR]>,
    len: usize,
},

将大小Node<()>从 784 减少到 272。您可以进一步将所有字段组合到一个新的结构中并将其装箱。