A SIMD-accelerated Adler-32 rolling hash algorithm implementation.

Marvin Countryman

Last update: Dec 19, 2022

Related tags

Overview

simd-adler32

A SIMD-accelerated Adler-32 rolling hash algorithm implementation.

Features

No dependencies
Support no_std (with default-features = false)
Runtime CPU feature detection (when std enabled)
Blazing fast performance on as many targets as possible (currently only x86 and x86_64)
Default to scalar implementation when simd not available

Quick start

Cargo.toml

[dependencies]
simd-adler32 = "*"

example.rs

use simd_adler32::Adler32;

let mut adler = Adler32::new();
adler.write(b"rust is pretty cool, man");
let hash = adler.finish();

println!("{}", hash);
// 1921255656

Support

CPU Features

impl	arch	feature
✅	`x86`, `x86_64`	avx512
✅	`x86`, `x86_64`	avx2
✅	`x86`, `x86_64`	ssse3
✅	`x86`, `x86_64`	sse2
🚧	`arm`, `aarch64`	neon
	`wasm32`	simd128

MSRV 1.36.0**

Minimum supported rust version is tested before a new version is published. [**] Feature const-generics needs to disabled to build on rustc versions <1.51 which can be done by updating your dependency definition to the following.

Cargo.toml

[dependencies]
simd-adler32 = { version "*", default-features = false, features = ["std"] }

Performance

Benchmarks listed display number of randomly generated bytes (10k / 100k) and library name. Benchmarks sources can be found under the bench directory. Crates used for comparison are adler and adler32.

Windows 10 Pro - Intel i5-8300H @ 2.30GHz

name	avg. time	avg. thrpt
10k/simd-adler32	212.61 ns	43.805 GiB/s
10k/wuffs	3843 ns	2.63 GiB/s*
10k/adler32	4.8084 us	1.9369 GiB/s
10k/adler	17.979 us	530.43 MiB/s
-----------------------	---------------	------------------
100k/simd-adler32	2.7951 us	33.320 GiB/s
100k/wuffs	34733 ns	2.6814 GiB/s*
100k/adler32	48.488 us	1.9207 GiB/s
100k/adler	178.36 us	534.69 MiB/s

* wuffs ran using mingw64/gcc, ran with wuffs bench -ccompilers=gcc -reps=1 -iterscale=300 std/adler32.

MacBookPro16,1 - Intel i9-9880H CPU @ 2.30GHz

name	avg. time	avg. thrpt
10k/simd-adler32	200.37 ns	46.480 GiB/s
10k/adler32	4.1516 us	2.2433 GiB/s
10k/adler	10.220 us	933.15 MiB/s
-----------------------	---------------	------------------
100k/simd-adler32	2.3282 us	40.003 GiB/s
100k/adler32	41.130 us	2.2643 GiB/s
100k/adler	83.776 us	534.69 MiB/s

Safety

This crate contains a significant amount of unsafe code due to the requirement of unsafe for simd intrinsics. Fuzzing is done on release and debug builds prior to publishing via afl. Fuzzy tests can be found under fuzz the directory.

Resources

LICENSE - MIT
CHANGELOG

Credits

Thank you to the contributors of the following projects.

Contributing

Feel free to submit a issue or pull request. 😄

The labs of Raft consensus algorithm based on MadSim.

MadRaft The labs of Raft consensus algorithm based on MadSim. Some codes are derived from MIT 6.824 and PingCAP Talent Plan: Raft Lab. Thanks for thei

48 Dec 28, 2022

Maximum Relevance - Minimum redundancy feature selection algorithm

mrmr Maximum Relevance - Minimum redundancy feature selection algorithm implemented in Rust. Usage CLI app. It gets input from a csv dataset with head

2 Jan 1, 2022

Example of a genetic algorithm in Rust and Python

Example of a genetic algorithm in Rust and Python Monkey typewriter Finding the phrase 'To be or not to be. That is the question.' Inspired by the exa

2 Jan 27, 2022

hubpack is an algorithm for converting Rust values to bytes and back.

hubpack is an algorithm for converting Rust values to bytes and back. It was originally designed for encoding messages sent between embedded programs. It is designed for use with serde.

6 Nov 11, 2022

Library that implements different versions of PPMD algorithm (compress and decompress)

ppmd-rs Library that implements different versions of PPMD algorithm (compress and decompress) Dependencies Rust 1.58 or newer Cargo How to build Clon

3 Jun 20, 2022

Online algorithm for mean and variance, with support for uneven weights

welford Online algorithm for mean and variance, with support for uneven weights. This implements the Welford's online algorithm for computing mean and

1 Sep 8, 2022

Welcome to our bird training simulator! Here you can observe the birds in real time, and use the genetic algorithm to train them to fly and eat food. Through the process of natural selection, this allows the best birds to survive and evolve over generations.

Flyoff Flyoff is a project that uses Rust and WebAssembly (WASM) to train virtual birds to get the most food using a genetic algorithm and a custom ne

3 Jan 18, 2023

Rust implementation of real-coded GA for solving optimization problems and training of neural networks

revonet Rust implementation of real-coded genetic algorithm for solving optimization problems and training of neural networks. The latter is also know

19 Aug 11, 2022

Raft implementation in Rust

rsraft Raft implementation in Rust. The aim of this project is implementing the Raft Consensus Algorithm as described in the paper, with the goal of f

42 Dec 24, 2022

Comments

Release 0.3.3
Features

from_checksum: add Adler32::from_checksum

Performance Improvements

scalar: improve scalar performance by 90-600%

Defer modulo until right before u16 overflow
opened by mcountryman 0
Rolling hash support

A requirement of support rolling hashes is the ability to remove old bytes. Can this crate in any way provide that? Are the SIMD implementations prohibiting this? Is it just faster to re-calculate the entire hash instead? Thanks for this incredible code!

opened by Icelk 2
Implement Neon SIMD

This ports the WASM algorithm over to Aarch64 / ARM Neon. Rust itself isn't quite ready yet, but this should start compiling soon.

Blocked on: https://github.com/rust-lang/stdarch/pull/1230

opened by CryZe 4