enum变体过大导致性能问题的解决方案 [英] Solutions to performance issues caused by large variant size of enum

问题描述

我正在尝试使用 Node 表示来构建树状数据结构:

I am trying to build a tree-like data structure using the Node representation:

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

playground

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

The RelaxedBranch variant of the enum will be used rarely, sometimes not at all. Since the size of enums in Rust is defined by the size of the largest variant, RelaxedBranch increases overall the memory footprint of Node drastically. The large size of this enum causes a 20% performance hit, which is not acceptable in my case.

作为枚举的替代方案，我决定尝试使用 trait 对象:

As an alternative to enums, I have decided to try trait objects:

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

游乐场

我很快发现了一种叫做 trait 对象安全的东西 :) 这不允许用于 trait 对象的 trait 返回 Self 类型的对象，这是我的情况，由于从 继承克隆.

I have quickly discovered something called trait object safety :) This doesn't allow traits used for trait objects to return objects of the Self type, which is my case due to inheritance from Clone.

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

How can I represent a tree node without having the overhead of enums?

推荐答案

这里不需要 trait 对象，因为你不需要它们提供的无限多态性.

You don't need trait objects here because you don't need the unbounded polymorphism they provide.

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.您可以通过将所有字段组合成一个新结构并对其进行装箱来进一步.

Reduces the size of Node<()> from 784 to 272. You could go further by combining all the fields into a new struct and boxing that.

这篇关于enum变体过大导致性能问题的解决方案的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！