没有动态调度如何表达这个概念?

How to express this concept without dynamic dispatch?

我正在构建一个模拟(相当于模型火车集的编码)。它是一个模拟经济,各种经济主体相互作用。经济主体之间互动的主要方式是交易。在每个 "tic",每个代理都会生成一个包含零个或多个建议交易(例如购买食物)的列表。在每个 "toc" 处,所有交易对手都以随机顺序处理针对他们的拟议交易,以免引入偏差。在这些片段中,提议的交易表示为 u32.

我的目标是尽可能多地模拟这些经济主体,因此性能是关键。我是生锈的新手(或任何一种低级语言),我从阅读生锈书的理解是,如果我想要最高性能,那么使用 "zero cost abstractions" 并避免动态调度。

因此,我提出了以下 3 种方法。

选项 1

trait EconomicAgent {
    fn proposed_transactions(&self) -> Vec<u32>;
}

struct Person {
    health:f64,
    energy:f64,
    nutrition:f64,
    money:f64,
    food:f64
}

impl EconomicAgent for Person {
    fn proposed_transactions(&self) -> Vec<u32> {
        vec![1, 2, 3]
    }
}

struct FoodStore {
    money:f64,
    food:f64
}

impl EconomicAgent for FoodStore {
    fn proposed_transactions(&self) -> Vec<u32> {
        vec![4, 5, 6]
    }
}

人和食品店是实现 EconomicAgent 特征的不同类型。然后我可以遍历特征对象的向量以获得建议交易的列表。我相信每个调用都是动态调度的。

选项 2

enum EconomicAgent2 {
    Person(Person),
    FoodStore(FoodStore)
}

impl EconomicAgent2 {
    fn proposed_transactions(&self) -> Vec<u32> {
        match self{
            EconomicAgent2::Person(person) => person.proposed_transactions(),
            EconomicAgent2::FoodStore(food_store) => food_store.proposed_transactions()
        }
    }
}

在这里,EconomicAgent 不是一个特征,而是一个枚举,你可以看到它是如何工作的。

选项 3

const HEALTH_INDEX : u8 = 0;
const ENERGY_INDEX : u8 = 1;
const NUTRITION_INDEX : u8 = 2;
const MONEY_INDEX : u8 = 3;
const FOOD_INDEX : u8 = 4;

enum EconomicAgentTag {
    Person,
    FoodStore
}
struct EconomicAgent3 {
    tag: EconomicAgentTag,
    resources:[f64; 5],
    proposed_transactions: Box<fn(&EconomicAgent3) -> Vec<u32>>
}

fn new_person() -> EconomicAgent3 {
    EconomicAgent3 {
        tag: EconomicAgentTag::Person,
        resources: [0.0,0.0,0.0,0.0,0.0],
        proposed_transactions: Box::new(|_| vec![1, 2, 3])
    }
}

fn new_food_Store() -> EconomicAgent3 {
    EconomicAgent3 {
        tag: EconomicAgentTag::FoodStore,
        resources: [0.0,0.0,0.0,0.0,0.0],
        proposed_transactions: Box::new(|_| vec![4, 5, 6])
    }
}

这里经济主体是更抽象的表示。

现在假设有许多不同类型的经济主体(银行、矿山、农场、服装店等)。他们都通过提议和接受交易进行交互。选项 1 似乎受到动态调度的影响。选项 2 似乎是我自己的通过匹配表达式进行动态调度的版本,所以可能不会更好,对吗?选项 3 似乎应该是性能最高的,但实际上并没有让程序员的认知轻松很多。

最后是问题:

  1. 显然选项 1 涉及动态调度。选项 2 和 3 呢?
  2. 预计哪个性能最高?请注意,我真的无法进行测试,因为完整的想法(目前仅在纸上)显然比这些片段更复杂,现在的选择将影响整个项目的整个结构。
  3. 这里的惯用选择是什么?

如何避免动态调度?

您可以选择选项 1,而不是使用特征对象的向量,将每种类型保留在自己的向量中并单独迭代它们。这不是很好的解决方案,所以...

而是...

选择可以让您最好地模拟模拟的选项,不用担心动态调度的常量。开销很小。还有其他的事情会更多地影响性能,例如为每个调用分配新的Vec

动态调度的主要代价是间接分支预测器做出错误的猜测。为了帮助 cpu 做出更好的猜测,您可以尝试在向量中将相同类型的对象彼此相邻。例如按类型排序。

哪个是地道的?

选项 1 存在一个问题,即要将不同类型的对象存储到 vector 中,您必须通过间接寻址。最简单的是 Box 每个对象,但这意味着每次访问不仅会动态分配函数,而且还必须遵循额外的指针才能获取数据。

带有枚举的选项 2(在我看来)更加惯用 - 您将所有数据都放在连续的内存中。但请注意,枚举的大小大于(或等于)其最大变体。因此,如果您的代理商规模不同,最好选择选项 1。

您的所有选项都以一种或另一种方式使用动态分派或分支来为每个元素调用正确的函数。原因是您将所有代理混合到一个地方,这是不同性能损失的来源(不仅是间接调用或分支,还包括缓存未命中等)。

相反,对于这样的问题,您希望将不同的 "agents" 分成独立的 "entities"。然后,为了重用代码,您需要分解出 "components" 的哪些子集由 "systems".

迭代

这就是通常所说的"Entity-Component-System"(ECS),有很多模型和实现。它们通常用于游戏和其他模拟。

如果您搜索 ECS,您会发现许多关于它的问题、文章等以及不同的方法。

什么是动态调度?

Dynamic Dispatch 通常保留给间接函数调用,即通过函数指针发生的函数调用。

你的情况,方案一和方案三都是动态调度的情况:

  • Traits 使用虚拟 table,这是一个 table 函数指针。
  • fn(...) -> ...是一个函数指针。

动态调度的性能损失是多少?

在 运行 时间,常规函数调用和所谓的虚拟调用之间几乎没有区别:

  • 间接函数调用可以预测,在您的CPU.
  • 中有一个针对它们的特殊预测器
  • 函数调用的成本主要是 saving/restoring 个寄存器,这两种情况都会发生。

性能损失更隐蔽,它发生在编译时

优化之母是 内联,它本质上是 copy/paste 在调用点调用函数的主体。一旦一个函数被内联,许多其他优化过程就可以在(组合的)代码上进行。这对于非常小的函数(getter)尤其有利可图,但对于较大的函数也非常有益。

但是,间接函数调用是不透明的。有很多候选函数,因此优化器无法执行内联……将许多潜在的优化扼杀在萌芽状态。去虚拟化有时是可用的——编译器推断可以调用哪些函数——但不应依赖。

选择哪个选项?

在提供的选项中:选项 2!

选项 2 的主要优点是没有间接函数调用。在你的 match 的两个分支中,编译器都有一个已知的方法接收者类型,因此如果 suitable 可以内联方法,启用所有优化。

还有更好的吗?

采用开放式设计,结构数组是构建系统的更好方式,主要避免分支预测错误:

EconomicAgents {
    Person(Vec<Person>),
    FoodStore(Vec<FoodStore>),
}

这是提出的ECS方案的核心设计。

注意:正如@Acorn 在评论中指出的那样,结构数组也接近于最佳缓存——没有间接寻址,元素之间的填充很少。

使用完整的 ECS 是一个更棘手的提议。除非你有动态实体——Person/FoodStores 在 运行 期间是 added/removed —— 我不会打扰。 ECS 有助于动态化,但必须在各种特性之间做出权衡:你想要更快 add/remove 还是更快的迭代?除非您需要他们的所有功能,否则他们可能会因权衡不符合您的需求而增加自己的开销。