Last Comment Bug 129115 - Reflow coalescing within JS called from SetTimeout
: Reflow coalescing within JS called from SetTimeout
Status: VERIFIED FIXED
[adt1 RTM]
: perf, testcase, top100, topembed-, topperf
Product: Core
Classification: Components
Component: Layout (show other bugs)
: Trunk
: All All
: P2 major with 14 votes (vote)
: mozilla1.0.1
Assigned To: Chris Waterson
: Sivakiran Tummala
: Jet Villegas (:jet)
Mentors:
http://www.formula-one.nu/mozilla/dom...
: 128901 (view as bug list)
Depends on: 130760 135146 138057 143959 145272
Blocks: 21762 118933 49095 64516 70156 advocacybugs 94576 97287 114584 116593 124178 136447 139986 142863
  Show dependency treegraph
 
Reported: 2002-03-05 12:08 PST by Randell Jesup [:jesup]
Modified: 2014-12-25 20:40 PST (History)
114 users (show)
See Also:
Crash Signature:
(edit)
QA Whiteboard:
Iteration: ---
Points: ---
Has Regression Range: ---
Has STR: ---


Attachments
current test patch, needs more work (3.45 KB, patch)
2002-03-06 12:11 PST, Randell Jesup [:jesup]
no flags Details | Diff | Splinter Review
Updated patch, much faster, almost certainly would cause regressions (6.89 KB, patch)
2002-03-06 16:19 PST, Randell Jesup [:jesup]
no flags Details | Diff | Splinter Review
conversation between dbaron and shaver about this bug (5.87 KB, text/plain)
2002-03-06 18:04 PST, David Baron :dbaron: ⌚️UTC-10
no flags Details
First VERY rough cut as a patch. Compiles, does not run. For Shaver (69.76 KB, patch)
2002-03-10 03:08 PST, Randell Jesup [:jesup]
no flags Details | Diff | Splinter Review
patch to build the brach with msvc (1.33 KB, patch)
2002-03-16 09:55 PST, Bernard Alleysson
no flags Details | Diff | Splinter Review
Current patch that makes up branch (against ...._BASE) (119.15 KB, patch)
2002-03-23 22:18 PST, Randell Jesup [:jesup]
no flags Details | Diff | Splinter Review
Patch to dom to enable batching of reflows in SetTimeout() callbacks. (1.11 KB, patch)
2002-03-25 18:43 PST, Randell Jesup [:jesup]
no flags Details | Diff | Splinter Review
patch that matches the current branch (109.00 KB, patch)
2002-03-28 08:43 PST, Randell Jesup [:jesup]
no flags Details | Diff | Splinter Review
Updated patch to match branch (109.75 KB, patch)
2002-03-28 10:46 PST, Randell Jesup [:jesup]
no flags Details | Diff | Splinter Review
proposed modificiations (130.46 KB, patch)
2002-04-11 11:29 PDT, Chris Waterson
no flags Details | Diff | Splinter Review
more functional version of above (137.11 KB, patch)
2002-04-11 22:52 PDT, Chris Waterson
no flags Details | Diff | Splinter Review
working patch against current trunk (145.46 KB, patch)
2002-04-12 18:00 PDT, Chris Waterson
no flags Details | Diff | Splinter Review
as above, but diff -w (for human perusal) (131.66 KB, patch)
2002-04-12 18:05 PDT, Chris Waterson
no flags Details | Diff | Splinter Review
patch incorporating above fixes (149.39 KB, patch)
2002-04-15 21:05 PDT, Chris Waterson
no flags Details | Diff | Splinter Review
ready for prime time? (152.49 KB, patch)
2002-04-16 19:58 PDT, Chris Waterson
no flags Details | Diff | Splinter Review
testcase showing nsBlockFrame changes still need work (1.36 KB, text/html)
2002-04-16 20:26 PDT, David Baron :dbaron: ⌚️UTC-10
no flags Details
updated to this morning's trunk, minor bug fixes. (154.66 KB, patch)
2002-04-17 19:26 PDT, Chris Waterson
no flags Details | Diff | Splinter Review
against 2002-04-22 trunk. includes fixes for reflow ommission in table row group, crasher in fixed frame. (157.99 KB, patch)
2002-04-22 19:09 PDT, Chris Waterson
no flags Details | Diff | Splinter Review
patch for review (169.66 KB, patch)
2002-04-24 21:49 PDT, Chris Waterson
no flags Details | Diff | Splinter Review
updated patch (170.53 KB, patch)
2002-04-28 21:55 PDT, Chris Waterson
no flags Details | Diff | Splinter Review
(non compiled) patch with minor changes to tables (30.67 KB, patch)
2002-04-30 18:17 PDT, karnaze (gone)
no flags Details | Diff | Splinter Review
incorporate karnaze's changes; add code-level documentation (174.29 KB, patch)
2002-05-01 14:54 PDT, Chris Waterson
no flags Details | Diff | Splinter Review
with patch for SVG (178.28 KB, patch)
2002-05-01 17:30 PDT, Chris Waterson
attinasi: superreview+
Details | Diff | Splinter Review
fix for assertions, MathML incremental reflow (190.10 KB, patch)
2002-05-02 15:25 PDT, Chris Waterson
no flags Details | Diff | Splinter Review
better fix for mathml incremental reflow (195.02 KB, patch)
2002-05-03 13:53 PDT, Chris Waterson
rbs: review+
Details | Diff | Splinter Review
after review with kin (197.07 KB, patch)
2002-05-07 16:12 PDT, Chris Waterson
no flags Details | Diff | Splinter Review
partial review comments from dbaron (2.56 KB, text/plain)
2002-05-07 19:32 PDT, David Baron :dbaron: ⌚️UTC-10
no flags Details
incorporate dbaron's comments, bz & kin testing (198.64 KB, patch)
2002-05-09 17:31 PDT, Chris Waterson
no flags Details | Diff | Splinter Review
2002051104, XP: test results from http://www.umsu.de/jsperf/index2.php (17.09 KB, text/html)
2002-05-11 11:20 PDT, R.K.Aa.
no flags Details
2002051104, XP: test results from http://www.umsu.de/jsperf/index2.php (17.09 KB, text/html)
2002-05-11 11:20 PDT, R.K.Aa.
no flags Details
oops.. i was a little fast: Here results from MSIE6, same PC (18.89 KB, text/html)
2002-05-11 11:42 PDT, R.K.Aa.
no flags Details
patch for the branch (210.28 KB, patch)
2002-06-05 17:12 PDT, Chris Waterson
no flags Details | Diff | Splinter Review
Comparison Test Results between Branch & Other Browser. (9.63 KB, text/html)
2002-06-11 12:48 PDT, Prashant Desale
no flags Details
Comparison Test Results between Branch & The Other Browser. (13.50 KB, text/html)
2002-06-12 14:18 PDT, Prashant Desale
no flags Details
Comparison Testing Results amoung 3 different Browser builds & The Other Browser. (19.21 KB, text/html)
2002-06-17 17:35 PDT, Prashant Desale
no flags Details

Description Randell Jesup [:jesup] 2002-03-05 12:08:38 PST
We have a real problem with excessive reflow called from within DHTML, commonly
in  code called from SetTimeout().  See bug 118933 among many others.

One possible solution is to NOT generate a reflow event for every CSS
position/etc change (in nsCSSFrameConstructor::StyleChangeReflow).  Instead,
reflow (if needed) when the code called by SetTimeout returns, or if more than N
ms have elapsed (I suggest 50 or 100ms as a first cut - it can be tuned).  To be
more detailed, we might put the reflow commands into a separate queue (ala the
mTimeoutReflowCommands queue) (and suppress duplicates in that queue), and then
process that queue off either a timer or right before we go to sleep after a
SetTimeout callback.

There are some other possible solutions, like adding a general delay to
processing reflows if other things are active, or perhaps event prioritization
(which is another RFE in bugzilla).
Comment 1 Randell Jesup [:jesup] 2002-03-05 12:10:28 PST
Also see lots of other DHTML bugs, such as bug 118933
Comment 2 Randell Jesup [:jesup] 2002-03-05 22:41:04 PST
I chatted with dbaron for a while on IRC.  I'm not sure if there's a win to be
had here - it depends if the reflows are getting flushed during the running of
the code called by SetTimeout()'s callback.  He did remark that we appeared to
not be reflowing very incrementally from glancing at the jprof to bug 118933.

I'm going to instrument and see what I can figure out.
Comment 3 Marc Boullet 2002-03-06 04:15:23 PST
What about bug #64516 comment #21 by attinasi/buster for
a possible solution ?
Comment 4 Randell Jesup [:jesup] 2002-03-06 08:33:14 PST
Looking around a bit, there's a rather under-used mechanism for batching reflows
(used in only one place, in Editor).  For this purpose we'd need to put a
maximum time to batch the reflows for, and there may be some additional issues,
but it looks like a good place to start.  I'm going to try a patch that batches
reflows around calls to JS from RunTimeout and see what happens.

(The methods are nsIPresShell::BeginReflowBatching(),
nsIPresShell::EndReflowBatching(PRBool reflow), and a query method (no one uses it).
Comment 5 Randell Jesup [:jesup] 2002-03-06 12:07:44 PST
I have my batched-reflows up and running (without the timeout).  It does appear
to properly batch the 100 reflows generated per timeout in the testcase for
129079.  However, this doesn't appear to help much; my assumption is that when
the 100 reflows commands unbatch, they still cause a hundred reflows to occur. 
The next thing (I guess) is to see if the 100 reflows can be coalesced at all.

I'll upload my (trivial) little patch for this so far. 
Comment 6 Randell Jesup [:jesup] 2002-03-06 12:11:06 PST
Created attachment 72830 [details] [diff] [review]
current test patch, needs more work
Comment 7 Randell Jesup [:jesup] 2002-03-06 15:17:23 PST
I'm looking at merging reflows in nsPresShell::ProcessReflowCommands to help
DHTML (which spends all it's time in reflow it seems).  Can I just merge the
nsHTMLReflowCommand Paths (with common element elimination), or will incremental
reflow of a common parent reflow all the children? (which would allow me to
throw away reflows for the same common parent (root?) node).

I'm slogging through the code but some guidance wouldn't hurt.
Comment 8 Randell Jesup [:jesup] 2002-03-06 16:19:50 PST
Created attachment 72873 [details] [diff] [review]
Updated patch, much faster, almost certainly would cause regressions

This patch cuts the time for the text case (for me) from ~100000ms to ~9300ms. 
THe Debug/viewer demos/DHTML testcase is faster too.

This WILL cause regressions, I cheated.  I probably need to merge reflow
command framelists.
Comment 9 David Baron :dbaron: ⌚️UTC-10 2002-03-06 16:26:37 PST
Don't we already have some sort of reflow coalescing code?  (But I think it
works at an earlier stage.)
Comment 10 Mike Shaver (:shaver -- probably not reading bugmail closely) 2002-03-06 17:04:43 PST
http://bugzilla.mozilla.org/attachment.cgi?id=59020&action=view is a test case
for bug 70156, and it very nicely demonstrates the beauty of this patch.

resource:///res/samples/test12.html (more fixed pos demo) doesn't display
anything for me until I resize.  11 does, sometimes.
Comment 12 Boris Zbarsky [:bz] (still a bit busy) 2002-03-06 17:24:24 PST
http://www.narain.com/gecko/bugs/js-stress-test.html is an interesting test.
Comment 13 David Baron :dbaron: ⌚️UTC-10 2002-03-06 18:04:38 PST
Created attachment 72893 [details]
conversation between dbaron and shaver about this bug

This is a conversation I just had with shaver on IRC about this bug.
Comment 14 Brendan Eich [:brendan] 2002-03-06 19:02:13 PST
Nominating for 1.0 -- go strong, kudos to rjesup!

I wouldn't hold 1.0 for this, but if it can be done safely and well, without too
much opportunity cost, I'm all for it.  Just one driver's opinion.

/be
Comment 15 Mike Shaver (:shaver -- probably not reading bugmail closely) 2002-03-06 19:04:39 PST
Addendum to conversation: we looked a little bit at doing the
mark-divergent-subpath-as-dirty thing, but that looked kind of evil.  Less evil
-- probably trivial for blocks, of as-yet-unknown non-triviality for tables --
would be to store the reflow commands in a tree, and teach block and table code
how to reflow all the tree-children for a reflow pass.

I'm going to poke at the code overnight and see if I can hack up a patch. 
Randall has certainly laid down an impressive gauntlet for us. =)
Comment 16 Boris Zbarsky [:bz] (still a bit busy) 2002-03-06 19:48:35 PST
Please test pageload with that patch... I'm seeing two issues: 1)  a long time
to unsupress painting and 2) much longer time taken (as far as I can tell).
Comment 17 Randell Jesup [:jesup] 2002-03-06 20:29:39 PST
I just read dbaron's and shaver's comments.  I agree we need to merge paths or
otherwise make sure all the right frames get reflowed (I strongly suspected as
much, in fact I was surprised it works as well as it does without it).

Seems like we have two or three possibilities (I'm still trying to grok the code
in BlockFrame/Viewport/etc):

1) Merge the lists throwing away duplicates.  I'm not sure we can keep it a
list, or that may depend on how we access it.  Probably a tree structure makes
the most sense, or a list structure that makes a virtual tree.  I haven't yet
determined if order is critical, but I imagine it is (requiring a tree, or the
extra info).

2) Mark the nodes when the coalescing takes place using a new (different) flag.
 Then let the reflow start at the top and work it's way down the existing tree.
 Downside is that with flat structures (lots of children), you have a lot of
nodes to examine. At the cost of more memory in the nodes, we could still encode
it without the perf hit.

3) Do the coalescing only for the easy cases (target frames all have a common
parent), or some such.

I'm sure there are more solutions to the issue....
Comment 18 Randell Jesup [:jesup] 2002-03-06 20:58:56 PST
adding mozilla1.0, targetting 1.0
Comment 19 Randell Jesup [:jesup] 2002-03-06 23:40:27 PST
Some ideas about a tree for reflow framelists.  I haven't coded this, just
written some comments:

Reflow array consists of an array of pointers.  If the low bit is set, then it's
not an nsIFrame *, it's an nsAutoVoidArray holding a list of children.  Each
entry in that array of children is another reflow array.  This is efficient for
the common case of a single or small number of reflows.  Also, it works well for
cases where there's a large overlap.

They're also pretty easy to build from the reflow command arrays. You can reuse
each mPath array after removing the first N entries (where N is the amount it
matches with it's parent). You could avoid that overhead with more work, but
it's not worth it I think.

GetNext goes away.  In it's place, an iterator on the stack stores where in the
child array we are (assuming there is more than one).  Places where GetNext is
called become something like
"while (NS_OK == iterator.GetNextReflowChild(&reflowChild))) ..."
or some such.

Just some ideas before I crash.
Comment 21 Cathleen 2002-03-07 10:52:50 PST
adding nsbeta1.
this is a good one to fix for DHTML performance.
Comment 22 Randell Jesup [:jesup] 2002-03-07 20:48:47 PST
Taking bug.

The proper method for combining reflow paths (I think):

Build a tree that has all the target nodes (with parents) with no duplication. 
All reflows must be for the same reflow command type (note: could relax by
storing types in the tree).

When walking the tree in Reflow(), when we come across a node, we check to see
if it's a target.  If so, we do a reflow from that point using the normal dirty
flags.  This will reflow anything marked dirty under the target so long as
there's a chain of DIRTY_CHILDREN flags between it and the target.  Then we
check the list of children for the node, and iterate into each of them.

While in theory we could end up traversing frames more than once, it's
unlikely in practice that a frame would both be marked as dirty and be
on the path to a target node.

If we're really worried about this, we could refuse to merge paths that
have a target above another target.  I think in practice it will be rare, and
would work correctly anyways.

This means that the code that current looks a lot like:

  if (I_am_target)
  {
     reflow myself
     reflow any children with DIRTY or DIRTY_CHILDREN flags
  } else {
     GetNext(&nextFrame);
     find the frame
     call the frame's Reflow()
  }

will become more like:

  // this lets me iterate through the reflow children; initialized
  // from state within the reflowCommand
  nsReflowIterator reflowIterator(aReflowState.reflowCommand);
  nsIFrame *childFrame;

  // See if the reflow command is targeted at us
  PRBool I_am_target = reflowIterator->IsTarget();

  if (I_am_target)
  {
     // we're off the tree
     aReflowState.reflowCommand->SetCurrentNode(nsnull);
     reflow myself
     reflow any children with DIRTY or DIRTY_CHILDREN flags
  }
  while (reflowIterator.NextReflowNode(&childFrame))
  {
     // Make sure the iterator in the next level down can find its data.
     // Possible optimization: if DIRTY (not DIRTY_CHILDREN), and 
     // a reflow of a DIRTY node above handles reflowing all sub-frames,
     // we may be able to skip it.  Not a big deal in practice, so ignore
     // for now.
	 aReflowState.reflowCommand->SetCurrentNode(reflowIterator);
     call the child frame's Reflow()
  }

The one trick to worry about is the current reflow node in the tree.  We
need to set the current node to null so that any children that look at the
reflow tree will not think they're targets, and won't think they have
children in the tree (even if they are targets or have children - that will
be handled when the current target gets control back and goes through it's
children in it's iterator).

Comment 23 Randell Jesup [:jesup] 2002-03-07 20:55:58 PST
BTW, things like blobs and vectorsine run _immensely_ faster with the patch
(from the dynamic-core.net tests).
Comment 24 David Baron :dbaron: ⌚️UTC-10 2002-03-07 21:02:40 PST
I didn't completely follow comment 22, but one thing I worry you might not be
accounting for is that when something dirty is reflowed, it will often cause
other things to be marked dirty during the reflow (e.g., if something changes
size, if a floater moves, etc.).  So we really want to process everything in one
pass.  Your comment "While in theory we could end up traversing frames more than
once" scared me.
Comment 25 Mike Shaver (:shaver -- probably not reading bugmail closely) 2002-03-07 22:12:34 PST
I cut a branch for this, because trading patches is going to start sucking
_very_ soon.

: layout; cvs tag -b REFLOW_TREE_COALESCING_20020308_BRANCH
: layout; cvs tag REFLOW_TREE_COALESCING_20020308_BASE

Comment 26 Randell Jesup [:jesup] 2002-03-07 22:31:30 PST
N.B. here are waterson's reflow docs, VERY useful for understanding this bug:

http://www.mozilla.org/newlayout/doc/reflow.html
Comment 27 Randell Jesup [:jesup] 2002-03-08 07:55:14 PST
Another thing from shaver's and my conversation last night:

Some Reflow() methods reflow all their children (not just dirty ones), such as
nsInlineFrame.cpp, regardless if they're a target or not.  In order to make
things work correctly if there's a target inside there (keep the tree and
iterators in sync with the frames being walked), we need to find the correct
tree node for the child we're entering to reflow.  The iterator needs a method
|iter.SelectChild(nsIFrame *foo)|, which finds the tree node in the current list
being iterated that matches frame foo, or none if there is none that matches.

Comment 28 Mike Shaver (:shaver -- probably not reading bugmail closely) 2002-03-08 21:09:16 PST
Sample tree built from the chasing-clock demo I mention in comment 10:

Tree dump:
|
+-- 0x8834e50
  |
  +-- 0x8834f84
    |
    +-- 0x8835178
      |
      +-- 0x8834e88
        |
        +-- 0x8837e58
          |
          +-- 0x8842c2c (T)
          |
          +-- 0x8843028 (T)
          |
          +-- 0x88433ec (T)
          |
          +-- 0x8843738 (T)
          |
          +-- 0x8843a84 (T)
          |
          +-- 0x822e140
            |
            +-- 0x884411c (T)
          |
          +-- 0x8843dd0 (T)
          |
          +-- 0x884411c (T)
          |
          +-- 0x88444a8 (T)
          |
          +-- 0x88447f4 (T)

So it looks like we go from 61 frame-reflow calls to 16 here.  Promising!
Comment 29 Randell Jesup [:jesup] 2002-03-10 03:08:37 PST
Created attachment 73443 [details] [diff] [review]
First VERY rough cut as a patch.  Compiles, does not run.  For Shaver



Note: this really is for Shaver; I'll check this into the branch once I get it
limping up.  Currently dies in startup due to a null reflowCommand (makes
sense, can easily be fixed, but the sun is coming up...)
Comment 30 Randell Jesup [:jesup] 2002-03-10 21:41:17 PST
Checked in very rough first cut of patch to the branch.  (There may be some
build issues with content; shaver has resolved them and will check in in the
morning).

Runs (there's some minor editor wierdness, the every-other-character updates bug
is back I think with this patch).  Most browsing and DHTML seems to work
correctly otherwise, other than it being slow because it's Dumping the tree
every time, and it's still running in compatibility mode (no tree merging).  

There are known problem spots, mostly where I added XXX's.  Also, each spot
needs to be reviewed for correctly where I modified the flow, and I haven't even
looked at source style issues yet.

But it runs.
Comment 31 Randell Jesup [:jesup] 2002-03-10 23:17:50 PST
Checked in some updates.  Full tree merging is now enabled and working (mostly,
there are a few regressions, especially with cnn.com).  DHTML works.  The
nsReflowTree code has a bug with adding chunks, so I set the chunksize to 110
for the moment.  That will work for all but the worst sites (vectorsize and blobs).

Comment 32 Randell Jesup [:jesup] 2002-03-11 09:39:43 PST
Shaver checked in a fix for the reflow chunking, and I'm about to check in a fix
so that it actually deletes commands when it merges them, and implements
IsATarget (in a very simplistic way, we probably want to use a hash instead of
an array).
Comment 33 Randell Jesup [:jesup] 2002-03-11 15:26:21 PST
FYI, tests on the same machine I tested the "cheat" patch on (full opt, with
tree dumping on each reflow) show almost identical performance for the current
branch as the cheat patch, around 10x faster than trunk.  Looks like the perf
win holds up with the merged tree.  Still a bunch of detail work and regression
testing to do.  I'm running the current branch, with (in nsReflowTree.h)
KIDS_CHUNK_SIZE = 300 instead of 10, to work around a bug.
Comment 34 Randell Jesup [:jesup] 2002-03-11 15:30:03 PST
Current known regressions:
Editor: the "every other character echoes when typing bug"
http://bugzilla.mozilla.org/  - image and some text don't show up
cnn.com - main page is ok, stories often don't show the story text/image


Comment 35 Randell Jesup [:jesup] 2002-03-11 18:30:50 PST
From http://umsu.de/jsperf/index2.php

a) sliding an element 100px to the right, setTimeout set to 0ms between steps
b) sliding an element 100px to the right, setTimeout set to 30ms between steps
c) calculate the first 91380 elements of the harmonic series 
d) sliding 100 elements at once (20 steps, setTimeout set to 30ms per step)
e) Move GIFs with many transparent parts above each other

Time in ms

   reflow
   branch	IE4		IE5
	IE6		Mozilla		NS4		Opera
a)
318
	861		5,280	981		2,406		2,347	660		<<<<-----
b)
3,608
3,317
5,500
2,984
4,444
	4,350	5,440	
c)
2,146
-
	440		141		1,600		1,980	-		
d)
1,957
-
	1,150	636		14,743		1,041	-		<<<<-----
e)
4,836
-
	10,610	2,704	4,159		2,300	-	


NOTE: this is with a preliminary version of the branch, with trees being
dumped at every reflow(!).  Compiled with -O2, Linux RH 7.2, trunk 20020311xx,
450MHz P3, remote X display(!)

Also note: take those with a grain of salt, since I don't know which values
they display by default.  I'll re-run on the same machine tomorrow from the
trunk to check.  Note that we're still 1/2 to 1/3 the speed of IE on case d.
Comment 36 Randell Jesup [:jesup] 2002-03-11 18:35:07 PST
FEH, durn thing don't like nice tabs.

   reflow
   branch   IE4     IE5     IE6     Mozilla     NS4     Opera
a)  318     861     5,280   981     2,406       2,347   660     <<<<-----
b)  3,608   3,317   5,500   2,984   4,444       4,350   5,440	
c)  2,146   -       440     141     1,600       1,980	-		
d)  1,957   -       1,150   636     14,743      1,041	-		<<<<-----
e)  4,836   -       10,610  2,704   4,159       2,300	-	
Comment 37 Hixie (not reading bugmail) 2002-03-13 07:28:22 PST
Do we know why (c) got slower?
Comment 38 Randell Jesup [:jesup] 2002-03-13 08:08:46 PST
Those numbers (other than my test) were from some unknown build and system
reported by the site.  When I get a chance (or have the regressions fixed) I'll
run numbers before and after on the same machine.

BTW, I notice we are getting some merging of reflows into trees loading pages
(such as bugzilla.mozilla.org, merges 4 reflows), so I do think we're going to
get a bit of pageload improvement from this patch.
Comment 39 Mike Shaver (:shaver -- probably not reading bugmail closely) 2002-03-13 12:35:58 PST
http://xlat.assembler.org/ is a test case from the .perf group.
Comment 40 chris hofmann 2002-03-13 13:50:59 PST
are we thinking this is going to be baked enough land in the next week or two?
Comment 41 Pete Collins (MDG) 2002-03-13 13:56:51 PST
I was under the impression that good, solid patches that are approved land.
Then they bake along w/ everything else for a long time on the branch before a
release is rolled out.

--pete

Comment 42 Mike Shaver (:shaver -- probably not reading bugmail closely) 2002-03-13 16:21:23 PST
Things are looking pretty good right now, though there are a handful of
regressions we need to sort out (some things aren't getting reflowed correctly
in a batched case).  I'd certainly like to have this at a landable state within
2 weeks, but I'd be more confident if we could enlist some help from a layout
expert  to help us better understand the nature of the things we're seeing.

I'm going to be in California next week (San Jose area), so maybe I can pop in
and spend some quality time with a Mountain View layout hacker.

pete: things have to be solid and baked before they're ready to land on the
trunk (1.0 development is on the trunk right now, not a branch); we're long past
the point of throwing something against the trunk to see if it sticks.
Comment 43 Brendan Eich [:brendan] 2002-03-13 16:49:55 PST
I would hold mozilla1.0 for this fix, speaking only for myself and not for all
drivers.  DHTML has suffered for too long because of a basic design flaw that
was actually contested long ago by hyatt and evaughan, to no avail (the
perpetrator is long-gone).  Rather than "prematurely optimize", we're doing it
just in time for 1.0, and things look close enough, and good enough, that I'd wait.

/be
Comment 44 Mike Shaver (:shaver -- probably not reading bugmail closely) 2002-03-13 17:08:52 PST
The more I spend in this code and talking to dbaron and co, the more I
understand why the perpetrator in question doesn't want to use the XUL dirty-bit
system, which I think is the hyatt-evaughan lobbying you describe.  How well
does XUL's model handle an LXR-like page with many thousands of children below a
single parent?  Not sure I want to find out this close to 1.0. =)

Anyway, I'm heartened by your support, and hope that we have something very soon
that's ready for wide-scale testing.  In the meantime, people who want to start
banging on the branch are very much invited to do so and report troublesome
sites.    I've created a bug, marked as blocking this one, for tracking
regressions discovered in testing of this branch.

I'll try to merge against the tip and prepare test builds on at least Linux
(other platform volunteers please speak up!) tomorrow or Friday.
Comment 45 Brendan Eich [:brendan] 2002-03-13 18:02:05 PST
I didn't mean to bash unnamed perp from the past too much, or to endorse dirty
bits naively applied to wide, bushy trees.  Only to say that this ain't rocket
science, and that terrible DHTML perf has been a stain on Gecko's escutcheon for
too long.

/be
Comment 46 John Morrison 2002-03-13 18:02:32 PST
I don't think shaver meant to remove bug 130760 (the companion regressions 
tracking bug) as a blocker of this bug. Putting back. Slap me down if I'm 
wrong.
Comment 47 Aaron Kaluszka 2002-03-13 18:10:38 PST
I don't know if any work done here is related, but:
Bug 87808 disappeared on the February 2nd build but reappeared somewhere between
the 6th and the 9th of February.  Did something get checked in and backed out
that anybody knows about?
Comment 48 Robert O'Callahan (:roc) (email my personal email if necessary) 2002-03-13 21:48:19 PST
I'm a bit more cautious than brendan. Maybe it's because I understand just
enough about reflow to fear it :-).

If we're going to try to land this in 1.0 then I think it needs to land at least
a couple of weeks before putative 1.0 ship, and someone needs to be committed to
put a lot of energy into fighting any resulting fires. rjesup, shaver, this
means you :-). As long as we understand that, I'm OK with this.
Comment 49 Johnny Stenback (:jst, jst@mozilla.com) 2002-03-13 23:08:56 PST
IMO this is important enough that we could involve all (most) of Netscape's QA
people in doing a DHTML/Layout testing marathon to get lots of eyes on builds
with these changes in them once the diff is done.
Comment 50 Jesse Ruderman 2002-03-13 23:22:52 PST
Is this bug/patch specific to setTimeout, or does it also apply to inline
javascript and javascript event handlers?
Comment 51 Adam D. Moss 2002-03-14 00:53:19 PST
jst, that sounds terrific.
Comment 52 John Morrison 2002-03-14 02:10:53 PST
Pulled the current ./layout from branch REFLOW_TREE_COALESCING_20020308_BRANCH
and rebuilt from the top. (I also tried this on win32, but msvc was not happy 
with the nested classes in nsReflowTree.h).

I hate to report this after seeing that 'clock' dhtml running so smoothly on 
mozilla, but I gave this a quick A-B run (only changes between build A and 
build B being the changes in layout). So, anyways, with the build without 
these changes, on redhat6.1/500MHz/128MB, I got an avg. median of 1315msec.
With the changes and a rebuild, I got an avg. median time of 1451msec, which 
is ~9% slower.

Most of the deltas ranged from ~20% to 0% difference, with the most notable
slowing (before=3536, after=5391; change=+50%) being for content equivalent 
to <http://www.w3.org/TR/DOM-Level-2-Core/core.html>

This assumes, of course, I didn't make any bonehead errors, which is always 
possible. I note also that the console was chirping "Releasing 1 reflows 
batched" during the test, which can't help (but isn't likely the key factor).

But I don't think this is all bad news. Obviously I didn't crash  :-), and 
most of the pages appeared correctly (although some were missing various parts 
of the normal content).

[Sidenote: I am away till Monday, so I can't answer questions about the above 
till then. Ping kerz if you want some more help testing this in the meantime].
Comment 53 Randell Jesup [:jesup] 2002-03-14 06:13:08 PST
I certainly plan to do a careful analysis of perf on pageload before this lands,
including comparison of pageload runs with and without the branch.  There
probably are optimizations we can do for the "normal" case of a single
branch/target in the tree.
Comment 54 Randell Jesup [:jesup] 2002-03-14 11:33:48 PST
In debug builds, you can get lots of analysis of the reflow patterns.  See:

http://bugzilla.mozilla.org/show_bug.cgi?id=103925#c11

and you can also set these vars:

setenv NSPR_LOG_MODULES frame:21
setenv NSPR_LOG_FILE /tmp/reflow-tracing.log

Note: you get a lot....

JRGM: I'll remove the fprintf's from the opt builds for you.  Note I still
haven't even made an initial "clean up" pass; there are a lot of opts like not
creating the hash until you have a second item, etc that will speed things up. 
Also moving the reflowIterators deeper into the control flow in Reflow()
methods, and allocation pools/etc for the trees and such.


I currently suspect two major regressions: editor repaints are funky or
non-existant (in HTML only, XUL seems ok,  which makes some sense), and table
rows/etc don't always get laid out (tinderbox, bugzilla.mozilla.org), which
interestingly works ok if you remove the:

document.forms['f'].id.focus();

from the bugzilla page.  Very interesting.....
Comment 55 andreww 2002-03-14 18:34:21 PST
Here's another test js app. Runs fast in IE - dog slow in current mozilla 
builds. I dont have the branch so I have no way to test it out.

http://www.javascript-games.org/cgi-bin/socketMonkey.cgi?game=pool

Comment 56 Randell Jesup [:jesup] 2002-03-15 08:47:14 PST
Cleaned up a bunch of code on the branch.  No effect on the major regressions.
Editor echo issues seem to be linked to the frame being marked as dirty, so when
you type a character it doesn't issue a new reflow - but there is no reflow for
the editor frame active, which is why we seeBatch release of 0 frames.  (This is
for text widgets that don't echo at all, like bugzilla.mozilla.org.) 
Comment 57 Randell Jesup [:jesup] 2002-03-15 18:55:01 PST
Checked in a fix to the DIRTY bit maintenance in nsBoxLayoutState.cpp:UnWind().
 Didn't solve the regression, but was definitely a bug.
Comment 58 Bernard Alleysson 2002-03-16 06:14:08 PST
I pulled the branch and tried to compile
I use VC70 to build a static build
I had to comment out 2 lines in nsReflowtree.h to suppress all msvc errors:
            //friend class nsReflowTree::Node;
            //friend class nsReflowTree::Node::Iterator;

I'm restarting a full build now, I only tried layout with this patch


Comment 59 Bernard Alleysson 2002-03-16 09:55:15 PST
Created attachment 74532 [details] [diff] [review]
patch to build the brach with msvc

add nsReflowTree to makefile.win, comment out problematic "friend" declarations
Comment 60 David Baron :dbaron: ⌚️UTC-10 2002-03-17 08:59:08 PST
I just took a look at the changes to nsBlockFrame.cpp in the patch (yes, I
should have been reading diffs earlier, but...), and found what appears to me to
be a significant problem in the case where a block has multiple children in the
reflow path tree.  You're calling PrepareChildIncrementalReflow for all the
children in the reflow tree before reflowing any of them.  This says to me that
there's either a major case where you're reflowing too much or a major case
where you're reflowing too little.  (I haven't looked closely enough to figure
out which.)

First, I'll describe (roughly) how I think this should be handled in the block
code, and then I'll try to explain why the code currently on the branch can't
work.  I think what needs to happen is that a good bit of the incremental reflow
logic needs to be moved down into ReflowDirtyLines.  In particular, most of
PrepareChildIncrementalReflow (although not the part that causes incremental
reflows to change into resize reflows) can't be called from the top-level reflow
anymore, but, rather, needs to be done in ReflowDirtyLines.  In particular, the
marking a line dirty that PrepareChildIncrementalReflow does can't happen until
after all the lines before that line have been reflowed.  Then, when we get to
the line that has the next reflow target, we should check if that line is dirty.
 If it *is* dirty, we have to somehow merge the dirty reflow with the
incremental reflow targetted at some descendant of that line -- in some cases
that might mean just doing a dirty reflow, but I'm not sure if that would work
if the relevant incremental reflow is a style-change reflow.

So, what's wrong with the current code?  I think one of two things is probably
happening.  Either:
 1) We're reflowing too much.  In other words, whenever the reflow tree splits,
we do a full dirty reflow on the entire subtree for each child that's on a path
other than the first path, rather than following that path down to the target of
the reflow.
Or:
 2) We're reflowing too little.  In other words, if the incremental reflow of
the first child that's in the reflow tree causes damage to the line that's the
second child in the reflow tree, we're ignoring that damage and just targetting
the reflow down the path that we have, which may only touch a small portion of
what was dirtied by the change to an earlier line (e.g., a floater being pushed
down).

I'm not thinking that this will be somewhat difficult to fix in the presence of
the BRS_INLINEINCRREFLOW optimization, which allows the possibility that you
could have two children in the reflow path within the same line of a block.  If
we eliminate this by changing text inputs and textareas to be reflow roots
(something I've wanted to do for a while that would both improve performance and
reduce code complexity), then these changes would become much easier.

Or am I missing something that makes this all work?
Comment 61 Randell Jesup [:jesup] 2002-03-17 23:30:47 PST
David: Thanks whole-heartedly for the analysis; not knowing all the side-effects
of the Reflow/etc routines was a major problem when reworking this for
tree-based reflow.   I'll go over your comments in more detail tomorrow; they
look VERY helpful.  I think the editor/text optimizations might be a significant
win for cleaning up the code, as you suggest.  My apologies for not spending
more time on it this weekend; personal life (and taxes) intervened.  I'm back on
it full time tomorrow.
Comment 62 Adam D. Moss 2002-03-18 04:01:40 PST
One interesting perf regression for the branch versus
the trunk: typing in the URL-bar is about 3x or 4x slower
on the branch (Linux/X11/x86/-O2).
Comment 63 Randell Jesup [:jesup] 2002-03-18 11:49:51 PST
dbaron: if you were looking at the patch, I should note that the recent set of
changes I checked in added a ReflowDirtyLines() after each
PrepareChildIncrementalReflow() (i.e. I moved it into the loop).  Now, that may
not be sufficient; I'm looking at it more closely today.

In fact, looking at it for a few minutes, I see that
RetargetInlineIncrementalReflow() must be written for trees, and hasn't been. 
I'll work on that now.  Thanks again, and keep the commentary (or fixes) coming.

Comment 64 Randell Jesup [:jesup] 2002-03-21 18:21:30 PST
I've made some major checkins and fixed editor widgets (text lines and areas). 
This also seems to have fixed most of the "doesn't lay out all of tables" bugs.

Note: this exposes a number of things that were previously not getting invoked,
and there's at least one assertion I added firing.  Also, I'm doing most of my
testing in non-merged versions, so there may be MERGE_REFLOW=1 bugs (to turn off
merging but still use trees, change the define in nsPresShell.cpp).

Mention regressions (and there may be more now) in bug 130760.
Comment 65 Randell Jesup [:jesup] 2002-03-23 21:30:57 PST
Fixed most if not all of the assertions firing - they were mostly due to not
selecting the correct tree node when reflowing each line, and in some cases
reflowing lines more than once.

The main remaining regressions (incorrect spacing (cnn.com), lines move when you
type) are now fixed, and the assertions seem to be gone (very incomplete
testing, though).

New regressions (perhaps due to under-reflowing now): on bugzilla bug pages,
some of the text widgets paint their text (in the wrong spot) but not their
frames/etc.  Resize fixes this.

It's getting a lot closer, and is highly usable now.  Still needing to be done:
merge to tip.  (Is there a standard method/procedure for updating or replacing a
branch with one based off the current tip?)  I'll attach a patch based on the
diffs against the base.

People who've been considering trying this: it's a good time to start thinking
about it.
Comment 66 Randell Jesup [:jesup] 2002-03-23 22:18:16 PST
Created attachment 75808 [details] [diff] [review]
Current patch that makes up branch (against ...._BASE)

Does not include the msvc patch yet
Comment 67 Randell Jesup [:jesup] 2002-03-25 18:41:35 PST
New branch, REFLOW_TREE_COALESCING_20020325_BRANCH (layout ONLY).

To add, cd layout (VERY IMPORTANT), cvs update -r
REFLOW_TREE_COALESCING_20020325_BRANCH

I'm going to attach an additional patch that enables reflow merging in dom for
SetTimout() callbacks (which is what helps DHTML).  Note that this seems to
currently be over-reflowing, so temporarily you may not see the full
improvement.  I'm concentrating on correctness first, we know this is the right
way to improve performance from previous tests.

Please report regressions in bug 130760.  Biggest known regression involves
extra white space at the top of some websites.  I'll be doing a layout
regression run tomorrow morning early.
Comment 68 Randell Jesup [:jesup] 2002-03-25 18:43:22 PST
Created attachment 76134 [details] [diff] [review]
Patch to dom to enable batching of reflows in SetTimeout() callbacks.
Comment 69 Randell Jesup [:jesup] 2002-03-26 11:46:55 PST
Layout regression test results (current branch plus dom patch):

12 tests out of ~2385 failed.  Also there are a couple of reported crashes from
jrgm, and the known problems with netscape.com and bugzilla bug pages.  I'm also
building an optimized tree to test performance.

I'll list the failed tests on bug 130760
Comment 70 Randell Jesup [:jesup] 2002-03-27 13:08:01 PST
I'm about to commit some more small fixes to the branch.

Note that currently, I can't find any regressions if I set MERGE_REFLOWS to 0 in
nsPresShell.cpp, which means the remaining bugs are in the case where a node has
multiple children, or a node is both a target and a parent of a target.

I'm going to re-run the layout regression tests with MERGE_REFLOWS of 0 to see
how close we are in the non-merged case.

NOTE: we may well still be reflowing too much (even with MERGE_REFLOWS at 0). 
Other known issues:

- RetargetInlineIncrementalReflow() definitely needs to be rewritten more,
though I'm not sure of the correct algorithm.
- It would be nice not to have to call ReflowDirtyLines for each child of a
block that's in the tree.  Currently we do in order to make sure the current
reflow tree node is correct for the lines we're reflowing.
- I'm not sure if I need to call BuildFloaterList() after each call to
ReflowDirtyLines().
Comment 71 Randell Jesup [:jesup] 2002-03-28 08:43:29 PST
Created attachment 76574 [details] [diff] [review]
patch that matches the current branch

For anyone who wants to easily look at the changes or apply against tip, this
is the current branch as a patch (BRANCH vs. BASE)
Comment 72 Randell Jesup [:jesup] 2002-03-28 10:46:48 PST
Created attachment 76590 [details] [diff] [review]
Updated patch  to match branch

Moved updated IncrementalDamageConstrained() into nsBlockReflowContext.cpp to
match trunk changes that occurred on 3/12. (Had been in nsBlockFrame.cpp,
commented out during the merge for the 3/25 branch.)
Comment 73 Bernd 2002-03-28 12:08:15 PST
I am shocked whats going on in this bug.
<start rant>
 How on earth can this thing make it into 1.0??? My predictions is that it will
take two milestones to fix the regressions if this gets checked in. I really
argue the drivers to keep the promises from the mozilla manifesto.

We contend that a milestone where only fixes for topcrash and other severe bugs
(e.g., dataloss) get checked in, with lots of regression testing and code
review, is necessary before we can confidently brand a mozilla1.0.

In my oppinion this is the largest change layout has seen over month's. It
scares that everybody who I recognize for intimate knowledge of reflow issues
stays as away from this bug. So do I.  Further I don't think that it is a good
idea to start such a large change and then require people with layout knowledge
to spend theire time on it: it is not only the qa that would need to spend time,
but also people who would fix the layout topcrashes otherwise, and I think thats
a far better use of theire time and expertise.
<stop rant>

even a single failed testcase in the layout tests is enough to stop a checkin.
Comment 74 David Baron :dbaron: ⌚️UTC-10 2002-03-28 12:46:34 PST
I agree with bernd (and what Marc said in email), and I don't think this should
go in 1.0 at this point.  I've tried to hint gently at this over the past week
or so after seeing the current state of the patch (see comment 60), but I didn't
want to discourage it too much, since I think it is the correct approach, and I
think it should land on the trunk sometime after 1.0 branches.  I should have
been more discouraging about the potential for this to make 1.0 earlier, and I'm
sorry for letting rjesup work so hard on it in the hope that it might make 1.0
without being clearer.

I've looked at the patch quickly and I think it still has some serious problems
-- including the potential for making a *single* incremental reflow pass O(N^2)
in the number of children of an element (rather than O(N) of them, as most of
the O(N^2) algorithms in layout are).  I think it's probably worth getting some
careful review before doing too much testing, since I think review is going to
turn up issues that are going to require some pretty significant changes to the
patch (such as comment 60 above, which I don't think has been fully addressed).
 Having said that, I really don't have time to do that review now.
Comment 75 Randell Jesup [:jesup] 2002-03-28 14:07:13 PST
While I would love to see this in 1.0, I agree that it is a quite risky patch
for this late in the game.  I've been ready to say "drop this from 1.0", but
it's not for me to decide how important fixing DHTML is for 1.0.  Brendan
certainly thinks it's important (and I do too).  However, the complexity of the
reflow code is such that this will need more baking that we're likely to want. 
(It doesn't help that Waterson is away.)  It also doesn't help that I'm learning
the complexities of reflow as I do this, and because of sabbaticals and
workloads none of the people who know reflow already have had enough time to
really help (which is not meant to be a complaint; this idea/patch came up at
the last minute, and I'm grateful for the help I've gotten - in fact, I'm amazed
that it's as close to solid as it is, given the dangers of reflow).

I will keep hammering away at this regardless.  If this is not taken for 1.0, it
should go into trunk as the 1st post-1.0 patch, and be strongly considered as
one of the first patches to migrate from trunk to the 1.0 branch.

 -- Randell, posting using the reflow branch
Comment 76 Markus Hübner 2002-03-29 01:35:53 PST
As Jesup said "... how important fixing DHTML is for 1.0". Many major DHTML 
perf bugs have been postponed due to this bug and now this one also won't make 
1.0

Furthermore bug 117061 is also not fixed for 1.0 - what remains is a very 
disappointing mozilla1.0 milestone in view of DHTML.

Comment 77 Tom Mraz 2002-03-29 02:45:39 PST
I'd even suggest to postpone Mozilla 1.0 release one release farther -> to make
Mozilla 0.9.10 with this code in.
Comment 78 Adam D. Moss 2002-03-29 03:08:56 PST
I think we're going to have to accept that
Mozilla fumbled the DHTML ball for 1.0 and
look to the future.
Comment 79 Federico Giannici 2002-03-29 03:19:13 PST
I have been waiting Mozilla 1.0 for three years!
I don't care to wait one month more to have a REAL Mozilla 1.0...
Comment 80 Markus Hübner 2002-03-29 03:33:04 PST
Well, mozilla is already real in its current version and so are the major 
DHTML / timer problems we have in 1.0
Comment 81 David Baron :dbaron: ⌚️UTC-10 2002-03-30 13:53:10 PST
Bug 73348 should make some interesting reading, and is probably an interesting
source for testcases.
Comment 82 andreww 2002-04-01 10:25:21 PST
I wonder if it would be possible to put in place "hooks" into the trunk that 
would allow someone to install (post 1.0) some xpi which could enable 
this feature.  This way folks who want to can make the choice of less 
stability (perhaps) in return for faster DHTML.  sorta similar to how SVG 
was set up for a while, where you had builds that were "ready" for SVG 
and turned it on after some xpi file was installed.  Just a thought.
Comment 83 Chris Waterson 2002-04-01 14:44:16 PST
What bernd and dbaron said -- this is post-1.0 material by a large measure. I
understand how to do what rjesup is trying to do with block frames (and probably
even enough to make sure that block and box play nicely), but I don't know how
to do it with tables. karnaze or bernd should comment on that.

I'll take a look at this patch (rjesup, stop mangling the brace style!), and try
to comment more constructively anon.
Comment 84 Adam D. Moss 2002-04-01 15:10:16 PST
> stop mangling the brace style

Yay, waterson is back!  :)
Comment 85 Chris Waterson 2002-04-01 19:30:54 PST
So I'm thinking that a better approach here might be to change the `reflow
queue' data structure into a `dirty tree'. AppendReflowCommand would simply add
a path to the tree, the leaf of which would refer to the reflow command (or the
subset of the data that was useful during the reflow; e.g., the reflow type).
During a reflow, clean nodes would be removed from the tree as they were flowed.

This:

1. Automatically coalesces reflows when the command is posted. One fly in the
ointment is desaling with two commands with different types (e.g., `resize' and
`style change') posted to the same node: in this case, I think we could
determine a precedence relationship among the reflow types (perhaps dirty <
content changed < style changed) and evict the command with lower precedence. 

Presumably _any_ reflow (including resize and global style change) could clean
up the `dirty tree', avoiding the (probably rare) case where a global reflow is
processed while the reflow queue is not empty.

2. Allows for a natural implementation of `interruptible reflow'. An in-progress
incremental reflow could dead-reckon that it's spent too much time, and return
to the main event loop. Doing so would leave the frame tree and the
corresponding reflow structures with their invariants maintained.

3. Seems cleaner than the current approach, which grovels the reflow queue to
coalesce commands.

The `dirty tree' could be maintained as part of the pres context, eliminating
the need for the reflow command on the nsHTMLReflowState object.

Presumably, CancelReflowCommand could be implemented using the same logic that
removes a reflow path from the tree when the reflow is completed.

Thoughts?
Comment 86 David Baron :dbaron: ⌚️UTC-10 2002-04-01 20:57:38 PST
Both approaches have a problem that we need to think harder about, although the
previous approach might have been trying to work around it using multiple
reflows:  how to deal with different reflow types.  For example, how do we
handle merging a global resize-reflow with a style-changed reflow targeted at a
specific frame?  The style-changed reflow must clear more information, such as
preferred size / min size information.
Comment 87 Robert O'Callahan (:roc) (email my personal email if necessary) 2002-04-01 22:03:01 PST
Perhaps in your example
-- The global resize reflow propagates resize reflows to descendant frames
-- The style-changed descendant merges the incoming resize reflow with its own
reflow type, getting a style-change reflow
-- Frames on the path from the root to the style-changed descendant need to
reflow considering *both* that they are resize-reflowed *and* that they have a
style-reflowed child. Presumably this means in some places we'll have to
separate logic that checks the reflow type into two parts: one part that
considers the reflow type for this frame, and another part that considers the
merge of the reflow types for the children. The latter part consists of the code
that runs even when the current frame is not the reflow target.

Did that make any sense? I'm never quite sure how well I understand reflow.
Comment 88 Randell Jesup [:jesup] 2002-04-02 07:19:34 PST
I always end up mangling brace style in places, but I put it back before I
release the changes for real.  :-)  (Or I get beaten up by reviewers)

Maintaining a tree to start with makes sense; we chose the current mechanism to
minimize disruption of the code (in the hope it might make 1.0, and to minimize
unexpected side-effects).  As you said, it allows for some useful side-effects
as well (especially in the issue of interruptable reflow, which is a big problem
when loading large pages - you may be looking at another window/tab while the
page is loading, but you get frozen anyways).

CancelReflow would need us to maintain in each node the number of targets in all
children, or (perhaps better) search the tree to see if the branch can be pruned
(search for targets).  Which is better depends on how often CancelReflow is
done.  It may make more sense to maintain the info in the tree and avoid
possible O(n^2) effects on Cancel.

Merging the different types may be possible as suggested.  Worst case would be
to separate reflows by type - i.e. only coalesce reflows of the same type.  If
order of operation is important, you can maintain a (small) list of reflow trees
and only allow addition to the last tree in the list (with a new tree being
added if the tree reflow types don't match).
Comment 89 Chris Waterson 2002-04-02 08:33:10 PST
> Both approaches have a problem that we need to think harder about, although the
> previous approach might have been trying to work around it using multiple
> reflows:  how to deal with different reflow types.  For example, how do we
> handle merging a global resize-reflow with a style-changed reflow targeted at a
> specific frame?  The style-changed reflow must clear more information, such as
> preferred size / min size information.

Just to be clear, there are two cases here.

1. Merging two incremental reflows targeted at the same frame; e.g., an
incremental reflow of type `style change' targeted at frame f, followed by an
incremental reflow of type `dirty' targeted at frame f.

(As an aside, merging incremental reflows where the second reflow is targeted at
frame g, where g is an ancestor or descendant of f, is another story. We have
several bugs in the current system that occur when this happens, which replacing
the incremental reflow queue with a single incremental reflow tree may be able
to fix. More later.)

I believe this problem could be dealt by assigning a precedence to the reflow
types, and promoting the reflow command to the `most destructive'. I think
minimal change would be required in the Reflow methods that handle processing
for the target of an incremental reflow.

2. Merging a global reflow (resize, style change) with one or more incremental
reflows.

I don't think this is going to be much of a problem in real-life: I suspect that
the incremental reflow queue is currently empty most of the time we do a global
reflow. Nevertheless, a simple solution here would be to process (flush) any
incremental reflows before doing the global reflow. Although it may imply that
many frames are reflowed twice, it would certainly not be any less efficient
than the mechanism we have now (which processes the reflow queue after the
global reflow).

A more efficient solution might involve modifying the Reflow methods to
unilaterally check the incremental reflow tree as the reflow progresses,
regardless of the reflow `reason'. This could be implemented later.


> CancelReflow would need us to maintain in each node the number of targets
> in all children, or (perhaps better) search the tree to see if the branch
> can be pruned (search for targets).

Ideally, the number of nodes in the tree would be small, so I'd suggest the
latter as a first cut. If that turns out to be inefficient, we can maintain an
index (i.e. hash table) of current target frames, so removal would be O(1).
Comment 90 Stuart Ballard 2002-04-02 09:01:08 PST
> 2. Merging a global reflow (resize, style change) with one or more incremental
> reflows.
> 
> I don't think this is going to be much of a problem in real-life: 

I hate to butt in to a conversation that's obviously well over my head, but I've
been trying to follow this discussion and this part is confusing to me. It
sounds to me as if a global reflow ought to have a strictly greater level of
"destruction" than an incremental reflow. In which case, surely simply
_aborting_ the pending incremental reflows and doing the global reflow instead
would have the desired effect?
Comment 91 David Baron :dbaron: ⌚️UTC-10 2002-04-02 10:15:32 PST
> It sounds to me as if a global reflow ought to have a strictly greater level of
> "destruction" than an incremental reflow.

The point of this discussion (see comment 86) is that this isn't true.  A resize
reflow (or dirty reflow) doesn't clear as much information as a style-changed
reflow, so a style-changed reflow on a subtree still requires clearing more
information than would be done by a resize-reflow on the whole document.  At
least I think so.
Comment 92 Stuart Ballard 2002-04-02 10:28:47 PST
Ahhh, okay. Sorry for the spam.
Comment 93 Randell Jesup [:jesup] 2002-04-02 13:32:54 PST
An interesting observation about the URL for this bug (which moves 100 elements
by their left attribute):

When tracing through the blockframe that all 100 are children of (in the reflow
tree), I found that all of them are being marked as resize reflows; i.e.
PrepareChildIncrementalReflow() does FindLineFor(), and none of the 100 come
back as a match, so it does a PrepareResizeReflow() on each one, which marks all
the lines as dirty.

Perhaps this is an issue with other DHTML animations as well?
(Note: my testing is with the current branch).
Comment 94 Randell Jesup [:jesup] 2002-04-02 14:26:29 PST
Just checked in some significant improvements to the reflow tree stuff, mostly
in nsBlockFrame.cpp.  I found that the DHTML entries weren't being picked up as
incremental absolute frame reflows properly (which was why they turned into
resize reflows).  This _may_ (or may not) have been happening on the trunk for
DHTML, if so we may have a way to make a simple, safe patch that may improve
DHTML perf a bit (nowhere near what this branch does, but it may be a small,
safe win).  I'll look into it tonight.  THis solves some of the few remaining
editor regressions.

I also removed most of the usage of BRS_ISINLINEINCREFLOW, and created a wrapper
for ReflowDirtyLines() to include processing we need to do on each call.
Comment 95 Chris Waterson 2002-04-03 06:53:20 PST
rjesup, the more I look at your changes, the more I think dbaron was right wrt.
removing the inline incremental reflow stuff before we proceed here.

I've been following your changes to the block reflow code, and I am starting to
feel like things are going in the wrong direction. It looks to me like we're
calling ReflowDirtyLines multiple times from Reflow (via ReflowDirty), and I'm
not sure that's appropriate. 

If you don't mind, I'd like to take a stab at implementing dbaron's idea of
`reflow roots' to eliminate the inline incremental reflow optimization. I think
that should allow us to proceed here with minimal intrusion on the block frame
code path. As dbaron pointed out, the bulk of what ought to happen then is
moving logic from PrepareChildIncrementalReflow to ReflowDirtyLines.

Also, with respect to fixing other bugs with absolute positioning, can we fix
those independently of this patch? I.e., could you file another bug, make a test
case, so we can fix that separately on the trunk: don't fall into your old habit
of lumping the kitchen sink into a single bug! ;-)
Comment 96 Chris Waterson 2002-04-03 07:03:34 PST
Bug 135146 covers implementation of reflow roots.
Comment 97 Randell Jesup [:jesup] 2002-04-03 08:56:30 PST
Go right ahead with work on BRS_ISINLINEINCREFLOW elimination; in my latest
changes I started in that direction, but you understand this far better than I.

I'll see if the absolute position stuff is broken in trunk and if so open a bug
on it (and supply a patch).  (I just found that issue in my branch 10 minutes
before I left last night).  Again, it won't provide more than a marginal
improvement I believe.  Perhaps something that notices that the only thing that
changed was position might help (I think someone commented on that in a
reflow/DHTML bug somewhere that's been mentioned here).

The ReflowDirty/ReflowDirtyLines stuff - I agree we should probably only call it
once; BRS_ISINLINEINCREFLOW was the main reason I wasn't (or at least the main
reason I was unsure if I could get away with calling it once).  Note that the
way I have it currently, if a blockframe has multiple children in the tree, it
calls ReflowDirty for each child - which is what would have happened at that
point if the reflows hadn't been merged.  If we can merge those calls to
ReflowDirty, then we'll get a nice perf improvement in some cases.  The current
design should be no worse than the trunk code, but isn't optimal.
Comment 98 Randell Jesup [:jesup] 2002-04-11 10:58:17 PDT
Made a checkin to the branch that merges in waterson's bug 135146 changes
(including a change to nsReflowTree.cpp to work with 135146).  Also rewrote
RetargetInlineIncrementalReflow() to work correctly with trees (recurses to do
the actual retargetting).  In preparation for waterson's comments/updates to the
branch (feel free to either post a patch or simply update the branch).  We also
could merge the branch forward to the tip again at this point.
Comment 99 Chris Waterson 2002-04-11 11:29:42 PDT
Created attachment 78744 [details] [diff] [review]
proposed modificiations

I'd like to propose something along these lines (this patch isn't really
working yet, but it should be suitable for flavor). I'm loathe to summarize
before it's working, but...

I've lifted the nsReflowTree idea from the rjesup/shaver patch, but promoted
the nsReflowTree object to encapsulate the node/subtree idea. (I've simplified
it a bit, too, using nsSmallVoidArray instead of a one-off data structure.)

I've removed the reflowCommand member from nsHTMLReflowState, and replaced it
with a `tree' member which is of type nsReflowTree. As reflow descends through
the frame hierarchy, the nodes are pulled off the nsHTMLReflowState's `tree'
member in parallel. (I think I'd like to rename nsReflowTree to nsReflowPath,
or maybe just the member variable of nsHTMLReflowState to `path', but that can
wait.)

I've removed the notion of a `table' of reflow targets, and simply stored the
reflow commands in the nsReflowTree at appropriate points in the path. When an
incremental reflow arrives at a frame, it `knows' it is a target by virtue of
the fact that nsReflowTree::mReflowCommand is non-null.

Like the rjesup/shaver patch, each point in the reflow flow-of-control that
previously assumed a single descendant now must iterate through the
nsHTMLReflowState::tree's children. Furthermore, I've tried to make logic
changes so that a `reflow target' iterates through nsHTMLReflowState::tree's
children. In other words, even if you've been targeted for an incremental
reflow, there may still be paths `beneath' you that need to be dealt with.

This patch was made against an two- or three-day old tree, so don't try to
apply it to the trunk. It's for expository purposes only! :-)
Comment 100 Randell Jesup [:jesup] 2002-04-11 20:42:38 PDT
waterson: check your code for nsViewPortFrame.cpp - I think you're reflowing
mFrames.FirstChild potentially more than once, unless there can only be one
child in mFrames for this (which is quite possible).  Also, isHandled seems to
be confused with your patch.
Comment 101 Chris Waterson 2002-04-11 22:52:56 PDT
Created attachment 78854 [details] [diff] [review]
more functional version of above

This patch actually works, to some extent. I think nsViewportFrame is better
now, along with enough other things that you can actually browse. That said,
table timeout reflows are still broken, as are incremental reflows to combobox
child frames. I've XXX commented some scary stuff in the box code. I'm sure
that there are some subtleties with nested reflows to block frames that are
broken (i.e., block frame as a target with a child as a target). And  MathML
and SVG are both on the floor. Patch is still made against an (essentially)
mozilla-1.0 tree; I'll update to the trunk tomorrow if the builds smell good.
Comment 102 Chris Waterson 2002-04-12 18:00:40 PDT
Created attachment 79014 [details] [diff] [review]
working patch against current trunk
Comment 103 Chris Waterson 2002-04-12 18:03:34 PDT
The above patch passes my personal (very basic) smoketests and should be ready
for public consumption. Most notably, I've ripped out the table `timeout' reflow
code, which should be subsumed by the reflow tree.
Comment 104 Chris Waterson 2002-04-12 18:05:23 PDT
Created attachment 79016 [details] [diff] [review]
as above, but diff -w (for human perusal)
Comment 105 Chris Waterson 2002-04-12 19:13:18 PDT
Checked in changes on REFLOW_20020412_BRANCH. This should build on Linux and
Win32 (although I haven't tried the latter), but you'll need to *disable
MathML*. (Just haven't gotten around to getting that working yet.)
Comment 106 Chris Waterson 2002-04-12 21:54:33 PDT
- Mail headers are don't show up when initially displaying a message, probably
  due to the fact that I've stuffed style reflows targeted at a box.

- I don't think it's necessary to remove subtrees from the
  nsHTMLReflowState::path during block reflow. (Why did we ever do that, anyway?)

- I should make sure that this isn't leaking nsReflowPath objects all over the
  place. I suspect it is.
Comment 107 Heikki Toivonen (remove -bugzilla when emailing directly) 2002-04-13 00:23:12 PDT
Could you test bug 116593 and bug 81546 testcases, does this by any change fix
those?
Comment 108 Chris Waterson 2002-04-14 17:37:39 PDT
- Mail folder pane doesn't update when emptying trash.

- Mail message pane needs resize-reflow to get rid of horizontal scollbar
  on some messages.

- www.m-w.com won't let you look up any words. Looks like a dead
  presentation shell.
Comment 109 Chris Waterson 2002-04-14 20:09:33 PDT
Stealing from rjesup, setting component to `Layout'. Ran the page loader tests
on the (admittedly not all the way working) branch, here's what I saw:


BASE
Avg. Median : 711 msec		Minimum     : 171 msec
Average     : 724 msec		Maximum     : 2309 msec

BRANCH
Avg. Median : 699 msec		Minimum     : 150 msec
Average     : 711 msec		Maximum     : 2184 msec

So, a marginal speedup (I'll be generous and call it 2%), presumably due to the
fact that we collapse multiple incremental reflows targeted to different
containers in the tree.
Comment 110 Chris Waterson 2002-04-14 20:13:23 PDT
heikki: this does appear to fix bug 116593 (adding as dependency); however, it
does not appear to fix bug 81546.
Comment 111 Chris Waterson 2002-04-15 20:29:24 PDT
Fixed problems with mail three pane (update nsBoxLayoutState.[h|cpp]): we were
failing to properly handle nested reflow commands targeted at boxes in the same
hierarchy.

Also fixed problem with m-w (update nsPresShell.cpp): it turns out that text
frames append a reflow command _during their initial reflow_, which I had
dropped on the floor.

The only problem that I notice now is that we appear to be missing at least one
reflow on some pages. In other words, loading any large page (like this bug
report), and the doing a slight vertical resize, causes the page's width to jump
slightly.
Comment 112 Chris Waterson 2002-04-15 21:05:47 PDT
Created attachment 79386 [details] [diff] [review]
patch incorporating above fixes

This patch (against the current trunk) incorporates the above fixes, as well as
fixing the nsReflowPath leak.
Comment 113 Chris Waterson 2002-04-16 19:58:33 PDT
Created attachment 79562 [details] [diff] [review]
ready for prime time?

This patch (made against this morning's trunk):

- Fixes some more memory leaks (nsReflowPath::Remove was not deleting the
  subtree it removed),

- Makes sure that the nsBoxToBlockAdaptor prunes the incremental reflow subtree

  from the path after performing the reflow. This ensures that any subsequent
  reflows (e.g., due to addition of scrollbars in a scroll frame!) are treated
  as resize reflows. This fixes the extraneous horizontal scrollbar that would
  suddenly disappear as soon as the window was resized.

- Fixes a crash in nsViewportFrame where an incremental reflow targeted at
  the viewport was being incorrectly propagated as an incremental reflow to
  the viewport's children.

AFAICT, it's a wrap, and ready for some heavy-duty testing. These changes have
been mirrored onto the REFLOW_20020412_BRANCH.
Comment 114 Chris Waterson 2002-04-16 20:00:43 PDT
(N.B., I still need to fix MathML and SVG, but I'll wait to do that until I hear
a `yea' or `nay' from some people...)
Comment 115 Chris Waterson 2002-04-16 20:18:25 PDT
Oops:

1. I still need to handle incremental reflows targeted at combobox frames.

2. After thinking about a brief exchange that dbaron and I had a few days ago,
   I think it's probably safe to remove all of the reflow retargeting code in
   the block frame. (I managed to convince myself that the situation there was
   specific to text frames -- because there was an inline element with a
   scrollframe.)

3. This patch contains a fix for a another bug (cf. CalculateBlockSideMargins
   in nsHTMLReflowState); can't recall which.

4. I need to deal with the case where more than one reflow command is targeted
   at the same frame. (I think I'll just kick that command back into the
   reflow queue and process it in a separate pass -- I have yet to hit that
   case, FWIW.)

5. Need to double-check the viewport frame: does anyone else ever post
   UserDefined reflows? (The Viewport assumes that this means `reflow my fixed
   frames'; the previous code did this for any (?) user-defined reflow.)

Comment 116 David Baron :dbaron: ⌚️UTC-10 2002-04-16 20:26:53 PDT
Created attachment 79566 [details]
testcase showing nsBlockFrame changes still need work

This is a test case that demonstrates why you should do something like what I
described in comment 60.

Steps to reproduce:
 * Load testcase.
 * Click "Go"

In trunk build:
 * Text rewraps around float, as it should.

In branch build:
 * Text doesn't rewrap around float.
Comment 117 David Baron :dbaron: ⌚️UTC-10 2002-04-16 20:38:11 PDT
This method in nsReflowPath.h is never defined:

    // Find or create a child of this node corresponding to forFrame.
    // XXX better name
    nsReflowPath *EnsureChild(nsIFrame *aFrame);

Comment 118 Chris Waterson 2002-04-17 12:17:12 PDT
Fixed the unused method. My assumption is that PrepareChildIncrementalReflow
would mark just those lines dirty that contained frames along the reflow path
(or, in the case that the reflow was targeted at a floater, it would mark _all_
frames dirty); e.g.,

 1: clean -----------------------------
 2: dirty -----XXXXX-------------------
 3: clean -----------------------------
 4: clean -----------------------------
 5: dirty --------------XXXXXXX--------
 6: clean -----------------------------

If reflowing line 2 impacted line 3, line 3 would be marked dirty and reflowed.
If no impact continued on to line 4, line 4 would be skipped. Line 5 would be
reflowed. If the reflow in line 2 was targeted at a placeholder frame, then we'd
bail out to PrepareResizeReflow, which should mark all wrapped lines as dirty.

Clearly, I don't understand this as well as I should. :-)

I think it's safe to remove the last vestiges of the inline incremental reflow
retargeting stuff, but I still haven't thought hard enough about it (and was
hoping to defer it to a second pass). But, removal would certainly make
implementing your proposal in comment #60 simpler.

Anyway, thanks for the test case. I'll keep pounding on this.
Comment 119 Randell Jesup [:jesup] 2002-04-17 13:22:18 PDT
Great work Chris!

I'm updating to the latest stuff with a clean tree and will start doing some
real testing/debugging.  I'm somewhat tied up with driver issues and getting
worldgate stuff done.

How does perf on DHTML look with the new stuff in an opt build?
Comment 120 David Baron :dbaron: ⌚️UTC-10 2002-04-17 13:25:30 PDT
The problem is that you're *using* the reflow path when reflowing frame 5, even
though it was marked dirty *again* by the damage caused when reflowing frame 2,
so that you only reflow its descendant along the path rather than all of its
descendants.

(However, that brings up some questions about the meanings of the different
reflow types.  If certain types of reflows (e.g., StyleChange) cause more damage
than just being marked dirty, you might need to somehow use both.  I'm not sure
if this is the case, and I think we need to define what the different reflow
types (and reasons) mean much more clearly.  This could also help performance. 
(For example, which reflow types require invalidating a cached pref-size,
min-size, or max-size?  Just style change, or anything-but-resize?))

That said, I don't understand your diagram in the previous comment.  I also
don't understand what the punting to PrepareResizeReflow for floaters gets us
(i.e., what would fail if we didn't do that), and I suspect it's not needed anymore.

Also, while I'm on the topic, how do we pick up the reflow path again when it
goes through a floater?  I haven't looked into how we do that in general,
though, so it might be a silly question...
Comment 121 Chris Waterson 2002-04-17 14:45:16 PDT
dbaron: I think that the reason your test case doesn't work is because only the
width changes on the floated <div>. If I also adjust the height of the <div>
(e.g., setting the height to 301px as well as increasing the width), then your
test case works fine (cf. your comments in nsBlockFrame::RememberFloaterDamage).

Alternatively, forcing a jump in the debugger to execute the code in
RememberFloaterDamage at an opportune time makes the test case work, as well.
Comment 122 Chris Waterson 2002-04-17 14:57:05 PDT
IOW, if we could notice horizontal changes to floats, it seems to me like things
ought to `just work': passing an incremental reflow to a child frame seems like
it should be sufficient to account for damage caused by changes to previous
frames in the flow.
Comment 123 Chris Waterson 2002-04-17 15:40:29 PDT
Sorry, I'm a little out-of-sync. My last two comments didn't take into account
what you'd written in comment #120.

You wrote:

> The problem is that you're *using* the reflow path when reflowing frame 5,
> even though it was marked dirty *again* by the damage caused when reflowing
> frame 2, so that you only reflow its descendant along the path rather than
> all of its descendants.

So let's look at specifically how this is different from an incremental reflow
where we reflow frames not along the reflow path. There are two cases:

1. The line contains a block frame. In this case, the block reflow context
   will set the reflow reason to resize (rather than incremental). This causes
   nsBlockFrame::Reflow to PrepareResizeReflow instead of
   PrepareChildIncrementalReflow. The substantial difference here is that
   PrepareResizeReflow will dirty all the lines that are impacted by floaters.
   PrepareChildIncrementalReflow will dirty only the line (well, now lines)
   along the reflow path -- relying on PropagateFloaterDamage to detect cases
   where a line must be `lazily' dirtied to account for float movement.

2. The line contains a inline frames. In this case, all of the frames in the
   line will be reflowed anyway, so it's a moot point (modulo weird cases
   involving box frames that want to be treated like inlines; hence my concern
   for retargeting reflows).

> (However, that brings up some questions about the meanings of the different
> reflow types.  If certain types of reflows (e.g., StyleChange) cause more
> damage than just being marked dirty, you might need to somehow use both.
> I'm not sure if this is the case, and I think we need to define what the
> different reflow types (and reasons) mean much more clearly.  This could
> also help performance. (For example, which reflow types require invalidating
> a cached pref-size, min-size, or max-size?  Just style change, or
> anything-but-resize?))

I don't have much to say about this other than it smells right. It would also
allow us to combine reflows targeted at the same frame in a useful way (instead
of what I propose in point 4 of comment #115, above).

> That said, I don't understand your diagram in the previous comment.  I also
> don't understand what the punting to PrepareResizeReflow for floaters gets us
> (i.e., what would fail if we didn't do that), and I suspect it's not needed
> anymore.

If RememberFloaterDamage worked, I think you'd be right. As is, I think that the
aState.IsImpactedByFloater check force-dirties lines that might not otherwise be
reflowed.

> Also, while I'm on the topic, how do we pick up the reflow path again when it
> goes through a floater?  I haven't looked into how we do that in general,
> though, so it might be a silly question...

In general, the reflow path is maintained in the nsHTMLReflowState object (just
like the reflow command object used to be). The nsHTMLReflowState object's ctor
takes a child frame; when the reflow reason is `incremental', the ctor finds the
next branch in the path that contains the child frame.

You'll see that there are some places where I had to explicitly add a reflow
reason of `resize' to the nsHTMLReflowState's ctor (e.g., when computing
collapsing margins) so that the ctor doesn't try to pluck from the path -- and
wind up dereferencing a null pointer.
Comment 124 Randell Jesup [:jesup] 2002-04-17 17:09:40 PDT
Working from your patch on trunk:

nsPresShell.cpp:  In ~IncrementalReflow() the loop needs to start at Count()-1,
not Count().

nsReflowPath.cpp: In ~nsReflowPath() the loop needs to start at Count()-1, not
Count().

nsReflowPatch.h:  RemoveChild() should be more like this:
    void
    RemoveChild(nsIFrame *aFrame) { 
        iterator iter = FindChild(aFrame);
        if (iter.mIndex != -1)
            Remove(iter);
    }


The whole way mIndex is used worries me.  It looks rife for errors (mostly not
checking for equality with EndIterator() (or mIndex == -1) before calling things
like Remove().

Perhaps these have been fixed on the branch (last time I tried the branch I
couldn't get it to work, probably because the rest of my tree was newer).
Comment 125 Randell Jesup [:jesup] 2002-04-17 17:34:16 PDT
The throbber seems to not work with the patch (and my fixes as per above), and
as per the comments in the code, RetargetInlineIncrementalReflow() isn't done
(though from the comments I'm not sure you think it's necessary, so I won't work
on fixing it).
Comment 126 Chris Waterson 2002-04-17 18:37:32 PDT
Yeah, I fixed those off-by-ones on the branch earlier today. I've fixed a few
other things on the branch, too -- probably time for a new patch.

nsReflowPath::Remove(iterator&) actually bounds-checks the iterator it's passed,
so I don't think extra checking is needed in
nsReflowPath::RemoveChild(nsIFrame*). Not sure I understand your other concerns
about mIndex?

The throbber is working for my trunk+patch build, as well as my branch
build...any other changes in your tree?
Comment 127 Chris Waterson 2002-04-17 19:26:19 PDT
Created attachment 79750 [details] [diff] [review]
updated to this morning's trunk, minor bug fixes.

Current. Fixes off-by-one errors; removes the spurious bug fix mentioned in
point 3 of comment #115.
Comment 128 Randell Jesup [:jesup] 2002-04-18 08:20:10 PDT
RemoveChild() needs to check for FindChild() not finding the child (I hit this
one and crashed); checking for mIndex == -1 seems to be the easiest way.

Remove() does have an assertion of mIndex >= 0 (which triggered in the crash I
had above); I guess there's no need to do more so long as we're sure no one is
going to call Remove() with an iterator at the end (mIndex of -1).

I have no changes in my tree except for the ones I mentioned; I pulled it around
4/15 at 11:30 am edt.  I'll re-apply your new patch and see.  Throbber not
working could have been a trunk breakage.

I got this, though I'm not sure if it's related to the patch, when loading
neowin.net:

###!!! ASSERTION: nsFrameManager::GenerateStateKey didn't find content by type!:
'index > -1', file
/home/jesup/src/mozilla_trunk/mozilla/layout/html/base/src/nsFrameManager.cpp,
line 2261
###!!! Break: at file
/home/jesup/src/mozilla_trunk/mozilla/layout/html/base/src/nsFrameManager.cpp,
line 2261
Comment 129 Chris Waterson 2002-04-18 08:32:57 PDT
rjesup: thanks for testing this. I think you've got an older patch (or at least
an older version of nsReflowPath.cpp). This is what it looks like in my tree:

void
nsReflowPath::Remove(iterator &aIterator)
{
    NS_ASSERTION(aIterator.mNode == this, "inconsistent iterator");

    if (aIterator.mIndex >= 0 && aIterator.mIndex < mChildren.Count()) {
        delete NS_STATIC_CAST(nsReflowPath *, mChildren[aIterator.mIndex]);
        mChildren.RemoveElementAt(aIterator.mIndex);
    }
}

neowin.net triggers frame manager assertion in a clean tree, so it's not related
specifically to these changes.
Comment 130 Randell Jesup [:jesup] 2002-04-18 09:21:45 PDT
Yes, it must be the older patch that tripped me up on that (I used the "ready
for prime time" patch, which is now obsolete.  I'll be updating today.

BTW, I was doing some testing on http://umsu.de/jsperf/index2.php as well as a
bunch of the testcases mentioned here, and we do show significant DHTML perf
improvements, even without the patch here to the DOM to use batching for
SetTimeout() callbacks.

There are significant regressions with
http://www.dynamic-core.net/scripts/index.php (waterson has seen these).  Other
than that, it looks very good.
Comment 131 Stuart Ballard 2002-04-18 09:50:53 PDT
I don't think this is directly relevant to this bug as described, but it might
be an interesting test to see if this style of code can actually get reflow
right in a case where the current code *doesn't*. If it's irrelevant to this bug
(eg because it's table-related) then I'm sorry for mentioning it here.

The webpage at mp3.wuffies.net (obLegal: this is my personal site, for my
personal use: please don't download the mp3s from it, because that's illegal) is
a table in which the first column grows substantially wider when its last row is
reached. The table is also dynamically generated by a process which is often
slow (well, a couple of seconds slow). Mozilla usually renders the first half of
the table, then re-renders afterwards when the last row comes in. When this
happens, artefacts of the original reflow are left around (specifically, bits of
the second column persist too far to the left, where the first column is now).

I thought this might be a good testbed for a reflow-related change... sorry if
it's offtopic for this bug.
Comment 132 Randell Jesup [:jesup] 2002-04-18 16:00:36 PDT
Updated to waterson's most recent patch against trunk.  Throbber works fine now.
 No other changes in the tree other than my DOM patch to batch SetTimeout()
callbacks (which, BTW, I did have in my tree when I was doing that perf testing
earlier today).

I don't see any regressions now on dynamic-core.net with this patch.  I'm going
to do some profiling on the patch and see if there are any new DHTML hotspots.
Comment 133 Chris Waterson 2002-04-18 16:24:25 PDT
The dynamic-core.net problem appears to be timing- and cache-dependent (*sob*).
Comment 134 Dawn Endico 2002-04-18 18:10:13 PDT
waterson's linux and win32 builds should show up on ftp.mozilla.org in
a few minutes at:

http://ftp.mozilla.org/pub/mozilla/nightly/experimental/bug-129115-reflow/
Comment 135 Tuukka Tolvanen (sp3000) 2002-04-18 18:35:09 PDT
Reproducible crash with bug-129115-reflow 2002041810 test build on linux:
1) go to resource:///res/samples/test12.html (more fixed pos demo)
2) resize window so you get a scrollbar in the main frame
3) drag srollbar thumb

trunk cvs 2002-04-19 doesn't crash
Comment 136 srikanth Koneru 2002-04-18 18:56:32 PDT
just downloaded the latest build 2002041803. The following sites about which
others reported problems, i tired the following sites  and didn't seem  to have
a problem.

http://dynamic-core.net/
http://mp3.wuffies.net/cgi-bin/v3/mpjbdir

These web pages showed up instantly. I should mention that i have a dsl connection.

I have lost track of what was putback to which gate(branch or trunck).  Anyway
some putback seems to have fixed these bugs.
Comment 137 Chris Nelson 2002-04-18 19:47:50 PDT
Are the Win32 experimental reflow builds that have just shown up in the
/nightly/experimental directory debug builds? Because I see a significant DHTML
slowdown in the tests I've tried with my PII-400, 128Mhz, Win98.

The URL in comment #12 seems about 1/2 the speed, and doesn't complete properly.
The 4th box never reaches its final stopping point, and the rest don't appear at
all.

The fireworks example in comment #11 doesn't display properly (doesn't seem to
work).

The dynamic core link in comment #20 doesn't display anything, but hogs all the CPU.

Test a) in comment #35 gave me a result of 550000 for the experimental reflow
build, but 390000 for the 2002041617 Win32 daily on the same machine. 
Comment 138 José Jeria 2002-04-19 01:25:21 PDT
Actually the examples on dynamic-core.net worked very good last week (well at
least they didnt hang mozilla). But since bug 129953 was backed out they dont
work at all anymore. You probably knew about this though, sorry for spamming.
Comment 139 Markus Hübner 2002-04-19 04:22:21 PDT
Testing http://ftp.mozilla.org/pub/mozilla/nightly/experimental/bug-129115-
reflow/ makes hardly any sense since bug 129953 is still open.

Comment 140 Chris Waterson 2002-04-19 05:23:54 PDT
The builds that dawn posted are optimized. Note that they were branched from the
trunk on 4/12 (although I'm not sure if anything has regressed between now and
then). I'm seeing  better performance (or at worst, no change) on every test
that has been mentioned in the bug; however, I'm running on Linux @ 700MHz. I'll
try some slower Win32 boxes today.
Comment 142 Chris Waterson 2002-04-19 06:43:46 PDT
That's great -- thanks for the links. I'd appreciate it more, though, if people
could use these builds for normal browsing and report any crashers or layout
glitches that they've found.

On the branch, I've fixed the crasher that Tuukka reported, as well as the
incremental table reflow problem on dynamic-core.net that caused some of the
demos not to appear in the list.

I'm probably going to cut a new branch today (hopefully with fixes for bug
138057 and some of the other issues mentioned in comment 115). But in the
meantime, please keep banging on the experimental bits.

Thanks!
Comment 143 Olli Pettay [:smaug] 2002-04-19 08:14:36 PDT
bug-129115-reflow/linux crash in http://www.w3.org/Style/CSS/. 
(1_0_0/2002041809/Linux does not crash.)
Comment 144 Chris Waterson 2002-04-19 08:59:52 PDT
smaug: thanks. The crash on w3.org is the same as test20.html, so that's fixed.
Comment 145 Chris Waterson 2002-04-19 09:37:08 PDT
Wow, Win32 really sucks! :-)

Is this because of pavlov's bug 129953? If, so I agree with comment 139.
Comment 146 Randell Jesup [:jesup] 2002-04-19 15:55:19 PDT
I think pav's win32 patch (backed out on branch, but checked into trunk I think)
helps DHTML a LOT.  I have it on the RC2 Not Suck list, so I think it makes
sense to test with it.  

Note that 137706 is for enabling the same thing on Linux and Mac
Comment 147 Randell Jesup [:jesup] 2002-04-22 17:15:02 PDT
Using the last patch uploaded here (plus the DOM patch), I see some significant
layout issues when loading the ebay "sell item" page.  (Go to ebay, select sell,
log in, select (say) art & antiquities.  Note that most of the page isn't
visible until you resize.)
Comment 148 Chris Waterson 2002-04-22 19:09:58 PDT
Created attachment 80515 [details] [diff] [review]
against 2002-04-22 trunk. includes fixes for reflow ommission in table row group, crasher in fixed frame.

I've created REFLOW_20020422_BRANCH, based off this morning's trunk. I'll post
experimental builds as soon as possible (probably tomorrow morning).
Comment 149 Chris Waterson 2002-04-22 23:12:29 PDT
Linux, Win32, and Mac builds from REFLOW_20020422_BRANCH (attachment 80515 [details] [diff] [review]
versus this morning's trunk) have just been posted to:

  <ftp://ftp.mozilla.org/pub/mozilla/nightly/experimental/bug-129115/>

Note that I _didn't_ back out pavlov's image stuff on this branch as the Win32
build I tested seemed to work reasonably well. Please continue to test, and make
notes here.

thanks!
Comment 150 José Jeria 2002-04-23 07:01:02 PDT
Hopefully I am not wrong on this one. But bug 49095 works for me using a copy from:

ftp://ftp.mozilla.org/pub/mozilla/nightly/experimental/bug-129115/

But the bug is there with Mozilla RC1...
Comment 151 Olli Pettay [:smaug] 2002-04-23 13:24:56 PDT
Sometimes the "final painting" is missing.
So you have to resize or otherwise get the Moz to repaint itself.

This happens (rarely) for example in 
http://www.iltasanomat.fi/saa/paikallis.asp.

Maybe this is the same problem as #147.

Tested: 
  Linux REFLOW_20020422_BRANCH : errors
  Linux Trunk 2002042221 : ok
Comment 152 andreww 2002-04-23 14:58:36 PDT
I'm testing this out on mac - on my iMac - and I'm not seeing much of a
difference, if at all with the latest build from the ftp site.  I guess at least
it's not slower :)

I wish there was an example I could point to on mac and say 'see? it's much
faster in the test build'  but going over the examples posted here I could see
no measurable difference in speed..

One oddity which is probably just my machine was that I could not see the
autocomplete widget the first time I launched the test build. It showed up fine
on subsequent launches though.
Comment 153 Chris Waterson 2002-04-23 15:03:35 PDT
Okay, it sounds like there may still be some table incremental reflow bugs
lurking in there. I couldn't reproduce problems on either ebay or the .fi site,
above. Any other reports greatly appreciated.
Comment 154 Neil Marshall 2002-04-23 15:49:47 PDT
http://www.globalserve.net/~brent/tech/beam
It's a lot faster now, but still not close to IE.
Comment 155 Stuart Ballard 2002-04-23 15:54:30 PDT
If you're looking for table testcases, try the mp3.wuffies.net site I mentioned
above. The problem occurs if it loads slow enough that you get an incremental
reflow half-way through the table. If you don't get a reflow in that situation
directly from the server (I almost always get one the first time I load it - the
server-side code does a bunch of directory scanning of stuff that probably isn't
in the OSs disk cache) then try simulating it on an artificially hobbled slow
server - eg make the server pause for 5s before the letter 'L'.

That shows an incremental reflow bug on all mozilla builds I've tried up to and
including RC1 (I only use linux, so it might be OS-dependant, but that seems
unlikely).

I know that probably isn't directly related to this bug, but you did ask for
incremental table reflow testcases :)
Comment 156 /\/\arcio Galli 2002-04-23 16:41:53 PDT
Adding topembed also.
Comment 157 Randell Jesup [:jesup] 2002-04-23 17:14:11 PDT
My ebay table problem (see bug 130760) did appear to be an incremental reflow
issue, but it was before the current patch.  I'll see if I can make it happen
again with the current one.  Try slow websites like realtor.com as well.
Comment 159 Chris Waterson 2002-04-24 11:41:07 PDT
Just so people understand: making the changes described in this bug will by no
means fix all of Mozilla's DHTML problems. It might not even fix very many of them.

At this point, the most useful thing to do is to test the patch in that bug
(which lays the groundwork for other improvements), and look for _reproducable
regressions_ in _normal layout_. Zarro regressions means that we can land the
patch on the trunk, and continue with `the next big DHTML win'.

thanks.
Comment 160 Chris Waterson 2002-04-24 21:49:27 PDT
Created attachment 80898 [details] [diff] [review]
patch for review

This patch leaves combobox `broken' (but I can't seem to construct a test case
that causes it to misbehave: dead code?). It deals with multiple incremental
reflows with different reflow types being targeted at the same frame (even
though this didn't seem to cause any problems). It also includes the patch from
bug 138057.

This is ready for review, IMO. There appears to still be a table (?)
incremental reflow bug in here, but I figure there's enough code to go over
that reviewers might as well get started if this is to have any chance of
landing this millenium: I can work on tracking down the table problem in
parallel.
Comment 161 Jacob Wexler 2002-04-25 09:55:54 PDT
Using Build ID 2002042219 on NT SP6a:

Opening
http://www.haaretz.co.il/hasite/pages/ShArt.jhtml?itemNo=156091&contrassID=1&subContrassID=0&sbSubContrassID=0

paints the left column on the page OK momentarily, but after reflowing the center
column the left column is left partially covered and does not reflow unless I
re-size the page, scrolling vertically, or let Windows repaint it (by opening
another app over the Mozilla window and then minimize that other app).

FWIW, this page also tries to load a shockwave flash applet at the top. I don't
have that plugin installed.
Comment 162 Ronald van Kuijk 2002-04-28 10:19:03 PDT
There have been recent checkins in the trunk that, combined with this patch give
us  an enourmous boost in DHTML performance especially on Windows. See bug
#21762#c103

A new experimantal build would be great (i'm still learning to do this my self,
at least on linux...)
Comment 163 Chris Waterson 2002-04-28 21:55:53 PDT
Created attachment 81450 [details] [diff] [review]
updated patch

This patch was updated to be current with the trunk as of 2002-04-28 (accounts
for some changes to block frame, etc. that have gone into the tree over the
last week).

Also, this fixes a problem with nested reflows targeted at block frames that
dbaron pointed out to me. See

  <http://www.maubi.net/~waterson/mozilla/bugs/index.html#block-and-line>

for details.

dbaron: I juggled the reflow reason mangling logic in
nsBlockReflowContext::ReflowBlock and nsLineLayout::ReflowFrame to cover the
cases we'd discussed...
Comment 164 Markus Hübner 2002-04-30 07:46:48 PDT
There is a very interesting thing about the test at
http://taboca.com/worlds/gek/testcases/lia/lia.html

The animation moves perfectly until the big image with the baby isn't 
completely loaded. Then the performance dramatically degrades. Does this 
provide any valuable information?
Comment 165 karnaze (gone) 2002-04-30 18:17:54 PDT
Created attachment 81810 [details] [diff] [review]
(non compiled) patch with minor changes to tables 

I installed the patch dealing with tables and removed some remaining timeout
reflow stuff (e.g. eReflowType_Timeout was in a case statement and 4 methods
were still declared), changed the style/comments somewhat, and raised a
question (see "question for waterson") for the case when a cell is both a
target and has children which are targets. I did not install all of the other
files and so it may not compile. I didn't change anything that would cause any
additional testing. I like it very much. r=karnaze for the table files.
Comment 166 rbs 2002-05-01 01:30:14 PDT
I read the patch and it is looking pretty good. The plan of migrating to the
reflow tree/path and from there on doing further specific tweakings with the
mindset of the new framework sounds attractive. Have you been maintaining a
branch (or another recent patch) that I can apply (for tracing purposes in the
debugger)?

The bug has come a long a way, and so did comments... (and the patches...) Mind
opening a follow-up bug to ease slow transfers?
Comment 167 Robert Kaiser 2002-05-01 14:15:19 PDT
I tried to compile with attachment 81450 [details] [diff] [review] applied to my tree, but SVG didn't
build with that. I got the following lines:
nsSVGOuterSVGFrame.cpp:307: `struct nsHTMLReflowState' has no member named
`reflowCommand'
nsSVGOuterSVGFrame.cpp:308: `struct nsHTMLReflowState' has no member named
`reflowCommand'
nsSVGOuterSVGFrame.cpp:312: `struct nsHTMLReflowState' has no member named
`reflowCommand'
nsSVGOuterSVGFrame.cpp:306: warning: `class nsIFrame * target' might be used
uninitialized in this function
nsSVGOuterSVGFrame.cpp:310: warning: `class nsIFrame * nextFrame' might be used
uninitialized in this function
make[4]: *** [nsSVGOuterSVGFrame.o] Error 1
before the build broke.
BTW, against what state should attachment 81810 [details] [diff] [review] be applied? It seems I couldn't
even apply the patch successfully, so I also couldn't try compiling :(
Comment 168 Chris Waterson 2002-05-01 14:54:53 PDT
Created attachment 81924 [details] [diff] [review]
incorporate karnaze's changes; add code-level documentation

karnaze: I rolled your changes into the main patch.

A style change reflow targeted at a table cell should subsume any other
incremental reflows targeted at the cell's children. So I think that should be
fine.

Also added some code-level documentation based on private feedback from
attinasi.
Comment 169 Chris Waterson 2002-05-01 17:30:34 PDT
Created attachment 81952 [details] [diff] [review]
with patch for SVG

This should fix the SVG build bustage.
Comment 170 rbs 2002-05-01 21:48:16 PDT
[This bug is already too long and might need a continuation bug as the fixups 
continue]

I am hitting the assertion below at startup. The problem seems to be an 
incorrect reflow reason being used.

In #2, |reason| is initial, but aReflowState.reason is said to incremental in 
the constructor in #1, causing the lookup of the path (in GetSubtreeFor) to fail 
(since the real reason should have been initial). From the trace, the problem 
goes back to IncrementalReflow::Dispatch() where in the root reflow state is 
always defaulted to incremental.

In this case the box overwrites the reason back to what it should be, but in the 
general case I wonder if this isn't suggesting that there are some frames that 
are never reflowed with the initial reason.

====
nsBoxToBlockAdaptor::Reflow()
[...]
#1    nsHTMLReflowState   reflowState(aPresContext, aReflowState, mFrame,        
                                      nsSize(size.width, NS_INTRINSICSIZE));
#2    reflowState.reason = reason;
#3    reflowState.path   = path;
====


NTDLL! 77f9eea9()
nsDebug::Assertion(const char * 0x022fc984, const char * 0x022fc974, const char 
* 0x022fc924, int 207) line 291 + 13 bytes
nsHTMLReflowState::nsHTMLReflowState(nsIPresContext * 0x012cb658, const 
nsHTMLReflowState & {...}, nsIFrame * 0x03eb6490, const nsSize & {...}) line 207 
+ 35 bytes
nsBoxToBlockAdaptor::Reflow(nsBoxLayoutState & {...}, nsIPresContext * 
0x012cb658, nsHTMLReflowMetrics & {...}, const nsHTMLReflowState & {...}, 
unsigned int & 0, int 0, int 0, int 0, int 0, int 1) line 793
nsBoxToBlockAdaptor::RefreshSizeCache(nsBoxToBlockAdaptor * const 0x03eb64ec, 
nsBoxLayoutState & {...}) line 363 + 49 bytes
nsBoxToBlockAdaptor::GetMinSize(nsBoxToBlockAdaptor * const 0x03eb64ec, 
nsBoxLayoutState & {...}, nsSize & {...}) line 504
nsSprocketLayout::GetMinSize(nsSprocketLayout * const 0x03b43fe8, nsIBox * 
0x03da3aa0, nsBoxLayoutState & {...}, nsSize & {...}) line 1373
nsContainerBox::GetMinSize(nsContainerBox * const 0x03da3aa0, nsBoxLayoutState & 
{...}, nsSize & {...}) line 536 + 38 bytes
nsBoxFrame::GetMinSize(nsBoxFrame * const 0x03da3aa0, nsBoxLayoutState & {...}, 
nsSize & {...}) line 1119 + 20 bytes
nsStackLayout::GetMinSize(nsStackLayout * const 0x0141cdd0, nsIBox * 0x03da38b4, 
nsBoxLayoutState & {...}, nsSize & {...}) line 124
nsContainerBox::GetMinSize(nsContainerBox * const 0x03da38b4, nsBoxLayoutState & 
{...}, nsSize & {...}) line 536 + 38 bytes
nsBoxFrame::GetMinSize(nsBoxFrame * const 0x03da38b4, nsBoxLayoutState & {...}, 
nsSize & {...}) line 1119 + 20 bytes
nsBoxFrame::Reflow(nsBoxFrame * const 0x03da387c, nsIPresContext * 0x012cb658, 
nsHTMLReflowMetrics & {...}, const nsHTMLReflowState & {...}, unsigned int & 0) 
line 951
nsRootBoxFrame::Reflow(nsRootBoxFrame * const 0x03da387c, nsIPresContext * 
0x012cb658, nsHTMLReflowMetrics & {...}, const nsHTMLReflowState & {...}, 
unsigned int & 0) line 243
nsContainerFrame::ReflowChild(nsIFrame * 0x03da387c, nsIPresContext * 
0x012cb658, nsHTMLReflowMetrics & {...}, const nsHTMLReflowState & {...}, int 0, 
int 0, unsigned int 0, unsigned int & 0) line 784 + 31 bytes
ViewportFrame::Reflow(ViewportFrame * const 0x03da3840, nsIPresContext * 
0x012cb658, nsHTMLReflowMetrics & {...}, const nsHTMLReflowState & {...}, 
unsigned int & 0) line 603
IncrementalReflow::Dispatch(nsIPresContext * 0x012cb658, nsHTMLReflowMetrics & 
{...}, const nsSize & {...}, nsIRenderingContext & {...}) line 943
PresShell::ProcessReflowCommands(int 0) line 6368
PresShell::FlushPendingNotifications(PresShell * const 0x03b774f0, int 0) line 
5175
nsXULDocument::FlushPendingNotifications(nsXULDocument * const 0x013e7d30, int 
1, int 0) line 2503
nsXBLResourceLoader::NotifyBoundElements() line 300
nsXBLResourceLoader::StyleSheetLoaded(nsXBLResourceLoader * const 0x03cd2f58, 
nsICSSStyleSheet * 0x04609450, int 1) line 209
CSSLoaderImpl::InsertSheetInDoc(nsICSSStyleSheet * 0x04609450, int 2, nsIContent 
* 0x00000000, int 1, nsICSSLoaderObserver * 0x03cd2f58) line 1196
InsertPendingSheet(void * 0x046098a0, void * 0x03ead438) line 757
nsVoidArray::EnumerateForwards(int (void *, void *)* 0x01ce83c0 
InsertPendingSheet(void *, void *), void * 0x03ead438) line 660 + 21 bytes
CSSLoaderImpl::Cleanup(URLKey & {...}, SheetLoadData * 0x03eb5070) line 821
CSSLoaderImpl::SheetComplete(nsICSSStyleSheet * 0x00000000, SheetLoadData * 
0x03eb5070) line 914
CSSLoaderImpl::ParseSheet(nsIUnicharInputStream * 0x03bc3a50, SheetLoadData * 
0x03eb5070, int & 1, nsICSSStyleSheet * & 0x04609450) line 949
CSSLoaderImpl::DidLoadStyle(nsIStreamLoader * 0x03eb5840, nsString * 0x03c3f240 
{"/*
 * The contents of this file are subject to the Netscape Public
 * License Version 1.1 (the "License"); you may not use t"}, SheetLoadData * 
0x03eb5070, unsigned int 0) line 984 + 27 bytes
SheetLoadData::OnStreamComplete(SheetLoadData * const 0x03eb5070, 
nsIStreamLoader * 0x03eb5840, nsISupports * 0x00000000, unsigned int 0, unsigned 
int 2298, const char * 0x03bc2028) line 741
nsStreamLoader::OnStopRequest(nsStreamLoader * const 0x03eb5844, nsIRequest * 
0x03ebb200, nsISupports * 0x00000000, unsigned int 0) line 163
nsJARChannel::OnStopRequest(nsJARChannel * const 0x03ebb204, nsIRequest * 
0x03eb5b54, nsISupports * 0x00000000, unsigned int 0) line 606 + 49 bytes
nsOnStopRequestEvent::HandleEvent() line 213
nsARequestObserverEvent::HandlePLEvent(PLEvent * 0x03ebf954) line 116
PL_HandleEvent(PLEvent * 0x03ebf954) line 596 + 10 bytes
PL_ProcessPendingEvents(PLEventQueue * 0x01237e50) line 526 + 9 bytes
_md_EventReceiverProc(HWND__ * 0x02bc07f8, unsigned int 49488, unsigned int 0, 
long 19103312) line 1077 + 9 bytes
USER32! 77e148dc()
USER32! 77e14aa7()
USER32! 77e266fd()
nsAppShellService::Run(nsAppShellService * const 0x03ae9550) line 451
main1(int 1, char * * 0x00304e70, nsISupports * 0x00000000) line 1431 + 32 bytes
main(int 1, char * * 0x00304e70) line 1780 + 37 bytes
mainCRTStartup() line 338 + 17 bytes
KERNEL32! 77e992a6()
Comment 171 rbs 2002-05-01 22:59:10 PDT
Another problem that I find is that the path ends up null anyway for the case 
where a frame tries to reflow a child for which no reflow command was 
dispatched. To be more precise, suppose that there is a recorded path from root 
R to frame F, and continuing downward to F's child f.

Now suppose that F wishes to reflow another child g (a sibling of f) using the
pseudo-code:

for child in (f, g) {
  setup the child's ReflowState( in:F's reflowState, in:child ) 
  -->problem is: this will give a path for f, but will give a null path for g
                 since no reflow path for g was registered earlier.
                 I am seeing some crasher in the JavaScripted MathML editor as a
                 result of such a scenario
  ...
}
Comment 172 Chris Waterson 2002-05-02 13:15:30 PDT
I've fixed the issue that you've described in comment 170. (I wasn't seeing the
assertions because I've been running in an optimized build...the box frame needs
to create the reflow state as `resize' in this case as it does the path munging
by hand.)

WRT. the issue in comment 171, the container frame should convert the reflow
reason to `dirty' in that case. The `new rules' for the reflow reason are:

  - A reflow reason of `incremental' implies that the current frame is along
    the reflow path, and therefore path will not be null.

  - A frame should convert the reflow reason to `dirty' (or possibly
    `resize') if it needs to propagate damage from an incremental reflow to
    siblings or children.

  - A frame must propagate a reflow reason of `style changed' to all of its
    children.

Longer term, it may make sense to eliminate the `dirty' reflow reason, and
replace it with `incremental' and a null path. (I didn't want to do that in this
pass, however -- too much change in one fell swoop leads to confused code
reviewers, I've found from being on the receiving end.)

If you could point me to the `JS MathML editor', and let me know how to
reproduce the crash, I'd be happy to try to fix the problem.
Comment 173 rbs 2002-05-02 13:50:23 PDT
The JS MathML editor auto-installs as a .xpi :
http://groups.google.com/groups?hl=en&th=e2966aa753c00059&rnum=1

Steps to reproduce the crash after launching the editor:
1. click somewhere in the editor window to position the caret
2. click the menu-item '(\square)' in the toolbar (this inserts it)
3. make a selection with the inner \square
4. click the menu-item Insert -> Matrix -> 2x2 (this inserts it)
5. make a selection with the \square in the first cell
6. click the menu-item '(\square)' in the toolbar
   -> crash
Comment 174 rbs 2002-05-02 13:57:44 PDT
Regarding the 'new rules', it might be safer to fold a bit of that logic in the
reflowstate constructor then, what do you think? Since the constructor is
testing to see if the frame is in the path, it might as well adjust its default
reason accordingly (while the caller can still tweak it as the box is doing).
Comment 175 Marc Attinasi 2002-05-02 15:13:23 PDT
Comment on attachment 81952 [details] [diff] [review]
with patch for SVG

Thanks for adding the comments and assertions :)

What do you think about adding this assertion

 NS_ASSERTION(reason == eReflowReason_Incremental?
path != nsnull :
path == nsnull, "path required for incremental reflow, disallowed for other
reflow types");

to the HTMLREflowState constructors, as a POSTCONDITION?

Just and idea - I don't mean to make a fuss or anything, take it or leave it
(though I do believe it is good to assert the invariant somewhere). 

So, I looked this stuff over, ran it as dogfood for a few days, found it to be
very very good. sr=attinasi, assuming that you forward to me documentation on
this change for inclusion into the layout docs.
Comment 176 Chris Waterson 2002-05-02 15:25:26 PDT
Created attachment 82108 [details] [diff] [review]
fix for assertions, MathML incremental reflow

Okay, I've fixed the MathML incremental reflow problem (knock on wood): I've
made it so that MathML container frame will not incrementally reflow children
not along the reflow path (which seems like the right thing anyway). The MathML
editor seems to work fine with this change -- if only I could figure out how to
install the fancy fonts on Linux.

Also, I've cleaned up the bajillion assertions that my previous patch caused
(shame on me, I was running an opt build that didn't show any of them).
Basically, there were a half-dozen places where we'd hit that assertion in a
`beningn' way (because immediately after creating the reflow state, we'd whack
the reflow reason). I've made changes so that we now compute the reflow reason
up-front, and pass it to the reflow state's ctor.
Comment 177 Chris Waterson 2002-05-02 16:34:06 PDT
Marc, it may be a bit strong to enforce that path == nsnull when reason !=
eReflowReason_Incremental, in general. I think it would be better to just say,
`if reason != eReflowReason_Incremental, path is irrelevant'. There are a few
places that twiddle with the reason post-nsHTMLReflowState construction, and
there isn't a systematic way to enforce it.

And while we could enforce that as a post-condition of the nsHTMLReflowState's
ctors, it seems superfluous since each of the non-root ctors is explicitly
_setting_ path to nsnull when reason != eReflowReason_Incremental. (It's not
going to change before we leave the scope of the ctor.)

That said, I _did_ add assertions to make sure that path != nsnull when
constructing an nsHTMLReflowState with eReflowReason_Incremental. This required
me to juggle logic in about a half-dozen places where we were getting `benign'
assertions; e.g.,

  nsHTMLReflowState childRS(...);
  childRS.reason = /* anything but eReflowReason_Incremental */

This is `benign' because although the ctor panics, we immediately whack the
reason to something else. To avoid assert-botch noise, I changed these to:

  nsReflowReason reason = /* twiddle this however */;
  nsHTMLReflowSTate childRS(..., reason);

rbs: the reflow reason twiddling is ad hoc enough that I'm not sure it can be
merged systematically into the reflow state object. For example, in some places,
we actually _do_ convert an incremental reflow to a dirty reflow; in other
places, we just don't flow the child frames if they're not along the path.

Comment 178 rbs 2002-05-02 16:54:08 PDT
+  nsIFrame* childFrame;
+  for (childFrame = mFrames.FirstChild();
+       childFrame != nsnull;
+       childFrame->GetNextSibling(&childFrame)) {
+    if (aReflowState.reason == eReflowReason_Incremental) {
+      // Don't incrementally reflow child frames that aren't along the
+      // reflow path.
+      // XXXwaterson inverting this loop logic (e.g., so that we
+      // iterate through the reflow path's children) would be more
+      // performant, but I don't want to be too intrusive here.
+      if (! aReflowState.path->HasChild(childFrame))
+        continue;
+    }

I see that you are skipping some reflows now. I am suspicious that this might
have side-effects with stretchy MathML frames or frames which are 
context-sensitive (i.e., frames for which changes outside can still affect 
them). E.g., if the baseFrame of an accentFrame is changed, then the accentFrame 
still needs to be reflowed (extended or shrinked) along with the baseFrame to 
ensure that the accent continues to cover the base accurately.

So let's continue to keep the contract that MathML isn't doing incremental 
reflow for now given that not all the details of what to do have been worked 
out. Let's just reflow the whole lot and move on, i.e., if the incremental 
reason is where the crash comes from, what about setting it to resize if 
path->HasChild() is false? BTW, there are other similar loops to watch out 
(e.g., in mfencedFrame).

The rest of the patch looks okay to me, r=rbs applies from now on your patch as
I am going off-line now. I agree with attinasi that the 'new rules' need to be 
documented (e.g., the non-null command which means 'this == target'!).
Comment 179 Chris Waterson 2002-05-02 20:27:52 PDT
I'm hoping to address rbs's comments off-line (because this bug is just too 
darn big at this point). I'll post a summary here when we resolve the issues. 
In the meantime, I've created a new branch: REFLOW_20020502_BRANCH, that is 
this morning's trunk plus attachment 82108 [details] [diff] [review]. I've just posted a win32 binary to

  <ftp://ftp.mozilla.org/pub/mozilla/nightly/experimental/bug-129115/>

I'll post a Linux binary later tonight. If all goes well, I will try to land 
this early next week.
Comment 180 Chris Waterson 2002-05-03 13:53:27 PDT
Created attachment 82259 [details] [diff] [review]
better fix for mathml incremental reflow

This incorporates a less aggressive (and more comprehensive) fix for handling
incremental reflows that arrive at MathML frames:

- The prior patch would flow only the child frames along the incremental reflow
path. This patch reflows all the child frames, using eReflowReason_Dirty for
child frames that don't lie along the reflow path.

- The prior patch only tackled nsMathMLContainerFrame; this patch also handles
maction, mfenced, and mroot frames.
Comment 181 rbs 2002-05-03 14:26:56 PDT
Comment on attachment 82259 [details] [diff] [review]
better fix for mathml incremental reflow

r=rbs
Comment 182 rods (gone) 2002-05-03 14:47:44 PDT
r=rods for forms controls
Comment 183 Chris Waterson 2002-05-07 16:12:18 PDT
Created attachment 82719 [details] [diff] [review]
after review with kin

kin and I spent most of the afternoon going through the block-and-line changes.
I've made some minor mods where obvious problems came up. Overall, I think we
realized that the Viewport is a sewer that needs a bit of an overhaul (I don't
know if it's necessary to do that in this patch, though). I wasn't able to
remember or explain my box changes very well: I'll probably want to refresh my
memory and add a big comment there.
Comment 184 David Baron :dbaron: ⌚️UTC-10 2002-05-07 19:32:39 PDT
Created attachment 82759 [details]
partial review comments from dbaron

Here are review comments on the first part of the patch (previous version).  I
didn't get through the whole thing, and I may not have time to in the next few
days, so I figure some comments are better than none.  Nothing major here,
though.
Comment 185 rbs 2002-05-07 21:43:43 PDT
waterson: do you mind opening a continuation bug? Since this one is already
weird, and with the usual fixups that might happen even after the checkin, it is
not going to be convenient to revisit the bug to double-check things out.
Comment 186 Chris Waterson 2002-05-09 17:31:57 PDT
Created attachment 82984 [details] [diff] [review]
incorporate dbaron's comments, bz & kin testing

dbaron wrote:

>|#if defined(DEBUG_dbaron) || defined(DEBUG_waterson)
>|    NS_NOTREACHED("We don't have a line for the target of the reflow.  "
>|		    "Being inefficient");
>|#endif
>Do we still hit this?

The only place that I've hit it is when we reflow the combobox (press
the `edge case' button on

 <http://www.maubi.net/~waterson/mozilla/bugs/select_js.html>,

for example). I really think that this is a problem in the combobox,
though.

>How about an assertion that the child isn't in the reflow path, and a
>note to remove it if we hit the assertion because we've started putting
>inlines in the reflow path again?

In the patch I'll attach shortly, I've put the code back. If we're
going to leave RetargetInlineIncrementalReflow in the code, we might
as well leave this there, too.

>We have a bug on that extra reflow to get the overflow area, right?
>Maybe it should be cited in the code?	(And it looks like there's a
>similar problem in nsInlineFrame.)

Not sure.

>+    // But...if the incremental reflow command is a StyleChanged
>+    // reflow and its target is the current block, change the reason
>+    // to `style change', so that it propagates through the entire
>+    // subtree.
>+    nsHTMLReflowCommand* rc = mOuterReflowState.path->mReflowCommand;
>
>This needs a big XXX comment saying that this is really insufficient
>(the damage loss problem), and it should probably point to the comment
>at the beginning of nsBlockFrame::ReflowDirtyLines, and vice versa.

What is the `damage loss problem'?

>|    if (state & NS_FRAME_IS_DIRTY)
>|	reason = eReflowReason_Dirty;
>
>I wonder if this check should be right after the initial setting of the
>reason to resize rather than within the check of the parent reflow
>state's type.	What if a resize causes floater damage that marks
>something dirty?  Shouldn't it get a dirty reflow?  I doubt it really
>matters, though.  (Where do we differentiate dirty and resize?)

The only difference for the block frame is whether or not
PrepareResizeReflow gets called. (PrepareResizeReflow will
pre-emptively mark lines dirty -- based on floater damage, wrapping,
percentage-aware children, etc.)  In the `dirty' case, it's not
called, and so only the lines that are currently marked as dirty get
reflowed (modulo floater damager propagation, etc).

>nsHTMLReflowCommand.{h,cpp}
>
>You should remove the mPrevSiblingFrame member completely, since it's
>unused.

Done.

In other news...

I've fixed the incremental reflow problem with <select> frames that bz
pointed out (breaking the test case in bug 82873). Looks like we'll
need that code I ignored in nsComboboxControlFrame, after all! :-)
rods, it'd be great if you could re-review this stuff.

kin noticed some assertions firing with the sidebar. Caught a case
where the nsHTMLFrameOuterFrame needed to convert an incremental
reflow to a dirty if the child wasn't on the reflow path. Also, needed
to tweak the nsBoxToBlockAdaptor to pass back the `fixed' reflow path
from CanSetMaxElementSize since RefreshSizeCache can cause the adaptor
to reflow its frame.

kin also discovered that resizing a frame group would cause a crash. I
think I checked the nsHTMLReflowState ctors in every subdirectory of
layout except for layout/document. Oops.

After thinking about it some more, I think that I'm a dolt for
ignoring rbs's suggestion in comment 174. I've changed the logic in
the nsHTMLReflowState ctors so that if the child frame isn't along the
path, it automatically converts the reflow reason from `incremental'
to `dirty'. This allowed me to undo the reflow reason twiddling in
MathML, as well as some other places. It also makes it a lot harder to
walk off the end of the reflow path by mistake, which should mean I'll
have fewer crash bugs to deal with when this gets checked in.
Comment 187 rods (gone) 2002-05-10 07:09:21 PDT
from what I can tell it looks right r=rods
Comment 188 kinmoz 2002-05-10 08:40:31 PDT
Comment on attachment 82984 [details] [diff] [review]
incorporate dbaron's comments, bz & kin testing

r=kin@netscape.com on the block and line changes.
Comment 189 Chris Waterson 2002-05-10 11:31:44 PDT
Changes checked in. May the Force be with us.
Comment 191 Aleksey Nogin 2002-05-10 19:08:27 PDT
This check-in added a new "might be used uninitialized" warning (and removed two
of them):

-layout/html/base/src/nsPresShell.cpp:6184
- `PRTime afterReflow' might be used uninitialized in this function
- `PRTime beforeReflow' might be used uninitialized in this function
+layout/html/base/src/nsPresShell.cpp:6335
+ `PRIntervalTime deadline' might be used uninitialized in this function
Comment 192 R.K.Aa. 2002-05-11 11:20:27 PDT
Created attachment 83208 [details]
2002051104, XP: test results from http://www.umsu.de/jsperf/index2.php

The performance boost after this checkin outright extreme in a few cases:
Mozilla got 9 times faster on the "sliding 100 elements at once (20 steps,
setTimeout set to 30ms per step)" test at http://www.umsu.de/jsperf/index2.php

Mozilla is now faster than MSIE6 in all but one of the "Complex" cases there.
For an other (extreme improvement) sample, check out the "text follows cursor"
effect at http://my.iwebland.com/ with a build from before and after this fix.

WOW :))
Comment 193 R.K.Aa. 2002-05-11 11:20:59 PDT
Created attachment 83209 [details]
2002051104, XP: test results from http://www.umsu.de/jsperf/index2.php

The performance boost after this checkin outright extreme in a few cases:
Mozilla got 9 times faster on the "sliding 100 elements at once (20 steps,
setTimeout set to 30ms per step)" test at http://www.umsu.de/jsperf/index2.php

Mozilla is now faster than MSIE6 in all but one of the "Complex" cases there.
For an other (extreme improvement) sample, check out the "text follows cursor"
effect at http://my.iwebland.com/ with a build from before and after this fix.

WOW :))
Comment 194 R.K.Aa. 2002-05-11 11:22:24 PDT
doh.. sorry - sometimes moz just keeps spinning when i attach files - and
"silantly" keep attaching and attaching without notifying it's succeeded ://
Comment 195 R.K.Aa. 2002-05-11 11:42:37 PDT
Created attachment 83211 [details]
oops.. i was a little fast: Here results from MSIE6, same PC

bz pointed out that the other numbers may be averages, so i ran on MSIE6 too.
The numbers even here. But we're VERY good at sliding elements 100px to the
right ;)
Comment 196 /\/\arcio Galli 2002-05-11 14:55:22 PDT
R.K.Aa, 

Adding my old scrolling credits demo - but this time the scrolling DOM effect on
top of the mozilla.org DOM tree. So we can measure what happens. This represents
the scenario where Style Animation would be running on top of an existing web
site (existing DOM tree).  

http://taboca.com/tests/credits.html (credits on top of mozilla.org home page DOM)

http://www.mozilla.org/docs/dom/samples/dom-css-fonts/credits.html (credits
running alone)
Comment 197 /\/\arcio Galli 2002-05-11 19:19:06 PDT
The following sample now makes sense:

http://livesidebar.com/lsblabs/desktabs/index-desktop.html

NOw you can drag IFRAMES with ("Sidebar Tabs") Panels inside and have a nice
experience. The scrolling demo that I sent is weird it's really slow, but I
checked many other cases and it's really great improvement!!. Before, was not
only about slow, we had this "dhtml hangs" behavior when the reflow time was
bigger than the setTimeout time window. Now panels and windows on top of sites
is possible and the dHTML door is open again. This is a amazing start! :)
Mozilla DHTML community will be glad and I am sure the future will be nice
again. As an evangelist for Gecko, a new world of demonstrations will be
showcased now. This is a for sure requirement to other products using Mozilla.

Thanks!! 
Comment 198 Dimitrios 2002-05-12 01:28:50 PDT
I run almost all testcases posted here in Win2K, except for those posted in
comment #192 or later which were already tested after the recent fix. Comparing
20020511 to the performance of 20020509 build, 10 cases have noticeable to
extremely noticeable improvementwhile in 5 cases there isn't any noticeable
difference. IE6 does it very well in all cases, usually being about 2x faster
(where performance results are available) except for some tests in
alladyn.art.pl where there is performance parity (those tests didn't gain
anything from the patch). So IE is still faster but the gap is much smaller than
before. 
Comment 199 Prashant Desale 2002-05-24 16:48:23 PDT
Verified on 2002-05-23-08-trunk.
Comment 200 Susie Wyshak 2002-05-30 15:11:58 PDT
Will this fix the extremely fast cursor flicker in Netscape.com's home page
search field?

Mgalli believes it is because the scrolling news is making a bunch of setTimeout
calls, each of which causes a reflow/update to the entire document.


Comment 201 Aaron Kaluszka 2002-05-30 15:29:39 PDT
No, I don't believe it addresses that problem.
Comment 202 Jaime Rodriguez, Jr. 2002-05-31 14:37:44 PDT
Mass removing adt1.0.0, and adding adt1.0.1 because, we are now on 1.0.1.
Comment 203 scottputterman 2002-06-03 12:06:14 PDT
Adding adt1.0.1+ and mozilla1.0.1+ for checkin to 1.0.1 per the ADT and Drivers.

Let's set up a tracking bug for any issues that come up and then announce this
change and direct people to this tracking bug so they can update it with any
issues they are seeing.
Comment 204 Chris Waterson 2002-06-05 17:12:15 PDT
Created attachment 86515 [details] [diff] [review]
patch for the branch

This is a patch for the MOZILLA_1_0_BRANCH. It incorporates the dependent bug
fixes, as well.
Comment 205 scottputterman 2002-06-07 13:49:41 PDT
Chris, is the patch different from the one that landed on the trunk or is it
just all of the patches merged together.  If it's different, does it need a review?
Comment 206 David Baron :dbaron: ⌚️UTC-10 2002-06-07 17:12:26 PDT
Changes landed on MOZILLA_1_0_BRANCH.
Comment 207 Jaime Rodriguez, Jr. 2002-06-10 09:22:23 PDT
stummala - can you pls verify the fix on the branch? thanks!
Comment 208 Prashant Desale 2002-06-11 12:40:46 PDT
I'm covering for stummala since he is on leave.

I performed lots of tests on branch & IE6 for direct comparison & looking at
results I think I will have to re-open this bug & mark it fixed [Removing
Verified]  so it does not go out of our watch radar.

I'm going to attach my results table.
Comment 209 Prashant Desale 2002-06-11 12:43:27 PDT
Marking it Fixed [Removing verified to keep it on watch list]
Comment 210 Prashant Desale 2002-06-11 12:48:42 PDT
Created attachment 87245 [details]
Comparison Test Results between Branch & Other Browser.

Test results are attached of multiple tests I performed. Test results are
direct comparison of branch & The Other Browser.
Comment 211 Prashant Desale 2002-06-12 14:18:46 PDT
Created attachment 87424 [details]
Comparison Test Results between Branch & The Other Browser.

Markus Hubner sent me some more test links, so I performed those tests as well
for direct comparison between two browsers. Attached are results.
Comment 212 Markus Hübner 2002-06-13 09:50:57 PDT
Those numbers in the results file will be considerably improved using a current
trunk build - great improvements through bug 124685, bug 141786, bug 85595.
Prashant, could you please add tests with a current trunk to your results.
Comment 213 Jaime Rodriguez, Jr. 2002-06-17 08:36:01 PDT
stummala - can you pls verify this one on the 1.0 branch (also check around for
possible regressions), then replace "fixed1.0.1" with "verified1.0.1"? thanks!
Comment 214 Prashant Desale 2002-06-17 11:58:24 PDT
Jaime Rodriguez, As I mentioned earlier I'm covering this bug for "stummala"
since he is on leave. I attached testing comparison table to the bug & our
branch is not really performing as expected. I re-opened this bug & marked it
fixed to keep it on radar.
It is really tough to decide if we really want to replace "fixed1.0.1" with
"verified1.0.1" since branch is not performing greatly compared to other
browser. Please check my last attachment for comparison test results. 
Comment 215 Stuart Ballard 2002-06-17 13:32:19 PDT
Desale, surely you should be comparing to prior versions of *this* browser (ie,
prior to this fix) to see if there's a substantial improvement. If this fix has
resulted in vast performance increases but we still don't quite beat IE, I'd say
that's plenty to mark this bug verified. After all, this bug is "Reflow
coalescing within JS called from SetTimeout" not "Be faster than IE on all DHTML
testcases".

If we have a crasher bug, we don't test for it to be fixed by looking to see if
we crash more often than IE or not, and we don't refuse to verify any crasher
bug if our MTBF is worse than IE. Each bug has to be evaluated on its own merits.

Test builds with this fix against builds without it, and if the builds with it
are substantially faster and have no regressions, this bug can be marked verified.
Comment 216 Prashant Desale 2002-06-17 17:35:30 PDT
Created attachment 88042 [details]
Comparison Testing Results amoung 3 different Browser builds & The Other Browser.

Stuart, what you said is correct & we should be comparing browser with prior
versions of browser , but evaluating performance is not either BLACK or WHITE
thing as it is in other bugs right ? If there is some crash, we can say it is
fixed if there is no crash any more. In case of performance, there is no such
sound result & we should be defining our level of satisfaction with
performance.
You really have a point that we should compare versions before check in & after
check in. Hence I did it now. I'm also including results on trunk, which are
better than branch.
Here is attached comparison testing results table.
Comment 217 Prashant Desale 2002-06-17 17:46:00 PDT
replacing "fixed1.0.1" with "verified1.0.1" since branch comparison showed lot
of improvement. Trunk was best of all three.
Adding hong@netscape to cc list since hong's team have good resources to perform
performance testing. hong please check out my results comparison & perform your
set of testing, & please take appropriate action on this bug. 
Comment 218 Jaime Rodriguez, Jr. 2002-06-19 10:35:45 PDT
Marking as Verified per Comment #217 From Prashant Desale.
Comment 219 m_mozilla 2002-08-31 11:58:44 PDT
*** Bug 128901 has been marked as a duplicate of this bug. ***

Note You need to log in before you can comment on or make changes to this bug.