如何在没有动态调度的情况下表达这一概念？

Question

我正在建立一个模拟(编码相当于一个模型火车集)。它是一个由各种经济主体相互作用的模拟经济。经济主体之间相互作用的主要方式是交易。在每个"tic“中，每个代理都生成一个零或多个拟议交易(例如购买食品)的列表。在每个"toc“中，所有的对头都以随机顺序处理针对它们的拟议事务，这样就不会引入偏见。在这些代码段中，建议的事务被表示为u32。

我的目标是尽可能多地模拟这些经济因素，因此性能是关键。我对生锈(或任何一种低级语言)都是新手，我从阅读生锈书中的理解是，如果我想要最大限度地提高性能，那么就使用“零成本抽象”，避免动态分派。

就这样，我提出了以下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. 在这里什么是习惯的选择？

Answer 1

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

相反，对于这样的问题，您希望将不同的“代理”分离成独立的“实体”。然后，为了重用代码，您将需要对“组件”中的子集进行“系统”迭代。

这通常被称为“实体-组件-系统”(ECS)，其中有许多模型和实现。它们通常用于游戏和其他模拟。

如果你搜索ECS，你会发现很多关于它和不同方法的问题、文章等等。

Answer 2

什么是动态调度？

动态调度通常保留给间接函数调用，即通过函数指针进行的函数调用。

在您的例子中，选项1和选项3都是动态分派的情况：

• 特征使用虚拟表，它是一个函数指针表。
• fn(...) -> ...是一个函数指针。

动态调度的性能惩罚是什么？

在运行时，常规函数调用与所谓的虚拟调用之间几乎没有区别：

• 间接函数调用可以预测，在您的CPU中有一个特殊的预测器。
• 函数调用的成本主要是保存/恢复寄存器，这在这两种情况下都会发生。

性能损失更多的是在编译时发生的。

优化的根源是内联，本质上是复制/粘贴调用站点上调用的函数的主体。一旦一个函数被内联，许多其他优化传递都可以通过(组合)代码到达城镇。对于非常小的函数( getter)来说，这是特别有利可图的，但是对于更大的功能也是非常有益的。

然而，间接函数调用是不透明的。有许多候选函数，因此优化器无法执行内联。在萌芽阶段扼杀许多潜在的优化。有时可以使用去虚拟化--编译器可以推断哪些函数可以调用--但是不应该依赖。

选择哪一种？

其中包括：选项2！

选项2的主要优点是没有间接函数调用。在match的两个分支中，编译器对于该方法的接收方具有已知的类型，因此可以在适当的情况下内联该方法，从而启用所有优化。

有没有更好的？

在开放式设计中，结构数组是构建系统的更好方法，主要是避免分支错误预测：

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

这是@橡子提出的ECS解决方案的核心设计。

注意:正如@Acorn在注释中所指出的，Array of Structs也接近最佳缓存--没有间接性，元素之间的填充非常少。

使用完整的ECS是一个更棘手的问题。除非你有动态实体ECS对动态性很有帮助，但必须在各种特性之间进行权衡:您想要更快的添加/删除，还是更快的迭代？除非您需要它们的所有功能，否则由于与您的需求不匹配的权衡，它们可能会增加自己的开销。

Answer 3

如何避免动态调度？

您可以使用选项1，而不是拥有特征对象的向量，将每种类型保留在它自己的向量中，并单独迭代它们。这不是个好办法所以..。

而是..。

选择哪一个选项可以让您最好地建模您的仿真，不要担心动态调度的const。头顶很小。还有其他因素会对性能产生更大的影响，例如为每个调用分配新的Vec。

动态调度的主要成本是间接分支预测器的误判。为了帮助cpu做出更好的猜测，您可以尝试在向量中保持相同类型的对象相邻。例如，按类型对其进行排序。

哪个是惯用的？

选项1有一个问题，要将不同类型的对象存储到向量中，必须通过间接进行。最简单的方法是对每个对象进行Box，但这意味着每个访问不仅具有函数的动态调度，而且还必须遵循额外的指针才能到达数据。

带枚举的选项2(在我看来)更惯用--您将所有数据放在连续的内存中。但请注意，枚举的大小比其最大的变体大(或相等)。因此，如果您的代理人的大小不同，它可能是更好的选择1。