0%

Bitmap实现过程中的一些思考

发表于 更新于

前段时间为了做一个分享，实现了一个简单的搜索引擎（https://github.com/imaben/ts-engine), 其中有一个标记删除的地方用到了bitmap，刚开始没有想那么复杂，真正写起来，发现需要注意的一些细节还是不少的，所以在此记录一下开发过程中的一些心得，主要是一些位运算相关的点。

代码链接：https://github.com/imaben/ts-engine/blob/master/bitmap.h

首先说一下bitmap的原理，bitmap的应用非常广泛，它通常是以bit位来标记某个id的状态，优点是占用空间小，查询效率高，1byte = 8bit，假如一共1000万的数据量，总共算下来占用的空间也只有 10000000/8/1024 = 1220KB, 刚刚有1MB多一点。查询时直接根据id来找到对应的byte，然后做位于运算，直接可以拿到结果，由于不涉及到复杂运算，寻址的范围也很小，所以整体的查询效率非常高。

但这种方式本身也有局限性，就是要标记的id最好是从1开始自增的情况，如果id完全没有规律，则很容易出现内存空洞的情况。

bitmap结构体的定义如下：

1
2
3
4
typedef struct {
    uint8_t *c;
    uint64_t l;
} ts_bitmap_t;

结构体本身比较简单，一个uint8_t(char)类型的指针，指向一块保存bitmap数据的内存，一个uint64_t类型的长度，用来标记c的长度。有一些做法是采用int型指针来保存数据，但在跨平台时，可能要考虑大小端的问题，但个人感觉没有本质上的区别。

第一步要做的就是要保证每次set时c的长度是足够的，所以需要在每次set时，都需要检查一下c的长度，以防止内存访问越界的情况发生。但是为了减少内存频繁分配的开销，一般都会有一些预分配的做法，比如按照128字节做对齐，当小于128字节时，也分配128字节的大小，当是129字节时，就分配256字节，以此类推。这样做有两点好处，一是避免递增访问时，内存频繁分配，二是保证整个buffer的内存大小总是cpu cacheline的整倍数，从而提高cpu缓存的存取性能。

首先要实现上面提到的预分配逻辑：假如按照比较传统的写法应该是这样(伪代码)：

1
2
3
4
5
6
7
8
9
10
#define PREALLOC 128
int mem_align(int size) {
    if (size <= PREALLOC) {
        return PREALLOC;
    }
    // 求size是PREALLOC的多少倍
    // 向上取整并乘以PREALLOC
    int multiple = ceil(size / PREALLOC);
    return multiple * PREALLOC;
}

但这样显然不太优雅，性能上开销也比较大，如果通过位运算来解决呢？
举两个例子，假如有10和129，我们需要最终转换为128和256，如下表：

10进制 2进制 目标2进制
10 00001010 10000000
129 10000001 100000000

拿10来举例，既然要做128字节对齐，我们不妨先把它加个128：

1
10 + 128 = 138 = 10001010

跟我们的目标值已经很像了，我们只需要把最高位1后面的所有的非0，全部置为0就达到目的了，可以使用反码加位与的操作解决，如下：

1
2
3
4
5
128 - 1 = 01111111 // 先将需要置为0的位数全部置为1

~(128 - 1) = 11111111 11111111 11111111 10000000 // 按位取反，以32位整数为例

(10 + 128) & (~128 - 1) = 10000000 // 成功转换

但是这个地方有一个极端情况，就是当值正好是128时，用上面的算法算出来就是256了，所以再处理一下就是

1
(10 + 128 - 1) & (~128 - 1)

这样就解决了上面所说的问题。

最终预分配的代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#ifndef TS_BITMAP_PREALLOC
#define TS_BITMAP_PREALLOC 128LL
#endif

#define ts_bmp_align(s) ((s + TS_BITMAP_PREALLOC - 1) & ~(TS_BITMAP_PREALLOC - 1))

#define ts_bitmap_reserve(bm, n) { \
    if ((n) > ((bm)->l)) {  \
        uint64_t __len = ts_bmp_align(n); \
        (bm)->c = ts_realloc((bm)->c, __len); \
        assert((bm)->c != NULL); \
        bzero((void *)((bm)->c + (bm)->l), __len - (bm)->l); \
        (bm)->l = __len; \
    } \
}

小细节：

在上面按位取反的时候，需要注意32位与64位的问题，假如有以下函数：

1
2
3
4
uint64_t mem_align(uint64_t i, int align)
{
        return (i + align - 1) & ~(align - 1);
}

看似很和谐，其实隐藏着一个大坑，我们将这段代码编译成汇编（GCC），生成如下代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
_mem_align:                             ## @mem_align
        .cfi_startproc
## %bb.0:
        push    rbp
        .cfi_def_cfa_offset 16
        .cfi_offset rbp, -16
        mov     rbp, rsp
        .cfi_def_cfa_register rbp
        mov     qword ptr [rbp - 8], rdi
        mov     dword ptr [rbp - 12], esi
        mov     rdi, qword ptr [rbp - 8]
        movsxd  rax, dword ptr [rbp - 12]
        add     rdi, rax
        sub     rdi, 1
        mov     esi, dword ptr [rbp - 12]
        sub     esi, 1
        xor     esi, -1
        movsxd  rax, esi
        and     rdi, rax
        mov     rax, rdi
        pop     rbp
        ret
        .cfi_endproc
                                        ## -- End function
        .globl  _main                   ## -- Begin function main
        .p2align        4, 0x90

可以看到在15行至17行在对align做-1并取反的操作中，竟然是在32位寄存器中进行的，这样就会导致当i的值超过32位时，取反后的结果总是等于0，进而得到的结果也会是0，解决办法很简单，就是把align的类型也改为64位即可。
这种情况不同编译器可能会有不同的行为，所以为了稳妥起见，故在定义128长度的时候，改成了64位的128LL。

—–分割线—–

解决完内存的问题，再看一下怎么根据id定位到id应该存储的byte上，因为1byte = 8bit，所以也就是单纯的除以8即可，用位运算操作数右移三位即可：

1
#define ts_bmp_dig(p) ((p) >> 0x3)

找到了对应的字节，再要在字节中找到每N位，直接对8取模即可：

首先8的二进制为1000，模除只需要将二进制后三位置为1，再与操作数做位与操作：

1
#define ts_bmp_mod(p) ((p) & 0x7)

需要注意的是这种方式只有在模除数是2的n次方时有效。

—–分割线—–

下面就是操作set、unset和get了，set最简单：

1
2
3
4
#define ts_bitmap_set(bm, p) { \
    ts_bitmap_reserve(ts_bitmap_p(bm), ts_bmp_dig(p) + 1); \
    ts_bitmap_p(bm)->c[ts_bmp_dig(p)] |= (1 << ts_bmp_mod(p)); \
}

直接通过dig找到对应byte后，将1左移取模后的第n位，做位或操作即可。

unset操作如下：

1
2
3
#define ts_bitmap_unset(bm, p) { \
    if (ts_bmp_dig(p) < (bm)->l) ts_bitmap_p(bm)->c[ts_bmp_dig(p)] &=  ~(1 << (ts_bmp_mod(p))); \
}

先判断如果unset操作数的所在的字节已经超过buffer的总长度，直接忽略。
然后为了在unset时不影响当前byte的其它位，故需要左移后做个取反，再与原数做位于操作。

get操作如下：

1
2
#define ts_bitmap_get(bm, p) ((ts_bmp_dig(p) >= ((ts_bitmap_p(bm))->l) ? 0 : \
            ((ts_bitmap_p(bm)->c[ts_bmp_dig(p)]) >> ts_bmp_mod(p))) & 1)

和unset一样做一个长度的基本判断，然后按照对应byte，将对应的bit右移到最后一位，与1做位于操作。

至此，bitmap的实现完成。