[Webkit-unassigned] [Bug 37060] List item markers are not always updated after changes in the DOM

[bugzilla-daemon at webkit.org]

https://bugs.webkit.org/show_bug.cgi?id=37060





--- Comment #14 from Jakub Wieczorek <jwieczorek at webkit.org>  2010-04-05 10:24:58 PST ---
(In reply to comment #13)
> > We're not making the complexity worse as such (it was already pretty much n^2)
> > but yes, we're possibly making the code slower for some cases. To fix the bugs
> > we're fixing here we need to be traversing more than before.
> 
> I'd like to see some actual test data. It should be easy to make something so
> huge that you can easily see these effects with a "stopwatch test".

OK, I'll give it a go.

> One thing that's different from our list marker code and our other similar code
> is that it's not coalesced. The values of markers are updated immediately, even
> if they are about to be invalidated a moment later by another DOM modification.
> Whereas other sorts of updates use an invalidation scheme and then get updated
> later, for example when layout occurs.

Are you sure this is the case? What the patch does (and so does the old code)
is calling updateValue() on the RenderListItems, which is:

void RenderListItem::updateValue()
{
    if (!m_hasExplicitValue) {
        m_isValueUpToDate = false;
        if (m_marker)
            m_marker->setNeedsLayoutAndPrefWidthsRecalc();
    }
}

And then, on the next layout, RenderListMarker pulls the value, which is lazily
calculated in updateValueNow().

But still, what we're doing too many times is marking items as outdated.

> > We can benefit from the assumption, that whenever a list item is marked as
> > needing an update to the marker, then all the subsequent ones will be too (this
> > was not true before but with this patch is). I can't think of any situation
> > where that would not be the case:
> > 1) changing the start value for a list revaluates the whole list
> > 2) changing the value of an item revaluates all the subsequent ones
> > 3) adding/removing items revaluates all the subsequent ones
> > 
> > If this is true, then I could improve this, either as part of this patch, or a
> > separate one.
> 
> There's another patch adding support for the "reversed" attribute for <ol>,
> which will probably change these assumptions and thus change this code.

Yes. For a reversed list, however, an opposite assumption would be true
(adding/removing an item requires all the previous ones to be updated or the
whole list for other changes, as above).

> An improvement that helps improve the case where you're constantly adding a new
> last item for an existing list is probably worthwhile. 

If we're adding a new last item for an existing list, we need to find out if
it's the last one. But anyway, we only go through the nodes after the new item
within the list subtree. So this case should already be fast.

> If we can prove this
> patch doesn't make any case significantly worse, then we can definitely leave
> optimization for a later patch. But we do need to double check that we haven't
> added any new bad performance behavior. I don't want any nasty surprises later
> from people testing live websites.

I understand that. I hope we can simply add the optimization I mentioned as
it's quite straightforward. This would make the code even faster than it was
before (assuming I got it right).

-- 
Configure bugmail: https://bugs.webkit.org/userprefs.cgi?tab=email
------- You are receiving this mail because: -------
You are the assignee for the bug.