欢迎光临散文网 会员登陆 & 注册

【深圳 IO 攻略】番外篇:上电时设置符号以提高运行效率

2022-08-11 16:33 作者:ココアお姉ちゃん  | 我要投稿

本文首发于 B 站《深圳 IO》文集(https://www.bilibili.com/read/readlist/rl569860)。原创不易,转载请注明出处。

上一个番外篇中,我们提到了“终止条件前置法”去掉了简单循环中的 jmp 指令,大幅提高了循环的运行效率。但是,此方法有一些局限性:首先,进入准备工作前一定要满足循环终止条件;其次,循环结束后不能有难以消化的收尾工作,要么没有收尾工作,要么确保第一个周期额外执行的收尾工作没有副作用,不能画蛇添足。这次我要提的是另外一种优化循环的方法:上电设置符号法。这种优化方法不能减少代码行数,但普适性更强。它不要求进入准备工作前一定要满足循环终止条件,同时对于有收尾工作的循环,也能很好地优化。

我们首先说明一下带收尾工作的循环结构:

如果我们在准备工作前,加一条上电执行的,一定成立的判断语句的话,代码就会变成下面这个样子:

上电时激活 + 号指令,执行准备工作。进入循环后,只要不满足循环终止条件,芯片就一直处于 - 号激活的状态,就一直只执行循环体相关代码。直到满足循环终止条件后,+ 号指令激活,执行收尾工作,然后再跳回第 2 行执行下一次任务的准备工作。

和“终止条件前置法”一样,优化前循环体执行 n 次就要执行 n-1 条 jmp 指令,优化后多了一条必然成立的判断,同时去掉了 jmp 指令,共计能省下 n-2 格电。考虑到几乎没有只执行一次的循环,那么 n-2 以非负数居多。不增加成本、不增加代码行数,但是电量却降下来了。优化后的方案是完爆优化前的方案的。

示例 1:第 22 关《加密货币存储终端》

原版攻略:【深圳 IO 攻略】第 22 关:加密货币存储终端

上一个番外篇里,我说过,第 22 关的循环无法使用“终止条件前置法”优化,因为循环结束后有收尾工作,且收尾工作在第一个周期额外执行时会产生副作用。但是这一关的循环是可以用本期番外篇里提到的“上电设置符号法”来优化的。

注意右边芯片的这个循环,由于第 5 行写的是 - jmp 2,因此很明显,第 2~5 行是循环体。然后,循环体上方的部分(第 1 行)是准备工作,循环体下方的部分(第 6~7 行)是收尾工作。我们按照上面所说的优化模板对该芯片做“上电设置符号法”的优化,将芯片改写成如下代码:

①准备工作前添加 @ teq 0 0;②准备工作和收尾工作全部带上 + 号;③循环体去掉 jmp。三步曲一气呵成。这里要注意一下,终止条件由原先的 tcp acc 7 改成了 teq acc 7,因为要确保终止时【激活 + 号指令】,而不是像之前一样【不激活 - 号指令】就行。

点击左下角的【模拟】,稍等片刻,便会弹出结算界面:

成本和代码行数没有增加,电量却活生生地省下来了。这就叫完爆。

顺便说一下 459 电量是怎么做到的。这是因为修改了左边芯片的代码。左边芯片的代码改成了这个样子:

官方谜题里的所有非阻塞 x 口输入,第一秒一定是无数据(-999),所以将睡眠指令移动到第一行以节省电量。teq x1 0, + jmp 7 这两行代码合并成了一行 tcp x1 0,这样每当从 DX-300 读到 0 时,就关闭一切 + - 号指令,直接跳到第 7 行,完全不需要手写 jmp 指令跳转。从第 7 行开始一直到最后是一个三态判定。只是,这里如果用 tcp 做三态判定的话需要多写两条 jmp 指令,会有效率浪费。因为读到 -999 时是不执行任何操作的,我们关心的只有【大于 -1】和【等于 -1】这两态。从读卡器中读到了大于 -1 的数字时,将一位卡号写入 RAM(mov x0 dat, tgt dat -1, + mov dat x2);从读卡器中读到了 -1 时(- tlt dat -1, 既不大于 -1 也不小于 -1 则等于 -1),将已存金额发给右侧的芯片,然后清空 acc(- mov acc x3, - sub acc)。

由于左边的芯片去掉了 3 条 jmp 指令,533 电量再次骤降到 459 电量。

示例 2:第 28 关《防剧透耳机》

原版攻略:【深圳 IO 攻略】第 28 关:防剧透耳机

第二版【哈希表】方案因为不涉及循环,所以不是我们的优化目标。我们这次需要优化的是第一版【线性查找】方案。

第 12 行的代码是 jmp 3,那么很明显第 3~12 行是循环体,在此之前的是准备工作,在此之后的是收尾工作。那么还是同样的三步曲,优化后的代码如下:

原先的 tcp x3 0 是“循环继续条件”,ROM 地址大于 0 时跳回去继续比对,直到 ROM 地址归零时循环结束。那么,按照本篇里的优化要求,“循环继续条件”(ROM 地址大于 0)要变更成“循环终止条件”(ROM 地址等于 0),所以优化后,原先的 tcp x3 0 变成了 teq x3 0。

另外还要注意一下,大循环体里还套了一层小的静音循环(第 8~10 行,上一版方案里是第 7~9 行),优化后 jmp 的行号也要跟着一起变(由 jmp 7 变成了 jmp 8)。

不鸣则已,一鸣惊人。就这么简简单单地优化一下,1.4K 电量减少到了 1.1K,减少了 300 格电,已经和早期未微操的哈希表效率相当了。

示例 3:阿瓦隆城第 1 关《冷库机器人》

原版攻略:【深圳 IO 攻略】阿瓦隆城第 1 关:冷库机器人

注意一下 2 号数据库管理员芯片:

第 3~5 行是循环体,在此之前的是准备工作,在此之后的是收尾工作。三步曲走起,优化成如下的样子:

好吧,同样的优化方案在这道题里只省下了 1 格电量。原因是冷库最多只有 6 格,所以随便找找就能找到空位了,平均只少执行了两次 jmp 指令。不过聊胜于无,能省一格电也不错。

无法优化的情形

如果准备工作/收尾工作里有判断或循环,导致这两部分的代码不能完全带上 + 号覆盖的话,就无法使用“上电设置符号法”来优化。因为这和我们的前提相悖。本优化方案要求准备工作和收尾工作的代码都必须带上 + 号前缀。

举例,第 26 关《电子门锁》:

第 2~10 行构成了循环,在此之前的是准备工作,在此之后的是收尾工作。但是收尾工作却出现了分叉:仅当 acc 不为 11 时才向 p1 发送 6 秒的 100 信号(teq acc 11, - gen p1 6 0)。然后分叉又合并了,不论 acc 的值为多少,都要将 RAM 地址和 acc 自己清零(mov 0 x3, sub acc)。mov 0 x3 这条指令倒是可以放在判断的前面,但是 sub acc 这条指令万万不可前置,因为这样会丢失 acc 的信息,导致接下来的 teq acc 11 这条判断返回恒假。因此,本题的收尾工作必然是“出现分叉后再合并”。然而,本优化方案要求准备工作和收尾工作必须全部带上 + 号,这就意味着,一旦在这些地方出现了分叉,就不能将分叉再合并回来。本方案的算法逻辑和本优化方案的要求相悖。

再举例,第 29 关《变色鞋》:

注意一下右边的芯片,第 3~12 行构成了循环,在此之前的是准备工作,在此之后的是收尾工作。准备工作没有分叉,可以全部带上 + 号,但是收尾工作却是一个循环清零的工作。正是这个收尾时的循环,导致了本优化方案的落空。因为,收尾工作全部带上 + 号时,你也只能用 + 号开头的 jmp 在收尾阶段执行循环。而一旦结束循环后,整个芯片的状态会变成 - 号激活,就无法继续执行同样是带 + 号前缀的准备工作了。

【深圳 IO 攻略】番外篇:上电时设置符号以提高运行效率的评论 (共 条)

分享到微博请遵守国家法律