A bit vector with the Rust standard library's portable SIMD API

Chojan Shang

Last update: Dec 21, 2022

Related tags

Overview

`bitsvec`

A bit vector with the Rust standard library's portable SIMD API

Usage

Add bitsvec to Cargo.toml:

bitsvec = "x.y.z"

Write some code like this:

let mut bitvec = BitVec::ones(1000); // create a bitvec contains 0 ..= 999
bitvec.set(900, false); // delete 900 from bitvec
bitvec.set(1200, true); // add 1200 to bitvec (and expand bitvec to length 1201)
let bitvec2 = BitVec::ones(1000);

let new_bitvec = bitvec.and_cloned(&bitvec2); // and operation, without consume
let new_bitvec2 = bitvec & bitvec2; // and operation, consume both bitvec

// Operation Supported:
// and, or, xor, not, eq, eq_left

assert_eq!(new_bitvec, new_bitvec2);

Performance

Compared on AMD Ryzen 9 5900hs, aginst:

$ cargo bench

bitsvec(this crate)     time:   [330.34 ns 330.75 ns 331.18 ns]
Found 6 outliers among 100 measurements (6.00%)
  4 (4.00%) high mild
  2 (2.00%) high severe

bitsvec_u16x8(this crate)
                        time:   [332.23 ns 333.90 ns 335.98 ns]
Found 16 outliers among 100 measurements (16.00%)
  6 (6.00%) high mild
  10 (10.00%) high severe

bitvec_simd 0.15.0      time:   [371.96 ns 372.23 ns 372.53 ns]
Found 6 outliers among 100 measurements (6.00%)
  4 (4.00%) high mild
  2 (2.00%) high severe

bitvec_simd 0.15.0 u16x8
                        time:   [578.38 ns 578.68 ns 579.01 ns]
Found 7 outliers among 100 measurements (7.00%)
  6 (6.00%) high mild
  1 (1.00%) high severe

bitvector_simd 0.2.2    time:   [288.55 ns 289.11 ns 289.64 ns]
Found 1 outliers among 100 measurements (1.00%)
  1 (1.00%) high mild

bit-vec 0.6             time:   [1.5177 us 1.5200 us 1.5224 us]

bitvec 1.0              time:   [32.119 us 32.254 us 32.390 us]

bitsvec(this crate) with creation
                        time:   [888.59 ns 889.45 ns 890.39 ns]
Found 10 outliers among 100 measurements (10.00%)
  9 (9.00%) high mild
  1 (1.00%) high severe
                                                                                                              bitsvec_u16x8(this crate) with creation
                        time:   [1.1006 us 1.1031 us 1.1059 us]
Found 11 outliers among 100 measurements (11.00%)
  8 (8.00%) high mild
  3 (3.00%) high severe

bitvec_simd 0.15.0 with creation
                        time:   [970.09 ns 970.82 ns 971.67 ns]
Found 12 outliers among 100 measurements (12.00%)
  10 (10.00%) high mild
  2 (2.00%) high severe
                                                                                                              bitvec_simd 0.15.0 u16x8 with creation
                        time:   [1.1158 us 1.1185 us 1.1215 us]
Found 8 outliers among 100 measurements (8.00%)
  6 (6.00%) low mild
  2 (2.00%) high mild

bitvector_simd 0.2.2 with creation
                        time:   [736.46 ns 737.95 ns 739.49 ns]
Found 1 outliers among 100 measurements (1.00%)
  1 (1.00%) high severe

bit-vec 0.6 with creation
                        time:   [1.6515 us 1.6527 us 1.6539 us]
Found 2 outliers among 100 measurements (2.00%)
  2 (2.00%) high mild

bitvec 1.0 with creation
                        time:   [28.484 us 28.501 us 28.518 us]
Found 20 outliers among 100 measurements (20.00%)
  15 (15.00%) low severe
  3 (3.00%) high mild
  2 (2.00%) high severe

bitsvec(this crate) resize false
                        time:   [676.30 ns 677.13 ns 677.93 ns]
                                                                                                              bitsvec_u16x8(this crate) resize false
                        time:   [618.70 ns 619.73 ns 620.98 ns]
Found 2 outliers among 100 measurements (2.00%)
  1 (1.00%) high mild
  1 (1.00%) high severe

bitvec_simd 0.15.0 resize false
                        time:   [676.27 ns 677.96 ns 679.66 ns]
Found 4 outliers among 100 measurements (4.00%)
  3 (3.00%) high mild
  1 (1.00%) high severe

bitvec_simd 0.15.0 u16x8 resize false
                        time:   [472.84 ns 473.76 ns 474.71 ns]
Found 2 outliers among 100 measurements (2.00%)
  2 (2.00%) high mild

bitvec 1.0 resize false time:   [108.23 us 108.29 us 108.36 us]
Found 9 outliers among 100 measurements (9.00%)
  6 (6.00%) high mild
  3 (3.00%) high severe

bitsvec(this crate) resize true
                        time:   [679.71 ns 680.66 ns 681.75 ns]
Found 9 outliers among 100 measurements (9.00%)
  7 (7.00%) high mild
  2 (2.00%) high severe

bitsvec_u16x8(this crate) resize true
                        time:   [876.21 ns 876.89 ns 877.71 ns]
Found 8 outliers among 100 measurements (8.00%)
  6 (6.00%) high mild
  2 (2.00%) high severe

bitvec_simd 0.15.0 resize true
                        time:   [672.44 ns 672.82 ns 673.24 ns]
Found 9 outliers among 100 measurements (9.00%)
  6 (6.00%) high mild
  3 (3.00%) high severe

bitvec_simd 0.15.0 u16x8 resize true
                        time:   [748.77 ns 751.48 ns 754.59 ns]

bitvec 1.0 resize true  time:   [100.50 us 100.63 us 100.75 us]

Credits

Most code of this crate is from (https://github.com/GCCFeli/bitvec_simd). On top of that, some changes were made.

License

This library is licensed under either of:

MIT license LICENSE-MIT or http://opensource.org/licenses/MIT
Apache License 2.0 LICENSE-APACHE or https://opensource.org/licenses/Apache-2.0

at your option.

sparse linear algebra library for rust

sprs, sparse matrices for Rust sprs implements some sparse matrix data structures and linear algebra algorithms in pure Rust. The API is a work in pro

311 Dec 18, 2022

DataFrame / Series data processing in Rust

black-jack While PRs are welcome, the approach taken only allows for concrete types (String, f64, i64, ...) I'm not sure this is the way to go. I want

30 Dec 10, 2022

A Modern Real-Time Data Processing & Analytics DBMS with Cloud-Native Architecture, written in Rust

Datafuse Modern Real-Time Data Processing & Analytics DBMS with Cloud-Native Architecture Datafuse is a Real-Time Data Processing & Analytics DBMS wit

5k Jan 4, 2023

(MERGED) Rust bindings for TVM runtime

DEPRECATED The RFC is closed and this has been merge into TVM. TVM Runtime Frontend Support This crate provides an idiomatic Rust API for TVM runtime

26 Sep 29, 2022

ConnectorX - Fastest library to load data from DB to DataFrames in Rust and Python

ConnectorX enables you to load data from databases into Python in the fastest and most memory efficient way.

939 Jan 5, 2023

Fill Apache Arrow record batches from an ODBC data source in Rust.

arrow-odbc Fill Apache Arrow arrays from ODBC data sources. This crate is build on top of the arrow and odbc-api crate and enables you to read the dat

21 Dec 27, 2022

A new arguably faster implementation of Apache Spark from scratch in Rust

vega Previously known as native_spark. Documentation A new, arguably faster, implementation of Apache Spark from scratch in Rust. WIP Framework tested

2.1k Jan 5, 2023

Work out how to read Parquet files in a browser using web assembly (via the Rust toolchain)

wasm-pack-template A template for kick starting a Rust and WebAssembly project using wasm-pack. Tutorial | Chat Built with 🦀 🕸 by The Rust and WebAs

5 Oct 11, 2022

bspipe A Rust implementation of Bidirectional Secure Pipe

2 Nov 14, 2022

Releases(v0.1.1)

v0.1.1(Feb 15, 2022)
A bit vector with the Rust standard library's portable SIMD API.

support u64x8

benchmark with other simd bitvec

more clarity

Source code(tar.gz)
Source code(zip)
v0.1.0(Feb 13, 2022)
A bit vector with the Rust standard library's portable SIMD API.

no std

portable SIMD with core::simd

Source code(tar.gz)
Source code(zip)