Scan HTML faster with SIMD instructions – Chrome edition

Original Article ↗ Hacker News Discussion ↗

SIMD instructions can significantly speed up tasks that seem inherently serial, such as scanning and partially parsing HTML, with real-world gains for browsers, crawlers, and other tooling built on Chromium. Commenters explore how far parallelization can be pushed in parsing, what kinds of language and data format designs are more amenable to SIMD and multi-core execution, and how small percentage improvements scale to large energy and latency savings at global usage levels. The thread also branches into comparisons of Rust, C++, and C# for low-level, performance-critical code, and into whether human-readable text formats like HTML and JSON are worth their parsing overhead compared to binary serialization.

SIMD and HTML Parsing

  • Many are impressed that seemingly serial tasks like HTML or JSON parsing can gain large speedups from SIMD by isolating sub-tasks without strict byte-to-byte dependencies.
  • The specific Chrome optimization is seen as only one small piece of full HTML parsing, but still a useful, high-leverage hotspot.
  • Techniques discussed include:
    • Nibble-based lookup tables where target bytes share unique low bits.
    • Bitset-based membership tests via two lookups and shifts.
    • Using broadcast-from-memory and shuffles efficiently (e.g., PSHUFB).
  • There is debate about how far such tricks generalize, and mention of prior SIMD-parsing work (e.g., Parabix, simdjson).

Parallel Parsing and Language Design

  • Some argue HTML is “not fundamentally serial” and could be subdivided, though HTML’s lenient, context-sensitive rules make large-scale parallelism mostly an engineering challenge.
  • Others mention GPU- or array-language–style parsing and suggest grammars with fewer rules to make parallelization easier.
  • Ideas like bidirectional parsing (splitting the input and parsing forward/backward) are discussed as limited ~2× gains compared to broader SIMD approaches.

Rust, C++, and C# Debate

  • One side sees Rust’s memory safety as not worth the complexity, slow compilation, and difficulty of implementing pointer-heavy or highly mutable data structures.
  • Others counter that:
    • Rust data structures can favor indices/arrays over pointers, which can be faster and more compact.
    • Libraries like Rayon make parallel mutation patterns (e.g., matrix blocks) straightforward.
  • There is a parallel thread praising C#:
    • Strong memory safety with almost no unsafe in user data structures.
    • Good SIMD APIs in .NET and growing use of spans to avoid allocations.
  • GC tradeoffs are debated: some see .NET as viable even for realtime-ish media and games; others warn about allocation-heavy libraries (e.g., LINQ, YAML parsers).

Text vs Binary Formats

  • Some criticize HTML/JSON as human-oriented encodings that waste compute on serialization/deserialization, arguing for zero-copy binary formats.
  • Others defend text formats:
    • Human readability, debuggability, and rapid iteration outweigh raw efficiency.
    • JSON compresses well, is often not the bottleneck, and internal systems already use binary (protobuf/Thrift/Avro).
  • Benchmarks around JSON vs protobuf performance are contested; participants note parser quality and environment (e.g., JavaScript’s native JSON.parse) can dominate.

Practical Impact and Tooling

  • Even a 1% HTML parsing win in Chromium is framed as a large global energy and latency benefit.
  • Faster parsing could reduce the need for extra caching layers or heavy DOM structures.
  • Some see LLMs as helpful for understanding SIMD-heavy code; others warn they are unreliable, especially for nontrivial shuffle logic.

Miscellaneous Points

  • Clarification that CR (\r) detection is used for normalizing CRLF to LF in HTML parsing.
  • Questions arise about lack of modern C/C++ HTML parsers.
  • Some wonder if compilers could auto-vectorize such loops; others imply current compilers are not yet good enough at these patterns.