Vectorize base64 decoding

[k0ekk0ek]

Base64 encoding is used quite a lot. i.e. in RRSIG and DNSKEY records. Wojciech Muła and Daniel Lemire wrote the paper "Faster Base64 Encoding and Decoding Using AVX2 Instructions" in which they outline use of SIMD instructions to improve performance. The current implementation is very basic and improving it is extremely likely to result in a significant performance boost. More research is available too and even improving the current scalar implementation is a big gain.

The flamegraph for parsing an .se zone looks nice and balanced, except for base64 data as the parser spends about 30% of the time in parse_base64.

[lemire]

@k0ekk0ek Are spaces allowed within the codes? That's a big limiting factor pre-AVX-512.

[k0ekk0ek]

Sort-of, but I don't think they're an issue(?) Spaces (among others) are delimiters within zone files so we get a separate token for each block of characters (we require this data to be specified as contiguous, so no spaces inside the token). However, we will need to track state because there may be multiple tokens (at least for RRSIG (presentation format)).

An example of how this occurs in zone data:

host.example.com. 86400 IN RRSIG A 5 3 86400 20030322173103 (
                               20030220173103 2642 example.com.
                               oJB1W6WNGv+ldvQ3WDG0MQkg5IEhjRip8WTr
                               PYGv07h108dUKGMeDPKijVCHX3DDKdfb+v6o
                               B9wfuh3DTJXUAfI/M0zmO/zz8bW0Rznl8O3t
                               GNazPwQKkRN20XPXV6nwwfoXmJQbsLNrLfkG
                               J5D6fwFm8nN+6pBzeDQfsS3Ap3o= )

Looking at .se they cut the signature up into blocks of 56 characters (without ( ... ), so one line), while .com seems to keep it as one set of contiguous characters.

[lemire]

This is an important problem. Node.js has a related issue.

See
nodejs/performance#128

I want to work on solving this issue as soon as I can.

[k0ekk0ek]

Sounds good @lemire! The client9 decoders are probably good to have as fallback(?) At least the base64 one got adopted and modified by @aklomp. The same can be done for base16 (hex). At least, I am planning to do so. The stream decoding interface fits simdzone nicely. Something I noticed in the modified version is that whole blocks need to be written. So the base64 AVX2 version requires at least 45 bytes of input (8 bytes for the fallback) to ensure proper output. Since simdzone guarantees enough padding in input and output buffers, we can perhaps let that requirement go. That may make things speedier/easier(?) Of course, this may or may not apply to Node.js. I'm currently focused on getting the SVCB RRTYPE done, after that testing and api cleanup to get to a first release, but if you need me to look at something, I'd be happy to help!

[lemire]

The main challenge I am concerned with are the spaces in the input… The overflows can be handled in some way but I agree that simdzone can benefit of faster routines than other systems.

[lemire]

Of course, this may or may not apply to Node.js

I am not sure how much of a difference this makes. It is an empirical issue and it is easy to implement both padded and strict versions.

[k0ekk0ek]

I/we'd have to test. Adding the faster base64 decoder made a big difference for the .se zone. Going by that example, any TLD zone that has widespread DNSSEC usage (such as .nl) will benefit. A really simple test would be to replace consecutive dec_loop_generic_32_inner calls in dec_loop_generic_32 by one (or more) SIMD function replacements. Also note that we don't have to account for spaces in the input. That part is handled automatically because they're separate tokens (base64 is to be written as <contiguous> not <quoted>, except for svcb parameters, but there we simply do not allow spaces), so we can quite easily select the right decoder based on token length.

[k0ekk0ek]

I'd have to study the library a bit better, but the loop currently selects for rounds 8, 4, 2 and 1. As 8x4 = 32 and 4x4 = 16, we could simply add AVX2 and SSE versions there.

[lemire]

I'll be working on this (starting 'now'). My current 'vision' is to make it configurable so one can explore the usage space.