CKB/CKB-VM 扩展指令集 B

写代码时, 我们总希望代码执行得越快越好, 对于区块链上的智能合约同样如此.

更快的执行速度意味着更高的 TPS, 当然, TPS 受多种因素影响, 这里说的只是其中一个维度. 与此同时, 更快的执行速度也意味着能够承载更多复杂业务: 当虚拟机足够高效时, 我们才有能力将一些复杂的密码学算法直接在链上实现.

通常有两种途径来提升性能: 软件层面和硬件层面. 在软件层面, 程序员们积累了许多口耳相传的优化技巧, 有些晦涩难懂, 却能带来显著的性能提升, 寥寥数行代码便能替代几十行的朴素实现, 或借助某种精妙的算法将性能提升几十乃至上百倍. 我记得 2017 年做图像处理工作时, 手头有几十 TB 的图像数据需要批量处理, 每一次对算法的微小优化, 都能节省几个小时甚至几十个小时的运行时间, 那种成就感令人印象深刻.

然而, 纯软件优化终究有其上限. 若想进一步突破瓶颈, 就需要从运行软件的底层载体入手. CKB 的链上程序运行在 CKB-VM 上, 因此让 CKB-VM 本身执行得更快, 是提升程序运行效率的另一个关键方向.

B 扩展指令集中的 B 代表 Bit Manipulation, 即"位操作". RISC-V 的 B 扩展指令集旨在增强处理器处理位操作的能力, 典型的位操作包括前导零计数 (CLZ), 尾随零计数 (CTZ), 循环移位等.

下面我将通过几个版本的前导零计数算法, 来说明将 B 扩展指令集引入 CKB-VM 的实际意义. 首先解释一下什么是前导零计数: 将一个整数视作二进制表示, 统计其最高位起连续的零的个数. 例如, 数字 12345678 的二进制表示如下, 其前导零个数为 40:

0000000000000000000000000000000000000000101111000110000101001110(12345678)
|<--------------40-------------------->|

实现前导零计数并不难, 绝大多数程序员能在一分钟内写出来. 最直观的做法是逐位扫描: 每次将数字左移一位, 检查最高位是否为零, 直到遇到第一个 1 为止.

uint64_t clz(uint64_t n)
{
    int c = 0;
    for (int i = 0; i < 64; i++) {
        if (((n << i) & 0x8000000000000000) == 0) {
            c += 1;
        } else {
            break;
        }
    }
    return c;
}

前导零计数在许多密码学算法和底层运算中被频繁使用, 自然令人不禁思考: 有没有办法让它跑得更快? 对于这类范围收缩问题, 二分法往往是个高效的选择: 每次将问题规模减半, 逐步缩小目标范围, 直到得出答案. 具体到前导零计数, 我们可以先判断高 32 位是否全为零, 再依次对 16 位, 8 位, 4 位, 2 位, 1 位做同样的判断:

uint64_t clz(uint64_t n)
{
    if (n == 0) return 64;
    int c = 0;
    if (n <= 0x00000000FFFFFFFF) { c += 32; n <<= 32; };
    if (n <= 0x0000FFFFFFFFFFFF) { c += 16; n <<= 16; };
    if (n <= 0x00FFFFFFFFFFFFFF) { c += 8; n <<= 8; };
    if (n <= 0x0FFFFFFFFFFFFFFF) { c += 4; n <<= 4; };
    if (n <= 0x3FFFFFFFFFFFFFFF) { c += 2; n <<= 2; };
    if (n <= 0x7FFFFFFFFFFFFFFF) { c += 1; };
    return c;
}

第二个版本的性能远优于第一个. 对于目前的 CKB-VM 而言, 这大概是纯软件实现中最快的方案之一, 约需 30 条指令. 此外还可以使用查表法进一步提速, 这是经典的以空间换时间的策略, 但代价是需要预先分配一张较大的查找表.

然而我想更进一步: 既然前导零计数如此常用, 为何不在指令集层面直接提供这一原语? RISC-V 将指令集分为基础指令集和扩展指令集, 前导零计数恰好就被纳入了 B 扩展指令集. 这意味着, 一旦 CKB-VM 实现了 B 扩展, 上述所有实现都可以被一条指令替代:

static inline int64_t _rv64_clz(int64_t rs1) {
    int64_t rd;
    __asm__ ("clz %0, %1" : "=r"(rd) : "r"(rs1));
    return rd;
}

单条指令相较于 30 条指令的软件实现, 性能提升是显而易见的. 完整的 B 扩展指令集共提供了 43 条新指令, 涵盖位计数, 位提取, 字节翻转, 移位混合等多类操作, 可阅读官方文档了解详情. 总体而言, 对于有大量位操作需求的合约(如哈希算法, 椭圆曲线运算等), 引入 B 扩展指令集可以带来一个数量级以上的性能提升.

上面的内联汇编写法需要手动标注每一处位操作, 实际工程中这样做既繁琐又容易出错. 更好的做法是直接告诉编译器目标平台支持 B 扩展, 让编译器自动完成指令选择.

RISC-V 的 B 扩展在规范中被细分为四个子扩展:

子扩展	名称	典型指令
zba	Address calculation	sh1add, sh2add, sh3add
zbb	Basic bit-manipulation	clz, ctz, cpop, ror, rol, rev8
zbc	Carry-less multiplication	clmul, clmulh, clmulr
zbs	Single-bit operations	bset, bclr, binv, bext

在使用 clang 编译时, 通过 -march 参数将这些子扩展附加到基础 ISA 字符串上即可:

$ clang --target=riscv64-unknown-elf \
        -march=rv64imc_zba_zbb_zbc_zbs \
        -O3 -o main main.c

开启这些选项后, 编译器会自动将 C 标准内置函数(甚至是你手写的朴素实现)映射到对应的 B 扩展指令. 例如:

#include <stdint.h>

// Clang 会将以下函数自动编译为单条指令: clz
uint64_t clz(uint64_t n) { return __builtin_clzll(n); }

// Clang 会将以下函数自动编译为单条指令: cpop
uint64_t pop(uint64_t n) { return __builtin_popcountll(n); }

// Clang 会将以下函数自动编译为单条指令: ror
uint64_t ror(uint64_t n, int shift) { return (n >> shift) | (n << (64 - shift)); }

使用下面的命令编译后, 生成的汇编代码中会直接使用 clz, cpop, ror 等 B 扩展指令, 而不是模拟它们的普通指令序列:

$ clang --target=riscv64-unknown-elf -march=rv64imc_zba_zbb_zbc_zbs -O3 -c -o main.o main.c
$ llvm-objdump -d main.o
# main.o: file format elf64-littleriscv
#
# Disassembly of section .text:
#
# 0000000000000000 <clz>:
#        0: 60051513      clz     a0, a0
#        4: 8082          ret
#
# 0000000000000006 <pop>:
#        6: 60251513      cpop    a0, a0
#        a: 8082          ret
#
# 000000000000000c <ror>:
#        c: 60b55533      ror     a0, a0, a1
#       10: 8082          ret

这意味着: 只要在编译 CKB 合约时指定正确的 -march 参数, 代码中所有符合条件的位操作都会被自动替换为 B 扩展指令, 无需修改任何源代码.

---