Rework nsPropertyTable usage for frames

RESOLVED FIXED

Status

()

Core
Layout
RESOLVED FIXED
8 years ago
8 years ago

People

(Reporter: roc, Assigned: roc)

Tracking

(Blocks: 1 bug)

Trunk
Points:
---
Dependency tree / graph

Firefox Tracking Flags

(Not tracked)

Details

Attachments

(10 attachments, 1 obsolete attachment)

6.91 KB, patch
Details | Diff | Splinter Review
1.57 KB, text/plain
Details
8.33 KB, text/plain
Details
1.78 KB, text/plain
Details
17.15 KB, patch
mats
: review+
dbaron
: superreview+
Details | Diff | Splinter Review
171.29 KB, patch
mats
: review-
dbaron
: superreview+
Details | Diff | Splinter Review
16.94 KB, patch
Details | Diff | Splinter Review
171.61 KB, patch
Details | Diff | Splinter Review
17.39 KB, patch
mats
: review+
Details | Diff | Splinter Review
169.51 KB, patch
mats
: review+
Details | Diff | Splinter Review
Created attachment 431822 [details] [diff] [review]
patch to collect statistics for nsPropertyTable

I was looking at bug 534566 and decided to get some data for how we use nsPropertyTable for frames. The results are quite interesting.
Created attachment 431823 [details]
Perl script to analyze results

I ran the previous patch over one cycle of our Tp3 pageset and analyzed the results with this script.
Interesting fact #1: for frame properties, nsPropertyTable::GetPropertyListFor took an average of 6.8 iterations through the linked list to find the property table for a given nsIAtom*. That sounds bad. Worse, there's a lot of lookups taking 10-12 iterations. This gets called a lot --- every frame property get, set and delete.

Interesting fact #2:
Property		Fraction of frames where it occurs during frame-tree teardown
OverflowArea		3.59%
BaseLevel		1.41%
EmbeddingLevel		1.41%
UsedPaddingProperty	1.26%
FloatRegionProperty	1.02%
charType		0.83%
UsedMarginProperty	0.78%
ComputedOffsetProperty	0.57%
ViewProperty		0.37%
IBSplitSpecialPrevSibling	0.33%
IBSplitSpecialSibling	0.33%
BoxMetricsProperty	0.30%
:after			0.18%
:before			0.15%
TableBCProperty		0.04%
LineCursorProperty	0.03%
RowCursorProperty	0.00%

These were measured at frame-tree teardown, so properties like 'overflow' that are only used during reflow are not present.

Interesting fact #3: number of properties on each frame at frame-tree teardown
Number Of Properties	Frequency
0			90.74%
1			6.95%
2			1.31%
3			0.98%
4			0.02%
5			0.00%
Created attachment 431833 [details]
Usage of layout properties

This is a list based on code review of the names that we use for frame properties and what the type of the associated property value is. I've used nsAutoPtr to indicate where the property value points to an allocated object it owns. The interesting fact here is that almost all properties are owning pointers to heap-allocated objects.
Note that for more dynamic content, the iterations in nsPropertyTable::GetPropertyListFor would probably be a lot worse, since on every frame Destroy() we have to walk the entire list of property names --- doing a hash lookup on each one!
Based on this data, I think using a hashtable that maps frame pointers to a linked list of the properties for that frame would be a clear improvement. Enumerating and deleting all properties of a frame becomes trivial, getting/setting/deleting a property of a frame becomes significantly faster in the common case.

We could put a pointer to the property list directly in nsIFrame instead of using a hashtable. I'm not sure if that's a good idea or not. It's a pointer that would only be used for 9% of frames, in the steady state. Then again, each entry in a pointer-to-pointer hashtable probably costs 3-4 pointer-sized memory words on average (2 per entry, multiplied by some load factor), so 0.3 to 0.4 of a word per frame... maybe go with adding a pointer to nsIFrame.

The significant users of frame properties who don't already heap-allocate the property, who would need to with this scheme:

embeddingLevel (int)
baseLevel (int)
charType (int)

Should probably combine these into a single Bidi property value and allocate it.

IBSplitSpecialSibling (nsIFrame*)
IBSplitSpecialPrevSibling (nsIFrame*)

Should probably combine these into a single IBSiblings property value and allocate it.

changeListProperty (void)

This seems to be used in quite a bogus way. I'm not sure what to do about it.

newline (int)

There's only one of these at a time, normally, so we can recycle the object if allocating it is a problem.

viewProperty (nsIView*)
lineCursorProperty (nsLineBox*)
before (nsRefPtr<nsIContent>)
after (nsRefPtr<nsIContent>)

These are relatively rare, we can just allocate them.
BTW the reason I'm caring about this is because I want to add some more frame-property stuff to track retained layers and I was worried about the impact.

Also, using a pointer on the frame to a linked list of properties makes checking for the presence of a property very fast in the common case where the frame has 0 or 1 properties, which would let us simplify some code.
On reflection, the safest thing to do is probably to use a hashtable mapping frames to property lists and don't force all property values to be heap-allocated objects. If there's only one property (very common, see above), we can just put the property value pointer inline in that hash entry. If there are multiple properties we can heap-allocate a block of say 4 property entries (2 words each --- property name/descriptor, plus property value) which will be enough for almost all cases.
Created attachment 432515 [details] [diff] [review]
Part 1: FramePropertyTable

Untested, not looking for review, just super-review-ish comments on the API before I convert everything in layout...
Attachment #432515 - Flags: feedback?(dbaron)
It seems reasonable; however, I wonder if it's worth exposing the object representing the set of properties for a given frame more publicly.  I suspect (though I didn't look just now) that there are a bunch of places in code where we do more than one frame-property manipulation for the same frame, e.g., a get and a set of the same property, or manipulation of two or three properties in the same code.

Or would that make the API too ugly?
Attachment #432515 - Flags: feedback?(dbaron) → feedback+
I think you're probably right. I'll keep an eye out for that as I do the conversion.
If we do have a FrameProperties helper object, then a big question is whether we should make code like this safe:
  FrameProperties props = frame1->Properties();
  frame2->Properties().Set(...);
  props.Set(...);

Consider three implementation strategies:
1) FrameProperties contains a pointer to the property table and a pointer to the frame. We can just forward everything to the property table, and in the property table use a single-element cache of the last frame looked up and its hashtable entry to make repeated property accesses fast. The code above is safe.
2) FrameProperties contains a pointer to the property table, a pointer to the frame, and a pointer to the hashtable entry. The code above is not safe.
3) FrameProperties contains a pointer to the property table, a pointer to the frame, a pointer to the hashtable entry, and a generation counter so we can detect hashtable changes and invalidate our cached hashtable entry. The code above is safe.

3 is definitely a lose compared to 1. I lean towards 1. It's simple, safe and only negligibly less efficient than 2.

The question then is whether we should have a FrameProperties object at all, since with scheme 1, repeated accesses through the FramePropertyTable would be just as fast. I think probably yes, because we can then have just one method on nsIFrame that returns a FrameProperties object, so you can write "frame->Properties().Get(...)", "frame->Properties().Set(...)" instead of having to add many methods to nsIFrame.
Created attachment 433873 [details] [diff] [review]
Part 1: Create FramePropertyTable

I ended up going with strategy 1 --- just cache the last frame->Entry mapping in FramePropertyTable.
Attachment #432515 - Attachment is obsolete: true
Attachment #433873 - Flags: superreview?(dbaron)
Attachment #433873 - Flags: review?(matspal)
Created attachment 433874 [details] [diff] [review]
Part 2: convert frame code to use FramePropertyTable

Requesting sr only due to trivial interface changes in nsIFrame plus a few changes from nsIAtom* to const FramePropertyDescriptor* in other interfaces.
Attachment #433874 - Flags: superreview?(dbaron)
Attachment #433874 - Flags: review?(matspal)
Whiteboard: [needs review]
Comment on attachment 433873 [details] [diff] [review]
Part 1: Create FramePropertyTable

>+ * Property values are passed as void* but do not actually have to be
>+ * valid pointers. You can use NS_INT32_TO_PTR/NS_PTR_TO_INT32 to
>+ * store PRInt32 values. Null/zero values can be stored and retrieved.

Maybe have a comment that this is all conditional on the destructor for
the property handling such values correctly?

>+  /**
>+   * Remove and destroy all property values for a frame. This requires one
>+   * hashtable lookup (using the frame as the key) and a linear search
>+   * through the properties of that frame.
>+   */
>+  void DeleteAllFor(nsIFrame* aFrame);
>+  /**
>+   * Remove and destroy all property values for all frames. This requires
>+   * a linear search through the properties of all frame.
>+   */
>+  void DeleteAll();

Is "search" really the right term for going through every value in a
list?

>+/**
>+ * This class encapsulates the properties of a frame.
>+ */
>+class FrameProperties {
>+public:
>+  FrameProperties(FramePropertyTable* aTable, nsIFrame* aFrame)
>+    : mTable(aTable), mFrame(aFrame) {}
>+  FrameProperties(FramePropertyTable* aTable, const nsIFrame* aFrame)
>+    : mTable(aTable), mFrame(const_cast<nsIFrame*>(aFrame)) {}

Hmmm.  I'm not crazy about the const-ness here, but I can't think of a
better option.

sr=dbaron

(FWIW, I'm just looking at the interfaces when doing superreviews these
days.)
Attachment #433873 - Flags: superreview?(dbaron) → superreview+
Comment on attachment 433874 [details] [diff] [review]
Part 2: convert frame code to use FramePropertyTable

>+#define NS_DECLARE_FRAME_PROPERTY(prop, dtor)                   \
>+  static const FramePropertyDescriptor* prop() {                \
>+    static const FramePropertyDescriptor descriptor = { dtor }; \
>+    return &descriptor;                                         \
>+  }

Why is this a function rather than just a declaration of the struct?


sr=dbaron
Attachment #433874 - Flags: superreview?(dbaron) → superreview+
(In reply to comment #15)
> Maybe have a comment that this is all conditional on the destructor for
> the property handling such values correctly?

OK

> Is "search" really the right term for going through every value in a
> list?

No. I should just remove that comment, it's obvious that destroying all property values will be linear-time in general.

> (FWIW, I'm just looking at the interfaces when doing superreviews these
> days.)

Good!!!

(In reply to comment #16)
> (From update of attachment 433874 [details] [diff] [review])
> >+#define NS_DECLARE_FRAME_PROPERTY(prop, dtor)                   \
> >+  static const FramePropertyDescriptor* prop() {                \
> >+    static const FramePropertyDescriptor descriptor = { dtor }; \
> >+    return &descriptor;                                         \
> >+  }
> 
> Why is this a function rather than just a declaration of the struct?

You can't initialize static structs in a class definition, AFAIK.
Comment on attachment 433873 [details] [diff] [review]
Part 1: Create FramePropertyTable

In FramePropertyTable.h:
>    nsTArray<PropertyValue>* ToArray()

assert that IsArray() is true?

> FramePropertyTable::Set/Get/Remove/Delete

assert that aFrame and aProperty is non-null?

>  FrameProperties(FramePropertyTable* aTable, const nsIFrame* aFrame)
>    : mTable(aTable), mFrame(const_cast<nsIFrame*>(aFrame)) {}

If we change all nsIFrame in FramePropertyTable.h/.cpp to be const, we can
remove this and the const_casts.  I hacked the patch files directly and
it worked fine - none of the destructor functions needed a const_cast.
I'll upload the updated patches in case you want them.


In FramePropertyTable.cpp:
> FramePropertyTable::Set( ...
>     new (&entry->mProp.mValue) nsTArray<PropertyValue>(4);

we should PR_STATIC_ASSERT that
sizeof(nsTArray<PropertyValue>(4)) <= sizeof(entry->mProp.mValue)

r=mats with the above addressed (in case you don't want to do the
const nsIFrame version)


> FramePropertyTable::DeleteAll()

Just an observation: ~FramePropertyTable could use a special internal
version that use PL_DHASH_NEXT instead of PL_DHASH_REMOVE.  Looking at
PL_DHashTableEnumerate it seems to do extra work (for REMOVE) to
reallocate the table to some minimal size.
~nsTHashTable uses PL_DHashTableFinish which doesn't do that.
It's unfortunate that we need DeleteAll() as is for PresShell::Destroy()
since it makes said optimization useless.
Attachment #433873 - Flags: review?(matspal) → review+
Comment on attachment 433874 [details] [diff] [review]
Part 2: convert frame code to use FramePropertyTable

This fails to compile:
http://mxr.mozilla.org/mozilla-central/source/layout/generic/nsLineLayout.cpp#918

In layout/generic/nsBlockFrame.cpp:
DestroyOverflowLines() uses aFrame->PresContext() - this doesn't look safe
when called via DeleteAll() in PresShell::Destroy() which is after frames
are destroyed.  Perhaps we should just remove the aFrame parameter from
the destructor callback?
Attachment #433874 - Flags: review?(matspal) → review-
Created attachment 434155 [details] [diff] [review]
Part 1, const nsIFrame* version
Created attachment 434157 [details] [diff] [review]
Part 2, const nsIFrame* version

(I just removed the nsGkAtoms::collapseOffsetProperty bits, which isn't
the right thing of course...)
(In reply to comment #18)
> (From update of attachment 433873 [details] [diff] [review])
> In FramePropertyTable.h:
> >    nsTArray<PropertyValue>* ToArray()
> 
> assert that IsArray() is true?

OK

> > FramePropertyTable::Set/Get/Remove/Delete
> 
> assert that aFrame and aProperty is non-null?

OK

> >  FrameProperties(FramePropertyTable* aTable, const nsIFrame* aFrame)
> >    : mTable(aTable), mFrame(const_cast<nsIFrame*>(aFrame)) {}
> 
> If we change all nsIFrame in FramePropertyTable.h/.cpp to be const, we can
> remove this and the const_casts.  I hacked the patch files directly and
> it worked fine - none of the destructor functions needed a const_cast.
> I'll upload the updated patches in case you want them.

OK thanks, let's do that

> In FramePropertyTable.cpp:
> > FramePropertyTable::Set( ...
> >     new (&entry->mProp.mValue) nsTArray<PropertyValue>(4);
> 
> we should PR_STATIC_ASSERT that
> sizeof(nsTArray<PropertyValue>(4)) <= sizeof(entry->mProp.mValue)

Yes OK

> > FramePropertyTable::DeleteAll()
> 
> Just an observation: ~FramePropertyTable could use a special internal
> version that use PL_DHASH_NEXT instead of PL_DHASH_REMOVE.  Looking at
> PL_DHashTableEnumerate it seems to do extra work (for REMOVE) to
> reallocate the table to some minimal size.
> ~nsTHashTable uses PL_DHashTableFinish which doesn't do that.
> It's unfortunate that we need DeleteAll() as is for PresShell::Destroy()
> since it makes said optimization useless.

We could destroy the table in-place and lazily recreate it, but that doesn't seem worth it.

Sorry about the compilation errors, bug 551637 and bug 551632 are needed.

We probably should remove the nsIFrame* parameter from the destructor callback. I'm not sure how to fix the DestroyOverflowLines problem though. Maybe we should pass the nsPresContext* into all destructor callbacks? Kind of annoying since overflow lines should not survive reflow so we should only be destroying DestroyOverflowLines during frame destruction in weird/buggy situations. Maybe we should keep nsIFrame* in there but pass null when this runs during frame destruction, and let the overflow lines just leak in that situation?
Alternatively we could store a pointer to the prescontext in the FramePropertyTable and pass the prescontext to all destructor functions.
/* -*- Mode: C++; tab-width: 20; indent-tabs-mode: nil; c-basic-offset: 4

Please change c-basic-offset to 2 in the new files.

> We probably should remove the nsIFrame* parameter

Yeah, I don't think we should promise a frame and then only deliver it
sometimes.  Passing a prescontext as you suggest sounds ok, but after
reading nsBlockFrame::DestroyFrom I don't think we need it:
http://mxr.mozilla.org/mozilla-central/source/layout/generic/nsBlockFrame.cpp#305
There shouldn't be any overflow line properties after the frame tree
is destroyed, so DestroyOverflowLines should just assert if we reach it.
(I ran reftest/crashtest without hitting it)
I looked through nsBlockFrame.cpp and I couldn't find any code that
would delete the property, it's just Remove'd and then dealt with
directly.  SetOverflowLines that calls Set, but it asserts that the
property does not exist already.

IIRC, this was the only destructor callback that used aFrame.
OK, that makes sense.
Whiteboard: [needs review]
(In reply to comment #18)
> >  FrameProperties(FramePropertyTable* aTable, const nsIFrame* aFrame)
> >    : mTable(aTable), mFrame(const_cast<nsIFrame*>(aFrame)) {}
> 
> If we change all nsIFrame in FramePropertyTable.h/.cpp to be const, we can
> remove this and the const_casts.  I hacked the patch files directly and
> it worked fine - none of the destructor functions needed a const_cast.
> I'll upload the updated patches in case you want them.

We could do that, but in principle I think setting properties on const frames is a bad thing and should not be allowed. So I'd rather not do this.
Created attachment 434476 [details] [diff] [review]
updated for comments
Attachment #434476 - Flags: review?(matspal)
Created attachment 434477 [details] [diff] [review]
part 2 updated for comments
Attachment #434477 - Flags: review?(matspal)
Comment on attachment 434476 [details] [diff] [review]
updated for comments

In FramePropertyTable.cpp:
> +/* static */ void*
> +FramePropertyTable::Remove(...

Remove /* static */

> +PLDHashOperator
> +FramePropertyTable::DeleteEnumerator(...

Add /* static */

r=mats
Attachment #434476 - Flags: review?(matspal) → review+

Updated

8 years ago
Attachment #434477 - Flags: review?(matspal) → review+
Whiteboard: [needs landing]
http://hg.mozilla.org/mozilla-central/rev/1f811ed26219
http://hg.mozilla.org/mozilla-central/rev/46e3ca39d3d0
Status: NEW → RESOLVED
Last Resolved: 8 years ago
Resolution: --- → FIXED
Whiteboard: [needs landing]

Updated

8 years ago
Depends on: 555673
You need to log in before you can comment on or make changes to this bug.