7 ms·
So new IE’s dom::node essentially looks as struct node { element* parent; node *first_child, *next, *previous; } And that was also my init
by c-smile 10y ago
So 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 }
- c-smile 10y agoThis does not work, element/node shall have stable address so to be O(1) addressable. Elements/nodes can participate in multiple lists at the same time. Rendering lists (a.k.a. rendering tree) and things like Document.querySelectorAll() that returns NodeList.
- deleted 10y ago[deleted]
- Someone 10y agoCan I conclude that your earlier statement "yet the structure ensures that there are no loops in the tree." isn't correct? I could easily create a loop like this: this.children[0] = this;
- wtetzner 10y agoHow could that happen, given that children isn't a pointer? vector<node*> children;
- 10y ago
- smitherfield 10y agoWith all due respect (it looks like some seriously impressive work you've done), how do you know they're using "typical algorithms?" Maybe they've devised something new or uncommon, or significant new optimizations of the "typical algorithms." In general I'd give a company like Microsoft the benefit of the doubt that they know what they're doing, and have considered and rejected alternative approaches — at least when it comes to objectively-measurable technical goals like "create a fast data structure to represent a DOM tree," if not always subjective big-picture goals like "make a good web browser" (even in that case, IE was, for its time, a good web browser — the best — until Ballmer let it languish). Your data structure looks to me like it's roughly optimal for the case where the DOM tree is generated once and then is never or rarely modified, and nodes have several children relatively frequently and no children relatively rarely. But in the age of single-page-apps and other Javascript-heavy jQuery/Angular/React-type sites filled with DOM manipulation and AJAX, it's more important (especially in the exponentially-increasingly-common pathological case) to make it inexpensive to insert, delete and move nodes within the DOM tree. With your data structure, every time you create a new `Node`, even one without any children, you have to allocate a new `vector`, which is a lot more expensive than just three pointers. Every time you insert or move a Node to an arbitrary location means an extremely expensive random-access insert into a vector (especially if it triggers a realloc), and every insertion, move or deletion in an arbitrary location requires updating the `node_index` of every sibling (old and new, in the case of a move), which also defeats the advantage of vectors over linked lists (avoiding indirection).
- c-smile 10y ago"Your data structure looks to me like it's roughly optimal for the case where the DOM tree is generated once and then is never or rarely modified" Check gmail for example. It has just one list - element that has 100 children. Other elements have from 0 to 10 children. And that 100 list is normally populated as a whole. "even one without any children, you have to allocate a new `vector`" You don't need to allocate anything if vector is empty ... Vectors's data buffer gets allocated only when you put something in the vector. At least in my case. So empty vector is just one pointer - nothing to write home about it. "every insertion, move or deletion in an arbitrary location requires updating the `node_index` of every sibling" On any DOM insertion you need to scan all siblings almost always anyway. For quite many reasons, e.g. to reset styles that could use `this ~ that` or something like `:nth-child(odd)`
- deleted 10y ago[deleted]
- 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 10y agoAll nicecly ordered in linear memory for good data locality?