rust - Rust 中的动态调度替代方案

Question

我正在解析命令字符串并创建由不同类型的节点组成的抽象语法树(AST)。我正在尝试找出一种有效的方法来执行该命令。

此应用对性能极其敏感。它适用于在用户等待时需要处理数百万个项目的查询引擎。

在非 Rust 语言中执行此操作的标准方法是让每个节点类型实现一个公共(public)接口(interface)。然而，要在 Rust 中使用一个特征来做到这一点，你必须使用笨拙的 Box 语法，并且这需要在每次调用时进行动态调度。例如，

trait Node {
    fn get(&mut self) -> u32;
}

struct MyParentNode {
    my_int: u32,
    left: Box<dyn Node>,
    right: Box<dyn Node>,
}

impl Node for MyParentNode {
    fn get(&mut self) -> u32 {
        self.left.get() + self.right.get()
    }
}

struct MyLeafNode {
    my_int: u32,
}

impl Node for MyLeafNode {
    fn get(&mut self) -> u32 {
        self.my_int
    }
}

我看到的基准表明，与调用具体函数相比，动态调度非常慢。

另一种选择是使用枚举作为节点类型，但也好不了多少:

enum NodeEnum {
    Parent(Box<ParentInfo>),
    Leaf(Box<LeafInfo>),
}

impl NodeEnum {
    fn get(&mut self) -> u32 {
        match self {
            NodeEnum::Parent(parent) => parent.get(),
            NodeEnum::Leaf(leaf) => leaf.get(),
        }
    }
}

struct ParentInfo {
    left: NodeEnum,
    right: NodeEnum,
}

impl ParentInfo {
    fn get(&mut self) -> u32 {
        self.left.get() + self.right.get()
    }
}

struct LeafInfo {
    my_int: u32,
}

impl LeafInfo {
    fn get(&mut self) -> u32 {
        self.my_int
    }
}

(上面的代码可能看起来并不糟糕，但在真实的应用程序中，每个节点上会有几十个节点类型和十几个方法，因此有很多对 match 的调用)。

必须有更好的方法。有没有什么方法可以实现这一点，而无需动态调度的开销，或者每次调用 get() 时都必须调用 match ？

函数指针有帮助吗？

Answer 1

请在下面找到一个围绕您的问题的快速而肮脏的示例。

我知道我的计时方式(但是在 Release模式下，并在 cargo flamegraph 的帮助下)不够严格(为此目的存在一些工具)；这给人一种粗粒度的感觉。

测试了两种解决方案。 第一个使用一些动态调度。 第二个使用 enum_dispatch crate为了用一些(自动)match 语句替换虚拟表。 性能有了显着提升(在本例中和在我的计算机上分别为 4.7 秒和 2.0 秒)。

请注意，如果实际用例中的节点执行的操作远多于本示例中的简单添加，则调度成本可能并不显着。 最后，只有对您的实际用例进行计时才能告诉我们所有这些是否有益。

注意:在我的第一个答案中，我考虑了在计时中创建节点，因为我不知道用例。显然，大部分时间都花在分配/释放上，我测试了第三个版本以缓解这种情况。另一方面，如果我们认为节点一次性构建并多次使用(如这个新答案)，那么调度成本就会变得很大。

use enum_dispatch::enum_dispatch;

fn main() {
    let node_count = 200;
    let iter_count = 1_000_000;
    let warmup = iter_count / 100;
    with_dyn(node_count, iter_count, warmup);
    with_enum(node_count, iter_count, warmup);
}
/*
~~~~ with_dyn() ~~~~
4.712342453s
~~~~ with_enum() ~~~~
1.950779271s
*/

//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

trait DynNodeTrait {
    fn get(&self) -> i32;
    fn change(
        &mut self,
        offset: i32,
    );
}

struct ParentDynNode {
    left: Box<dyn DynNodeTrait>,
    right: Box<dyn DynNodeTrait>,
}
impl DynNodeTrait for ParentDynNode {
    fn get(&self) -> i32 {
        self.left.get() + self.right.get()
    }

    fn change(
        &mut self,
        offset: i32,
    ) {
        self.left.change(offset);
        self.right.change(offset);
    }
}

struct LeafDynNode {
    my_int: i32,
}
impl DynNodeTrait for LeafDynNode {
    fn get(&self) -> i32 {
        self.my_int
    }

    fn change(
        &mut self,
        offset: i32,
    ) {
        self.my_int += offset;
    }
}

fn with_dyn(
    node_count: i32,
    iter_count: usize,
    warmup: usize,
) {
    println!("~~~~ with_dyn() ~~~~");
    let r1 = node_count * (node_count + 1) / 2;
    let r2 = r1 + 100 * node_count;
    let mut root: Box<dyn DynNodeTrait> = Box::new(LeafDynNode { my_int: 1 });
    for i in 2..=node_count {
        let leaf = Box::new(LeafDynNode { my_int: i });
        root = Box::new(ParentDynNode {
            left: root,
            right: leaf,
        });
    }
    let mut t0 = std::time::Instant::now();
    for iter in 0..iter_count {
        if iter < warmup {
            t0 = std::time::Instant::now();
        }
        let r = root.get();
        if r != r1 {
            println!("{} != {}", r, r1);
        }
        root.change(100);
        let r = root.get();
        if r != r2 {
            println!("{} != {}", r, r2);
        }
        root.change(-100);
    }
    let t1 = std::time::Instant::now();
    println!("{:?}", t1 - t0);
}

//~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

#[enum_dispatch]
trait EnumNodeTrait {
    fn get(&self) -> i32;
    fn change(
        &mut self,
        offset: i32,
    );
}

#[enum_dispatch(EnumNodeTrait)]
enum EnumNode {
    Parent(ParentEnumNode),
    Leaf(LeafEnumNode),
}

struct ParentEnumNode {
    left: Box<EnumNode>,
    right: Box<EnumNode>,
}
impl EnumNodeTrait for ParentEnumNode {
    fn get(&self) -> i32 {
        self.left.get() + self.right.get()
    }

    fn change(
        &mut self,
        offset: i32,
    ) {
        self.left.change(offset);
        self.right.change(offset);
    }
}

struct LeafEnumNode {
    my_int: i32,
}
impl EnumNodeTrait for LeafEnumNode {
    fn get(&self) -> i32 {
        self.my_int
    }

    fn change(
        &mut self,
        offset: i32,
    ) {
        self.my_int += offset;
    }
}

fn with_enum(
    node_count: i32,
    iter_count: usize,
    warmup: usize,
) {
    println!("~~~~ with_enum() ~~~~");
    let r1 = node_count * (node_count + 1) / 2;
    let r2 = r1 + 100 * node_count;
    let mut root = Box::new(EnumNode::from(LeafEnumNode { my_int: 1 }));
    for i in 2..=node_count {
        let leaf = Box::new(EnumNode::from(LeafEnumNode { my_int: i }));
        root = Box::new(EnumNode::from(ParentEnumNode {
            left: root,
            right: leaf,
        }));
    }
    let mut t0 = std::time::Instant::now();
    for iter in 0..iter_count {
        if iter < warmup {
            t0 = std::time::Instant::now();
        }
        let r = root.get();
        if r != r1 {
            println!("{} != {}", r, r1);
        }
        root.change(100);
        let r = root.get();
        if r != r2 {
            println!("{} != {}", r, r2);
        }
        root.change(-100);
    }
    let t1 = std::time::Instant::now();
    println!("{:?}", t1 - t0);
}