c - 如何访问 C 中的结构而不在结果 ASM 中进行昂贵的乘法？

Question

我正在重构一些性能关键的代码，当我没有得到我希望的结果时，我检查了 ASM 代码(我在每次构建中保留的代码)，并注意到对 C 中结构的访问结果3 次昂贵的乘法(这实际上使得代码中的其他优化变得无用，因为 MUL 非常慢 - 约 70 个周期)。

为了更好地了解 vbcc 编译器处理结构的具体情况，我创建了这个简单的测试方法:

void TestMethod (struct SCube * C, struct SVis * V)
{
    int i;
    char idx;
    struct SWall * R;

    for (i = 0; i < V->NumLeft; i++)
    {
        idx = V->Left [i];
        R = &C [idx].Left;

        R->IsVisible = 1;
    }
}

这里是数据结构(请注意，注释中的大小只是未对齐的估计，以粗略地了解每个结构有多大 - 例如，我知道 68000 的对齐规则):

struct SWall /* (5+4*4+2*1,292) = 2,605 Bytes */
{
    char PotentiallyVisible;    
    char IsVisible;             
    char IsVertical;            
    char MaterialID;            
    char LightIdx;              
    struct SPoint Point [4];    
    struct SBresenham L1, L2;
};

struct SCube /* 6*2,605 + 1 + 8 = 15,639 Bytes */
{
    struct SWall Front, Back, Left, Right, Top, Bottom;
    bool IsPartialBack;
    short int Imgxp, Imgyp, Imgxl, Imgyl;
};

struct SVis
{
    int NumLeft, NumRight, NumTop, NumBottom;
    char Left [8], Right [9], Top [8], Bottom [8];
};

这是生成的 ASM 代码(在 -O2 优化级别生成；尚未检查 O3，但 O3 的性能差异可以忽略不计(~2.5%)，并且编译时间长 10 倍，并引入其他问题)。我添加了一些注释以使其更具可读性:

    public  _SScreen_vis1
    cnop    0,4
_SScreen_vis1
    movem.l l7543,-(a7)

    move.l  (4+l7545,a7),a3
    move.l  (8+l7545,a7),a2     a2 = V->NumLeft

    moveq   #0,d1               d1 = i
    tst.l   (a2)                Early Out  (bypass the loop)
    ble l7542
    lea (16,a2),a1
l7541                           Loop Start
    move.b  (a1)+,d0            d0 = idx = V->Left [i]
    ext.w   d0
    ext.l   d0

    move.l  #15648,d2           d2 = #15648 (sizeof SCube = 15,648)
    move.l  d0,d3               d3 = d0 = idx
    move.l  d2,d4               d4 = #15648
    swap    d3
    swap    d4
    mulu.w  d2,d3               d3 = (d3 * d2) = idx * #15648
    mulu.w  d0,d4               d4 = (d4 * d0) = #15648 * idx
    mulu.w  d2,d0               d0 = (d0 * d2) = idx * #15648
    add.w   d4,d3               d3 = (d3 + d4) = (idx * #15648) + (#15648 * idx)
    swap    d3
    clr.w   d3
    add.l   d3,d0
    lea (a3,d0.l),a0            a0 = R

    move.b  #1,(5213,a0)        R->IsVisible = 1

    addq.l  #1,d1               i++
    cmp.l   (a2),d1

    blt l7541                   Loop End

l7542
l7543   reg a2/a3/d2/d3/d4
    movem.l (a7)+,a2/a3/d2/d3/d4
l7545   equ 20
    rts

我检查了整个 ASM 列表，在我使用 1 个结构的每个地方，都有大约 11 个操作与 3 个 MUL 的组合。我能理解 1 MUL，但不能理解 3。

我必须采取哪些选项来加速对结构的访问？我能想到的有这些:

1. 将编译器切换为 gcc(最终会发生，只是不是现在)
2. 指针算术 - 我希望编译器在执行诸如 ptr++ 之类的操作时使用 ADD 指令
3. 使用 SoA 而不是 AoS(例如，使用数组结构而不是结构数组) - 这里的想法是指针将指向内在类型(char、short int、int、bool)，因此编译器应避免使用 MUL 指令.

我可以尝试其他经过验证的方法(除了直接使用 ASM 进行编码之外)来加速对结构数组的访问吗？

Answer 1

考虑到idx取值范围较小，可以使用查表的方式进行指针计算。

static const size_t table[] =
{
  sizeof(struct x) * 0,
  sizeof(struct x) * 1,
  ...
};

...
R = (struct x*)((char*)C + table[idx]);

此外，可以使用较小尺寸的表来计算右指针。例如，假设我们的索引范围为 [0..255]，但想要使用 16 项表:

static const size_t table[] =
{
  sizeof(struct x) * 0,
  sizeof(struct x) * 1,
  ...
  sizeof(struct x) * 15
};
...
R = (struct x*)((char*)C + (table[idx>>4] << 4) + table[idx&15]);