3 ms·

That last part sounds interesting. Can you elaborate?

kragen 5y ago
DOM nodes are mutable and have parent pointers, so there's no way to share structure between duplicated parts of the element tree; JS might mutate them to no longer be duplicates. NodeLists like the .childNodes property (but not the results of, say, .querySelectorAll) are required to be "live", magically updating when you change the document; this code produces 1 even though there's no explicit mutation of c: let d = document, b = d.body, c = b.childNodes, n = c.length; b.appendChild(d.createElement('div')); console.log(c.length - n); So to a significant extent we're stuck for eternity with the design tradeoffs and even bugs of Internet Explorer 3, because bugs like this one are exposed through this interface and standardized by the W3C. If you weren't constrained by W3C DOM compatibility and wanted to trade off lower memory usage for slower small mutations, one extreme strategy would be to maintain chunks of the page tree as Polish-notation bytecode instead of materialized nodes full of pointers; then this discussion-thread page, with its 60 K of text and 3000 HTML elements (expanded to 4758 since my earlier comment, but let's disregard that), might require 80K of RAM instead of 512K or more. So for example <tr class='athing comtr' id='30861517'><td><table border='0'> <tr> <td class='ind'indent='3'> might become { tr # 2 bytes attr class "athing comtr" # 3 bytes attr id "30861517" # 4 bytes, plus 16 or so for the string table entry { td # 2 bytes } # 1 byte { table attr border "0" text " " # 4 bytes, text is inline with prefixed length { tr text " " # 6 bytes { td attr class "ind" attr indent "3" ... } } } } assuming the tag names and attribute names and values are indices into a "symbol table" in a UTF-8-style variable-length encoding, an encoding which is also used for byte string lengths. This encoding reduces the original 97 bytes of this fragment (plus its end tags) to about 57 bytes. You wouldn't want to store the entire page as a single long string of such bytecode, because that would make tree traversals unreasonably slow. You'd limit the bytecode blocks to 32–256 operations and then build a more conventional node tree or B-tree to knit those leaves together into a whole document. Mutations to the page inside such a leaf block would require rebuilding the block. In 02022 slower small DOM mutations seems like a very reasonable idea given the prevalence of things like React which tend to rebuild large parts of the page from scratch anyway. Of course even more extreme points on the time/space tradeoff curve do exist; you could reparse the HTML source from an LZMA-compressed representation on every redraw (compression ratio 8.3 on the current 304kB version of this page, so the 179K incarnation we've been using as an example would be about 22K, and a little HTML minification might squeeze that down further). But my intuition is that even with current CPUs you wouldn't get reasonable performance that way. Why "512K or more"? The DOM more or less requires pointers to parent, nextSibling, and firstChild, which we can suppose are 64 bits, plus a 64-bit field for node type and padding, which gives us 32 bytes per node; there are about 0.85 text nodes per element, so we have about 5400 nodes for 3000 HTML elements, giving 172.8 kB, and adding in the size of the text gets us past 256KiB. And then we need some space for attributes, cached layout, cached styles, etc. So 512K is easy and the reality is more like 1–4 MiB. For a page that Links renders into 60K of UTF-8 text! For more markup-heavy pages, which is almost all of them, the ratio is larger. An intermediate tradeoff would be something like Fredrik Lundh's ElementTree interface for Python, but with iterators over the tree represented as variable-size paths down from the root, permitting hash consing to automatically share structure between all the instances of <td class='ind' indent='4'><img src="s.gif" height="1" width="160"></td>, "reply", " | ", "[–]", and <a href="user?id=akling" class="hnuser">akling</a>. Moreover the ElementTree design doesn't require type-tag fields (though CPython of course does spend memory on them). In ElementTree each element has string attributes .tag, .text (the leading CDATA text inside the element, possibly None in the Python implementation, which I see as a design error), and .tail (any CDATA text that follows the element, also possibly None in the Python implementation), a list of zero or more child elements, and a possibly-empty string-to-string map (dict) of attributes. There are no parent pointers, though the mutability of ElementTree itself means you still can't share child subtrees that happen to be equal. Child elements are always elements; text and tail are always strings (except where null). Consider a FORTRAN-style linked-list representation of an ElementTree. For a page tree of up to 65535 elements, 65535 text nodes, and 65535 name-value pairs, you could represent these as arrays of 16-bit integers, assigning each element a 16-bit element ID used to index parallel arrays of 16-bit ints named TAG, TEXT, TAIL, KID, NEXT, and ATTR. KID and NEXT contain element IDs which are -1 to indicate no children or no following siblings, respectively. ATTR may contain -1 (no attributes) or index three parallel arrays named NAME, VALUE, and MORE, the third of which contains -1 or another index into these three tables. TAG, TEXT, TAIL, NAME, and VALUE all index a string table, which is an array of 32-bit ints named START. START indexes an array of bytes named CHARS, and there's an allocation pointer FREE which points to the lowest unused index in START. The bytes of string N start at CHARS[START[N]] and continue to CHARS[START[N+1]]; the first unused byte in CHARS is at CHARS[START[FREE]]. Optionally you can build a hash table over the entries in START to allow the reuse of duplicate strings, since you can't efficiently insert or delete characters within an existing string anyway. This works out to 12 bytes per element, 6 bytes per attribute, and 4 bytes per string, and it allows mutation just as efficiently as the Python version (i.e., you have to make a copy of any string you want to modify, but you can insert and delete elements in constant time, or graft them onto a different part of the element tree). And it's simpler, not more complex, to iterate over or evaluate CSS-style selector queries on, than the W3C DOM. With this representation, if you had 3000 elements, 3000 attributes, and 2500 strings totaling 60 kB of text, you'd need 124 kB of memory, plus allocation overhead. And if you're in a reasonably dynamic language you can replace these arrays of 16-bit integers with arrays of 32-bit integers whenever one of these collections goes over 65536 elements. (In Numpy this is quite transparent once it is done.)
- kragen 5y ago
  I missed the editing window, but here's a simple example of ElementTree in Python; consider what it would take to do this in JS with the DOM if you had to implement .innerText yourself: >>> from xml.etree import ElementTree >>> def text(e): ... return (e.text or '') + ''.join( text(kid) for kid in e.getchildren()) + (e.tail or '') ... >>> text(ElementTree.fromstring('<p>My <b>Malamute</b> is <i>really</i> hairy.</p>')) 'My Malamute is really hairy.' Or if you had to implement .querySelectorAll yourself: >>> def find(e, clase): ... if e.get('class') == clase: yield e ... for kid in e.getchildren(): ... for nieto in find(kid, clase): yield nieto ... >>> list(find(ElementTree.fromstring('<p>My <b class="dog">Malamute</b> is <i>really</i> hairy.</p>'), 'dog')) [<Element 'b' at 0x7f14717c7a10>] In Python the .getchildren() call is unnecessary because ElementTree elements implement Python's iteration protocol, but I thought that might obscure the point a little. On the other hand, without the dopey None case I objected to above, you wouldn't need the "or ''".
  - easrng 5y ago
    You aren't implementing innerText, you're implementing textContent. Consider the HTML a<b>c</b>d<div>e<div>f</div></div>. Using textContent results in "acdef", while innerText results in "acd\ne\nf". Implementing textContent is easy: function getText(node, returnArray){ const a = Array.prototype.map.call(node.childNodes, e=>e.nodeType==3?e.data:getText(e, true)) return returnArray?a:a.flat(Infinity).join("") } Which can be golfed down to let getText=(n,f=(n,a)=>[].map.call(n.childNodes,e=>e.nodeType==3?e.data:f(e,1)))=>f(n,f).flat(1e333).join("") InnerText is harder, you have to consider visibility and if the element is block or inline. You can't properly calculate innerText without parsing CSS.
    - kragen 5y ago
      Very nice! And thank you for the correction about innerText. Still, I think that let getText = n => n.text + n.getchildren().map(getText).join('') + n.tail is nicer than let getText=(n,f=(n,a)=>[].map.call(n.childNodes,e=>e.nodeType==3?e.data:f(e,1)))=>f(n,f).flat(1e333).join("") and not just because it's less strokes.

DOM nodes are mutable and have parent pointers, so there's no way to share structure between duplicated parts of the element tree; JS might mutate them to no longer be duplicates. NodeLists like the .childNodes property (but not the results of, say, .querySelectorAll) are required to be "live", magically updating when you change the document; this code produces 1 even though there's no explicit mutation of c: let d = document, b = d.body, c = b.childNodes, n = c.length; b.appendChild(d.createElement('div')); console.log(c.length - n); So to a significant extent we're stuck for eternity with the design tradeoffs and even bugs of Internet Explorer 3, because bugs like this one are exposed through this interface and standardized by the W3C. If you weren't constrained by W3C DOM compatibility and wanted to trade off lower memory usage for slower small mutations, one extreme strategy would be to maintain chunks of the page tree as Polish-notation bytecode instead of materialized nodes full of pointers; then this discussion-thread page, with its 60 K of text and 3000 HTML elements (expanded to 4758 since my earlier comment, but let's disregard that), might require 80K of RAM instead of 512K or more. So for example <tr class='athing comtr' id='30861517'><td><table border='0'> <tr> <td class='ind'indent='3'> might become { tr # 2 bytes attr class "athing comtr" # 3 bytes attr id "30861517" # 4 bytes, plus 16 or so for the string table entry { td # 2 bytes } # 1 byte { table attr border "0" text " " # 4 bytes, text is inline with prefixed length { tr text " " # 6 bytes { td attr class "ind" attr indent "3" ... } } } } assuming the tag names and attribute names and values are indices into a "symbol table" in a UTF-8-style variable-length encoding, an encoding which is also used for byte string lengths. This encoding reduces the original 97 bytes of this fragment (plus its end tags) to about 57 bytes. You wouldn't want to store the entire page as a single long string of such bytecode, because that would make tree traversals unreasonably slow. You'd limit the bytecode blocks to 32–256 operations and then build a more conventional node tree or B-tree to knit those leaves together into a whole document. Mutations to the page inside such a leaf block would require rebuilding the block. In 02022 slower small DOM mutations seems like a very reasonable idea given the prevalence of things like React which tend to rebuild large parts of the page from scratch anyway. Of course even more extreme points on the time/space tradeoff curve do exist; you could reparse the HTML source from an LZMA-compressed representation on every redraw (compression ratio 8.3 on the current 304kB version of this page, so the 179K incarnation we've been using as an example would be about 22K, and a little HTML minification might squeeze that down further). But my intuition is that even with current CPUs you wouldn't get reasonable performance that way. Why "512K or more"? The DOM more or less requires pointers to parent, nextSibling, and firstChild, which we can suppose are 64 bits, plus a 64-bit field for node type and padding, which gives us 32 bytes per node; there are about 0.85 text nodes per element, so we have about 5400 nodes for 3000 HTML elements, giving 172.8 kB, and adding in the size of the text gets us past 256KiB. And then we need some space for attributes, cached layout, cached styles, etc. So 512K is easy and the reality is more like 1–4 MiB. For a page that Links renders into 60K of UTF-8 text! For more markup-heavy pages, which is almost all of them, the ratio is larger. An intermediate tradeoff would be something like Fredrik Lundh's ElementTree interface for Python, but with iterators over the tree represented as variable-size paths down from the root, permitting hash consing to automatically share structure between all the instances of <td class='ind' indent='4'><img src="s.gif" height="1" width="160"></td>, "reply", " | ", "[–]", and <a href="user?id=akling" class="hnuser">akling</a>. Moreover the ElementTree design doesn't require type-tag fields (though CPython of course does spend memory on them). In ElementTree each element has string attributes .tag, .text (the leading CDATA text inside the element, possibly None in the Python implementation, which I see as a design error), and .tail (any CDATA text that follows the element, also possibly None in the Python implementation), a list of zero or more child elements, and a possibly-empty string-to-string map (dict) of attributes. There are no parent pointers, though the mutability of ElementTree itself means you still can't share child subtrees that happen to be equal. Child elements are always elements; text and tail are always strings (except where null). Consider a FORTRAN-style linked-list representation of an ElementTree. For a page tree of up to 65535 elements, 65535 text nodes, and 65535 name-value pairs, you could represent these as arrays of 16-bit integers, assigning each element a 16-bit element ID used to index parallel arrays of 16-bit ints named TAG, TEXT, TAIL, KID, NEXT, and ATTR. KID and NEXT contain element IDs which are -1 to indicate no children or no following siblings, respectively. ATTR may contain -1 (no attributes) or index three parallel arrays named NAME, VALUE, and MORE, the third of which contains -1 or another index into these three tables. TAG, TEXT, TAIL, NAME, and VALUE all index a string table, which is an array of 32-bit ints named START. START indexes an array of bytes named CHARS, and there's an allocation pointer FREE which points to the lowest unused index in START. The bytes of string N start at CHARS[START[N]] and continue to CHARS[START[N+1]]; the first unused byte in CHARS is at CHARS[START[FREE]]. Optionally you can build a hash table over the entries in START to allow the reuse of duplicate strings, since you can't efficiently insert or delete characters within an existing string anyway. This works out to 12 bytes per element, 6 bytes per attribute, and 4 bytes per string, and it allows mutation just as efficiently as the Python version (i.e., you have to make a copy of any string you want to modify, but you can insert and delete elements in constant time, or graft them onto a different part of the element tree). And it's simpler, not more complex, to iterate over or evaluate CSS-style selector queries on, than the W3C DOM. With this representation, if you had 3000 elements, 3000 attributes, and 2500 strings totaling 60 kB of text, you'd need 124 kB of memory, plus allocation overhead. And if you're in a reasonably dynamic language you can replace these arrays of 16-bit integers with arrays of 32-bit integers whenever one of these collections goes over 65536 elements. (In Numpy this is quite transparent once it is done.)

kragen 5y ago
I missed the editing window, but here's a simple example of ElementTree in Python; consider what it would take to do this in JS with the DOM if you had to implement .innerText yourself: >>> from xml.etree import ElementTree >>> def text(e): ... return (e.text or '') + ''.join( text(kid) for kid in e.getchildren()) + (e.tail or '') ... >>> text(ElementTree.fromstring('<p>My <b>Malamute</b> is <i>really</i> hairy.</p>')) 'My Malamute is really hairy.' Or if you had to implement .querySelectorAll yourself: >>> def find(e, clase): ... if e.get('class') == clase: yield e ... for kid in e.getchildren(): ... for nieto in find(kid, clase): yield nieto ... >>> list(find(ElementTree.fromstring('<p>My <b class="dog">Malamute</b> is <i>really</i> hairy.</p>'), 'dog')) [<Element 'b' at 0x7f14717c7a10>] In Python the .getchildren() call is unnecessary because ElementTree elements implement Python's iteration protocol, but I thought that might obscure the point a little. On the other hand, without the dopey None case I objected to above, you wouldn't need the "or ''".
- easrng 5y ago
  You aren't implementing innerText, you're implementing textContent. Consider the HTML a<b>c</b>d<div>e<div>f</div></div>. Using textContent results in "acdef", while innerText results in "acd\ne\nf". Implementing textContent is easy: function getText(node, returnArray){ const a = Array.prototype.map.call(node.childNodes, e=>e.nodeType==3?e.data:getText(e, true)) return returnArray?a:a.flat(Infinity).join("") } Which can be golfed down to let getText=(n,f=(n,a)=>[].map.call(n.childNodes,e=>e.nodeType==3?e.data:f(e,1)))=>f(n,f).flat(1e333).join("") InnerText is harder, you have to consider visibility and if the element is block or inline. You can't properly calculate innerText without parsing CSS.
  - kragen 5y ago
    Very nice! And thank you for the correction about innerText. Still, I think that let getText = n => n.text + n.getchildren().map(getText).join('') + n.tail is nicer than let getText=(n,f=(n,a)=>[].map.call(n.childNodes,e=>e.nodeType==3?e.data:f(e,1)))=>f(n,f).flat(1e333).join("") and not just because it's less strokes.