Re:Modernizing the DOM Tree in Microsoft Edge
by c-smile on Wednesday April 19, 2017 @04:52PM
(#14151654)
Well, 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.
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.