BaseString

A lightweight Rust library for Base64 encoding and decoding.

Overview

Inspired by a series of joint papers by Wojciech Muła and Daniel Lemire (see [2] and [3]), basestring is a minimalist Rust library designed for fast conversion between raw byte strings and their Base64 representations. It provides two implementations of encoding and decoding algorithms:

• autovectorised: a straightforward, fully safe Rust version serving as a baseline.
• AVX2-optimised: a version using AVX2 intrinsics for increased performance.

The project is primarily educational. To what extent can Rust's compiler leverage strict aliasing rules to autovectorise the naïve algorithm? How does the straightforward approach compare to the finely tuned AVX2 code? The criterion crate has been used for benchmarking.

Performance

A detailed performance analysis is available in a separate PDF file; below is a brief summary. The Rust implementations of the AVX2‐optimised encoding and decoding algorithms outperform the corresponding C code by Daniel Lemire on which they are based. This implementation leverages immutability and scoping to increase the quality of generated assembly. Interestingly, iterating over a byte string using chunks_exact() rather than pointer-delimited slices further improves performance. Only the unchecked (*_unchecked()) algorithms were benchmarked.

Encoding

Encoding was benchmarked on strings of 24, 240, and 1128 bytes. These lengths were deliberately chosen to avoid triggering the fallback to the naïve algorithm for the (size % 24)‐byte remainder, which is not long enough to fill a zero-padded ymm register.

Both autovectorised and AVX2-optimised encoding algorithms exhibit nearly linear performance characteristics with respect to input size.

Decoding

Decoding was benchmarked on strings of 32, 320, and 1504 bytes. These lengths were chosen to avoid benchmarking the fallback for the (size % 32)‐byte remainder, which does not fit a ymm register.

Similar to encoding, the AVX2-optimised decoding algorithm shows near-linear scalability with input size. In contrast, the autovectorised decoding algorithm encounters a performance degradation for larger inputs. An analysis of the generated assembly suggests that memcpy() calls, invoked by a closure, may constitute a performance bottleneck.

License

This project is licensed under the terms of the MIT License. See the LICENSE.md file for details.

Changelog

See CHANGELOG.md for a detailed revision history.

References

[1] Designing a SIMD Algorithm from Scratch
[2] Faster Base64 Encoding and Decoding using AVX2 Instructions (arXiv)
[3] Base64 encoding and decoding at almost the speed of a memorycopy (arXiv)