gpt4 book ai didi

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

转载 作者:行者123 更新时间:2023-11-29 08:25:01 25 4
gpt4 key购买 nike

我正在尝试使用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,
},
}

playground

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

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

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

playground

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

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

最佳答案

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

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。您可以进一步将所有字段组合到一个新的结构中并将其装箱。

关于rust - 枚举变体大小过大导致的性能问题的解决方案,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/51200405/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com