Improve HtmlEncoder performance over largely ascii strings
- Dominant language
- C#
- Stars
- 18.3k
- Forks
- 5.6k
- PR merge metrics
- PR metrics pending
Description
Today the html encoder is fast until it's not. After the first encodable element it will proceed to encode scalar by scalar. This ends up being quite slow for ascii (utf8) strings containing e.g. a single quote near the start. Or even for encoding xml-like data, as these generally start with an encodable (utf8) character '<'.
Doing a chunked vector classification, returning per chunk (advancing e.g. 64 input elements at a time) which indices *may* need encoding, would instead eliminate a lot of the element by element scanning. Due to the requirement to examine each high surrogate or leading byte this won't do much for full unicode data but it will help a lot when the data is mostly ASCII (or entirely ASCII with a few encodable characters).
To illustrate the current behavior I tested some variations of the fortunes string `A computer scientist is someone who fixes things that aren't broken.` (where `'` gets encoded):
| Input | Mean | Remarks |
|----------------------------------------------------------------------|-------|-----------------|
| A computer scientist is someone who fixes things that aren't broken. | 20 ns | Late encodable (original) |
| A computer scientist is someone who fixes things that arent broken.' | 13 ns | Last encodable |
| A computer scientist is someone who fixes things that arenat broken. | 10 ns | Scan only |
| A computer' scientist is someone who fixes things that arent broken. | 64 ns | Early encodable |
| A computer' scient>st is some 3x slower) with very small input changes.
BDN benchmarks were done on an m1 max, purely executing `HtmlEncoder.Default.EncodeUtf8(input, span, out _, out _, isFinalBlock: true)`
cc @MihaZupan
Resources:
- https://github.com/zzau13/v_escape/blob/master/v_htmlescape/src/lib.rs this essentially only does a deny list mask (which I'm aware is against MS policy) but the algorithm would still mostly transfer. The mask defined in the link runs through the input encoder defined here https://github.com/zzau13/v_escape/blob/master/base/src/generic.rs#L98 (adapted from https://github.com/BurntSushi/memchr/blob/master/src/arch/generic/memchr.rs)
- https://lemire.me/blog/2024/07/20/scan-html-even-faster-with-simd-instructions-c-and-c/
Contributor guide
Assessment
This issue has not been assessed yet.