README
¶
bp128
Package bp128 implements SIMD-BP128 integer encoding and decoding. It requires an x86_64/AMD64 CPU that supports SSE2 instructions.
For the original C++ version and other fast encoding and decoding schemes see this.
Installation
go get github.com/robskie/bp128
API Reference
Godoc documentation can be found here.
Benchmarks
I used a Core i5 2415M (2.3GHz) with 8GB DDR3-1333 RAM for these benchmarks. For the test data, I generated 2^20 32-bit clustered integers in the range [0, 2^29) by following these instructions. These clustered integers are then grouped into 256KiB chunks before being fed into an encoder/decoder. The resulting encoding/decoding speed is measured in millions of integers per second (mis).
You can run these benchmarks by running these commands in terminal.
cd $GOPATH/src/github.com/robskie/bp128/benchmark
go run benchmark.go
Here are the results.
BenchmarkPack32 894 mis
BenchmarkUnPack32 2279 mis
BenchmarkDeltaPack32 1163 mis
BenchmarkDeltaUnPack32 3443 mis
BenchmarkPack64 511 mis
BenchmarkUnPack64 1596 mis
BenchmarkDeltaPack64 577 mis
BenchmarkDeltaUnPack64 2265 mis
Documentation
¶
Overview ¶
Package bp128 implements SIMD-BP128 integer encoding and decoding. It requires an x86_64/AMD64 CPU that supports SSE2 instructions.
For more details on SIMD-BP128 algorithm see "Decoding billions of integers per second through vectorization" by Daniel Lemire, Leonid Boytsov, and Nathan Kurz at http://arxiv.org/pdf/1209.2137
For the original C++ implementation visit https://github.com/lemire/SIMDCompressionAndIntersection.
Index ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func MakeAlignedSlice ¶
func MakeAlignedSlice(length int, dst interface{})
MakeAlignedSlice loads a 16-byte aligned slice to dst. dst must be a pointer to an integer slice.
func Unpack ¶
func Unpack(in *PackedInts, out interface{})
Unpack decompresses the given packed integers. The out parameter should be a pointer to an integer slice that has the same type as the one used when packing. If out is not aligned or has insufficient length to store the unpacked integers, out will be extended to an aligned slice before unpacking. To prevent this, create an aligned slice by calling MakeAlignedSlice and used in.Len() as the length parameter.
Types ¶
type PackedInts ¶
type PackedInts struct {
// contains filtered or unexported fields
}
PackedInts represents compressed integers.
func DeltaPack ¶
func DeltaPack(in interface{}) *PackedInts
DeltaPack compresses a given integer slice using differential coding. Aside from the input requirements of PackInts, the input slice should also be in ascending order.
func Pack ¶
func Pack(in interface{}) *PackedInts
Pack compresses a given integer slice. It accepts []int, []uint, []int64, []uint64, []int32, and []uint32 slices. If in is not aligned, it will be copied to a new aligned slice before packing. To prevent this, use MakeAlignedSlice and put the values in the created slice before calling Pack.
func (*PackedInts) GobDecode ¶
func (p *PackedInts) GobDecode(data []byte) error
GobDecode allows gob decoding of packed integers.
func (*PackedInts) GobEncode ¶
func (p *PackedInts) GobEncode() ([]byte, error)
GobEncode allows gob encoding of packed integers.
func (*PackedInts) Size ¶
func (p *PackedInts) Size() int
Size returns the compressed size in bytes.
Source Files
Directories