Parsing XHTML string with Regex in Javascript and converting it to DOM

Question

Disclaimer: before the you-can't-parse-html-with-regex blind mantra begins - please give me the benefit of the doubt and read this question to the end (+ assume I already know about That RegEx-ing the HTML will drive you crazy and Parsing Html The Cthulhu Way)

---

Most of the complaints with Regex matching HTML come from the fact that HTML is loosely formed and Regex has difficulty matching different problems and user errors + some other things like recursion, etc.

However - what if HTML is actually valid XHTML (or more XML-like), that originated from a controlled environment (not general user-generated HTML document, but for example HTML-fragment templates that you would use in a client-side templating engine) and has been both manually checked for errors and validated numerous times?

---

Let me explain why I'm interested. I'm doing a speed benchmark of different String2DOM techniques in Javascript and I've tested everything from innerHTML, outerHTML, insertAdjacentHTML, createRange, DOMParser, doc.write (via iFrame) and even John Riesigs HTMLtoDOM JS library.

And I'm curious if there is a way to go even faster.

createElement/appendChild (+setAttribute and createTextNode) is the fastest way to create DOM elements in Javascript. Regex is the fastest way to traverse large strings. Couldn't these two methods still be combined to possibly create an even faster way to parse DOMString fragments into DOM?

An example HTML string:

<div class="root fragment news">

    <div class="whitebg" data-name='Freddie Mercury'>
        <div id='myID' class="column c2">
            <h1>This is my title</h1>
            <p>Vivamus urna <em>sed urna ultricies</em> ac<br/>tempor d </p>
            <p>Mauris vel neque sit amet Quisque eget odio</p>
        </div>      

        <div class="nfo hide">Lorem <a href='http://google.com/'>ipsum</a></div>
    </div>

</div>

So ideally the code would return a documentFragment with Regex parsing the XHTML soup and using createElement/appendChild (+setAttribute/createTextNode) to fill in the elements. (a similar but not quite there yet example is HTML2DOM)

I (and the rest of the world) am very very interested if something like that could beat the good old innerHTML in generating DOM from DOMString in JS. Could it?

Who's game to try their knowledge making something like that? And claim their place in the annals of Stackoverflow? :)

---

EDIT2: who ever is blindly down-voting this - at least explain what you feel is wrong with the question? I am pretty familiar with the subject, have provided the logic behind it and also explain what is different about this scenario + even post some links that provide similar solutions. What about you?

Answer 1

First off, the answer to all performance-oriented questions is "just benchmark it". You can write the code if you want to write the code, and its performance will speak for itself.

That said, I'm going to attempt to answer your question from my knowledge of web browser behavior and potentially save you some man-hours.

No, a custom Javascript-driven HTML parser could not "beat the good old innerHTML in generating DOM from DOMString in JS". It might, in theory, be able to get equally good performance, but that result is very unlikely.

The reason why is because Javascript is an interpreted language. An ideal JS interpreter will optimize the JS code down to its native equivalent sequence of browser-API calls. So, in the best case, writing JS code that does the equivalent of platform-native code will get identical performance: the JS code cannot outperform its native equivalent because, under the hood, it must still make the native calls.

The task at hand here is creating a DOM tree. Here's what happens when you set the innerHTML of an element:

JS: Browser, render me some HTML! Here's a Javascript string object.

Browser: parse_html_and_create_dom_objects()

Browser: notify_javascript_of_dom_creation()

Now, here's what happens if you drive the parser with Javascript:

JS: scan_string_for_next_token()

JS: Browser, add a DOM element here!

Browser: create_dom_object()

JS: scan_string_for_next_token()

JS: Browser, add a DOM element here!

Browser: create_dom_object()

JS: Browser, append the DOM tree you created to this visible-on-screen DOM tree!

Browser: refresh_page_view_and_notify_js()

In the native version, what would be a sequence of JS calls back to the browser can all be batched together and performed in pure preoptimized C.

I think the reason you believe it might be faster to do the parsing in JS than in the browser internals is because you've found that some web browsers have calling createElement repeatedly take less time than setting innerHTML to a chunk. This is because those two calls are not performing the same amount of work. When you call createElement, you're not doing string processing (no tokenization, no lexing). When you call innerHTML = <string>, you are. So whether innerHTML is faster than a series of createElement calls depends on whether the cumulative overhead of getting the elements from JS one by one outweighs the cost of parsing the HTML string. In other words, you cheated: your benchmark is not measuring an equal amount of work, since the code that calls createElement must have known in advance which elements to create.

It is very unlikely that both parsing the HTML string and creating the elements individually from JS could be faster than doing both inside the browser. If you do manage to write JS code that outperforms the browser internals, please submit it upstream to the browser authors: web browser performance improvements help everybody, and I'm sure the developers would appreciate the irony of getting superior performance from within a nested interpreter than the best they could achieve outside that interpreter.