Welcome to OStack Knowledge Sharing Community for programmer and developer-Open, Learning and Share
Welcome To Ask or Share your Answers For Others

Categories

0 votes
1.1k views
in Technique[技术] by (71.8m points)

rust - Solutions to performance issues caused by large variant size of enum

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

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.

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

playground

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?

See Question&Answers more detail:os

与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome To Ask or Share your Answers For Others

1 Answer

0 votes
by (71.8m points)

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

Clippy tells you what to do:

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

Switching to

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

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.


与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…
Welcome to OStack Knowledge Sharing Community for programmer and developer-Open, Learning and Share
Click Here to Ask a Question

...