Improving `basenc` / `base32` / `base64`
Nobody has claimed this yet.
- Dominant language
- Rust
- Stars
- 24.1k
- Forks
- 2k
- Avg merge
- 1d 5h
- Merged PRs (30d)
- 365
Description
I've identified a few issues with the encoding/decoding tools that I'm interested in solving:
-
They are not iterative / streaming. The entirety of the input is read first before it is all decoded. One the one hand, this allows you to detect errors upfront before you've output anything. But it means that these tools can't be used for iterative computations (e.g. over
whileloops) and they may consume large amounts of memory. The GNU implementations of these tools are streaming as well, so I'd classify this as an incompatibility bug. -
Significant optimization potential is available. I have a fair bit of experience with SIMD and I've designed AVX2 and AVX512 algorithms for Base32 / Base64 encoding - it's difficult but I would like to see if there are performance benefits to it, particularly for large inputs. Optimizations can be added iteratively, and can be feature-gated or even based on runtime CPU feature detection.
-
Compiled binaries for
base32/base64, on my machine, currently take up 23 MiB in debug mode and 3 MiB in release mode. This is surprisingly large and I believe the majority of that work lies in the argument parsing rather than the actual encoding. Sincebasenc/base32/base64have essentially the same arguments to deal with, they can be combined.
To this end, here's my proposal:
-
Rewrite
src/uucore/src/lib/features/encoding.rsto expose a streaming rather than one-shot interface. Along the way, I can add a sub-module for each encoding format so that per-format optimization routines can be defined. Runtime CPU detection, if implemented, would be format-generic. -
Setup
basencas a multicall binary so thatbase32/base64are symlinks to it. The argument parsing forbasencwill have to be updated to only expose format-selecting arguments ifargv[0]isbasenc. -
Implement format-specific optimization routines over time, supported by benchmarking. For example, if the user only provides less than 1 KiB of data, a less optimized routine can be used (advanced AVX512 instructions have some interesting effects on CPU clock frequencies, so we should avoid them unless a large amount of input needs to be processed).
It may be preferable that I write a new, independent crate for optimized data encoding and create a dependency on that (rather than the current data-encoding crate); the alternative is to eliminate the external dependency completely.
I'd like to ask for prior approval from the uutils community before I start working on this. Note that task 1 and 2 are effectively independent - while I'm more interested in the first, the second seems more important. Maintainers, what do you think?
Contributor guide
First steps
- Read the whole issue, then the project's contributing guide.
- Comment on the issue to say you are picking it up — it saves two people doing the same work.
- Fork the repository and make your change on a branch.
- Open a pull request that references the issue number.
Research direction
Start by reviewing src/uucore/src/lib/features/encoding.rs and the existing basenc, base32, and base64 command behavior. Clarify the community-approved scope first; done would require an agreed streaming interface and multicall design, with any optimization work supported by benchmarks.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- rust
- Domain
- cli, performance
- Issue type
- Feature
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Stale
- Clarity
- Mostly clear
- Newbie friendliness
- 25/100