11 ms·

Scan HTML faster with SIMD instructions – Chrome edition

241 points by p_l 2y ago

nasretdinov 2y ago
To me it's fascinating that you indeed _can_ speed up what appears to be a non-parallelisable task like parsing HTML (or JSON to a lesser extent) using SIMD. And that the gains are so substantial too.
- dzaima 2y ago
  There's a surprising amount of things that are possible to parse in a parallel fashion if one tries hard enough, though keeping significant or any gains is more tricky. The operation in the article though is only a rather tiny part of parsing HTML though.
  - floxy 2y ago
    Can anyone recommend pointers to find out more about creating programming languages / markup languages that would be more parallel friendly for parsing? Or maybe even embarrassingly parallel? How does that affect the grammar, etc.. Maybe you need a different formalism rather than BNF do describe it, and you don't use regex to tokenize, and there is no recursive descent, or state machines in parsing, etc..
    - dzaima 2y ago
      There's not really that much specific to change I think; the general thing is just reducing the number of rules, as in a parallel thing you'll be applying every rule to every part versus just the rules given preceding context (there is the option of filtering parts to process if there are a bunch of rules applying to the same small subset of the input, but that requires such cont). All I can point at is from the array language world, with the notable thing of Co-dfns from Aaron Hsu, an APL compiler capable of running on the GPU (pointless as that may be): https://github.com/Co-dfns/Co-dfns/tree/master https://github.com/Co-dfns/Co-dfns/tree/master; and a 284-page dissertation: https://scholarworks.iu.edu/dspace/items/3ab772c9-92c9-4f59-bd95-40aff99e8c7a https://scholarworks.iu.edu/dspace/items/3ab772c9-92c9-4f59-... And Marshall Lochbaum following (https://mlochbaum.github.io/BQN/implementation/codfns.html https://mlochbaum.github.io/BQN/implementation/codfns.html) that work, and covering some basics of parsing expressions of infix & prefix ops to stack-based/RPN at the bottom of https://mlochbaum.github.io/BQN/implementation/index.html https://mlochbaum.github.io/BQN/implementation/index.html, though the code is in BQN. From that same author, parsers written in BQN, that I think should have sub-linear critical paths: Markdown: https://github.com/mlochbaum/BQN/blob/master/md.bqn https://github.com/mlochbaum/BQN/blob/master/md.bqn XML: https://github.com/mlochbaum/bqn-libs/blob/master/xml.bqn https://github.com/mlochbaum/bqn-libs/blob/master/xml.bqn and a compiler of BQN itself: https://github.com/mlochbaum/BQN/blob/master/src/c.bqn https://github.com/mlochbaum/BQN/blob/master/src/c.bqn (outputs stack-based bytecode).
      - floxy 2y ago
        Are you still operating on a single stream of characters? I was wondering about something more radical, like you start in the middle of the stream, and one thread parses the forward to the end, and the other parses backwards towards the beginning.
        dzaima 2y ago
        That's an option for a potential 2x boost, which I suppose could be good enough in certain contexts, but that's it. In particular, if you have a parser system able to utilize SIMD for all parsing, that'll get arbitrary parallelizability for "free" (at the cost of some log(n) increase in total operations across all threads).
- magicalhippo 2y ago
  Now all we need is for pre-2000s web to come back and we could have instant web surfing.
- anonymoushn 2y ago
  The approach to these vectorized parsers is generally to find some part of the parsing task that doesn't have a dependency chain through every dang byte, like a naively written parser would, then do that first, then do some harder stuff after. I'm pretty used to it now so I lack perspective on whether this is weird, but in general finding long dependency chains and getting rid of them or replacing them with several shorter dependency chains will make software a lot faster.
- emn13 2y ago
  As a very rough approximation, I suspect that html parsing (beyond the streaming of the data anyhow) isn't really all that fundamentally serial. After all, if you seek into an html document at some random point, you can generally interpret the html structure mostly locally, i.e. it's likely possible to subdivide the task of parsing an html document. Given how leniently html deals with errors and that some of the parsing rules have some context sensitivity (the various modes) actually exploiting large-scale parallelism is probably a very difficult bit of engineering. Additionally, there may be corner cases that have much more context dependence than normal. Also, parsing is already probably not a huge part of a browsers runtime, and aggressive parallelism might be faster but more power hungry for a very small latency win. But I can't think of a specific fundamental limitation that prevents the normal parsing case from being quite parallelizable; I believe it's "just" an engineering problem.
- bssrdf 2y ago
  Indeed. Even a simple 'wc -l' type operation can benefit from SIMD [0] [0]https://x.com/cloud11665/status/1799534538873290993 https://x.com/cloud11665/status/1799534538873290993
Const-me 2y ago
The reason why the single-lookup version works, the bytes being searched for have unique low 4 bits. So the lookup generates the vector with bytes equal to low_nibble_mask[ source[i] & 0x0F ]. The table contains the bytes being searched for, in the elements which correspond to the low 4 bits of these bytes. The next instruction compares bytes in the source vector for equality with the results of that lookup. So, for each byte in the source vector, the first 3 instructions are computing the following expression, in parallel for each of the 16 bytes in the vector: bool eq = ( b == low_nibble_mask[ b & 0x0F ] ); The rest is trivial, identifying index of the first byte which compared true. And one more thing. > If you have an old SSE2 PC, only the simple SIMD approach is available That PSHUFB table lookup SSE instruction was introduced in SSSE3 extension. Now in 2024 it’s hard to find an old SSE2 PC which doesn’t also support SSSE3. You gonna need things like Pentium D launched in 2005, or AMD K10 launched in 2007.
- ilrwbwrkhv 2y ago
  Do you still use c++ or have you moved to rust?
  - Const-me 2y ago
    I mostly use C++ and C#, and I’m not a fan of Rust.
    - victor106 2y ago
      I love C#. > I’m not a fan of Rust. I wonder why? Care to elaborate?
      - neonsunset 2y ago
        A little more on topic, if you like SIMD and C#, dotnet/runtime now has an introductory guide to Vector128/256/512<T> API: https://github.com/dotnet/runtime/blob/main/docs/coding-guidelines/vectorization-guidelines.md https://github.com/dotnet/runtime/blob/main/docs/coding-guid... Now, the default syntax can still be a bit more wordy with byref arithmetics than ideal, but you can add a few extension methods to make it look it closer to Rust's pointer arithmetics: https://github.com/U8String/U8String/blob/main/Sources/U8String/CaseConverters/U8AsciiCaseConverter.cs#L153-L171 https://github.com/U8String/U8String/blob/main/Sources/U8Str... (unrelated note but .NET lowers this to vpternlogd if AVX512VL is available) You can find more examples of SIMD use in dotnet/runtime if that interests you: https://grep.app/search?q=Vector%28128%7C256%7C512%29%3C%5Cw%2B%3E&regexp=true&filter[lang][0]=C%23&filter[repo][0]=dotnet/runtime https://grep.app/search?q=Vector%28128%7C256%7C512%29%3C%5Cw... Many paths are vectorized: to/from hexadecimal byte conversion, unicode encoding/decoding, various hash algorithms, counting and searching for elements, chunking text, there's a BLAS library now too and more.
o11c 2y ago
And how does `strcspn` from various libcs compare?
- deleted 2y ago
  [deleted]
klysm 2y ago
It’s always crazy to me that we have picked encodings for data that are human-first to send between computers. JSON is in a similar boat. Absolutely enormous amounts of computing power are spent on serialization and deserialization. That latency is experienced everywhere too. If we used zero-copy serialization structures everywhere, a whole lot of compute would be saved
- p_l 2y ago
  Considerable portion of that was early ARPANET work often involving somewhat lacking access to hardware, so I'm it's formative ages internet had a lot of directly attaching teletypes to network ports. Also one can't forget about TIPs, which provided "phone modem to telnet-like" bridge service in ARPANET. Another part was how text was the one thing that people had standardise enough between different computers. FTP's ASCII and binary modes aren't about love conversion for Unix, but because "binary" meant totally different things on different hosts (could be 8bit octets, could be 28bit words, could be 36bit words, could be 60 bit, before internet fully settled down there were 40 bit hosts too). Also people are scared of compilers. All of that led to cultural bias towards textual protocols
- bigbuppo 2y ago
  So... what you're saying is that we should do what cobol did in 1960?
  - dingdingdang 2y ago
    I tend to agree here, judiciously used json (these days often running under zstd compression) is seldomly the bottleneck on anything and allows immediate human debugging if need be.
    - hinkley 2y ago
      What we actually implement is often more constrained by what we can prototype and experiment on than how fast or how well we can define formal requirements and implement them. So much good stuff in software is down to a mix of serendipity and 'what if' and anything that reduces friction (improves ergonomics) has my vote.
scottlamb 2y ago
> The results follow my expectations: the simplest vectorized classification routine has the best performance. However, you may observe that even a rather naive SIMD approach can be quite fast in this instance. I've recently written my first SIMD code [1]. This matches my observation: you get a big improvement just moving from scalar code to autovectorized code (i.e. working in fixed widths and telling the compiler to use specific CPU features you've detected), another decent improvement going to basic use of vendor intrinsics, and then more and more modest improvements from extra sophistication. [1] uyvy->i420 pixel format conversion code, a much easier application of SIMD. No branching, just a bunch of pixels transformed in identical fashion.
- josephg 2y ago
  I think most optimisation work is like that. Early effort with each technique can yield large gains. But the marginal gain of using any specific technique decreases over time. For example, I've gotten a lot of speedups from essentially decreasing the number of malloc calls my programs make. Its often the case that ~80% of all allocations in a program come from just a few hotspots. Rewriting those hotspots to use a better data structure can yields big speed improvements, both because malloc & free are expensive calls and because the CPU hates chasing pointers. But there's usually only so much benefit in reducing allocations. At some point, it makes sense to just accept malloc calls. The reason is totally logical. Lets say you reduce the number of allocations your program does by 10x and that yields a 45% performance improvement (10 seconds -> 5.5 seconds). You might think reducing allocations by 10x again would yield another 45% performance improvement - but thats just not how the math works out. We should expect that would take your 5.5 seconds down to 5.05 seconds - which is just a 9% improvement. That might not be worth it, given the next 10x reduction in malloc calls will probably be much harder to achieve. If you want another 50% perf improvement, you need to run that profiler again and look at where the new hotspots are. If the CPU is spending less time following pointers, it'll now be spending more time (proportionately) running linear code. Maybe this time the performance wins will be found using SIMD. Or by swapping to a different algorithm. Or multithreading. Or by making better use of caching. Or something else - who knows.
ijidak 2y ago
It's amazing how ChatGPT makes code the reader may not be familiar with faster to grok. The examples in this article assume familiarity with SIMD. In the past, I would have tabled an article like this for deciphering later. But, with ChatGPT, I was able to ask about just a few bits of code and immediately grok the implementation. From a technology standpoint, the future is looking scary productive. Can't wait to see what new vistas developers open up with these new super powers.
- secondcoming 2y ago
  you’re assuming the output from ChatGPT is correct, and it’s not bluffing.
  - spartanatreyu 2y ago
    Bluffing is the wrong word. It assumes that the LLM is capable of knowingly telling falsehoods. Instead it always has full confidence in whatever it's last "thought" must be correct, even when asked to double check it's own output, even in a loop. It'll either doubledown on a falsehood or generate a new result and have complete confidence that it's last result was wrong and that it's new result must be correct, even though the initial confidence was the same. "Bluffing" certainly isn't the right word. "Hallucinating" fits much better.
    - kelnos 2y ago
      > By comparison, modern C# is memory safe all the way down, possible to implement even very complicated data structures without a single line of unsafe code "Confidence" is the wrong word. Confidence is a capability of thinking, sentient beings, and LLMs are not that. I say this to point out the futility in your post; "bluffing" is a perfectly fine thing for the GP to say, because it gets the point across. All of us here should know that an LLM can't actually bluff. (And if you'd prefer a different term, remember that not everyone on HN speaks English as their first language, and may not immediately come up with a more appropriate way of phrasing it.)
- anonymoushn 2y ago
Havoc 2y ago
What’s the usage case for scanning html at gigs per second speed? Speeding up browsers? Crawling?
- spartanatreyu 2y ago
  Sometimes html pages can get pretty big, why not optimise it? Also, speeding up html parsing means speeding up browsers, crawlers, e2e tests, visual regression tests, etc...
  - abirch 2y ago
    A lot of html, css, and JavaScript may not be independent.
    - kelnos 2y ago
      Sure, but if you parse the HTMl faster, you find the <script> and <link rel="stylesheet"> tags sooner, and can kick off another network thread to start fetching those files sooner. Overall you end up with a faster page load.
- noir_lord 2y ago
  If you improve parsed/scanned speed of html in Chromium by say 1%, that doesn't sound impressive. Then you consider 3 billion people use chrome (or Chromium derived browsers) multiply that out by how much html gets parsed/scanned a day by those users and then consider the energy costs - it quite quickly gets to a massive number (and that's just actual users, Chromium is also the core of Electron and a alot of other tooling) Simply put at Google's scale, tiny incremental gains compound to a massive species wide saving. At scale everything matters :).
- dmw_ng 2y ago
  Sufficiently fast software often allows leaving out whole layers of crap and needless indirection, the most common being caching. Fixing an algorithm so you can omit a dedicated database of intermediate results can be a huge maintainability/usability improvement. The same principle appears all over the place, e.g. immediate mode UIs, better networking (e.g. CSS image tiling vs. just fixing small request overhead in HTTP1 vs. QUIC), importing giant CSV files via some elaborate ETL process vs. just having a lightning fast parser+query engine, etc. Depending on how you look at it, you could view large chunks of DOM state through this lens, as intermediate data that only exists to cache HTML parsing results. What's the point of allocating a hash table to represent element attributes if they are unchanged from the source document, and reparsing them from the source is just as fast as keeping around the parsed form? etc. These kinds of tricks only tend to present themselves after optimization work is done, which is annoying, because it's usually so damn hard to justify optimization work in the first place.
cyberax 2y ago
I'm really bummed that Parabix went nowhere: https://ieeexplore.ieee.org/document/6169041 https://ieeexplore.ieee.org/document/6169041 It's apparently still alive, though: https://cs-git-research.cs.surrey.sfu.ca/cameron/parabix-devel/-/tree/master https://cs-git-research.cs.surrey.sfu.ca/cameron/parabix-dev...
JoshTriplett 2y ago
I'm surprised that this pays attention to '\r' (CR) specifically, and not '\n' (LF), ' ' (space), or '\t' (tab). It doesn't seem like HTML assigns any special meaning to carriage return compared to other whitespace. What is the parser doing with the locations of carriage returns?
- rurban 2y ago
  I also have no idea why he needs the newline-mask \r. Only <pre> blocks only on windows would need that.
  - account42 2y ago
    <pre> blocks don't depend on the OS, that would be ridiculous.
- kristianp 2y ago
  Is it something to do with http headers? They have CR LF pairs terminating the lines.
  - JoshTriplett 2y ago
    I wondered about that, but that wouldn't be described as parsing HTML, and it shouldn't involve parsing '<' and '&'.
- eknkc 2y ago
  Probably need to do a pass to find all \r chars, check if the next char is \n and if so, discard it. Otherwise convert it to \n. edit: Yeah, does exactly that: https://chromium-review.googlesource.com/c/chromium/src/+/5538407/33/third_party/blink/renderer/core/html/parser/html_document_parser_fastpath.cc#836 https://chromium-review.googlesource.com/c/chromium/src/+/55...
feverzsj 2y ago
We really need an updated html parser for c/c++. Most people are still using gumbo, which was abandoned by google 10 years ago. Some are using lexbor, which lacks basic document.
codedokode 2y ago
Cannot compilers auto-vectorize such loops? I think it would be more valuable to teach compilers to recognize such loops rather than simply write the code.
mistercow 2y ago
Seems like you could do something similar, combined with an exclusive scan, to rapidly find all the (potential) tag offsets in an HTML file on the GPU. I doubt that would be worthwhile in a browser due to the overhead of simply talking to the GPU, but it seems like it could be a useful trick if you have gigabytes of HTML to scan.
aynyc 2y ago
Maybe I'm jaded. As soon as this is out in the wild, web devs will come up with new ways to slow their websites down.
- kolme 2y ago
  Hey. Webdev here ;-) It's the other way around: after every optimization we have more "budget" to spend. More code, more bloat that we can get away with.

241 points by p_l 2y ago

To me it's fascinating that you indeed _can_ speed up what appears to be a non-parallelisable task like parsing HTML (or JSON to a lesser extent) using SIMD. And that the gains are so substantial too.

dzaima 2y ago
There's a surprising amount of things that are possible to parse in a parallel fashion if one tries hard enough, though keeping significant or any gains is more tricky. The operation in the article though is only a rather tiny part of parsing HTML though.
- floxy 2y ago
  Can anyone recommend pointers to find out more about creating programming languages / markup languages that would be more parallel friendly for parsing? Or maybe even embarrassingly parallel? How does that affect the grammar, etc.. Maybe you need a different formalism rather than BNF do describe it, and you don't use regex to tokenize, and there is no recursive descent, or state machines in parsing, etc..
  - dzaima 2y ago
    There's not really that much specific to change I think; the general thing is just reducing the number of rules, as in a parallel thing you'll be applying every rule to every part versus just the rules given preceding context (there is the option of filtering parts to process if there are a bunch of rules applying to the same small subset of the input, but that requires such cont). All I can point at is from the array language world, with the notable thing of Co-dfns from Aaron Hsu, an APL compiler capable of running on the GPU (pointless as that may be): https://github.com/Co-dfns/Co-dfns/tree/master https://github.com/Co-dfns/Co-dfns/tree/master; and a 284-page dissertation: https://scholarworks.iu.edu/dspace/items/3ab772c9-92c9-4f59-bd95-40aff99e8c7a https://scholarworks.iu.edu/dspace/items/3ab772c9-92c9-4f59-... And Marshall Lochbaum following (https://mlochbaum.github.io/BQN/implementation/codfns.html https://mlochbaum.github.io/BQN/implementation/codfns.html) that work, and covering some basics of parsing expressions of infix & prefix ops to stack-based/RPN at the bottom of https://mlochbaum.github.io/BQN/implementation/index.html https://mlochbaum.github.io/BQN/implementation/index.html, though the code is in BQN. From that same author, parsers written in BQN, that I think should have sub-linear critical paths: Markdown: https://github.com/mlochbaum/BQN/blob/master/md.bqn https://github.com/mlochbaum/BQN/blob/master/md.bqn XML: https://github.com/mlochbaum/bqn-libs/blob/master/xml.bqn https://github.com/mlochbaum/bqn-libs/blob/master/xml.bqn and a compiler of BQN itself: https://github.com/mlochbaum/BQN/blob/master/src/c.bqn https://github.com/mlochbaum/BQN/blob/master/src/c.bqn (outputs stack-based bytecode).
    - floxy 2y ago
      Are you still operating on a single stream of characters? I was wondering about something more radical, like you start in the middle of the stream, and one thread parses the forward to the end, and the other parses backwards towards the beginning.
      - dzaima 2y ago
        That's an option for a potential 2x boost, which I suppose could be good enough in certain contexts, but that's it. In particular, if you have a parser system able to utilize SIMD for all parsing, that'll get arbitrary parallelizability for "free" (at the cost of some log(n) increase in total operations across all threads).
magicalhippo 2y ago
Now all we need is for pre-2000s web to come back and we could have instant web surfing.
anonymoushn 2y ago
The approach to these vectorized parsers is generally to find some part of the parsing task that doesn't have a dependency chain through every dang byte, like a naively written parser would, then do that first, then do some harder stuff after. I'm pretty used to it now so I lack perspective on whether this is weird, but in general finding long dependency chains and getting rid of them or replacing them with several shorter dependency chains will make software a lot faster.
emn13 2y ago
As a very rough approximation, I suspect that html parsing (beyond the streaming of the data anyhow) isn't really all that fundamentally serial. After all, if you seek into an html document at some random point, you can generally interpret the html structure mostly locally, i.e. it's likely possible to subdivide the task of parsing an html document. Given how leniently html deals with errors and that some of the parsing rules have some context sensitivity (the various modes) actually exploiting large-scale parallelism is probably a very difficult bit of engineering. Additionally, there may be corner cases that have much more context dependence than normal. Also, parsing is already probably not a huge part of a browsers runtime, and aggressive parallelism might be faster but more power hungry for a very small latency win. But I can't think of a specific fundamental limitation that prevents the normal parsing case from being quite parallelizable; I believe it's "just" an engineering problem.
bssrdf 2y ago
Indeed. Even a simple 'wc -l' type operation can benefit from SIMD [0] [0]https://x.com/cloud11665/status/1799534538873290993 https://x.com/cloud11665/status/1799534538873290993

Const-me 2y ago

The reason why the single-lookup version works, the bytes being searched for have unique low 4 bits. So the lookup generates the vector with bytes equal to low_nibble_mask[ source[i] & 0x0F ]. The table contains the bytes being searched for, in the elements which correspond to the low 4 bits of these bytes. The next instruction compares bytes in the source vector for equality with the results of that lookup. So, for each byte in the source vector, the first 3 instructions are computing the following expression, in parallel for each of the 16 bytes in the vector: bool eq = ( b == low_nibble_mask[ b & 0x0F ] ); The rest is trivial, identifying index of the first byte which compared true. And one more thing. > If you have an old SSE2 PC, only the simple SIMD approach is available That PSHUFB table lookup SSE instruction was introduced in SSSE3 extension. Now in 2024 it’s hard to find an old SSE2 PC which doesn’t also support SSSE3. You gonna need things like Pentium D launched in 2005, or AMD K10 launched in 2007.

ilrwbwrkhv 2y ago
Do you still use c++ or have you moved to rust?
- Const-me 2y ago
  I mostly use C++ and C#, and I’m not a fan of Rust.
  - victor106 2y ago
    I love C#. > I’m not a fan of Rust. I wonder why? Care to elaborate?
    - neonsunset 2y ago
      A little more on topic, if you like SIMD and C#, dotnet/runtime now has an introductory guide to Vector128/256/512<T> API: https://github.com/dotnet/runtime/blob/main/docs/coding-guidelines/vectorization-guidelines.md https://github.com/dotnet/runtime/blob/main/docs/coding-guid... Now, the default syntax can still be a bit more wordy with byref arithmetics than ideal, but you can add a few extension methods to make it look it closer to Rust's pointer arithmetics: https://github.com/U8String/U8String/blob/main/Sources/U8String/CaseConverters/U8AsciiCaseConverter.cs#L153-L171 https://github.com/U8String/U8String/blob/main/Sources/U8Str... (unrelated note but .NET lowers this to vpternlogd if AVX512VL is available) You can find more examples of SIMD use in dotnet/runtime if that interests you: https://grep.app/search?q=Vector%28128%7C256%7C512%29%3C%5Cw%2B%3E&regexp=true&filter[lang][0]=C%23&filter[repo][0]=dotnet/runtime https://grep.app/search?q=Vector%28128%7C256%7C512%29%3C%5Cw... Many paths are vectorized: to/from hexadecimal byte conversion, unicode encoding/decoding, various hash algorithms, counting and searching for elements, chunking text, there's a BLAS library now too and more.

o11c 2y ago

And how does `strcspn` from various libcs compare?

deleted 2y ago
[deleted]

klysm 2y ago

It’s always crazy to me that we have picked encodings for data that are human-first to send between computers. JSON is in a similar boat. Absolutely enormous amounts of computing power are spent on serialization and deserialization. That latency is experienced everywhere too. If we used zero-copy serialization structures everywhere, a whole lot of compute would be saved

p_l 2y ago
Considerable portion of that was early ARPANET work often involving somewhat lacking access to hardware, so I'm it's formative ages internet had a lot of directly attaching teletypes to network ports. Also one can't forget about TIPs, which provided "phone modem to telnet-like" bridge service in ARPANET. Another part was how text was the one thing that people had standardise enough between different computers. FTP's ASCII and binary modes aren't about love conversion for Unix, but because "binary" meant totally different things on different hosts (could be 8bit octets, could be 28bit words, could be 36bit words, could be 60 bit, before internet fully settled down there were 40 bit hosts too). Also people are scared of compilers. All of that led to cultural bias towards textual protocols
bigbuppo 2y ago
So... what you're saying is that we should do what cobol did in 1960?
- dingdingdang 2y ago
  I tend to agree here, judiciously used json (these days often running under zstd compression) is seldomly the bottleneck on anything and allows immediate human debugging if need be.
  - hinkley 2y ago
    What we actually implement is often more constrained by what we can prototype and experiment on than how fast or how well we can define formal requirements and implement them. So much good stuff in software is down to a mix of serendipity and 'what if' and anything that reduces friction (improves ergonomics) has my vote.

scottlamb 2y ago

> The results follow my expectations: the simplest vectorized classification routine has the best performance. However, you may observe that even a rather naive SIMD approach can be quite fast in this instance. I've recently written my first SIMD code [1]. This matches my observation: you get a big improvement just moving from scalar code to autovectorized code (i.e. working in fixed widths and telling the compiler to use specific CPU features you've detected), another decent improvement going to basic use of vendor intrinsics, and then more and more modest improvements from extra sophistication. [1] uyvy->i420 pixel format conversion code, a much easier application of SIMD. No branching, just a bunch of pixels transformed in identical fashion.

josephg 2y ago
I think most optimisation work is like that. Early effort with each technique can yield large gains. But the marginal gain of using any specific technique decreases over time. For example, I've gotten a lot of speedups from essentially decreasing the number of malloc calls my programs make. Its often the case that ~80% of all allocations in a program come from just a few hotspots. Rewriting those hotspots to use a better data structure can yields big speed improvements, both because malloc & free are expensive calls and because the CPU hates chasing pointers. But there's usually only so much benefit in reducing allocations. At some point, it makes sense to just accept malloc calls. The reason is totally logical. Lets say you reduce the number of allocations your program does by 10x and that yields a 45% performance improvement (10 seconds -> 5.5 seconds). You might think reducing allocations by 10x again would yield another 45% performance improvement - but thats just not how the math works out. We should expect that would take your 5.5 seconds down to 5.05 seconds - which is just a 9% improvement. That might not be worth it, given the next 10x reduction in malloc calls will probably be much harder to achieve. If you want another 50% perf improvement, you need to run that profiler again and look at where the new hotspots are. If the CPU is spending less time following pointers, it'll now be spending more time (proportionately) running linear code. Maybe this time the performance wins will be found using SIMD. Or by swapping to a different algorithm. Or multithreading. Or by making better use of caching. Or something else - who knows.

ijidak 2y ago

It's amazing how ChatGPT makes code the reader may not be familiar with faster to grok. The examples in this article assume familiarity with SIMD. In the past, I would have tabled an article like this for deciphering later. But, with ChatGPT, I was able to ask about just a few bits of code and immediately grok the implementation. From a technology standpoint, the future is looking scary productive. Can't wait to see what new vistas developers open up with these new super powers.

secondcoming 2y ago
you’re assuming the output from ChatGPT is correct, and it’s not bluffing.
- spartanatreyu 2y ago
  Bluffing is the wrong word. It assumes that the LLM is capable of knowingly telling falsehoods. Instead it always has full confidence in whatever it's last "thought" must be correct, even when asked to double check it's own output, even in a loop. It'll either doubledown on a falsehood or generate a new result and have complete confidence that it's last result was wrong and that it's new result must be correct, even though the initial confidence was the same. "Bluffing" certainly isn't the right word. "Hallucinating" fits much better.
  - kelnos 2y ago
    > By comparison, modern C# is memory safe all the way down, possible to implement even very complicated data structures without a single line of unsafe code "Confidence" is the wrong word. Confidence is a capability of thinking, sentient beings, and LLMs are not that. I say this to point out the futility in your post; "bluffing" is a perfectly fine thing for the GP to say, because it gets the point across. All of us here should know that an LLM can't actually bluff. (And if you'd prefer a different term, remember that not everyone on HN speaks English as their first language, and may not immediately come up with a more appropriate way of phrasing it.)
anonymoushn 2y ago

Havoc 2y ago

What’s the usage case for scanning html at gigs per second speed? Speeding up browsers? Crawling?

spartanatreyu 2y ago
Sometimes html pages can get pretty big, why not optimise it? Also, speeding up html parsing means speeding up browsers, crawlers, e2e tests, visual regression tests, etc...
- abirch 2y ago
  A lot of html, css, and JavaScript may not be independent.
  - kelnos 2y ago
    Sure, but if you parse the HTMl faster, you find the <script> and <link rel="stylesheet"> tags sooner, and can kick off another network thread to start fetching those files sooner. Overall you end up with a faster page load.
noir_lord 2y ago
If you improve parsed/scanned speed of html in Chromium by say 1%, that doesn't sound impressive. Then you consider 3 billion people use chrome (or Chromium derived browsers) multiply that out by how much html gets parsed/scanned a day by those users and then consider the energy costs - it quite quickly gets to a massive number (and that's just actual users, Chromium is also the core of Electron and a alot of other tooling) Simply put at Google's scale, tiny incremental gains compound to a massive species wide saving. At scale everything matters :).
dmw_ng 2y ago
Sufficiently fast software often allows leaving out whole layers of crap and needless indirection, the most common being caching. Fixing an algorithm so you can omit a dedicated database of intermediate results can be a huge maintainability/usability improvement. The same principle appears all over the place, e.g. immediate mode UIs, better networking (e.g. CSS image tiling vs. just fixing small request overhead in HTTP1 vs. QUIC), importing giant CSV files via some elaborate ETL process vs. just having a lightning fast parser+query engine, etc. Depending on how you look at it, you could view large chunks of DOM state through this lens, as intermediate data that only exists to cache HTML parsing results. What's the point of allocating a hash table to represent element attributes if they are unchanged from the source document, and reparsing them from the source is just as fast as keeping around the parsed form? etc. These kinds of tricks only tend to present themselves after optimization work is done, which is annoying, because it's usually so damn hard to justify optimization work in the first place.

cyberax 2y ago

I'm really bummed that Parabix went nowhere: https://ieeexplore.ieee.org/document/6169041 https://ieeexplore.ieee.org/document/6169041 It's apparently still alive, though: https://cs-git-research.cs.surrey.sfu.ca/cameron/parabix-devel/-/tree/master https://cs-git-research.cs.surrey.sfu.ca/cameron/parabix-dev...

JoshTriplett 2y ago

I'm surprised that this pays attention to '\r' (CR) specifically, and not '\n' (LF), ' ' (space), or '\t' (tab). It doesn't seem like HTML assigns any special meaning to carriage return compared to other whitespace. What is the parser doing with the locations of carriage returns?

rurban 2y ago
I also have no idea why he needs the newline-mask \r. Only <pre> blocks only on windows would need that.
- account42 2y ago
  <pre> blocks don't depend on the OS, that would be ridiculous.
kristianp 2y ago
Is it something to do with http headers? They have CR LF pairs terminating the lines.
- JoshTriplett 2y ago
  I wondered about that, but that wouldn't be described as parsing HTML, and it shouldn't involve parsing '<' and '&'.
eknkc 2y ago
Probably need to do a pass to find all \r chars, check if the next char is \n and if so, discard it. Otherwise convert it to \n. edit: Yeah, does exactly that: https://chromium-review.googlesource.com/c/chromium/src/+/5538407/33/third_party/blink/renderer/core/html/parser/html_document_parser_fastpath.cc#836 https://chromium-review.googlesource.com/c/chromium/src/+/55...

feverzsj 2y ago

We really need an updated html parser for c/c++. Most people are still using gumbo, which was abandoned by google 10 years ago. Some are using lexbor, which lacks basic document.

codedokode 2y ago

Cannot compilers auto-vectorize such loops? I think it would be more valuable to teach compilers to recognize such loops rather than simply write the code.

mistercow 2y ago

Seems like you could do something similar, combined with an exclusive scan, to rapidly find all the (potential) tag offsets in an HTML file on the GPU. I doubt that would be worthwhile in a browser due to the overhead of simply talking to the GPU, but it seems like it could be a useful trick if you have gigabytes of HTML to scan.

aynyc 2y ago

Maybe I'm jaded. As soon as this is out in the wild, web devs will come up with new ways to slow their websites down.

kolme 2y ago
Hey. Webdev here ;-) It's the other way around: after every optimization we have more "budget" to spend. More code, more bloat that we can get away with.