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

Status: VERIFIED FIXED

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

Description

[Mats Palmgren (inactive)]

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

Comment 1

[Mats Palmgren (inactive)]

Attachment: Part 1, Add NewLineBox/FreeLineBox methods to nsBlockFrame

Comment 2

[Mats Palmgren (inactive)]

Attachment: part2, Make nsLineBox use a frame hash table for lines with many frames

BTW, sizeof(nsLineBox) stays the same (64 bytes) in my x86-64 Linux build -
apparently we have a 4-byte hole that gets used.

Comment 3

[Boris Zbarsky [:bzbarsky]]

Comment on attachment 600853 [details] [diff] [review]
Part 1, Add NewLineBox/FreeLineBox methods to nsBlockFrame

r=me

Comment 4

[Boris Zbarsky [:bzbarsky]]

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.

Comment 5

[Mats Palmgren (inactive)]

Attachment: part2, Make nsLineBox use a frame hash table for lines with many frames

(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

Comment 6

[Boris Zbarsky [:bzbarsky]]

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.

Comment 7

[Mats Palmgren (inactive)]

> 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

Comment 8

[Boris Zbarsky [:bzbarsky]]

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.

Comment 9

[Mats Palmgren (inactive)]

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

Comment 10

[Boris Zbarsky [:bzbarsky]]

I meant taking the stuff out of the C++ file entirely...

Comment 11

[Mats Palmgren (inactive)]

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

Comment 12

[Mats Palmgren (inactive)]

https://hg.mozilla.org/integration/mozilla-inbound/rev/8e48167e22f3
https://hg.mozilla.org/integration/mozilla-inbound/rev/9c6e7924e791

Comment 13

[Boris Zbarsky [:bzbarsky]]

Mats, thanks for testing that...  I wonder why we're getting this behavior difference here.

Comment 14

[Daniel Holbert [:dholbert]]

https://hg.mozilla.org/mozilla-central/rev/8e48167e22f3
https://hg.mozilla.org/mozilla-central/rev/9c6e7924e791

Comment 15

[Lukas Blakk [:lsblakk] use ?needinfo]

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.

Comment 16

[Mats Palmgren (inactive)]

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.

Comment 17

[u279076]

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?

Comment 18

[Boris Zbarsky [:bzbarsky]]

It should be somewhat faster than before this bugfix.

Comment 19

[u279076]

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.

Comment 20

[Boris Zbarsky [:bzbarsky]]

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.

Comment 21

[u279076]

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?

Comment 22

[Boris Zbarsky [:bzbarsky]]

Yes, though note that per comment 0 the expected win is on the order of 6% or so.

Comment 23

[u279076]

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.