c - 进行预先计算的真实性检查的不同方法

Question

我正在开发一个为一个函数生成 C 代码的程序。这个生成的 C 函数驻留在另一个目标程序的中央循环中；该函数对性能敏感。生成的函数用于基于 bool 值调用另一个函数——该 bool 值是使用传递给生成的函数的 2 个整数获取的:状态号和模式号。生成的函数如下所示:

void dispatch(System* system, int state, int mode) {
    // Some other code here...
    if (truthTable[state][mode]) {
        doExpensiveCall(system, state, mode);
    }
}

一些事实:

• “state”和“mode”值的范围从 0 开始，到 < 10,000 的某个数字结束。它们的可能值是连续的，之间没有间隙。因此，例如，如果“state”的最终值为 1000，那么我们就知道有 1001 个状态(包括状态 0)。
• 代码生成器了解状态和模式，并且它提前知道状态+模式的哪种组合将产生 true 值。理论上，状态+模式的任何组合都可以产生 true 值，从而调用 doExppressiveCall，但实际上，大多数状态+模式组合都会产生 true 值。同样，此信息在代码生成期间是已知的。
• 由于这个函数会被多次调用，所以我想优化对真值的检查。在一般情况下，我预计测试在大部分时间内都会产生错误结果。平均而言，我预计只有不到 1% 的调用会产生 true 值。但是，理论上，该概率可能高达 100%(这一点取决于最终用户)。

我正在探索计算状态+模式是否会调用 doExpectiveCall() 的不同方法。最后，我必须做出选择，所以我现在正在探索我的选择。到目前为止，我可以想到以下不同的方法:

1) 创建一个预先计算的二维数组，其中包含 bool 值。这就是我在上面的示例中使用的。这产生了我能想到的最快的检查。问题是，如果状态和模式的范围很大(例如 10,000x1000)，则生成的表开始变得非常大(在 10,000x1000 的情况下，仅该表就有 10MB)。示例:

// STATE_COUNT=4, MODE_COUNT=3
static const char truthTable[STATE_COUNT][MODE_COUNT] = {
  {0,1,0},
  {0,0,0},
  {1,1,0},
  {0,0,1}
}

2) 创建一个像 #1 一样的表，但经过压缩:每个数组条目不是单个 bool 值，而是一个字符位字段。然后，在检查过程中，我会使用状态+模式进行一些计算来决定如何索引到数组中。这会将预计算表的大小减少 MODE_MODE/8。缺点是减少的不是那么多，现在需要计算位域表中 bool 值的索引，而不是像 #1 中的情况那样只是简单的数组访问。

3) 由于产生 true 值的状态+模式组合的数量预计会很小，因此 switch 语句也是可能的(使用 #1 中的 trueTable 作为引用):

switch(state){
case 0: // row
 switch(mode){ // col
  case 1: doExpensiveCall(system, state, mode);
  break;
 }
break;
case 2:
 switch(mode){
    case 0:
    case 1: doExpensiveCall(system, state, mode);
    break;
 }
break;
case 3:
 switch(mode){
    case 2: doExpensiveCall(system, state, mode);
    break;
 }
break;
}

问题:

根据上述事实，还有哪些其他方法可以用来计算调用 doExpectiveCall() 所需的 bool 值？

谢谢

编辑: 我考虑了 Jens 示例代码，并想到了以下内容。为了只有一个 switch 语句，我可以在生成的代码中执行此计算:

// #if STATE_COUNT > MODE_COUNT
int i = s * STATE_COUNT + m;
// #else 
int i = m * MODE_COUNT + s;
// #endif

switch(i) {
case 1: // use computed values here, too.
case 8:
case 9:
case 14:
     doExpensiveCall(system, s, m);

}

Answer 1

我会尝试使用 (3) 的修改版本，其中实际上只有一个调用，并且所有 switch/case 内容都会导致该调用。通过这种方式，您可以确保编译器将选择他所拥有的任何启发式方法来优化它。

类似的东西

switch(state) {
 default: return;
 case 0: // row
   switch(mode){ // col
   default: return;
   case 1: break;
   }
   break;
 case 2:
   switch(mode){
   default: return;
   case 0: break;
   case 1: break;
   }
   break;
 case 3:
   switch(mode){
   default: return;
   case 2: break;
   }
   break;
 }

doExpensiveCall(system, state, mode);

也就是说，您只能在开关内进行“控制”。编译器应该能够很好地解决这个问题。

这些启发式方法在架构和编译选项之间可能会有所不同(例如 -O3 与 -Os)，但这就是编译器的用途，根据特定平台做出选择知识。

供您引用时间效率，如果您的函数调用确实像您声称的那样昂贵，那么这部分将被淹没在噪音中，请不要担心。 (或者以其他方式对您的代码进行基准测试以确保确定。)