Faster RRTYPE and CLASS parsing

[k0ekk0ek]

Record types are currently looked up using bsearch. While already being much better than simply iterating over all supported record types, i.e. O(log n) as opposed to O(n), this operation can be much improved. Note that lookup times increase with the addition of additional record types.

The same idea can be applied to classes. i.e. names for record classes cannot overlap with record types as no distinction between class and record can be made. Hence, a specialized lookup function can be implemented to simplify parsing the ttl+class+type trinity.

The idea is to use a best-effort one-level radix tree. Use the lower cased letter of the name to select a SIMD vector of 8x16, then use the hash of the lower cased name to identify the record type by issuing a straightforward _mm_cmpeq_epi8 (perhaps _mm_cmpeq_epi16). Then use the index to lookup the type descriptor in a properly indexed vector, much like the algorithm applied in ART (adaptive radix tree).

Preliminary tests show a performance increase of ~10% when applied to parsing the header. Note though that this mechanism will also significantly increase performance when parsing NSEC and NSEC3 record types.

[k0ekk0ek]

While working on replacing the dnsextlang generator, I couldn't resist throwing this in too. It proved quite a significant speedup. Especially so because of NSEC and NSEC3 records(?)

after:

parsed 341535548 records

real    0m20.750s
user    0m19.488s
sys     0m1.214s

before:

parsed 341535548 records

real    0m34.940s
user    0m32.840s
sys     0m1.942s

[k0ekk0ek]

Now that the second index is dropped by #64, finding the length for the hash has become more expensive. I ported it just to get it working, but it's likely a faster approach can be thought of. RRTYPEs may not be quoted and instead of scanning for non-structural characters we may get away with scanning for just [0-9a-zA-Z-]. It's also not very likely any RRTYPE name will use more than 16 characters or something not part of the aforementioned set.

[k0ekk0ek]

Some articles by Wojciech Muła (always a good read) contain interesting approaches to similar problems.

1. Fast parsing HTTP verbs
2. Modern perfect hashing for strings

It may be possible to use SIMD (maybe SWAR is sufficient) to generate the key and then use the mechanics in the first article. Perhaps, first figure all contiguous [0-9a-zA-Z-], convert that to a mask, load it, use the mask to zero out everything we don't need, then normalize case and run the prefix-switch?

[lemire]

Ada which is part of Node.js, has a very fast approach to recognize HTTP verbs...

https://github.com/ada-url/ada/blob/46ff6281d4d386bd3333720707a6a30b35c14779/include/ada/scheme-inl.h

I also have a blog post on the topic...

https://lemire.me/blog/2022/12/30/quickly-checking-that-a-string-belongs-to-a-small-set/

I later learned that Wojciech had investigated the same problems.

[lemire]

I can have a look at

simdzone/src/types.c

Line 191 in 4cc9b4a

};

But you have to precompute the hash function if you want it to be fast (i.e., it needs to happen at compile time), so it is going to involve some changes. You can't just use the set as if it were dynamic and get the same performance as a compile-time stet.

Anyhow, I can work on this if you'd like.

[k0ekk0ek]

If you're interested, that'd be awesome! It's the one data-type that every record is guaranteed to have. NSEC and NSEC3 type records even list multiple in RDATA (and those RRTYPEs get used a lot for zones that have DNSSEC).

; NSEC
alfa.example.com. 86400 IN NSEC host.example.com. (
                                   A MX RRSIG NSEC TYPE1234 )

; NSEC3
0p9mhaveqvm6t7vbl5lop2u3t2rp3tom.example. NSEC3 1 1 12 aabbccdd (
                       2t7b4g4vsa5smi47k61mv5bv1a22bojr MX DNSKEY NS
                       SOA NSEC3PARAM RRSIG )

[k0ekk0ek]

(my earlier attempt made sense when the length was available, because it involved only: use the first character to get the set of keys, then take the last character and add 0x07 (for distribution, so that 'a' + 1 != 'b') and add the length of the string)