预计算查找表和"branch prediction"的设计模式

Question

我有一个看起来像这样的程序：

struct EventTypeA {
    int someInt;        // random between 0 and 9
};
struct EventTypeB {
    int someOtherInt;   // random between 0 and 100000
};
int EventAHandler(EventTypeA e) {
    // Updates multiplier
    static int multipler = e.someInt;
    return multiplier;
}
double EventBHandler(EventTypeB e) {
    /* This is a simple example for illustration, the actual intermediate
       calculation takes up much more computational time than this */
    int intermediateResult = (e.someOtherInt * multipler) % 10 + 1;
    if (intermediateResult <= 3) { DoAction1(); }
    if (intermediateResult >= 7) { DoAction2(); }
}
...
...
void SomeMethodWithinSomeClass() {
    while (true) {
        // Listen for events of type A and B
        // if EventTypeA occurs, invoke EventAHandler
        // if EventTypeB occurs, invoke EventBHandler
    } 
}

我想让EventAHandler每次EventTypeA到达并且我有新multiplier时预先计算所有可能EventTypeB.someOtherInt的intermediateResult查找表，这样我就可以用查找替换EventBHandler中intermediateResult的计算。

这样做的理由是，我的EventBHandler对时间敏感，而EventAHandler不是：所以当EventTypeB稍后到达时，EventBHandler不必执行int intermediateResult = (e.someOtherInt * multipler) % 10 + 1;（让我们假设这个语句占用了更多的时钟周期），只需要查找。

我的问题是，只有当EventTypeA频繁发生而EventTypeB很少发生时，它才会表现良好。

在发生多个连续EventTypeB的情况下，比我预先计算查找表的速度更快，我想过早地终止预计算并切换回原始方法。有没有一种干净的方法来做到这一点？

Answer 1

您可以选择将用于计算中间结果的公式更新为：

intermediate_result = ((e.someOtherInt) % 10) * multiplier + 1

现在第一个结果将在 0-10 范围内，乘数本身也在同一范围内。现在，您应该很容易为值提供一个 10x10 的查找表。尽管使用上述公式，实际计算本身不会是次优的。

Answer 2

您可以预先计算一次0..9 * 0..100000值。（你想EventAHandler每次都能完成这项工作的 1/10......

然后EventBHandler只做一个查找。 EventAHandler不会每次都进行巨大的计算。

如果预计算的数组不适合内存，则可以使用数据库。

EventAHandler在检索数组的一部分时取消设置标志，并在准备就绪时设置标志。 如果标志未就绪，EventBHandler计算值，否则使用查找表。