bitproto 最近的开发笔记

最近对 bitproto 做了两项改进:

  1. 支持任意比特位数的有符号整数的编解码
  2. 提升 C 语言常规模式的编解码性能

本文是对这两项的开发笔记,以便日后回忆。

任意 int{n} 的支持

原本 bitproto 只支持整数个字节大小的有符号类型,也就是只支持 int8, int16, int32int64, 我和嵌软同学们的开发经历中,也很少会用到负数。 最近一位外国朋友发邮件过来,说 WNK8010 传感器返回的压力和温度数值都是 24bit 大小的。 希望 bitproto 可以支持任意比特大小的有符号整数, 就是说,需要支持形如以下的 bitproto 定义:

message X {
    int24 data = 1;
}

我们知道,有符号整数的最高位是符号位,对于一个整数,要想在编码后成功在解码端读出正确数值, 那么必须在拷贝比特时带上符号位,简而言之,必须在编解码时照顾到符号位

此前,int8/16/32/64 之所以可以 work,在于 bitproto 恰好把符号位照顾到了。

比如下面这个 bitproto 定义:

message X {
    int32 data = 1;
}

假如 data 的数值是 -11,其二进制表示为(高位在左侧,8 位一组):

11111111 11111111 11111111 11110101
^
符号位

在编码时,bitproto 会把 data32 个比特全部拷贝到目标 buffer 中。在解码时, bitproto 也恰好把 32 个比特拷贝到了目标变量的内存 buffer 上,所以符号位最终回到了最高位, 以 int32_t 类型去读这块内存,解析结果就是正确的。

// 编码时,符号位被拷贝到 s 了
struct X x = {.data = -11};
unsigned char s[BYTES_LENGTH_X] = {0};
EncodeX(&x, s);

// 解码时,符号位正好被拷贝到字段 `x1.data`
struct X x1 = {0};
DecodeX(&x1, s);
// x1.data 表示为 int32 就恰好是 -11
x1.data  // => -11

也就是说,bitproto 只忠实地拷贝比特,并没有特殊的照顾符号位。int32 可以 work 是因为恰好把符号位也拷贝了。

而对于 24bit 大小的 -11,bitproto 在编解码时却没有照顾到最高位的符号:

  1. 编码时,只拷贝了低 24 位:

    11111111 11111111 11111111 11110101
    ^        +------------------------+
    符号            低 24 位
    
  2. 解码时,同样是拷贝 24 位,高 8 位则自然留 0, 因此得到 16777205, 而非 -11

    00000000 11111111 11111111 11110101
    ^        +------------------------+
    符号             拷贝的 24 bit
    

也即, int24 这种 “不规整” 的有符号整数,符号位在拷贝时被忽视了,自然解码就会出错

正如 int8 类型的整数的表达范围是 -128~127 那样,按照默契, int24 类型的整数的表达范围,应该是 -2^23 ~ 2^23-1,也就是 -8388608 ~ 8388607

那么,应该把第 24 位视作符号位。 确切说,高 9 位都是符号标志: 

11111111 11111111 11111111 11110101
         ^
        符号

bitproto 在编码时,本来就会把第 24 位带上拷贝走,那么我们只需要关注解码端逻辑就行。 就是说,要关注如何在解码时,把高 9 位全部还原到符号标志

具体说,拿到错误的 16777205 后,如何修正其高 8 位符号,变为正确的 -11 ?

一个直接的思路是, 借助 算术右移 的符号位传播 (sign-propagation) 的特点, 先左移 8 位,再右移 8 位:

16777205 << 8 >> 8

详细的说明是:

// 最开始的数字 16777205
00000000 11111111 11111111 11110101
         ^

// 左移 8 位后, 符号来到最高位, 数字变为 -2816
11111111 11111111 11110101 00000000
^

// 再右移 8 位,左侧补 1, 数字变为 -11
11111111 11111111 11111111 11110101
         ^

与算术右移相对的是逻辑右移,不同点在于, 算术右移时会按最高位符号位补充高位,而逻辑右移会用 0 来填充。 这两种右移方式,对于非负数没什么区别,但对于负数,结果则是不同的。

从字面上理解,之所以叫做 “算术” 右移,是因为中间结果 -2816 除以 2^8,也就是除以 82, 就得到 -11 的结果,算术位移会遵循算术含义,右移一位就是除以 2,所以符号也不会变

这个思路看起来挺简洁的,不过,算术右移 or 逻辑右移是编译器实现决定的,C 标准并没有做要求。 所以,不可完全地假设算术右移存在,这个思路的可移植性没有那么强,虽然大部分 C 编译器是算术右移的。

于是,对于 C 语言,我选了另一个 “稍笨” 但是可移植的思路。

值得一提,Go 语言是算术右移的,所以 16777205 << 8 >> 8 的思路在 Go 语言的 bitproto 编解码中得到了应用。

稍微 “安全” 点的思路是非常朴素的,假设 V = 16777205

  1. 查看第 24 位符号标志。

    具体来说,安全地右移 23 位, 标志位来到最右端。

    此时如果最后一位是 1 就表示是负数,如果是 0 就是非负数。

    (V >> (24-1)) & 1
    
  2. 如果是负数,才需要处理符号问题。

    ~((1 << 24) - 1) 作为 mask

    // mask 的高 8 位全是 1,低 24 位全是 0
    11111111 00000000 00000000 00000000
    

    结果即 V | mask :

    // 最开始的数字 16777205
    00000000 11111111 11111111 11110101
    
    // 或 上这个 mask
    11111111 00000000 00000000 00000000
    
    // 最终得到下面的 -11
    11111111 11111111 11111111 11110101
    

这个思路避免了对负数的右移操作,因此对 C 语言说,是安全的、确保可移植的。

C 语言编解码性能优化

bitproto 一直有个 “鱼和熊掌,不可兼得” 的无奈现状, 有两种模式存在:

  1. 优化模式:不走 lib 形式, 不支持协议扩展,但是性能极高, 编译后体积可能会大
  2. 常规模式:走 lib 形式, 支持 协议扩展, 但编解码性能不如优化模式, 编译后体积有限

优化模式充分利用了 bitproto 协议固定大小 (Fixed-size) 的特点,在协议编译期预先做了所有编解码的计算, 平铺式地生成了编解码的最终代码, 所以它很快。不过,正是因为完全假定了所有协议消息是固定大小的, 优化模式也不能支持协议的可扩展性。

而我的目的就是希望可扩展性和高性能并存。

两种模式的性能差距还不小。在我的 STM32 板子上,对于 100 字节大小的 bitproto 消息, 两种模式的编解码耗时分别在大约 15μs170μs 左右,差距达十倍有余

虽然常规模式在 Unix 系统中表现的已足够快了,在我的电脑和 Github Action 上的 runner 中, C 语言编解码达到了 <2μs 的耗时, Go 语言编解码达到了 <10μs 的耗时, 对于服务器端、PC 端都是足够快了。

但在 STM32 上和优化模式的性能差距还是太大了,因此我花了两天来进一步探索优化的可能。

我其实并不懂嵌入式,只是和他们合作过。 之前一位嵌软同学(也是 bitproto 的 “粉丝”)教过我如何搭起来 STM32 的开发环境, 我凭着回忆和命令历史,摸索着重新搭了起来。

提到性能优化,我认为,算法思路的优化效果最佳,语言层面的、 trick 优化则次之

这次的性能优化主要有 2 类:

  1. 比特拷贝的性能优化,主要是细节技术优化
  2. 基本类型数组的批量比特拷贝(新思路)

下面展开说一下具体优化点:

  1. uint16/uint32 批量赋值。大概是这个意思:

    // 优化前
    uint32_t v32 = (*((uint32_t *)(src))) >> shift;
    unsigned char *ptr = (unsigned char *)(&v32);
    dst[0] = ptr[0];
    dst[1] = ptr[1];
    dst[2] = ptr[2];
    dst[3] = ptr[3];
    
    // 优化后
    ((uint32_t *)dst)[0] = ((uint32_t *)(src))[0] >> shift;
    
  2. 避免在每一次循环都计算乘法,转为每次累加,大概是这个意思:

    // 优化前
    unsigned char *data;
    
    for (int k = 0; k < cap; k++) {
        // 这里每次都要做一次乘法计算
        void *element_ptr = (void *)(data + k * element_size);
        //...
    }
    
    // 优化后
    element_ptr = data;
    
    for (int k = 0; k < cap; k++) {
        // ...
        element_ptr += element_size;
    }
    
  3. 改进核心比特拷贝的思路 7b1559

    原来单个字节内拷贝比特的思路是:

    // 假设 要拷贝的字节 src 中的 5 个比特到字节 dst 中
    // 拷贝的起始位置 si 是 1, 目标位置 di 是 2.
    
           +---+ 要拷贝的5个比特
    src: 10101011
               ^ 起始位置
    dst: 00000010
              ^ 目标位置
    

    先构造一个 “奇怪” 的 mask :

     +---+  第2到7位全部赋 1
    01111100
         ^ 目标位置 
    

    这个 mask 的意思是,两头儿写 0 的比特位不要,只要 src 字节中间的 5 个比特。

    src 字节视情况左移 or 右移,本例中是左移 1 位和目标字节 dst 对齐。

    // 左移 src 一位, 和 dst 齐
    src: 01010110
              ^ 起始位置
    dst: 00000010
              ^ 目标位置
    

    再拿着这个 mask 和位移后的 src 取与操作,即拷贝出了需要的第 2~7 位的比特:

    src: 01010110
    &  : 01111100
    // 结果
    dst: 01010100
          +---+ 拷贝出的比特,第 2~7 位
    

    以上是之前的老的思路,其 C 语言描述大概是:

    // 优化前
    unsigned char BpSmartShift(unsigned char n, int k) {
        return (k > 0) ? (n >> k) : ((k == 0) ? n : (n << (0 - k)));
    }
    
    int shift = si - di;
    unsigned char mask = (1 << (di + c)) - (1 << di);
    dst |= BpSmartShift(src, shift) & mask;
    

    优化后的思路则更简洁直接,同时省去了一些加减法计算,也更快

    大的思路是不变的,先对齐,再拿 mask 拷贝

    对齐不再做所谓的 BpSmartShift,而是对 src 字节先右移再左移。

    src: 10101011
               ^ 起始位置
    // 右移 1 位,消灭 si 右侧比特
    src: 01010101
                ^
    // 再左移 2 位,对齐目标字节的位置 di
    src: 01010100
              ^
    dst: 00000010
              ^ 目标位置
    

    mask 的构造也更简单,取 0xff 左移两次,再取反:

    // 0xff
    11111111
    // 左移 2 + 5 位, 右侧补零
    10000000
    // 取反
    01111111
    

    这个 mask 和之前的 mask 稍有不同,意思是, 要清除掉高位不需要的比特,本例中是最高位那个。 虽然 src 字节的低 2 位比特我们也不需要,但是它们已经确定是 0 了, 不会污染后续的或运算。

    最后,拿 mask 和位移后的 src 取与操作,即完成拷贝:

    src: 01010100
    &  : 01111100
    dst: 01010100
    

    这个思路用 C 语言描述起来特别简单:

    // 优化后
    dst |= ((src >> si << di) & ~(0xff << di << c));
    
  4. 本次中最激动人心的一个优化点:规整的基本类型数组的编解码优化 (367db7)。

    所谓 “规整的基本类型的数组”,是指例如 uint8/16/32/64[n], int8/16/32/64[n], byte 这种基本的、且整数个字节大小的类型。

    之前 bitproto 编解码的思路是,不断拆解到基本类型的处理,再进入单个字节内的比特拷贝。

    对于一个数组而言,编解码过程(其实就是比特拷贝过程)会被拆解到小颗粒度的基本类型一次一次的进行。 这个过程是非常碎片化的。

    以一个 uint16[5] 类型的数组 V 为例,考虑其编码到 buffer S 的过程:

    之前的做法是 “小碎步” 过程,就是按 uint16 的颗粒度不断调用基本编解码方法 BpEndecode, 所以要调用 5 次。

    而且如果未对齐的话,每一次调用 BpEndecode 方法都会处理对齐问题,产生的小碎片拷贝过程。 虽然 BpEndecode 方法内部已经做了批量拷贝比特的优化,但是其局限在 uint16 大小的 buffer 内不得不先解决对齐问题, 批量化处理能力也十分有限。

    可以看到,如果 VS 没有对齐的话,也就是说目标 buffer S 并不是从最低位开始拷贝比特的话,拷贝过程就会拆成 10 步来完成。

    但是,在 C 语言中基本类型的数组的内存是连续的!

    我们可以直接大批量地按字节、uint16, uint32 来拷贝!

    具体的过程是:

    先把目标 buffer S 的不规整的头部处理一下,拷贝一些碎片比特。

    接下来,尝试按 uint32, uint16 等四字节、双字节的方式,批量赋值拷贝:

    具体来说,就是先用 uint32_t 去读相关的 4 个字节,然后做位移对齐,再进行赋值!

    ((uint32_t *)dst)[0] = ((uint32_t *)(src))[0] >> si;
    c = 32 - si; // 追踪本次拷贝的比特数
    

    同理,按 uint16 双字节批量拷贝是一样的道理:

    最后,处理掉尾部的碎片部分:

    可以看到,对于这个例子而言,只需要 4 次拷贝。

    这个思路,对规整的基本类型的数组有效,例如 uint32[n],因为其内存是连续且无缝隙的。 对于结构体、布尔值则不行,因为虽然仍然是分布在连续内存上,但是其字段、元素之间有无效数据的缝隙。

上面四次优化下来,STM32 开发板上的编解码性能降低为 140μs 左右,开启 -O3 模式时可以达到 123μs

我仍然不满意,因为空间还是很大。

(完)


相关阅读

本文原始链接地址: https://writings.sh/post/bitproto-recent-dev-notes

王超 ·
喜欢这篇文章吗?
微信扫码赞赏
评论 首页 | 归档 | 算法 | 订阅