Investigate storing display lists using a different data structure
Categories
(Core :: Web Painting, enhancement, P2)
Tracking
()
| Tracking | Status | |
|---|---|---|
| firefox99 | --- | fixed |
People
(Reporter: mikokm, Assigned: mikokm)
References
Details
Crash Data
Attachments
(6 files)
Currently, display lists are stored in linked lists.
An interesting alternative to this would be to separate display item ordering from the display item data.
For example, we could have one array for all display items and assign an id for them based on their index in the array. This would give us O(1) lookups using the id. Display items containing other display items could then store a list of ids instead of the actual display items.
It is hard to quantify the impact of this, but it seems at least worth prototyping.
|
Assignee | |
Comment 1•3 years ago
|
||
I tried a couple of alternatives here that were relatively easy to get working: std::deque and std::list.
Using std::deque made display list related talos tests almost twice as slow, which is probably due to size and complexity of the data structure.
0 | class mozilla::nsDisplayList
0 | (nsDisplayList vtable pointer)
8 | class std::deque<class mozilla::nsDisplayItem *> mItems
8 | class std::_Deque_base<class mozilla::nsDisplayItem *, class std::allocator<class mozilla::nsDisplayItem *> > (base)
8 | struct std::_Deque_base<class mozilla::nsDisplayItem *, class std::allocator<class mozilla::nsDisplayItem *> >::_Deque_impl _M_impl
8 | class std::allocator<class mozilla::nsDisplayItem *> (base) (empty)
8 | class __gnu_cxx::new_allocator<class mozilla::nsDisplayItem *> (base) (empty)
8 | struct std::_Deque_base<class mozilla::nsDisplayItem *, class std::allocator<class mozilla::nsDisplayItem *> >::_Deque_impl_data (base)
8 | std::_Deque_base<class mozilla::nsDisplayItem *, class std::allocator<class mozilla::nsDisplayItem *> >::_Map_pointer _M_map
16 | std::size_t _M_map_size
24 | struct std::_Deque_iterator<class mozilla::nsDisplayItem *, class mozilla::nsDisplayItem *&, class mozilla::nsDisplayItem **> _M_start
24 | std::_Deque_iterator<class mozilla::nsDisplayItem *, class mozilla::nsDisplayItem *&, class mozilla::nsDisplayItem **>::_Elt_pointer _M_cur
32 | std::_Deque_iterator<class mozilla::nsDisplayItem *, class mozilla::nsDisplayItem *&, class mozilla::nsDisplayItem **>::_Elt_pointer _M_first
40 | std::_Deque_iterator<class mozilla::nsDisplayItem *, class mozilla::nsDisplayItem *&, class mozilla::nsDisplayItem **>::_Elt_pointer _M_last
48 | std::_Deque_iterator<class mozilla::nsDisplayItem *, class mozilla::nsDisplayItem *&, class mozilla::nsDisplayItem **>::_Map_pointer _M_node
56 | struct std::_Deque_iterator<class mozilla::nsDisplayItem *, class mozilla::nsDisplayItem *&, class mozilla::nsDisplayItem **> _M_finish
56 | std::_Deque_iterator<class mozilla::nsDisplayItem *, class mozilla::nsDisplayItem *&, class mozilla::nsDisplayItem **>::_Elt_pointer _M_cur
64 | std::_Deque_iterator<class mozilla::nsDisplayItem *, class mozilla::nsDisplayItem *&, class mozilla::nsDisplayItem **>::_Elt_pointer _M_first
72 | std::_Deque_iterator<class mozilla::nsDisplayItem *, class mozilla::nsDisplayItem *&, class mozilla::nsDisplayItem **>::_Elt_pointer _M_last
80 | std::_Deque_iterator<class mozilla::nsDisplayItem *, class mozilla::nsDisplayItem *&, class mozilla::nsDisplayItem **>::_Map_pointer _M_node
88 | _Bool mIsOpaque
89 | _Bool mForceTransparentSurface
| [sizeof=96, dsize=90, align=8,
| nvsize=90, nvalign=8]
std::list performed considerably better and took less space.
0 | class mozilla::nsDisplayList
0 | (nsDisplayList vtable pointer)
8 | class std::list<class mozilla::nsDisplayItem *> mItems
8 | class std::_List_base<class mozilla::nsDisplayItem *, class std::allocator<class mozilla::nsDisplayItem *> > (base)
8 | struct std::_List_base<class mozilla::nsDisplayItem *, class std::allocator<class mozilla::nsDisplayItem *> >::_List_impl _M_impl
8 | class std::allocator<struct std::_List_node<class mozilla::nsDisplayItem *> > (base) (empty)
8 | class __gnu_cxx::new_allocator<struct std::_List_node<class mozilla::nsDisplayItem *> > (base) (empty)
8 | struct std::__detail::_List_node_header _M_node
8 | struct std::__detail::_List_node_base (base)
8 | struct std::__detail::_List_node_base * _M_next
16 | struct std::__detail::_List_node_base * _M_prev
24 | std::size_t _M_size
32 | _Bool mIsOpaque
33 | _Bool mForceTransparentSurface
| [sizeof=40, dsize=34, align=8,
| nvsize=34, nvalign=8]
The performance of std::list was within 10-15% of our current implementation. Based on profiling, it seemed that std::list performed worse while appending items during merging. This is most likely the overhead of allocating internal list nodes, which our current implementation does not have to do, since the items themselves are list nodes.
Based on the results, while we are appending to both ends of the display lists, our current implementation is probably the best we can do. Fixing bug 1722346 would allow us to experiment further with std::vector or nsTArray.
|
|
Assignee | |
Comment 2•3 years ago
|
||
|
|
Assignee | |
Comment 3•3 years ago
|
||
|
|
Assignee | |
Updated•2 years ago
|
|
|
Assignee | |
Comment 4•2 years ago
|
||
|
|
Assignee | |
Comment 5•2 years ago
|
||
Depends on D138152
|
||
Updated•2 years ago
|
Pushed by mikokm@gmail.com: https://hg.mozilla.org/integration/autoland/rev/a2da895a58ce Part 1: Decouple nsDisplayList internal list from nsDisplayItems r=mstange https://hg.mozilla.org/integration/autoland/rev/3baead3e079b Part 2: Remove nsDisplayList::RemoveBottom() r=mstange
|
||
Comment 7•2 years ago
|
||
| bugherder | ||
https://hg.mozilla.org/mozilla-central/rev/a2da895a58ce
https://hg.mozilla.org/mozilla-central/rev/3baead3e079b
|
|
||
Comment 8•2 years ago
|
||
Backed out per developer's request for causing crashes
|
||
Updated•2 years ago
|
|
||
Comment 9•2 years ago
|
||
Here is a test case from the fuzzers.
|
|
||
Updated•2 years ago
|
|
|
||
Comment 10•2 years ago
|
||
A Pernosco session is available here: https://pernos.co/debug/Qq-zMvYInlhGUjJiyO865w/index.html
|
|
Assignee | |
Comment 11•2 years ago
|
||
Depends on D138153
|
||
Comment 12•2 years ago
|
||
Pushed by mikokm@gmail.com: https://hg.mozilla.org/integration/autoland/rev/a261bb633790 Part 1: Decouple nsDisplayList internal list from nsDisplayItems r=mstange https://hg.mozilla.org/integration/autoland/rev/ae6b08b3f4de Part 2: Remove nsDisplayList::RemoveBottom() r=mstange https://hg.mozilla.org/integration/autoland/rev/0f95a5563c86 Part 3: Add crashtest r=nical
|
||
Comment 13•2 years ago
|
||
| bugherder | ||
https://hg.mozilla.org/mozilla-central/rev/a261bb633790
https://hg.mozilla.org/mozilla-central/rev/ae6b08b3f4de
https://hg.mozilla.org/mozilla-central/rev/0f95a5563c86
|
||
Updated•2 years ago
|
Description
•