9 ms·
Modernizing the DOM Tree in Microsoft Edge
- yuhong 10y agohttps://news.ycombinator.com/item?id=3233935 https://news.ycombinator.com/item?id=3233935
- timtadh 10y agoI case people didn't click through it is an awesome comment by the original author of the IE5 DOM Tree explaining how it was implemented.
- 0x0 10y agoThis is interesting and something I've suspected for a long while. I remember struggling big-time with older IE versions giving some really strange results when doing to perform DOM node manipulations on improperly nested HTML (which in turn often came from copy-pasting from Word), erroneous results that definitively hinted towards DOM tree operations actually happening on flat substrings.
- c-smile 10y agoSo new IE’s dom::node essentially looks as struct node { element* parent; node *first_child, *next, *previous; } And that was also my initial implementation of it in Sciter Engine (https://sciter.com https://sciter.com) but after some testing I’ve found that these two structures work better: struct node { element* parent; uint node_index; // its index in parent->children } struct element: node { vector<node*> children; } a) better suits DOM manipulation/traversal needs, b) more compact and faster, c) more CSS friendly (for things like :nth-child(2)), e) yet the structure ensures that there are no loops in the tree.
- amelius 10y agoIsn't this something one could abstract away?
- c-smile 10y agoIt is about this part in the article: > The new tree structure is simple and straightforward; it uses four pointers instead of the usual five to maintain connectivity: parent, first-child, next, and previous sibling That straightforward four pointers structure is not the best for HTML DOM. Neither memory wise nor for typical algorithms applied to it.
- hsivonen 10y agoWhat’s better in your opinion?
- Someone 10y agoI would guess what (s)he writes in https://news.ycombinator.com/item?id=14150628 https://news.ycombinator.com/item?id=14150628, except that, maybe, vector<node*> children; is a typo, and should be vector<node>* children; Reason: I don't see how the former enforces "e) yet the structure ensures that there are no loops in the tree." The latter would mean more copying of nodes, but would have excellent cache locality, so I can see it could well be faster, too.
- c-smile 10y agoIt is precisely vector<node*> children; yet this vector<node>* children; makes little sense in DOM case.
- deleted 10y ago[deleted]
- smitherfield 10y agoThat does seem like it makes more sense; you could then implement `node_index` as a fast, stateless inline method like so: constexpr vector<Node>::difference_type node_index() const noexcept { return parent ? this - parent->children->begin() : -1; // is a root node }
- taeric 10y agoAt a gut shot, only concern for this would be highly dynamic trees that are not either appending or prepending elements to children. I'd be curious to see benchmarks checking that. With this, I'm always bemused that there are not more discussions on algorithms for doing tree traversal that don't use a queue or a stack. I think you have everything you need here to accomplish that.
- c-smile 10y agoIt was discussed quite a loot actually. ArrayList (sciter's children list) vs LinkedList (Edge children list) : http://stackoverflow.com/questions/322715/when-to-use-linkedlist-over-arraylist http://stackoverflow.com/questions/322715/when-to-use-linked...
- taeric 10y agoI meant specifically in modeling the Dom. Apologies if that wasn't clear. The specific questions would be how often are the trees of a site dynamic and how often they insert instead of prepend or append. Edit: And, of course, I'm still interested in why more people don't use stackfree algorithms for DFS.
- c-smile 10y agoWell, almost all HTML/CSS layout algorithms are O(N) complex so number of immediate children of an element is naturally limited by, say, 500-1000 sub-nodes. Otherwise the whole thing will not move. Note that GMail uses pagination with 500-800 elements on the page. So we are speaking about vectors of pointers that contain 1000 elements. memmove() performance (used for quite rare operation of insertion of elements in the middle) on modern CPU is comparable with the need to access left/right elements in DL-lists for insertion. Consider cache misses, etc.
- taeric 10y agoThis all makes sense, but I have become ridiculously empirical in my old age. Actual data wins many arguments in ways that surprise reasoning.
- chuckdries 10y agoUnrelated question: How would you compare sciter to Electron? If I'm seeing this right, your thing is just for UI whereas electron has the whole application running in a browser-like environment, yes? How is communication handled between business and HTML?
- c-smile 10y agoSciter is essentially UI, yes. Engine with plain C API. You can easily add native methods to be callable from script. So to use any library/backend of your choice. boost, POCO, whatever. Yet you can use it with C/C++, D, .Net/Mono, Delphi, Go, Rust, Python : https://github.com/sciter-sdk https://github.com/sciter-sdk
- socmag 10y agoWhen you say pointers, do you actually mean pointers? I've implemented something like you describe before in a game engine for a managed language. Instead of using pointers though I used integers throughout. The actual state was maintained in a flat vector of element blocks and were stable. The nice thing about integers on a GC'd platform are that they are opaque to the GC so zero time was spent on pointer chasing. The other nice thing is you could literally dump the entire state to disk or restore pretty much in one go. Looks good though, and I agree (as you mention further down) that state can often be part of multiple list/trees simultaneously, so it makes better sense to keep them separate.
- userbinator 10y agomore compact and faster This is more of a general comment and may not necessarily be true in your implementation, but I see this argument brought up a lot: "vectors are arrays, therefore smaller (because only one pointer is needed per element) and faster than linked lists". However, one must remember that vectors are not statically sized arrays --- they dynamically size to hold their contents, and for the resizing to be (amortised) constant-time, there will on average always be some amount of unused space in the dynamic array, and you still need the (one) pointer to this dynamic array in the node itself, plus additional overhead to keep track of size/used. That's the "smaller" argument debunked. As for faster, that's not always true either, since simple forward/backward scans will require two indirections, one to get the dynamic array's address and another to get the pointer to the node itself. That's two memory accesses to areas which might not be close together at all. Compare this to one indirection (follow the next pointer) for a linked list, that is also made to an address in the vicinity of the rest of the node. In summary: the linked-list will be faster for forward/backward scans and inserts/deletes and slower at indexing, while the vector will be faster for indexing and slower for forward/backward scans. The linked list will be smaller too.
- c-smile 10y agostruct Node does not need first_child pointer when it is TextNode/CommentNodes/etc. as they are just terminals. Yet text node here <div>text</text> does not need next/previous pointers as it is lone child. In case of DOM tree children-vector case takes always less than "children-dl-list" case. With only one exception - element with single child node when size of memory needed is the same as in "children-dl-list".
- emmab 10y ago> As for faster, that's not always true either, since simple forward/backward scans will require two indirections, one to get the dynamic array's address and another to get the pointer to the node itself. Can this be stored in a register when you're accessing multiple locations in the array in sequence?
- yorwba 10y agoIf no insertions or deletions happen between accesses, a vector scan can also be done with only a single indirection, by simply incrementing the pointer to the node. This also means better locality than a linked list, where the next pointer may be close to the current node, while the next node can be anywhere. In a vector, they are simply next to each other.
- bzbarsky 10y agoA problem with the vector representation is that it makes some common DOM operations (removeChild and insertBefore) O(N) in the number of children. This can be a major problem in some cases. Gecko actually used to have that sort of representation and we have been trying to move away from it, for precisely that reason. If your DOM is more static, I agree it's a better representation.
- c-smile 10y agoremoveChild and insertBefore on DOM tree are always O(N) operations or at least causing full scan of children later. No matter how children are stored. Think about rules :nth-child(4) { border:1px solid; } and the like.
- emmab 10y agoThe page might not use rules like that though? And the browser could optimize the case where it doesn't.
- c-smile 10y agoThat just one example. One element removal means invalidation of container's layout. That means you will need to relayout container. That is a scan of children again. And so on.
- bzbarsky 10y agoAn element removal may also mean absolutely nothing if the container is display:none, say...
- bzbarsky 10y ago> removeChild and insertBefore on DOM tree are always O(N) operations It depends. If you insert only one node, I agree you end up doing some O(N) work later in many cases (though not nearly always). If you remove/insert k nodes at the front, in the vector case you do O(kN) work while in the doubly-linked-list case you do O(k+N) work at worst. In the case when k == N the difference is between O(N) and O(N^2). And yes, this is a problem in practice. We've seen popular web libraries doing this to remove all the kids of an element: while (foo.firstChild) foo.removeChild(foo.firstChild); which will be O(N^2) in a vector implementation. So the real question is what the amortized cost of an insert/remove is. Unless your web page is flushing out layout after every DOM modification (which is sadly too common), you will only redo selector matching every however many DOM mutations. In many cases "however many" is "thousands".
- pjako 9y agoAll nicecly ordered in linear memory for good data locality?
- ko27 10y agoNot to take anything away from Microsoft's accomplishments, but the latest chrome canary has a speedometer score of 140 (70% faster than Edge).
- najajomo 9y ago> Not to take anything away from Microsoft's accomplishments, but the latest chrome canary has a speedometer score of 140 (70% faster than Edge). I don't agree with that statement and can't refute it, but I'm going to mod it down into oblivion anyway ;)
- wtetzner 9y agoI suspect it was down-voted because it didn't add anything to the conversation.
- EdSharkey 10y agoI can see now why DOM manipulation was so catastrophic for performance on IE5-8, all that bookkeeping of character positions must have been a killer once the DOM tree was of any significant size. Makes me wonder. If edits to DOM nodes on legacy IE were focused on attribute values only, and the string-lengths of those edited attributes never changed, whether one could bypass the bookkeeping and get good performance gains.
- tambourine_man 10y agoGotta love this new Microsoft. A blog post openly geeking out on browser data structures. So good
- jstimpfle 10y agoHeh, just today I made this https://gist.github.com/jstimpfle/a4f2661f8d042d9862b9fecdd85a7c93 https://gist.github.com/jstimpfle/a4f2661f8d042d9862b9fecdd8... as a poor-man's PHP. It looks for made-up tags and calls with the tag attributes as arguments, to make text substitutions (no, not a very innovative idea). I used a cheap regex to look for these tags instead of parsing the DOM properly to avoid unnecessary allocations and parsing overhead. So after reading the article, I guess I'm still in the 90s! > TreeWriter::AppendChild(parent, child); That's soo the right approach. OO must die. And the argument why method calls are (typically) wrong already on a syntactic level can be found in the article.
- bsimpson 10y agoAlmost makes me wish it worked on non-MS systems… Kudos to the MS Edge team for pushing the Web forward!
- angry-hacker 10y agoWho knows, maybe one day it will in order to fight Google's monopoly?
- Jyaif 9y agoWhat MS is explaining in the article is that they've merely started using the same data structure as all the other engines. It was probably a huge amount of work, but that's more like not dragging the web backwards than pushing it forward.
- JustSomeNobody 10y agoInteresting. However can we please retire the word modern already? It's as bad as game changer.
- adrianratnapala 10y agoWhat I like about this article, even more than the technical specifics, is that it is an account of a successful, deep, in-flight refactoring effort. That is, they avoided the two most common errors: rewriting, and piling technical ever higher.
- aconz2 10y agoI see something like this and think about how much an ensemble approach to the data structure would help. This keeps popping up in places where you have a very general abstraction (like the DOM) and want to support a broad set of operations and use cases (read-only, insert heavy, traversal heavy, etc.) and so you often choose the structure which supports most of these cases pretty well. But you sacrifice a lot of perf by doing so. What I'm wondering is how well you could do perf-wise by having the DOM be comprised of a heterogeneous set of structures, each of which is chosen based on the history of what operations have been performed on it (ie. we're appending a lot here, let's use a vector of children). This is all similar in spirit and goals of: - JIT compiling, but for the data structures, and not code - This work on composing allocators in D https://www.youtube.com/watch?v=LIb3L4vKZ7U https://www.youtube.com/watch?v=LIb3L4vKZ7U - ML ensemble methods