你的评判标准很垃圾,我要用 corner case 把它炸裂

ICS (计算机系统导论)课程中,第一个大作业 datalab 要求我们使用位运算实现一些操作。它的某些操作允许我们使用一般 C 程序的控制结构和大部分算术、逻辑、位运算,要求我们实现一些较为复杂的功能,要求“使用的操作符数目不超过某上界”。根据作业要求,之所以这么要求,是因为不希望同学们设计出过于糟糕的效率低下的算法。这毫无问题。

问题是,在提交网站上有一个排名表,排名依据是“使用的总操作符数目”。简单思考一下,就会发现这是一个非常愚蠢的评判标准(赋值和控制结构是免费的)。本文接下来的内容,就将展示为什么这个标准非常愚蠢、背离原意。

DISCLAIMER:今年的 datalab 已经 overdue。本文通过一定的设计,没有使用任何 datalab 的题目,没有给读者以任何代码级别的提示。本文作者相信本文对于解决 datalab 毫无用处;如果读者敢于用本文提交的方法进行提交,说明读者本来就会至少一种(正常的)解决方法。但,如果你正在、即将或者未来有可能做 datalab,我仍然不建议你阅读文章,防止破坏自己发现这个 exploit 的游戏体验。

为什么 op count 很垃圾?

假设我们要实现这么一个功能:

int f(int x) {
    return 1<<x;
}

一般正常人都会写出一个 1 op 的代码,就像上文展示的这样;但实际上它是可以 0 op 的。

int f_but_worse(int x) {
    switch(x) {
        case 0: return 1;
        case 1: return 2;
        case 2: return 4;
            // etc. etc. etc.
        default: return 0;
    }
}

注意到上述代码并没有使用任何操作符。根据 datalab 的评判标准,这确实是 0 op 的。我们知道,

  • 0 op 可以实现和常数比较。
  • 0 op 可以实现 ! 操作符。(提示:else 是免费的。)

习题。使用这一方法,实现 1 op 的 negpwr2。

可以发现,所有确定的函数都是 0 op 的,因为你只需要打一个巨大无比的表。但这显然不能提交上去。那我们就要问:

教练,有没有更刺激的?

当然可以。假设我们有一个数字 x : unsigned,我们要把它的高 5 位视作一个下标 \(i\),低 27 位视作一个长度为 27 的 01 串 \(s\),然后我们要获取 \(s[i]\) 。我们会有这样的函数:

unsigned g(unsigned x) {
    unsigned i = x >> 27;
    unsigned s = x & 0x07FFFFFF;
    return (s >> i) & 1;
}

这个是 4 op 的。但由于它只使用了两种操作,我们实际上可以利用循环,复用操作,把它变成 2 op。

unsigned g_but_worse(unsigned x) {
    // register files
    unsigned t = 0;
    unsigned shr0, shr1, shr2;
    unsigned and0, and1, and2;
    unsigned ret, hlt = 0;
    unsigned i, s;
    // clock
    while(true) {
        // ALU
        and0 = and1 & and2;
        shr0 = shr1 >> shr2;
        // instruction memory
        switch(t) {
            case 0:
                shr1 = x;
                shr2 = 27;
                and1 = x;
                and2 = 0x07FFFFFF;
                t = 1;
                break;
            case 1:
                i = shr0;
                s = and0;
                shr1 = s;
                shr2 = i;
                t = 2;
                break;
            case 2:
                and1 = shr0;
                and2 = 1;
                t = 3;
                break;
            case 3:
                ret = and0;
                hlt = 1;
                break;
        }
        if(hlt) {
            break;
        }
    }
    return ret;
}

由于已经上过了处理器架构,上文给出的注释是具有提示性的。

教练,有没有更刺激的?

上文只展示了一个简短的例子。

事实上,使用这种方法,我们可以把 C 中所有的控制结构都“编译”成上文这种指令集。你可以自己思考一下怎么处理 ifwhile

习题。如果 switch 不可用,找一种方法来照样放 instruction memory。(提示,你会需要很多变量。)

通过精心选取我们所使用的操作符种类,我们可以降低我们所需要的操作符数量。例如,

  • 减法可以判断相等。
  • 常数个减法可以完成加法。
  • 常数乘 32 个加法可以完成左移。
  • 常数乘 32 个加法和 &1 可以完成乘法。
  • 右移和减法(各一次)可以完成无符号小于比较。
  • 除法加查表可以实现右移;乘法和左移同理。
  • 除法和减法可以实现取模。
  • 常数次取模可以判断相等。

等等,等等。请读者自行证明以下结论:

命题。任何一段只使用了常数内存、符合CSAPP“浮点代码规范”的 C 代码都可以翻译成一段功能相同的 2 op 代码。其中,“浮点代码规范”是说没有 struct、数组、指针等高级东西,只有代数、逻辑、位操作符。

此处建议读者自行找出应该使用哪两个操作符。

如果读者已经自行实现了 float_i2ffloat_f2i ,它们适用这里的条件。但由于评测机的限制(譬如,每个循环至多进入 70 次;例如,形式化验证工具只能运行 60 秒),其中一个并不能跑过去,需要额外再加一个运算符。

如果你真想去实现这两个函数,作为对照,我自己的版本它们加起来接近一千行。我手写了其中的至少四百行。

习题(编译原理)。写一个把上述代码编译成 2 op 的编译器。

教练,有没有更刺激的?

float_abs,优化的鼎盛。注意到这个问题不仅要求绝对值,还要对 NaN 返回本身。(这本身就有点蠢。)它有着很平凡的 2 op 的实现,但有办法可以让它 1 op。

再说下去就违反学术诚信原则了,因此我给出一些提示:这个已知两种解法,一种是使用某位运算,然后运算次数和整数位数(32)相关;另一种使用某种算术运算,运算次数和 32 无关。

教练,可是……这有啥用?

呃,并没有。

那你为什么要研究这个?

呃……

那你为什么要写这个代码呢?

呃……这么说吧,如果你看到一个很垃圾的规则,你是不是会想找出一个奇怪的 corner case 来 hack 掉它?

不想啊,你脑子有问题吧。

爬。

Iʼm gonna shoot this damn car full of holes. —— Fateful Findings, a movie by Neil Breen.

这个东西近似于行为艺术。我想通过这两段非常长的代码,来展示一个似乎很有道理的评判标准(op count)可以完全背离它的初衷(降低代码复杂性)。我的本意是通过排行榜上那个 bug 一样的数字来让大家停止浪费时间刷榜,但好像自己也落入到自己的批判的射程里面了(x)。

Anyway,我认为这种 exploit 式的优化,是对认认真真优化操作次数的一种 parody。由于不影响成绩,对我这种 exploit 的批判,完全可以打在“认真优化”上。我只不过是通过 exploit,来放大了这种效应。它和飞天面条之于宗教的关系有一些(勉强的)相似之处。

但它确实很好玩啊!!