Closed Bug 730769 Opened 8 years ago Closed 8 years ago

Make lines with a large number of frames hash its frames to speed up Contains(), RFindLineContaining() etc

Categories

(Core :: Layout: Block and Inline, defect)

defect
Not set

Tracking

()

VERIFIED FIXED
mozilla13
Tracking Status
firefox-esr10 13+ verified

People

(Reporter: mats, Assigned: mats)

References

(Blocks 1 open bug)

Details

(Keywords: perf, verified-beta)

Attachments

(2 files, 1 obsolete file)

The suggested change, in nsLineBox:
  union {
    nsTHashtable< nsPtrHashKey<nsIFrame> >* mFrames;
    PRUint32 mChildCount;
  };

Lines with a large number of frames will allocate and use mFrames and call
PutEntry/RemoveEntry as frames are added/removed on the line.
The intention is that "normal" web pages will use mChildCount as usual.

I have set the threshold at 200 frames where I switch to using a hash table.
I collected 3 million samples running Tp4 which gave 20 hits where a hash
table was used for a line, so I'm pretty sure it shouldn't lead to memory
bloat in normal use.

OTOH, running IE Maze (bug 641341) it gives ~100% hit rate and completely
eliminates IndexOf from the Shark stats.  I think will also help in other
cases such as bug 726637.

On my MBP (2011 model), running 30x30 IE Maze:
original: 117s
+ patches in bug 728906 and dependents: 114s
+ patches in this bug: 107s
BTW, sizeof(nsLineBox) stays the same (64 bytes) in my x86-64 Linux build -
apparently we have a 4-byte hole that gets used.
Attachment #600855 - Flags: review?(bzbarsky)
Comment on attachment 600853 [details] [diff] [review]
Part 1, Add NewLineBox/FreeLineBox methods to nsBlockFrame

r=me
Attachment #600853 - Flags: review?(bzbarsky) → review+
Comment on attachment 600855 [details] [diff] [review]
part2, Make nsLineBox use a frame hash table for lines with many frames

>+++ b/layout/generic/nsLineBox.cpp
>+nsLineBox::StealHashTableFrom(nsLineBox* aFromLine, PRUint32 aFromLineNewCount)
>+  // remove aFromLine's frames that isn't on this line

s/isn't/aren't/

>+++ b/layout/generic/nsLineBox.h
>+ * If the frames was moved from another line then you're responsible

s/was moved/were moved/

>+ * for notifying that line using NoteFrameRemoved().

Can we somehow assert that this is done sanely?  For example, can we assert that aCount == 1 here?

>+ * Function to create a line box and initialize it with aCount frames
>+ * that is currently on aFromLine.

"that are currently"

>+  void operator delete(void* aPtr, size_t sz) MOZ_DELETE;

Add a comment that this is not implemented on purpose?

>+private:
>+  // Add a hash table for fast lookup when the line has more frames than this.
>+#define MIN_CHILD_COUNT_FOR_HASHTABLE 200

How about making this a static const int or something, so that other files including this one don't have to see it?  kMinChildCountForHashtable.

>+  void StealHashTableFrom(nsLineBox* aFromLine, PRUint32 aFromLineNewCount);
>+  void NoteFramesMovedFrom(nsLineBox* aFromLine);

Document?

>+  void SwitchToHashtable()
>+    mFrames->Init(NS_MAX(count, minSize) + count/2);

Document where this magic number is coming from, please.

r=me with the nits dealt with.
Attachment #600855 - Flags: review?(bzbarsky) → review+
Blocks: 371885
(In reply to Boris Zbarsky (:bz) from comment #4)
> Can we somehow assert that this is done sanely?  For example, can we assert
> that aCount == 1 here?

I removed the 'aCount' parameter since this method was only called with
a literal 1 anyway.

> >+  void operator delete(void* aPtr, size_t sz) MOZ_DELETE;
> 
> Add a comment that this is not implemented on purpose?

Seems redundant...  that's what MOZ_DELETE *means*, right?

> >+  void SwitchToHashtable()
> >+    mFrames->Init(NS_MAX(count, minSize) + count/2);
> 
> Document where this magic number is coming from, please.

Out of thin air? :-)  I removed the extra "count/2", until I have some
evidence that it actually helps.

I addressed your other nits as suggested.

https://tbpl.mozilla.org/?usebuildbot=1&tree=Try&rev=b147664bf01a
Attachment #604658 - Flags: review?(bzbarsky)
Attachment #600855 - Attachment is obsolete: true
Comment on attachment 604658 [details] [diff] [review]
part2, Make nsLineBox use a frame hash table for lines with many frames

I'm not sure why you need that ifndef MSC_VER block.  Code similar to this but without the block seems to work fine in other cases on gcc... why is that block needed?

The rest looks good.
Attachment #604658 - Flags: review?(bzbarsky) → review+
> I'm not sure why you need that ifndef MSC_VER block.

It's needed for 'kPrincipalList' et al in nsIFrame.h so I figured it's needed here too.
See bug 653649 comment 24, and 
http://mxr.mozilla.org/mozilla-central/source/layout/generic/nsFrame.cpp#795
Oh, hmm.  I wonder whether it works elsewhere because those are template classes...

I would still suggest pushing to try without the MSC_VER thing and seeing what happens.
It's still the same error:
"xul.dll : fatal error LNK1169: one or more multiply defined symbols found"
https://tbpl.mozilla.org/?usebuildbot=1&tree=Try&rev=bc48406a93ac
I meant taking the stuff out of the C++ file entirely...
Taking out the definition in the .cpp file in my local build,
using gcc 4.6.1 and gold 1.11:

/usr/bin/ld: error: /OBJDIR/toolkit/library/../../layout/generic/nsBlockFrame.o: requires dynamic R_X86_64_PC32 reloc against 'nsLineBox::kMinChildCountForHashtable' which may overflow at runtime; recompile with -fPIC
layout/generic/nsLineBox.h:382: error: undefined reference to 'nsLineBox::kMinChildCountForHashtable'
collect2: ld returned 1 exit status
Mats, thanks for testing that...  I wonder why we're getting this behavior difference here.
Status: NEW → RESOLVED
Closed: 8 years ago
Resolution: --- → FIXED
Comment on attachment 600853 [details] [diff] [review]
Part 1, Add NewLineBox/FreeLineBox methods to nsBlockFrame

Approval of part 1 for esr landing as per bug 750066's comment 6.
Attachment #600853 - Flags: approval-mozilla-esr10+
Part 1 landed on esr10 since it was needed for bug 750066.
https://hg.mozilla.org/releases/mozilla-esr10/rev/e24f68d63c1d
Part 2 will never land there though.
Can someone please clarify what the desired result of running http://ie.microsoft.com/testdrive/Performance/MazeSolver/Default.html should be to mark this bug verified?
It should be somewhat faster than before this bugfix.
Firefox 10.0.4esr 30x30: 105, 105, 109 (Average: 106)
Firefox 10.0.5esrpre 30x30: 106, 102, 104 (Average: 104)

Based on the above results, we are really only 2% faster, and there is probably some tolerance for randomization and error that I'm not accounting for.

I'm not sure this is "good enough" to call it verified. Please advise.
Oh, on ESR the part of this bug that affects performance wasn't landed.  See comment 16.  The only part that landed was the refactoring that the patch in bug 750066 depends on.  So as long as the patch for bug 750066 was checked in and the tree is compiling the ESR part of this bug is verified.
Looking at HG it appears the refactoring code is landed in ESR so I'm calling this verified for ESR, as per comment 20. Thanks Boris.

Boris, I suppose the perf case can still be used to verify this in Firefox 13.0b5?
Yes, though note that per comment 0 the expected win is on the order of 6% or so.
Firefox 13.0a1 Nightly from 2012-02-25 (a couple days before this bug was filed) gives an average of 104s on the 30x30 maze; Firefox 13.0b5 averaged 93s. This shows an improvement of 10.58% on average.
Status: RESOLVED → VERIFIED
Keywords: verified-beta
You need to log in before you can comment on or make changes to this bug.