dotnet / dotnet/runtime

Improve HtmlEncoder performance over largely ascii strings

Open
#122,005 1 comment 0 reactions 0 assignees View on GitHub
area-System.Text.Encodings.Web
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

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.