Golang高性能零分配SIMD位图/位集处理插件库bitmap的使用

简介

这是一个高性能的位图(Bitmap/Bitset)实现，底层使用[]uint64切片，专为密集的小型或中型集合设计。该实现通过避免堆分配、展开循环和在汇编中实现SIMD向量化来追求高性能。

主要特性

• 所有重要方法都优化为零堆分配
• 使用**向量化指令(SIMD)**优化某些操作如布尔代数
• 支持布尔代数运算，非常适合实现位图索引
• 支持位计数操作如Min()、Max()、Count()等
• 支持使用展开循环快速迭代设置为1的位
• 支持基于用户定义谓词的原地过滤
• 支持二进制编码，可读写且有无拷贝的切片转换
• 通过提供Clone()和Clear()操作支持可重用性

使用示例

基本使用

import "github.com/kelindar/bitmap"

func main() {
    var books bitmap.Bitmap
    
    // 设置位
    books.Set(300)      // 设置第300位为1
    books.Set(400)      // 设置第400位为1
    books.Set(600)      // 设置第600位为1(自动调整大小)
    
    // 检查位
    has300 := books.Contains(300) // 返回true
    has301 := books.Contains(301) // 返回false
    
    // 清除位
    books.Remove(400)   // 清除第400位
    
    // 最小/最大/计数
    min, ok := books.Min() // 返回300
    max, ok := books.Max() // 返回600
    count := books.Count() // 返回2
    
    // 布尔代数
    var other bitmap.Bitmap
    other.Set(300)
    books.And(other)      // 交集
    count = books.Count() // 现在返回1
}

布尔代数示例

// 假设我们有三个位图
books := bitmapFor("books")           // 所有书籍
recent := bitmapFor("books_recent")    // 最近出版的书籍
ebooks := bitmapFor("books_has_ebook") // 有电子书的书籍

// 找出最近出版且有电子书的书籍
books.And(recent)
books.And(ebooks)

单一位操作

var books bitmap.Bitmap

books.Set(3)                 // 设置第3位为'1'
hasBook := books.Contains(3) // 返回'true'
books.Remove(3)              // 设置第3位为'0'

位计数和搜索

// 计算设置为'1'的位数
numBooks := books.Count()

// 查找第一个和最后一个设置为1的位
min, ok := books.Min() // 第一个设置为1的位
max, ok := books.Max() // 最后一个设置为1的位

// 查找第一个和最后一个设置为0的位
minZero, ok := books.MinZero()
maxZero, ok := books.MaxZero()

迭代和过滤

// 迭代位图中的位
books.Range(func(x uint32) bool {
    println(x)
    return true // 返回false停止迭代
})

// 过滤位图 - 只保留偶数位
books.Filter(func(x uint32) bool {
    return x % 2 == 0
})

性能基准

以下基准测试是在一个预分配的100,000元素位图上运行的，大约50%的位设置为1。

cpu: Intel(R) Core(TM) i7-9700K CPU @ 3.60GHz
BenchmarkBitmap/set-8         552331321    4.319 ns/op    0 B/op    0 allocs/op
BenchmarkBitmap/remove-8     1000000000    1.621 ns/op    0 B/op    0 allocs/op
BenchmarkBitmap/contains-8   1000000000    1.309 ns/op    0 B/op    0 allocs/op
BenchmarkBitmap/clear-8        26083383    90.45 ns/op    0 B/op    0 allocs/op
BenchmarkBitmap/ones-8          6751939    347.9 ns/op    0 B/op    0 allocs/op
BenchmarkBitmap/min-8         757831477    3.137 ns/op    0 B/op    0 allocs/op
BenchmarkBitmap/max-8        1000000000    1.960 ns/op    0 B/op    0 allocs/op
BenchmarkBitmap/min-zero-8    776620110    3.081 ns/op    0 B/op    0 allocs/op
BenchmarkBitmap/max-zero-8   1000000000    1.536 ns/op    0 B/op    0 allocs/op
BenchmarkBitmap/count-8         6071037    382.5 ns/op    0 B/op    0 allocs/op
BenchmarkBitmap/count-to-8     82777459    28.85 ns/op    0 B/op    0 allocs/op
BenchmarkBitmap/clone-8        20654008    111.5 ns/op    0 B/op    0 allocs/op
BenchmarkBitmap/and-8          16813963    143.6 ns/op    0 B/op    0 allocs/op
BenchmarkBitmap/andnot-8       16961106    141.9 ns/op    0 B/op    0 allocs/op
BenchmarkBitmap/or-8           16999562    141.7 ns/op    0 B/op    0 allocs/op
BenchmarkBitmap/xor-8          16954036    144.7 ns/op    0 B/op    0 allocs/op
BenchmarkRange/range-8            18225   131908 ns/op    0 B/op    0 allocs/op
BenchmarkRange/filter-8           25636    93630 ns/op    0 B/op    0 allocs/op

完整示例

package main

import (
	"fmt"
	"github.com/kelindar/bitmap"
)

func main() {
	// 创建一个位图
	var bm bitmap.Bitmap

	// 设置一些位
	bm.Set(1)
	bm.Set(3)
	bm.Set(5)
	bm.Set(7)
	bm.Set(300) // 自动扩展

	// 检查位
	fmt.Println("Contains 1:", bm.Contains(1)) // true
	fmt.Println("Contains 2:", bm.Contains(2)) // false

	// 计数
	fmt.Println("Count:", bm.Count()) // 5

	// 最小/最大
	min, _ := bm.Min()
	max, _ := bm.Max()
	fmt.Println("Min:", min, "Max:", max) // Min: 1 Max: 300

	// 迭代
	fmt.Println("Iterating:")
	bm.Range(func(x uint32) bool {
		fmt.Println(x)
		return true
	})

	// 布尔运算
	var other bitmap.Bitmap
	other.Set(3)
	other.Set(5)
	other.Set(100)

	// 交集
	bm.And(other)
	fmt.Println("After AND, count:", bm.Count()) // 2 (3 and 5)

	// 克隆
	clone := bm.Clone()
	fmt.Println("Clone count:", clone.Count()) // 2

	// 清除
	bm.Clear()
	fmt.Println("After clear, count:", bm.Count()) // 0
}

这个库非常适合需要高性能位操作的场景，特别是作为索引或过滤大量数据时。