Serializer: `write_escaped` is O(n²) when text doesn't contain `<`, `>` or `"`

Abierto
  • ¿Algo no está bien?
#810 0 comentarios 0 reacciones 0 asignados Ver en GitHub

Los mantenedores suelen responder en 1 día

Nadie ha tomado este issue todavía.

Evaluación

Dificultad
3/5
Tiempo estimado
1-2 días
Aptitud para principiantes
68/100
Tipo de issue
Error
Claridad
Bien especificado
Estado de actividad
Activo
Stack tecnológico
rust
Área
performance

Línea de trabajo

Start in html5ever/src/serialize/mod.rs at HtmlSerializer::write_escaped, then build and run the html2html example with the reproduction in the issue. Compare timings as the input grows for &amp; and &nbsp; versus &amp;<; done means the problematic inputs no longer show the reported quadratic scaling.

Escrito por el modelo de indexación a partir del texto del issue.

Descripción

HtmlSerializer::write_escaped finds the next byte to escape with two memchr searches (introduced by #740):

https://github.com/servo/html5ever/blob/6fcf956f59f54f0455464e6cd48fa4a69b9e8706/html5ever/src/serialize/mod.rs#L111-L114

If the text doesn't have an <, > or ", every & or non-breaking space will cause a full scan of the remaining text.

It's pretty common for text to contain &amp; and &nbsp; without <s or >s.

Repro using the html2html example:

cargo build --release -p markup5ever_rcdom --example html2html

TIMEFORMAT='%R s'

for text in '&amp;' '&amp;<' '&nbsp;'; do
  for count in 100000 200000 400000; do
    yes "$text" | head -n "$count" | tr -d '\n' > input.html
    echo -n "$text x $count: "
    time target/release/examples/html2html < input.html > /dev/null
  done
done

On a Linode G6 Dedicated machine with 2 vCPUs and 4 GB RAM, I get:

&amp; x 100000: 0.148 s
&amp; x 200000: 0.462 s
&amp; x 400000: 1.665 s
&amp;< x 100000: 0.096 s
&amp;< x 200000: 0.197 s
&amp;< x 400000: 0.376 s
&nbsp; x 100000: 0.241 s
&nbsp; x 200000: 0.839 s
&nbsp; x 400000: 3.492 s
Lenguaje dominante
Rust
Estrellas
2.6k
Forks
299
Merge medio
8 d 22 h
PR fusionados (30 d)
3

Preparar el entorno

Este proyecto no incluye contenedor de desarrollo, Dockerfile ni guía de contribución, así que la configuración corre por tu cuenta: empieza por su README y consulta nuestra guía para la primera contribución para los pasos generales.

Primeros pasos

  1. Lee el issue completo y luego la guía de contribución del proyecto.
  2. Comenta en el issue que vas a ocuparte — evita que dos personas hagan lo mismo.
  3. Haz un fork del repositorio y trabaja en una rama.
  4. Abre un pull request que haga referencia al número del issue.

Más de servo/html5ever

Todos los issues de servo/html5ever

Issues similares

Más issues de Rust

Recibe los nuevos issues en tu correo

Un resumen breve de issues de GitHub para principiantes.