CKB/CKB-VM B 扩展指令集

在我们写代码的时候总是会希望代码执行的越快越好, 对于区块链上的智能合约也是.

更快的执行速度意味着更高的 TPS, 当然我这里说的是一个可能性, 因为 TPS 是一个受多因子影响的变量. 同时的话, 这也意味着能承载更多的复杂业务, 因为这代表着我们有能力把一些复杂的密码学算法在虚拟机中实现.

通常有两种方式来实现性能的提升, 即软件上和硬件上. 对于第一种情况来说, 我们有许多在程序员之间口耳相传的代码秘籍, 这些秘籍非常晦涩但却能显著提高性能, 它们可以用两三行代码实现本来需要几十行代码实现的功能, 或者使用某种神秘的算法, 来让代码的性能提升几十上百倍. 我记得在 17 年的时候, 那时候我在做图像相关的工作, 说实话那份工作很好玩, 我需要编写应用于图像的各种算法, 那时候我有几十个 T 的图像数据需要处理, 任何对算法细微优化, 都能几个小时甚至几十个小时的节省处理程序的运行时间.

但是从软件上来节省程序的处理时间的消耗是有极限的, 想要进一步提升就需要从运行软件的载体上着手. CKB 的链上程序运行在 CKB-VM 上, 因此如何让 CKB-VM 本身执行的更快, 也是提升程序运行效率的关键点.

B 扩展指令集中的 B 是 Bit Manipulation 的意思, 即"位操作". RISC-V 的 B 扩展指令集可以提高 CKB-VM 处理位操作的能力, 典型的位操作包括前导 0 计数, 循环移位等.

我将向你们展示几个不同版本的前导 0 计数算法版本, 来说明将 B 扩展指令集引入 CKB-VM 的意义. 首先解释一下什么叫做前导 0 计数, 它非常的简单, 它将一个数字作为二进制看待, 并统计数字的开头有多少个零. 例如: 数字 12345678 的前导 0 个数为:

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

我们要编写前导 0 计数的算法. 我认为这很简单, 绝大部分程序员能在一分钟内写出来. 最直观的一种做法是我们写一个循环, 每次将数字左移一位, 然后判断数字的最高位是否为 0 即可.

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;
}

前导 0 计数在许多加密算法中都是经常被使用的一种功能, 我们不经要思考: 是否有方法可以让它跑的更快呢? 在生活中, 如果我们想更快的完成一件事, "二分法"通常是一个不错的选择. 它的原理是将一个复杂的事情分成两个较为简单的事情, 然后继续对任务做分割, 直到任务不可再分割为止.

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 条左右的指令. 当然还有一些方法可以进一步对以上的算法进行提速, 例如使用查表法: 这是很经典的空间换时间的做法.

对此我想要更进一步: 我是说, 既然前导 0 计数的应用如此的广泛, 为什么不能在指令集层面直接提供这个运算呢? RISC-V 有许多指令集, 它们被分为基础指令集和扩展指令集, 其中前导 0 计数就被包含在 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;
}

完整的 B 扩展指令集提供了 43 条新的指令, 可阅读文档了解更多. 总的来说, 如果你有位操作的需求的话, 那么使用 B 扩展指令集能带来一个数量级以上的性能提升.