Решения проблем производительности, вызванных большим размером enum

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. Вы можете пойти дальше, объединив все поля в новую структуру и поместив ее в бокс.