92543 - BandRect.mFrames should be created as an nsAutoVoidArray

Status: VERIFIED FIXED

(Core :: Layout, defect, P2)

Description

[Randell Jesup [:jesup] (needinfo me)]

When it's created, mFrames always has 2 elements.  It's a good candidate for an
nsAutoVoidArray to a void extra allocations.  If it commonly has >> 8 entries
(which I don't think it does), it might want to be allocated as
nsVoidArray(probable size).

Comment 1

[Randell Jesup [:jesup] (needinfo me)]

The space manager's tricks to avoid creating nsVoidArrays for single-element
entries may want to  be folded into nsVoidArray itself for more general use. 
Note also that the 2 words of storage used for the count and the union are the
same amount of storage that an inline nsVoidArray member would take - but of
course you can't store a aingle entry in it.

Comment 2

[karnaze (gone)]

Reassigning to attinasi.

Comment 3

[Marc Attinasi]

Moving Mozilla 1.01 bugs to 'future' milestone with priority P1

I will be pulling bugs from 'future' milestones when scheduling later work.

Comment 4

[Randell Jesup [:jesup] (needinfo me)]

Attinasi is gone, re-taking bug

Comment 5

[Alfred Kayser]

Or possibly nsSmallVoidArray is a better candidate for replacement of the single-element trickery in BandRect?
It will mean some code simplification and reduction in nsSpaceManager.cpp.
(see http://developer.mozilla.org/en/docs/XPCOM_array_guide )

Comment 6

[Alfred Kayser]

Attachment: V1: Use nsSmallVoidArray instead of local optimizations for one entry

In Trapezoid merge mState, mFrame and mFrames into one nsSmallVoidArray mFrames (which has all the optimization for arrays with one entry)
Same for BandRect: merge mNumFrames and mFrames into one nsSmallVoidArray mFrames.

Compiled and verified with wide range of site, including acid2, meyerweb's floating CSS demos.

Comment 7

[Alfred Kayser]

notes: 
nsSmallVoidArray only uses 4 bytes for its class structure, and when only one item is stored, those 4 bytes are used as the pointer to the item.
By also making the nsSmallVoidArray mFrame direct embedding in the BandRect/Trapezoid classes, there is no need for a pointer to the nsSmallVoidArray, and there is no need for a separate new/alloc to create the nsSmallVoidArray.

So:
Old: 4 bytes for pointer, 4 bytes for state/numframes, 4 bytes (allocated) for nsVoidArray and 4 bytes allocated for each entry in array.
New: 4 bytes for nsSmallVoidArray and for 99% of the cases no more allocations...  Also some code reduction/simplification.

Comment 8

[Robert O'Callahan (:roc) (email my personal email if necessary)]

+      mFrames.AppendElement((void*)aFrame);
+    }
+    void    RemoveFrame(const nsIFrame* aFrame) {
+      mFrames.RemoveElement((void*)aFrame);

void* casts not needed.

+      return (nsIFrame*) mFrames.FastElementAt(index);

Use NS_STATIC_CAST.

-    if (1 == aBand->mNumFrames) {
-      trapezoid->mState = nsBandTrapezoid::Occupied;
-      trapezoid->mFrame = aBand->mFrame;
+    if (1 == aBand->mFrames.Count()) {
+      trapezoid->mFrames = &aBand->mFrames;
     } else {
-      NS_ASSERTION(aBand->mNumFrames > 1, "unexpected frame count");
-      trapezoid->mState = nsBandTrapezoid::OccupiedMultiple;
-      trapezoid->mFrames = aBand->mFrames;
+      NS_ASSERTION(aBand->mFrames.Count() > 1, "unexpected frame count");
+      trapezoid->mFrames = &aBand->mFrames;

You don't need this if statement anymore, right? You could modify the assertion instead...

+  const nsSmallVoidArray* mFrames; // list of frames occupying the space

Could you document what this is really for? If it always points to the mFrames of some BandRect, it might be clearer if we just have a pointer to the BandRect here. Can it ever actually be null?

Comment 9

[Alfred Kayser]

Attachment: V2: Fixed comments from ROC

Addressed comments from roc:
* remove casts from Append/RemoveElement
* use NS_STATIC_CAST
* added more comments to mFrames in trapezoid.

Note, the mFrames in trapezoid is used by BlockBandData to walk through the frames. Replacing that with BandRect will mean that the BandRect struct also needs to be explosed outside nsSpaceManager.

Comment 10

[Robert O'Callahan (:roc) (email my personal email if necessary)]

Comment on attachment 269192 [details] [diff] [review]
V2: Fixed comments from ROC

+          nsIFrame* f = (nsIFrame*) frames->ElementAt(j);

NS_STATIC_CAST

+        const nsSmallVoidArray *frames = trapezoid->mFrames;

       const nsSmallVoidArray* frames
(and elsewhere)

Comment 11

[Alfred Kayser]

Attachment: V3: With last comments addresed, ready for checkin

Who can do the checkin for me?

Comment 12

[Nickolay_Ponomarev]

mozilla/layout/generic/nsBlockBandData.cpp  1.51
mozilla/layout/generic/nsSpaceManager.cpp   3.78
mozilla/layout/generic/nsSpaceManager.h     3.48

Comment 13

[Nickolay_Ponomarev]

Backed out, because this breaks debug builds.

According to josh: 'struct nsBandTrapezoid' has no member named 'mState' in nsPresShell.cpp:6595 and 6620. Looking at those lines there indeed seem to be code that needs updating. I can't read the patch myself now to figure it out.

mozilla/layout/generic/nsBlockBandData.cpp  1.52
mozilla/layout/generic/nsSpaceManager.cpp   3.79
mozilla/layout/generic/nsSpaceManager.h     3.49

Comment 14

[Alfred Kayser]

Note, the problem in nsPresShell.cpp is in ifdef DEBUG code.
It can be easily fixed by replacing 
                    trap1[trapIndex].mState == trap2[trapIndex].mState;
with
                    (trap1[trapIndex].mFrame!=nsnull) == (trap2[trapIndex].mFrame!=nsnull);

(as the test is about verification that two trees are built up in the same way...)

(updated patch coming...)

Comment 15

[Alfred Kayser]

Attachment: Also patch the debug code

Comment 16

[David Baron :dbaron: (⌚️UTC-5, no longer working on Mozilla)]

That patch seems to include part of another patch.

Comment 17

[David Baron :dbaron: (⌚️UTC-5, no longer working on Mozilla)]

Also, the NS_STATIC_CAST(T, V) should now be a static_cast<T>(V).

Is this patch doing what the bug summary says?  Or something else in addition?

Comment 18

[Alfred Kayser]

Attachment: Patch without the nsObjectFrame part

Previous patch included accidentally another patch from same directory.

Note, this patch is all about replacing:
  State     mState;                     // state of the space
  union {
    nsIFrame*          mFrame;  // single frame occupying the space
    const nsVoidArray* mFrames; // list of frames occupying the space
  };
with just:
  const nsSmallVoidArray* mFrames; // list of frames occupying the space

This touches some code, mostly making it simpler, as the optimization for the 'single frame' case is allready within nsSmallVoidArray.

Comment 19

[David Baron :dbaron: (⌚️UTC-5, no longer working on Mozilla)]

Comment on attachment 278215 [details] [diff] [review]
Patch without the nsObjectFrame part

a1.9=dbaron

Comment 20

[Alfred Kayser]

Minor follow-up in bug 393781 for further optimization.

Comment 21

[:Gijs (he/him)]

Checking in mozilla/layout/base/nsPresShell.cpp;
/cvsroot/mozilla/layout/base/nsPresShell.cpp,v  <--  nsPresShell.cpp
new revision: 3.1052; previous revision: 3.1051
done
Checking in mozilla/layout/generic/nsBlockBandData.cpp;
/cvsroot/mozilla/layout/generic/nsBlockBandData.cpp,v  <--  nsBlockBandData.cpp
new revision: 1.53; previous revision: 1.52
done
Checking in mozilla/layout/generic/nsSpaceManager.cpp;
/cvsroot/mozilla/layout/generic/nsSpaceManager.cpp,v  <--  nsSpaceManager.cpp
new revision: 3.83; previous revision: 3.82
done
Checking in mozilla/layout/generic/nsSpaceManager.h;
/cvsroot/mozilla/layout/generic/nsSpaceManager.h,v  <--  nsSpaceManager.h
new revision: 3.50; previous revision: 3.49
done

Comment 22

[:Gijs (he/him)]

Backed out due to build bustage:

c++ -o nsPresShell.o -c -I../../dist/include/system_wrappers -include /builds/tinderbox/Fx-Trunk-Debug/Linux_2.6.9-42.ELsmp_Depend/mozilla/config/gcc_hidden.h -DMOZILLA_INTERNAL_API -DOSTYPE=\"Linux2.6.9-42\" -DOSARCH=Linux -D_IMPL_NS_LAYOUT -I/builds/tinderbox/Fx-Trunk-Debug/Linux_2.6.9-42.ELsmp_Depend/mozilla/layout/base -I/builds/tinderbox/Fx-Trunk-Debug/Linux_2.6.9-42.ELsmp_Depend/mozilla/layout/base/../generic -I/builds/tinderbox/Fx-Trunk-Debug/Linux_2.6.9-42.ELsmp_Depend/mozilla/layout/base/../forms -I/builds/tinderbox/Fx-Trunk-Debug/Linux_2.6.9-42.ELsmp_Depend/mozilla/layout/base/../tables -I/builds/tinderbox/Fx-Trunk-Debug/Linux_2.6.9-42.ELsmp_Depend/mozilla/layout/base/../printing -I/builds/tinderbox/Fx-Trunk-Debug/Linux_2.6.9-42.ELsmp_Depend/mozilla/layout/base/../xul/base/src -I/builds/tinderbox/Fx-Trunk-Debug/Linux_2.6.9-42.ELsmp_Depend/mozilla/layout/base/../../content/base/src -I/builds/tinderbox/Fx-Trunk-Debug/Linux_2.6.9-42.ELsmp_Depend/mozilla/layout/base/../../content/events/src -I/builds/tinderbox/Fx-Trunk-Debug/Linux_2.6.9-42.ELsmp_Depend/mozilla/layout/base/../../content/xbl/src -I/builds/tinderbox/Fx-Trunk-Debug/Linux_2.6.9-42.ELsmp_Depend/mozilla/layout/base/../../view/src -I/builds/tinderbox/Fx-Trunk-Debug/Linux_2.6.9-42.ELsmp_Depend/mozilla/layout/base/../../dom/src/base -I/builds/tinderbox/Fx-Trunk-Debug/Linux_2.6.9-42.ELsmp_Depend/mozilla/layout/base/../../content/svg/content/src  -I/builds/tinderbox/Fx-Trunk-Debug/Linux_2.6.9-42.ELsmp_Depend/mozilla/layout/base/../mathml/content/src -I/builds/tinderbox/Fx-Trunk-Debug/Linux_2.6.9-42.ELsmp_Depend/mozilla/layout/base/../mathml/base/src -I/builds/tinderbox/Fx-Trunk-Debug/Linux_2.6.9-42.ELsmp_Depend/mozilla/layout/base/../svg/base/src -I../../dist/include/xpcom -I../../dist/include/string -I../../dist/include/dom -I../../dist/include/content -I../../dist/include/xul -I../../dist/include/xuldoc -I../../dist/include/gfx -I../../dist/include/widget -I../../dist/include/view -I../../dist/include/necko -I../../dist/include/docshell -I../../dist/include/webshell -I../../dist/include/webbrwsr -I../../dist/include/uriloader -I../../dist/include/js -I../../dist/include/xpconnect -I../../dist/include/plugin -I../../dist/include/locale -I../../dist/include/pref -I../../dist/include/imglib2 -I../../dist/include/unicharutil -I../../dist/include/htmlparser -I../../dist/include/util -I../../dist/include/windowwatcher -I../../dist/include/accessibility -I../../dist/include/shistory -I../../dist/include/caps -I../../dist/include/thebes -I../../dist/include/cairo -I../../dist/include   -I../../dist/include/layout -I../../dist/include/nspr  -DMOZ_PNG_READ -DMOZ_PNG_WRITE   -I../../dist/sdk/include -I/usr/X11R6/include   -fPIC  -I/usr/X11R6/include -fno-rtti -fno-exceptions -Wall -Wconversion -Wpointer-arith -Wcast-align -Woverloaded-virtual -Wsynth -Wno-ctor-dtor-privacy -Wno-non-virtual-dtor -Wno-long-long -pedantic -fshort-wchar -pthread -pipe  -DDEBUG -D_DEBUG -DDEBUG_cltbld -DTRACING -g -fno-inline -I../../dist/include/cairo  -I/usr/X11R6/include -DMOZILLA_CLIENT -include ../../mozilla-config.h -Wp,-MD,.deps/nsPresShell.pp /builds/tinderbox/Fx-Trunk-Debug/Linux_2.6.9-42.ELsmp_Depend/mozilla/layout/base/nsPresShell.cpp
/builds/tinderbox/Fx-Trunk-Debug/Linux_2.6.9-42.ELsmp_Depend/mozilla/layout/base/nsPresShell.cpp: In member function ‘virtual nsresult PresShell::HandleEvent(nsIView*, nsGUIEvent*, nsEventStatus*)’:
/builds/tinderbox/Fx-Trunk-Debug/Linux_2.6.9-42.ELsmp_Depend/mozilla/layout/base/nsPresShell.cpp:5406: warning: comparison between signed and unsigned integer expressions
/builds/tinderbox/Fx-Trunk-Debug/Linux_2.6.9-42.ELsmp_Depend/mozilla/layout/base/nsPresShell.cpp: In function ‘PRBool CompareTrees(nsPresContext*, nsIFrame*, nsPresContext*, nsIFrame*)’:
/builds/tinderbox/Fx-Trunk-Debug/Linux_2.6.9-42.ELsmp_Depend/mozilla/layout/base/nsPresShell.cpp:6608: error: ‘struct nsBandTrapezoid’ has no member named ‘mFrame’
/builds/tinderbox/Fx-Trunk-Debug/Linux_2.6.9-42.ELsmp_Depend/mozilla/layout/base/nsPresShell.cpp:6608: error: ‘nsull’ was not declared in this scope
/builds/tinderbox/Fx-Trunk-Debug/Linux_2.6.9-42.ELsmp_Depend/mozilla/layout/base/nsPresShell.cpp:6608: error: ‘struct nsBandTrapezoid’ has no member named ‘mFrame’
/builds/tinderbox/Fx-Trunk-Debug/Linux_2.6.9-42.ELsmp_Depend/mozilla/layout/base/nsPresShell.cpp:6633: error: ‘struct nsBandTrapezoid’ has no member named ‘mFrame’
/builds/tinderbox/Fx-Trunk-Debug/Linux_2.6.9-42.ELsmp_Depend/mozilla/layout/base/nsPresShell.cpp:6633: error: ‘nsull’ was not declared in this scope
/builds/tinderbox/Fx-Trunk-Debug/Linux_2.6.9-42.ELsmp_Depend/mozilla/layout/base/nsPresShell.cpp:6633: error: ‘struct nsBandTrapezoid’ has no member named ‘mFrame’

I didn't feel comfortable enough with layout code to try and fix this myself.

Comment 23

[Alfred Kayser]

Apparently the wrong was uploaded (two typo's which I correctly later).
I will create a new patch after updating my tree.

Comment 24

[Alfred Kayser]

Attachment: Without the typos in the debug code

Comment 25

[Alfred Kayser]

Who want to resubmit this to the tree?

Thanks in advance, Alfred

Comment 26

[Martijn Wargers (dead)]

I think I get a build error with that latest patch (mingw debug build):
http://martijn.martijn.googlepages.com/builderror.txt
So I haven't checked it in yet.

Comment 27

[Alfred Kayser]

Attachment: Fix issue in ASSERT

Replaced line 576:
  NS_PRECONDITION(1 == aBandRect.mFrames.Count(), "shared band rect");
with
  NS_PRECONDITION(1 == aBandRect->mFrames.Count(), "shared band rect");

Comment 28

[Martijn Wargers (dead)]

Thanks, that one compiled just fine here.

Checking in generic/nsBlockBandData.cpp;
/cvsroot/mozilla/layout/generic/nsBlockBandData.cpp,v  <--  nsBlockBandData.cpp
new revision: 1.55; previous revision: 1.54
done
Checking in generic/nsSpaceManager.cpp;
/cvsroot/mozilla/layout/generic/nsSpaceManager.cpp,v  <--  nsSpaceManager.cpp
new revision: 3.85; previous revision: 3.84
done
Checking in generic/nsSpaceManager.h;
/cvsroot/mozilla/layout/generic/nsSpaceManager.h,v  <--  nsSpaceManager.h
new revision: 3.52; previous revision: 3.51
done
Checking in base/nsPresShell.cpp;
/cvsroot/mozilla/layout/base/nsPresShell.cpp,v  <--  nsPresShell.cpp
new revision: 3.1054; previous revision: 3.1053
done

Checked into trunk.

Comment 29

[Alfred Kayser]

This saved a number of bytes in codesize, and no visible impact on other statistics, and the tests are OK.

  libgklayout.so
  	Total:	       -624 (+412/-1036)
  	Code:	       -601 (+0/+0)
  	Data:	        -23 (+412/-1036)