base64 scalar - Improve performance of scalar base64 decoder and encoder - #1037

Short title (summary):

Accelerate scalar Base64 encoding and decoding

Description

Optimize the scalar Base64 clean-input paths while preserving existing API behavior. Encoding processes four 3-byte groups using 12-bit pair lookup tables; decoding processes three 4-character groups together with combined validation and a packed output store. Existing paths continue to handle tails, whitespace, garbage, URL-safe input, UTF-16, strict/partial modes, padding, and bounded output.

Type of change

• Bug fix
• Optimization
• New feature
• Refactor / cleanup
• Documentation / tests
• Other (please describe):

How to verify / test

The existing base64_tests and constexpr_base64_tests pass. A dedicated C++23 compile-time test covering the new encoder and decoder paths also passes.

Scalar-only benchmarks were compiled with MSVC 19.51 using /O2, with SIMD backends disabled. Each number is the average of the medians from two alternating original/patched runs, using seven samples of approximately 350 ms each. Throughput is measured against binary input for encoding and encoded input for decoding.

The benchmark validates output correctness before measuring each case.

Checklist before submitting

• I added/updated tests covering my change (if applicable)
• Code builds locally and passes my check
• Documentation / README updated if needed
• Commits are atomic and messages are clear
• I linked the related issue (if applicable)

Final notes

Further performance can be achieved if we reduce the responsibilities of the code, ex. externalize whitespace handling - see for example https://github.com/gaspardpetit/base64/

At this point, I maintained backward compatibility, but if interested, I can push this further.

[EDIT]

The original naive approach had an unexpected side effect - adding the new 12 bit handling branch added pressure on the registers and increased stack allocation, causing additional fixed cost on encoding of small payloads - in particular the 1-11 byte range.

The solution was to split the new branch in its own function - which still left a bit of degradation on small payloads (1-2%) for the extra branch.

I chose to integrate another PR I wanted to submit later with this one to make sure we improve all cases, and so I added size-based custom handling of tails. The net effect provides significant improvement on all small payloads sizes.

This improvement - although it primarily targets the scalar implementation - also benefits SIMD implementations that delegate the small tails (ex. < 28 bytes) to scalar handling. So these improvements are particularly beneficial to SIMD implementations when handling 1-256 bytes.

For encoding, I tested AVX2, but I expect similar results across the board for SIMD:

Similarly, for decoding, AVX2 degrades slightly (2ns) in the 1-8B because of the new branch, but then improves well in the 9-47 B range and the 57-95 B where we have 1 or 2 AVX2 blocks and enough tail bytes to follow the new branch. Meanwhile, pure scalar decoding is improved across the board.

(The +2% / -2% in the >1KiB is likely to be noise here - it is not supported by the changes being submitted).

I will be providing a third PR that will stack over this one and address the cliffs you have also been observing with SIMD implementations, there tail degrades until we reach the magic multiples.