2022-07-12

The saddest aspect of life right now is that science gathers knowledge faster than society gathers wisdom. — Isaac Asimov

达夫设备

达夫设备 duff-device

参见： https://mthli.xyz/duff-device/

循环展开：

// 正常情况下的 for 循环，
// 需要连续迭代 100000000 次
int sum = 0;
for (int i = 0; i < 100000000; i++) {
    sum += i;
}
 
// 每次循环展开 5 次，
// 只用迭代 20000000 次即可
int sum = 0;
for (int i = 0; i < 100000000; i += 5) {
    sum += i;
    sum += i + 1;
    sum += i + 2;
    sum += i + 3;
    sum += i + 4;
}

有如下一段程序（routine），是从 Evans & Sutherland Picture System II 中提取出来的，用于将一个 short 数组拷贝到 IO 数据寄存器上：

send(to, from, count)
register short *to, *from;
register count;
{
    do
        *to = *from++;
    while (--count > 0);
}

使用达夫设备：

send(to, from, count)
register short *to, *from;
register count;
{
    register n = (count + 7) / 8;   // => n = ceil(count / 8)
    switch (count % 8) {
    case 0: do { *to = *from++;
    case 7:      *to = *from++;
    case 6:      *to = *from++;
    case 5:      *to = *from++;
    case 4:      *to = *from++;
    case 3:      *to = *from++;
    case 2:      *to = *from++;
    case 1:      *to = *from++;
            } while (--n > 0);
    }
}

它的妙处在于：能够处理$\frac{count}{8}$除不尽的情况，其中$n=\lceil \frac{count}{8}\rceil$ ，利用switch语句的fall-through性质，第一次如果count除不尽8, 则会直接命中余数，然后接着往下走，共执行余数次语句。之后通过while循环，每循环做8次语句（循环展开），最后得到想要的结果。