Closed Bug 96108 Opened 23 years ago Closed 17 years ago

Make nsVoidArray::ElementAt() inline (plus a few others)

Categories

(Core :: XPCOM, defect, P3)

Product:
Core
Component:
XPCOM
Type:
defect

Tracking

()

Status:
RESOLVED FIXED

People

(Reporter: jesup, Unassigned)

References

(Blocks 1 open bug)

Details

(Keywords: perf)

Attachments

(6 files, 11 obsolete files)

Patch as checked in
(deleted), patch
Details | Diff | Splinter Review
offhand were you using viewer?
(deleted), patch
john
: review+
Details | Diff | Splinter Review
fix to nsTimerImpl.cpp
(deleted), patch
timeless
: review+
Details | Diff | Splinter Review
Same as above but should be a bit faster.
(deleted), patch
pavlov
: review+
brendan
: superreview+
Details | Diff | Splinter Review
add FastElementAt, make nsCOMArray use it, make nsVoidArray::ElementAt safe again
(deleted), patch
darin.moz
: review+
Details | Diff | Splinter Review
Warning clean-up in nsArray.cpp, use FastElementAt (through ObjectAt) in nsCOMArray_base::IndexOfObject, do some clean-up.
(deleted), patch
Details | Diff | Splinter Review 
We should inline nsVoidArray::ElementAt(index) like this in the .h file. 
ElementAt is quite small and would cause minimal to no code bloat.

  inline void* nsVoidArray::ElementAt(PRInt32 aIndex) const {
    if (aIndex < 0 || aIndex >= Count())
    {
      return nsnull;
    }
    return mImpl->mArray[aIndex];
  }

Ditto for nsSupportsArray:

  inline NS_IMETHOD_(nsISupports*) ElementAt(PRUint32 aIndex) {
    if (aIndex < 0 || aIndex >= mCount)
      return nsnull;
    nsISupports*  element = mArray[aIndex];
    NS_ADDREF(element);
    return element;
  }

and IndexOf:

  inline NS_IMETHOD_(PRInt32) IndexOf(const nsISupports* aPossibleElement) {
    return IndexOfStartingAt(aPossibleElement, 0);
  }

Also add a couple of out-of-bound index checks.
Status: NEW → ASSIGNED
Keywords: patch, perf
Priority: -- → P3
Target Milestone: --- → mozilla0.9.4
Attached patch Proposed patch (obsolete) (deleted) — — Splinter Review 

    
    

    
  
Looking for r=/sr=.  My only question would be should nsSupportsArray::ElementAt
(and IndexOf) be const (I think they can be, should they?)

    
    

    
  
Could you please verify that this does not cause an appreciable change in code
size? In theory, I agree that it shouldn't; however, here is the code that
gcc-2.96 generates for nsVoidArray::ElementAt() with ``-O'':

00000404 <ElementAt__C11nsVoidArrayi>:
     404:	55                   	push   %ebp
     405:	89 e5                	mov    %esp,%ebp
     407:	8b 55 08             	mov    0x8(%ebp),%edx
     40a:	8b 4d 0c             	mov    0xc(%ebp),%ecx
     40d:	85 c9                	test   %ecx,%ecx
     40f:	78 18                	js     429 <ElementAt__C11nsVoidArrayi+0x25>
     411:	83 3a 00             	cmpl   $0x0,(%edx)
     414:	74 0a                	je     420 <ElementAt__C11nsVoidArrayi+0x1c>
     416:	8b 02                	mov    (%edx),%eax
     418:	8b 40 04             	mov    0x4(%eax),%eax
     41b:	eb 08                	jmp    425 <ElementAt__C11nsVoidArrayi+0x21>
     41d:	8d 76 00             	lea    0x0(%esi),%esi
     420:	b8 00 00 00 00       	mov    $0x0,%eax
     425:	39 c1                	cmp    %eax,%ecx
     427:	7c 07                	jl     430 <ElementAt__C11nsVoidArrayi+0x2c>
     429:	b8 00 00 00 00       	mov    $0x0,%eax
     42e:	eb 08                	jmp    438 <ElementAt__C11nsVoidArrayi+0x34>
     430:	8b 02                	mov    (%edx),%eax
     432:	83 c0 08             	add    $0x8,%eax
     435:	8b 04 88             	mov    (%eax,%ecx,4),%eax
     438:	5d                   	pop    %ebp
     439:	c3                   	ret    
     43a:	89 f6                	mov    %esi,%esi

That's 22 instructions (54 bytes worth). Granted, we ought lose the four
instructions for the stack frame (5 bytes worth), but that's still 49 bytes of
code, vis a vis two pushes, a call, and a pop (ten bytes).

I'm not convinced that gcc does a very good job inlining (see, for example, the
discussion on |copy_string()| in n.p.m.performance.

    
    

    
  
Also, N.B. that NS_IMETHOD expands to ``virtual'', yielding ``inline virtual''
on nsSupportsArray. That rather seems like an oxymoron, and I suspect that the
compiler will ignore the inline altogether.

    
    

    
  
waterson: But it also has the advantage that nsVoidArray::ElementAt could in
some cases (eg where the compiler can prove that aIndex is in range, such as
when this is used in a loop) turn this function into a simple addition + pointer
dereference (assuming Count() is inline; I haven't checked)

    
    

    
  
bbaetz: Sure it could. Does it? Or does it just bloat the code by 4x at each
callsite? If the latter, then I suggest we hold off on doing this until compiler
technology catches up.

I'm just asking for a little due dilligence, man! ;-)

    
    

    
  
If it expands that much, waterson may be right here (though the IndexOf one
should be ok).  I'll look at some other cases in assembler (with and without
inline) and see.  I'll also size some modules.

    
    

    
  
nsISupportsArray::ElementAt should be deprecated -- it's too easy to leak if you
forget to use getter_AddRefs or dont_AddRef.  There was talk of making it return
an already_AddRefed<T> -- cc'ing dbaron.

/be

    
    

    
  
I have figures from Linux RH 7.1 GCC 2.96, -O2
The sizes are from the Unix 'size' command.  Total is just under 24K bytes total
bloat.  The fact that we have negatives is interesting.

xpconnect: -50
necko: +350
uconv: +60
oji: +20
caps: -50
rdf: +900
htmlpars: -80
gfxps: +50
gfx_gtk: +100
gfxxprint: +100
imglib2: +200
gkplugin: -60
gkview: +900
gkcontent: +10000
gklayout: +4000
docshell: +300
txmgr: +200
editor: +450
txtsvc: +900
appshell: +340
appcomps +300
cookie: +700
wallet: +2500
xpcom: +600
gkgfx: +300

    
    

    
  
Okay, so what's the upside? IOW, why is this worth doing? Are there measurable
performance improvements?

    
    

    
  
24K may or may not be worth it.  ElementAt is used a LOT in timing-critical
functions (and in O(n) or worse functions - see some of the Find code).  Still,
it's fast, and doesn't take up much time in those, but we do get hits in my Find
test - in the flat table it was #35 or so in one, about #20 in another (circa 1%
in the jprofs I've looked at).  When a simple array lookup is taking 1% of the
execution time, it is a prime candidate for inlining.

Note that this inlined both nsSupportsArray::ElementAt and
nsVoidArray::ElementAt.  SupportsArray is more complex (NS_ADDREF, etc) and
doesn't usually show up in jprofs I've looked at (admittedly mostly Finds and a
few page loads).  I'm going to make a run of inlining only
nsVoidArray::ElementAt and see what the size difference is.

    
    

    
  
The size difference for nsVoidArray::ElementAt only is still ~23K (as per above,
nsSupportsArray probably can't be inlined).

I should note that this is a called a LOT (if it's 1% of execution, and the
actual code for ElementAt is trivial, then it's being called an immense number
of times).  Even a small number of cycles of savings would amount to a win.

23K is 0.089% (less than 1/100th of a percent) of the size of mozilla (from the
same 'size' run the size of all .so's is 26050208 bytes).

I'm still not sure, but I think there is an argument for inlining it.


    
    

    
  
Bumping out to 0.9.5; this needs more evaluation
Target Milestone: mozilla0.9.4 → mozilla0.9.5
Target Milestone: mozilla0.9.5 → mozilla0.9.6

    
    

    
  
*** Bug 104325 has been marked as a duplicate of this bug. ***

    
    

    
  
Comment on attachment 46466 [details] [diff] [review]
Proposed patch

The current proposed patch is on the bug just dup'd to this.  My previous work showed that bloat is minimal (though non-zero), and Chris' patch should make it considerably less.  I worry however that we may miss some cases where something is relying on ElementAt(-1) == nsnull (or 1 past the end).  I found several when testing my version of this patch a while back and fixed a few.

        Attachment #46466 -
        Attachment is obsolete: true

    
    

    
  
Harumph.  Adding comments in the attachment-edit page leaves them
non-wrapable...  Repeated for clarity.

The current proposed patch is on the bug just dup'd to this.  My previous work
showed that bloat is minimal (though non-zero), and Chris' patch should make it
considerably less.  I worry however that we may miss some cases where something
is relying on ElementAt(-1) == nsnull (or 1 past the end).  I found several when
testing my version of this patch a while back and fixed a few.

    
    

    
  
Argh! So let's get this done. Let's use attachment 53251 [details] [diff] [review] as a starting point and
proceed to clean up all callers that assume and out-of-bounds reference will
return null. rjesup: are you going to do this for mozilla-0.9.6? If not, please
reassign to me. This will have to go in sooner rather than latern (next week) so
that we can feel safe that we've caught all the callers.

    
    

    
  
I plan to post a patch for review (based on Chris's) Monday or Tuesday, barring
problems.  I'm happy to incorporate bounds-checking fixes anyone can find in the
meantime.

    
    

    
  
Marking this as a dependency for the page load bug, per the fact that bug 104325
reports ~2% speedup. (I'd really like some confirmation on that fact, though!)
Blocks: 71668

    
  
Blocks: deCOM

    
    

    
  
rjesup, how is this coming?

    
    

    
  
I should have an update today.  I'm also working on cleanup up some usages of
ElementAt (negative indexes) as part of bug 100231.


    
    

    
  
Update: I'm still working on this.  There were a fair number of -1 references;
I've eliminated quite a few, but I'm sure there are more (probably in MailNews).
 Initial release of this will need to include the aIndex < 0 test; if people are
in agreement we should disallow negative indexes I'll include an assertion so we
can track down and kill the remaining negative indexes (and at some point remove
the test).  Alternatively we can leave the aIndex < 0 test forever and simply
allow the behaviour.

What do people think about the aIndex > mCount test?  Obviously, removing it
would improve performance, but I image even more parts of the system depend on
that returning nsnull.


    
    

    
  
I think we should remove both tests to optimize for the usual case.  We can
start by fixing the ones that are hit often and putting in an assertion along
with the check.

    
    

    
  
Ok, I'll give that a try.  I'll post a preliminary patch a little later with
asserts turned on and the worst offenders fixed.

    
    

    
  
You can combine tests using unsigned two's complement arithmetic.  Instead of this:

+    if (aIndex < 0 || aIndex >= Count())
+    {
+      return nsnull;
+    }
+    return mImpl->mArray[aIndex];

do this:

+    if (PRUint32(aIndex) >= PRUint32(Count()))
+    {
+      return nsnull;
+    }
+    return mImpl->mArray[aIndex];

I agree that we should assert and root out all out-of-bounds accesses (or else
purvey a new inline method, FastElementAt).

/be

    
    

    
  
Yeah, I suppose you can lean on the C++ spec for conversions that way.  Rather
freaky, though - I'd comment the heck out of it.

I'll run through and see what I get.  If a few are hard to fix, we could add
ElementAtBounded() and make them use that.  The danger is if one is missed we
can blow up.  Upside is that we don't have to make mods to a zillion files.

    
    

    
  
Not freaky, I do it all the time (ok, so I'm a freak :-).  Two's complement -1
is well-known to be UINT_MAX.

/be

    
    

    
  
Oh come _on_, you sissies! ;-)

If we assert botch, we'll never be brave enough to cut over. Do it now: we have
at least three weeks to root out the most serious problems. Add a
BoundsCheckedElementAt() method (good idea, randall!) as Rx for slackers who
can't figure out how to fix their code. 

    
    

    
  
We have three weeks?  Oh good, I stand a chance of fixing my 0.9.6 bugs!  I'm
all for cutting over ASAP.

/be

    
    

    
  
Ok - I'll upload a patch for review today with whatever fixed I can.  (I was
fighting a bad algorithm for insertion-sort in XULSortService last night which
causes lots of past-the-end references).

    
    

    
  
The biggest offender on going past the end of an array are uses of ChildAt(). 
Given the number of files (90) that reference it, I'm going to punt on that one
for now and add an aIndex < mChildren.Count() test to ChildAt(). Maybe I'll hit
that on a second pass.

    
    

    
  
Did you start from my patch in the other bug? I fixed those.

    
    

    
  
Yes (actually I used yours for reference; my version has some slight differences
in how I fixed those specific cases - minor efficiency/etc differences).  I
haven't yet found a case where I needed to fix nsGenericHTMLElement::ChildAt to
bounds-check, but I won't be surprised (I'm pretty sure it would be hit during
Find).  ChildAt doesn't seem to need checks for [-1] (every case of negative
indexes I've found I fixed).

I found dozens more places that go past ends of arrays, though.  Events, timers,
imageframe, XULSortService, etc.  Right now I'm working on the timer code, which
turns out to be somewhat broken.



    
    

    
  
Things that popped out while looking into references past the end of arrays:

Cute one in timer_gtk: we would check the same timer more than once (or even
miss firing timeouts if timers were added).  FireTimeout()  can add or remove
timers, but the code that walks the list doesn't check or care if the list was
modified.

Found a nasty little bug in nsSelectionState with a backwards test (filed a new
bug for that one); this might have been causing SaveSelection() to save too much.

    
    

    
  
Okay, you're a star for doing this. Thanks!

    
    

    
  
Grr.  I wish bugzilla would wrap those.

I have to go home and am still recompiling, but this should be good.  I've
browsed to a lot of sites with this with no assertions.  I assert on negative 
indexes, and on past-end I assert and (for now) I return nsnull still.

Tomorrow I plan to try it with mail/news,etc.  Anyone willing to try it is
welcome (for example, I can't build on Win32); pageload perf tests (with the
extra test for past-end removed and optimize (=-O2 especially) would be great.


    
    

    
  
I should note that the nsSmallVoidArray patches for bug 100231 are in that patch
as well; I can separate them when we're ready for review, or we can put them in
together.


    
    

    
  
I almost have a more complete patch ready, with a bunch of mailnews/editor fixes
in.

I found that nsISupportsArray.idl doesn't define any way to find the length of
the array... :-(

Updated patch to be submitted tomorrow morning probably.

I assume people are still in approval of removing error-checking from the
default ElementAt() code (which will be inlined).  I plan to add a
bounds-checked version for code that would have to check bounds anyways.

Also realize that my testing will almost certainly miss some instances,
especially where they may be called indirectly from JS code, or in unusual code
paths or platform-specific code I can't test.  A safer alternative would be to
bite the bullet and leave ElementAt as-is, and change all known safe references
over to an (inlined) FastElementAt().  The downside of this is that that's a LOT
of files to change, and people will still use the slow ElementAt and design
their loops for it.

Actually, things are now working quite well, even in mailnews.  I haven't tried
composer, but I have done some writing messages in mailnews.

    
    

    
  
> I found that nsISupportsArray.idl doesn't define any way to find the length of
> the array... :-(

nsICollection.idl defines |PRUint32 Count()|, and nsISupportsArray inherits from
nsICollection.

    
    

    
  
Wait, we're not talking about doing unchecked references from callers of
nsISupportsArray (with which we couldn't inline these methods anyway -- it's an
interface). Are we?

    
    

    
  
Hmmm.  I'll check, but the compiler was telling me it didn't support Count() in
an nsISupportsArray*.  (nsISupportsArray *foo = bar;  if (foo->Count()) ....
caused a compiler error, or so I remember.)  Just more fallout of the weirdness
that nsISupportsArray and nsVoidArray don't share anything, even an interface.  :-(

As for whether we should be doing things for nsSupportsArray - I hadn't intended
to; I simply was noticing that (similar to nsVoidArray) there was code written
that made the same assumptions about out-of-bounds array indexes.  If we're
changing nsVoidArray::ElementAt to not allow out-of-bounds access, we really
should do the same for nsSupportsArray if we don't want to confuse people with
dueling interface definitions.  (And this will also make it easier to eventually
make nsVoidArray and nsSupportsArray actually share code, though that's a minor
point.)




    
    

    
  
We must maintain bounds checking on nsISupportsArray. It can be accessed from
script. Ensuring that nsISupportsArray and nsVoidArray have identical semantics
seems like a non-goal to me.

    
    

    
  
I have no problems with bounds-checking on scripted nsSupportsArray references,
or for that matter any nsSupportsArray reference.  You'll note that this patch
doesn't include nsSupportsArray.  I mentioned it because I accidentally tried to
change an nsSupportsArray loop to use Count() and work like an nsVoidArray loop
and got bitten.

The reason for discussing differences in interfaces is because having EXTREMELY
similar interfaces (which is fact are very hard to tell apart when looking at
users of them) that have subtle semantic differences is dangerous.  It invites
misuse by mistake.  For example:

If you have an array with 3 elements in it ([0] to [2]), and do
nsVoidArray::ReplaceElementAt(myElement,12) it will implicitly add elements 3 to
11 (as nsnulls) and put myElement at 12.  (This behavior is used in the Event
handling arrays, for example.)

If you try that with nsSupportsArray::ReplaceElementAt(), it will not implicitly
add elements 3 to 11, and in fact it will fail the call.  Not only that, but it
won't even extend the array by 1 if you used
nsSupportsArray::ReplaceElementAt(myElement,3).  You can only expand
nsSupportsArrays with AppendElement(myElement), AppendElements(myArray) or
InsertElementAt(myElement,3).

To the user, however, the usage of an nsSupportsArray and an nsVoidArray look
almost identical, and the semantics of _almost_ all the calls are similar. 
There are just enough differences to be dangerous.

In a perfect world, both of them would support checked and unchecked references
with similar semantics (outside of the implicit addref of nsSupportsArray), and
in fact nsSupportsArray would be built on top of nsVoidArray (it almost could be
now if it were not for a few of those semantic issues - it still could be by
adding code to implement the semantic differences).  Perhaps only the
bounds-checked version of ElementAt in nsSupportsArray would be scriptable,
though.

    
    

    
  
My apologies, people got sidetracked into the nsSupportsArray discussion because
of my side-comment about Count(), and I got sucked into it.  Please take any
such discussion to bug 100231.

Still targetting getting this in ASAP.

    
    

    
  
Ok.  I've hit mailnews quite a bit, composer, etc.  I haven't touched chatzilla
or java or plugins.  At this point, things work very well.

I REALLY would like people to a) review this code, and b) try it, especially if
someone has a pageload or other such harness to see what perf improvement this
gets us with debug off and optimize on (-O or -O2).  It still has assertions for
past-end and negative references in debug mode, but only returns nsnull for
past-end refs.  Negative references WILL cause misbehavior and/or crashes.

I have not checked every ElementAt call; there are >200 files with them.

I have not added a bounds-checked call yet.  I can do so (and still plan to,
since I imagine I'll need to make some changes after people look at this), but
it doesn't solve any compatibility issues until we find cases that needs it.

BTW, if you going to use this you MUST also use the patch for 107600
(nsContentIterator problems with indexes).
Depends on: 107600
Depends on: 107831

    
    

    
  
blocker bug 107831 is a two-liner mis-use of array indexes when removing
elements; this might have caused a bug in PICS.  Patch ready for review
(trivial).

    
    

    
  
Just an update.  I'm continuing to go through every LXR reference to ElementAt
and check them.  I'm over 1/2 way through, and found a bunch more spots that
need bounds-checking.

    
    

    
  
Please try this, report any assertions, and/or review the patch.  I want this to
go in first thing for the 0.9.7 build to give it time to shake out.  Thanks.
Target Milestone: mozilla0.9.6 → mozilla0.9.7

    
    

    
  
My apologies, that patch had a last-second typo ("NS_STATIC_CASE" instead of
CAST).  I'll upload a corrected one.

Other than making ElementAt inlinable, the changes in the patch are:
1) changes to eliminate negative array indexes
2) addition of code to check for past-end  array indexes, or conversion of
   ElementAt to SafeElementAt
3) adding checks to things that use ElementAt internally like uses of GetShellAt
4) moving RemoveElementAt() outside of loops and changing it to Clear()
5) adding assertions and comments
6) rewrite some confused algorithms, particularly in TimerGtk/Xlib, and 
   XULSortService
7) changing some while() loops to for() loops
8) adding error cases
9) fixed serious indentation problems in nsXULControllers.cpp
10) moved nsCheapVoidArray into xpcom and renamed nsSmallVoidArray (this was
    bug 100231, but has been subsumed by this patch on people's agreement).
    nsSmallVoidArray now supports all nsVoidArray methods.
11) some cleanup of array usage in mailnews (RemoveElementAt instead of 
    RemoveElement, etc.
12) limit growth of an nsVoidArray to 1024 elements (4096 bytes, 1 page on most 
    machines) instead of doubling forever, to minimize bloat.  This is a tuning
    parameter - I'm willing to entertain requests to make it 2 or 4 pages, or
    to remove this and let it grow by powers of two.  (very few arrays get over
    a few thousand elements)
13) Fixed a couple of Mode lines


        Attachment #56631 -
        Attachment is obsolete: true

        Attachment #56371 -
        Attachment is obsolete: true

        Attachment #55813 -
        Attachment is obsolete: true

        Attachment #55000 -
        Attachment is obsolete: true

    
    

    
  
Argh! Well, I have bad news to bear. I've applied the patch (mangled a bit to
get to compile on Win32), and I'm not seeing any difference on jrgm's page load
tests. I've run two cycles each of ten iterations (one uncached, nine cached).

(BEFORE)

Test id: 3BE7AB3F3E
Avg. Median : 892 msec		Minimum     : 318 msec
Average     : 919 msec		Maximum     : 2990 msec

<http://cowtools.mcom.com/page-loader/graph.pl?id=3BE7AB3F3E>

See Notes at the bottom of this page for some details.

Test id: 3BE7AF3D33
Avg. Median : 892 msec		Minimum     : 315 msec
Average     : 921 msec		Maximum     : 3006 msec

<http://cowtools.mcom.com/page-loader/graph.pl?id=3BE7AF3D33>


(AFTER)

Test id: 3BE7A725E2
Avg. Median : 893 msec		Minimum     : 311 msec
Average     : 920 msec		Maximum     : 3075 msec

<http://cowtools.mcom.com/page-loader/graph.pl?id=3BE7A725E2>

See Notes at the bottom of this page for some details.

Test id: 3BE7AF3D33
Avg. Median : 892 msec		Minimum     : 315 msec
Average     : 921 msec		Maximum     : 3006 msec

<http://cowtools.mcom.com/page-loader/graph.pl?id=3BE7AF3D33>

I'll keep digging on this. But it's certainly possible that I was overzealous in
proclaiming a 2-3% improvement in bug 104325.


    
    

    
  
I can't say I'm totally surprised.  None of my jprofs of all sorts of different
things ever showed more than 1% ElementAt and most lower - but on the other hand
I don't have access to a pageload jprof, and most of my tests were of a specific
issue with a specific site (usually one that was eating a lot of time in places
we'd rather it not).

Certainly there are good things to come from this work even if we don't get 2%
perf.  We will save a bunch of cycles (it gets called a LOT).  A lot of code was
misusing arrays, and negative indexes aren't really a good thing IMHO.  I found
some annoying bugs in some of the algorithms too (timers, XULSortService for
example).

Unfortunately, some of the hot-spot users are people like ContentIterator, which
works with ChildAt, which is still error-checked.  (Though in this work I found
and fixed a nasty little bug in jfrancis' rewrite of my patch.)

I wish jrgm would get that jprof of an entire pageload cycle up...


    
    

    
  
BTW, I can't access cowtools, of course.
Depends on: 105783

    
    

    
  
Looking at dbaron's page-load jprof:

There are 55 nsVoidArray::ElementAt hits out of 14000 (realtime) hits.

This matches waterson's commentary - it's not a real problem, less that 1/2%.  I
have seen jprofs of specific cases that have it in the 1% or higher range, but
those don't seem to be the norm for regular pageload (you can get higher numbers
for things like Find in large pages and some content-insertion cases).

As I see it we can:
(ignoring the issues from bug 100231 (move nsCheapVoidArray into xpcom)

1. Commit this and take the minor win.  There is some risk, though I have looked
at _every_ ElementAt call and most indirect calls (GetShellAt, etc), and we have
NS_ASSERTIONs to catch this in debug.
2. Commit this with bounds-checks for negative and past-end left in for opt
builds (i.e. a bug in array code will NOT crash it) but leave the asserts in.
3. Commit this with bounds-checks for negative and past-end left in for opt
builds (i.e. a bug in array code will NOT crash it) and remove the asserts (i.e.
as now with inlining -- no need for SafeElementAt).
4. Commit just the clean-up portions of this (Clear() over loops of
RemoveElementAt(), algorithm fixes, setting up loops more correctly, etc) and
leave bounds-checking and inlining as per today.


    
    

    
  

      
      
      
      

        Attached patch
          
          
        same as above, with some nits picked inline (obsolete) (deleted)
        — 
          — Splinter Review
      

    


  
This patch is mostly the same as the previous, modified to compile on Win32. I
also:

1. Went all the way and removed non-debug checking from ElementAt.
2. Removed nsVoidArray:: qualification inside the class
3. Cleaned up random style vandalism
4. Fixed some places where you'd modified nsSupportsArray callers (which
   doesn't have a SafeElementAt).

I'm about half-way through reviewing your patch, but in general it looks fine.
I'll file a parallel bugscape bug to do similar cleanup in the commercial tree
(took a quick look -- probably an hour or two's worth of work there).

I'm not going to mark this as obsoleting attachment 56713 [details] [diff] [review], just because I'd
like you to be happy with the changes, rjesup.

    
    

    
  
Overall your mods to the patch look fine.  Comments:

A few checks for GetShellAt(0,...) returning nsnull were removed in
nsDocument.cpp::DispatchEvent() and ::CreateEvent().  GetShellAt() uses
SafeElementAt(); is it absolutely guaranteed that GetShellAt(0,...)
will return a pointer?

Why were the changes to widget/src/photon/nsMenuBar.cpp removed?  (not that
they're important changes).

Everything else seems fine.

I would like opinions on which of the alternatives we're going to take.  It
appears that Chris (waterson) is in favor of commiting the entire patch.  Anyone
else?

    
    

    
  
FYI, the patch does cause a regression in form submission - single-line text
widgets with a separate submit button appends %0D%0A to the string for
submission.  I suspect something, perhaps DocumentEncoder or Range (the forms
and editor code looks clean by eye).

URL for the regression is www.comcastonline.com; type a zip code and hit return.
(You can use 18940 - it should say you can get service; instead it says you
can't).

FYI, I noticed on single-line insertion we add &x=0&y=0 if you hit return in the
text box, while ns4.7 didn't.  (Those are for the submit button.)  I suppose it
makes sense though I worry slightly about compatibility if IE also suppressed
the &x=0&y=0.


    
    

    
  
Found the regression, it's in nsDocumentEncoder.cpp.  The first hunk should be
"if (start >= 0 &&" and "if (end >= 0 &&" instead of both being "> 0".

I'll post an updated patch based on waterson's with my nits with his nits
addressed.

Reviews?  Decision on which of the options we should go with?


    
    

    
  

      
      
      
      

        Attached patch
          
          
        Updated patch, ready for review (obsolete) (deleted)
        — 
          — Splinter Review
      

    


  
Updated waterson's patch for the regression fix; also re-added the checks for
GetShellAt(0,...) returning nsnull in nsDocument.cpp (paranoia).

        Attachment #56713 -
        Attachment is obsolete: true

        Attachment #57428 -
        Attachment is obsolete: true

    
    

    
  
Ok, we need to get off the fence here.

I'm continuing to keep the patch from rotting in my local trees.  We either need
to commit this or drop it and just check in a few usage cleanups I found along
the way.  Last we visited the issue, the performance improvement is marginal to
nil for most usages (pageload, etc).  In some specific really-big-whatever cases
it may make a difference (cases where we're tightly looping on some aspect of
Find, or large pages, etc).  So the remaining issues are cleanness of design (at
the cost of more methods/code), some advantage in edge performance cases, and
general cleanup that came from looking at every use of ElementAt.

I'm tempted to just check in the usage cleanups.  If so, should we remove the
asserts (and remove code that stopped us from trying to go past the end of
arrays), or leave the asserts in and the code that avoids tripping the asserts?


    
    

    
  
Who's on the fence here?  I'd be surprised if this doesn't make some measurable
performance difference on btek, which is a good bit more sensitive than other
machines due to its setup.  I'm for getting the whole thing in.

    
    

    
  
Well, I've seen no comment from anyone since other than waterson since I laid
out the fact that this is not a measurable performance win so far as I can tell,
and no response from him since I incorporated his suggestions.

I'm more than willing to check it in if people will review it; however I've
never had a jprof where ElementAt used more than 1% (and in fact I think all my
tests were below .8%, with your (dbaron's) full pageload jprof showing it as
<0.5%).  We do pay some penalty for yet more slightly-variant interfaces and the
chance someone will mis-use the interface and not catch it in testing.

The only jprofs I have that are above 0.5% are mostly searching very large pages
(viewsource pages).

Note that the perf gain from this change will be less than the listed 0.5%, of
course.  If a perf gain of (say) 0.1-0.3% (0.5% best-case) gain is worth this,
then fine, let's review it and get it in.  If not, I'll post a usage-cleanup
patch, we can review that, and get it in.


    
    

    
  
I would like it to go in for the footprint. Right now it will cost me a couple
of 100 bytes in code to replace some static arrays with a dynamic nsVoidArray.
Making elementAt and Count inline should cut most of that away I hope. 

If having elementAt inline means a footprint win and a performance win, however
small, it's obviously the right thing to do given the priorities now when most
of the work is done. It would also be nice to get it in as soon as possible to
get some time before the milestone release to find any uncovered bugs.

    
    

    
  
Daniel - I doubt there's a footprint win here.  If we're lucky, it's pretty much
a wash footprint-wise.  (Before removing bounds-checking from ElementAt, it was
a footprint loss, though only about 24K across all of mozilla.)

    
    

    
  
sr=waterson. Bring it.

    
    

    
  
I'm double-checking my build for bit-rot (I've been updating it daily).  We have
sr=waterson, anyone willing to r=?

    
    

    
  
- Looks like the patch would not deal well with null values in
nsSmallVoidArray's, seems like that would be something we should fix while we're
at it.

- In nsFontMetricsGTK.cpp:

+      name.Assign("font.scale.outline.min.");
+      name.Append(langGroup);

This should use name.Assign(NS_LITERAL_CSTRING("...") + langGroup) to avoid
multiple string copies and potentially multiple allocations. There's a few cases
of similar code in the same file.

- The nsPresShell.cpp changes don't look really safe to me, what if a call to
ReflowCommandRemoved() ends up queueing more feflow commands, then the changes
cause those reflow commands to be lost. I don't know if this can happen in
todays code, but we should at least add an NS_ASSERTION() that would detect that
if we make this change.

- nsMsgHdr.cpp, messed up indentation. There's lots of this in the patch, too
much to mention, but most of it is due to bad indentation to start with, so it's
not your responsibility to fix all of it. In hope that the owners of the messed
up code would start cleaning up their mess I'm even a little bit glad of you're
messing up the already messed up indentation some more :-) No offence indented.

- In nsSmallVoidArray::InsertElementAt():

+      if (0 == aIndex)
+      {
+        SetSingleChild(aElement);
+        return PR_TRUE;
+      }
+      else
+      {
+        return PR_FALSE;
+      }

"else after return", loose the else. Same thing in
nsSmallVoidArray::ReplaceElementAt()

Nits of the day:

- In nsXULElement.cpp:

+    nsIContent* content = NS_STATIC_CAST(nsIContent*,
mChildren.SafeElementAt(aIndex));
+    NS_IF_ADDREF(content);
+    aResult = content;

Assign first, then addref the out parameter, addref'ing the temporary is not
what you mean to do here, even though it does the right thing.

- In nsXULDocument.cpp (line ~4560):

+    nsCOMPtr<nsIEventStateManager> esm;
+    if (presContext &&
+        NS_SUCCEEDED(presContext->GetEventStateManager(getter_AddRefs(esm)))) {
+        return esm->DispatchNewEvent(NS_STATIC_CAST(nsIDocument*, this),
aEvent, _retval);
+    }

stick to either two or four space indentation here, don't mix them, at least not
within a function.

If you have a look at the above, r/sr=jst

    
    

    
  
Thanks JST (and waterson); I'm revising for your comments and preparing for
checkin.

    
    

    
  
*** Bug 116036 has been marked as a duplicate of this bug. ***

    
    

    
  
All of JST's minor nits were addressed.  His more major nits:

>- nsMsgHdr.cpp, messed up indentation. There's lots of this in the patch, too
much to mention, but most of it is due to bad indentation to start with, so it's
not your responsibility to fix all of it. In hope that the owners of the messed
up code would start cleaning up their mess I'm even a little bit glad of you're
messing up the already messed up indentation some more :-) No offence indented.

My patch shouldn't mess it up; I use spaces for indentation and obey the
tab-width & c-basic-offset values at the top (if you're not using Emacs or
something that obeys tab-width, it may look really bad since the file is full of
tabs).  The base problem is that it has tabs in it.

>- The nsPresShell.cpp changes don't look really safe to me, what if a call to
ReflowCommandRemoved() ends up queueing more feflow commands, then the changes
cause those reflow commands to be lost. I don't know if this can happen in
todays code, but we should at least add an NS_ASSERTION() that would detect that
if we make this change.

Added assertions, though I think that would be a Very Bad thing to do - these
Clear()s are in CancelAllReflowCommands(); I'd argue that new reflows inserted
by the cancelling would be bugs - and thus the NS_ASSERTION()s.

>- In nsFontMetricsGTK.cpp:
+      name.Assign("font.scale.outline.min.");
+      name.Append(langGroup);
This should use name.Assign(NS_LITERAL_CSTRING("...") + langGroup) to avoid
multiple string copies and potentially multiple allocations. There's a few cases
of similar code in the same file.

I removed that code and simplified the changes to that file; that wasn't really
supposed to be part of this patch; it just snuck in.

>- Looks like the patch would not deal well with null values in
nsSmallVoidArray's, seems like that would be something we should fix while we're
at it.

nsSmallVoidArray is pretty special purpose; only works for pointers (that don't
have a lowest bit 1 set), and yes it has an assumption about entries being
non-null.  This already existed as part of nsCheapVoidArray, and to remove it
would require losing some of the (few) advantages of nsSmallVoidArray over an
nsVoidArray.  We'd have to keep a separate count or at least flag (still takes
space) to know if there was supposed to be a single null entry in it, or if it's
empty.  (Or we'd have to add more special-meaning values and tests for it all
over the nsSmallVoidArray code).  I'm leaving this alone for now, sorry.

As I have r/sr on this modulo the nits addressed above, I'll check in as soon as
I verify no last-second bitrot after the tree opened.  I'll also attach a final
patch for anyone who's interested (probably no one given it's length).

Thanks all!

Note that I've left a past-end check in nsVoidArray::ElementAt even in opt
builds for now.  That test will be removed later, before 0.9.8.  I want to
minimize the chance of crashing people right at checkin and making a blocker; it
should just assert and give us a chance to fix anything I missed.  I did not
leave a <0 check in; I really think I have them alln (again, it will assert).

    
    

    
  

      
      
      
      

        Attached patch
          
          
        Patch as checked in (deleted)
        — 
          — Splinter Review
      

    


  
Patch as checked in

        Attachment #57923 -
        Attachment is obsolete: true

    
    

    
  
Checked in.  Be very afraid.  :-)

Added a couple of assertions for JST as well.
Status: ASSIGNED → RESOLVED
Closed: 23 years ago
Resolution: --- → FIXED

    
    

    
  
I had a question about this change in nsIMAPBodyShell.cpp that was part of this
patch....

 while (Count() > 0)                                                         
 {
  nsIMAPMessagePartID *part = GetPart(0);
  delete part;
-  RemoveElementAt(0);
 }
+    Clear();

If we are no longer removing elements from the array, when will we exit this
while loop in order to call clear? 


    
    

    
  
I also don't understand this change to nsMsgBiffManager:

   if(pos != -1)
   {
     nsBiffEntry *biffEntry = (nsBiffEntry*)mBiffArray->ElementAt(pos);
-    mBiffArray->RemoveElementAt(pos);
     delete biffEntry;
   }
+  mBiffArray->Clear();

we went from code which was removing a single entry from mBiffArray to code
which appears to be clearing the array entirely. That doesn't seem to do what
the code was doing before or am I missing something.




    
    

    
  
mscott: thanks, fixed.

Now reads (ignore indentation, this is an evil file with tabs):

void nsIMAPMessagePartIDArray::RemoveAndFreeAll()
{
        int n = Count();
	for (int i = 0; i < n; i++)
	{
		nsIMAPMessagePartID *part = GetPart(i);
		delete part;
	}
        Clear();
}

As for Biff, you're correct, fixing.  I oopsed when checking every use of
ElementAt (and RemoveElementAt) in the entire tree; I shouldn't have hit that
one.

    
    

    
  
Thanks for fixing those. I have more too. btw, it's customary to ask for module
owner approval before checking into those modules. I'm a little concerned at the
quality of the review the mail code got by waterson and jst here. They should be
ashamed of themselves!

In addition to the first 2, here are a couple more:

1) nsMsgCopyService.cpp
   while(j-- > 0)
   {
       ncs = (nsCopySource*) m_copySourceArray.ElementAt(j);
-      m_copySourceArray.RemoveElementAt(j);
       delete ncs;
   }
 }

We used to remove the elemnt from the array after each iteration in the while
loop. Now we aren't doing anything. Shouldn't there at least be call to Clear()
at the end if you are going to remove the while loop?

2) In nsAddrDatabase.cpp
@@ -200,7 +200,6 @@
                {
                        void* pPtr = pArray->ElementAt(i);
                        PR_FREEIF(pPtr);
-                       pArray->RemoveElementAt(i);
                }
We are removing a removeElement call but not replacing it with a Clear call
outside of the loop. 

This is just after a quick glance at the mailnews changes. I'll try to go over
them in more detail with a more thorough review tonight. 

    
    

    
  
1) nsMsgCopyService.cpp
   while(j-- > 0)
   {
       ncs = (nsCopySource*) m_copySourceArray.ElementAt(j);
-      m_copySourceArray.RemoveElementAt(j);
       delete ncs;
   }
 }

>We used to remove the elemnt from the array after each iteration in the while
>loop. Now we aren't doing anything. Shouldn't there at least be call to Clear()
>at the end if you are going to remove the while loop?

This is in the destructor; m_copySourceArray will be destroyed anyways, so
nsVoidArray's destructor will handle that.

2) In nsAddrDatabase.cpp
@@ -200,7 +200,6 @@
                {
                        void* pPtr = pArray->ElementAt(i);
                        PR_FREEIF(pPtr);
-                       pArray->RemoveElementAt(i);
                }
>We are removing a removeElement call but not replacing it with a Clear call
>outside of the loop. 

That's followed by "delete pArray", so no Clear() is needed.

Thanks for checking so carefully!



    
    

    
  
One solution is to break patches up by modules (top-level directories, at least)
and solicit r= from the various owners or peers.  Let's try to do that, even
though the all-in-one patch is easier to wrangle.

/be

    
    

    
  
I hit the assertion "###!!! ASSERTION: nsVoidArray::ElementAt(negative index) -
note on bug 96108: 'aIndex >= 0', file nsVoidArry.h, line 77", coming from
http://lxr.mozilla.org/seamonkey/source/widget/src/mac/nsDynamicMDEF.cpp#465.
gPreviousMenuHandleStack.Count() is 0. I tried to open the View menu on my mac
build.
Blocks: 116413

    
    

    
  
I filed bug 116577 when I hit the assertion

    
    

    
  
bug 119843 nsAbView::GetCardFromRow
Blocks: 119843

    
  
Depends on: 127528

    
    

    
  
Bug 135630 nsTreeContentView::AttributeChanged

    
    

    
  
The idea of ultimately removing the bounds-checking code in
nsVoidArray::ElementAt(...) is DEEPLY troubling to me.

I just hit an Assertion case as a result of a patch in bug #145994.  In this
case, choices made in an external embeddor's code caused the assert to trigger.
 We would NOT have detected this situation in ANY of the mozilla testing.

I can't imagine that it will EWVER be safe to remove the bounds-checks from
nsVoidArray::ElementAt(...) because of just this kind of risk.

I wish that we would have followed brendan's suggestion in comment #25 to add a
*new* method such as nsVoidArray::FastElementAt(...) and ONLY replace those
calls to nsVoidArray::ElementAt that satisfy the following criteria:
  1. The call usage is 'safe'.  (ie. no possibility of the array 
     contents changing between the bounds check and the accessor.

  2. There is a Quantify-able reason for *not* incurring the if-check overhead.

Using this strategy, there is the ability to *immediately* remove the if-check
for code that actually benifits from it !

In 99.9% of the calls, i would bet that the extra overhead for the bounds-check
is undetectableb -- but potentially devistating (in the form of memory corruption).

Please reconsider this decision.  Or at the very least, let the rest of the
mozilla developers know that this change has been made !!  I, like most
developers, simply assumed that nsVoidArray::ElementAt(...) had the
bounds-checking support that IT HAS ALWAYS HAD IN THE PAST !!

-- rick

    
    

    
  

      
      
      
      

        Attached patch
          
          
        offhand were you using viewer? (deleted)
        — 
          — Splinter Review
      

    


  

    
    

    
  
Comment on attachment 84584 [details] [diff] [review]
offhand were you using viewer?

r=jkeiser

        Attachment #84584 -
        Flags: review+

    
    

    
  
No.  This was caused by an embeddor calling nsIWebNavigation::Stop() from 
nsIWebProgressListener::OnStateChange(...)

It should be noted that the same situation could occur from an onLoad() 
javascript handler ;-)

Following the current strategy, we will have to examine EVERY usage of 
nsVoidArray::ElementAt() and verify that no reenterent modifications can be 
made to the array between the bounds-check (usually at the top of the loop) and 
the call to ElementAt().

I think that this is an IMPOSSIBLY hard task... given the alternative of 
creating a new method and selectively fixing those call sites that actually 
benifit.

-- rick
-- rick


    
    

    
  
rick's right, my parenthetical was too mild: I think we should leave ElementAt
bounds-checking, compatibility is king.  Let's do the fast and less safe thing
in FastElementAt.

/be
Status: RESOLVED → REOPENED
Resolution: FIXED → ---

    
    

    
  
But we have been running with the assertion for almost half a year without many
problems I know of. If I remember correctly it was the massive use of ElementAt
from hundreds of places that caused it to show on profiles. Fixing all those
places is a job that probably won't be done. Fixing it in ElementAt will at
least give us the benefit of a faster array generally. 

Remember also, that most (almost any?) callers that access outside the array do
it by mistake so that code is already broken one way or another. By "helping"
them we might just hide other problems. 

It might be necessary to run with the check for quite a while longer, but I
still want to see unchecked access being the default and safe access being the
luxuary version for the ones who can afford it.

    
    

    
  
Someone managed to trigger this assetion recently doing something along the
lines of document.frames[1] when the document didn't have any frames. At leat I
think it was this one; it may have been a related assertion. I can't remmeber
who or when, though.

    
    

    
  
I'm with rpotts and brendan on this one.

    
    

    
  
daniel, I'm not confident we have code coverage to be sure we're ok now.  Plus,
people will tend to add unsafe uses.  The places to optimize should be called
out by vtune, and we can prefer correctness over optimization until each case is
proven to be (a) worth optimizing; (b) safe for unchecked access, or patched to
be safe.

/be

    
    

    
  
I get your point, but you can't make me like it. ;-)


    
    

    
  
I just hit an assertion which said to add a note to this bug whenever the
assertion is hit. I am on the prudent side too... No point driving fast to crash
on the way and not reach the destination on time anyway. So, additional vote for:

ElementAt() - default, bounds-check, future-proof...
FastElementAt() - for code (new or existing) that has been double-checked to be
guaranteed to be safe now and always.

    
  
Depends on: 162163

    
    

    
  
I'm seeing this assertion on shutdown from a 8/14/02 homebuilt clobber debug 
build on XP.  The offending code is in nsTimerImpl.cpp
http://lxr.mozilla.org/seamonkey/source/xpcom/threads/nsTimerImpl.cpp#519

The variable count on line 516 is 0, therefore the loop should never occur, but 
it does because the test is <= instead of <

    
    

    
  

      
      
      
      

        Attached patch
          
          
        fix to nsTimerImpl.cpp (deleted)
        — 
          — Splinter Review
      

    


  
Loop control at line 518, I meant.

/be

    
  

        Attachment #95421 -
        Flags: review+

    
    

    
  


  
This is the same fix as brendan's fix but it also eliminates the
RemoveElement() call on the array which causes the remaining elements in the
array to be shifted down in the array for AFAICT no good reason. This is
untested, but AFAICT this can't cause any ptoblems.

    
    

    
  
Comment on attachment 95427 [details] [diff] [review]
Same as above but should be a bit faster.

sr=brendan@mozilla.org

Pavlov, you should r= this one fast, in penance!

/be

        Attachment #95427 -
        Flags: superreview+

    
    

    
  
Comment on attachment 95427 [details] [diff] [review]
Same as above but should be a bit faster.

r=pavlov

        Attachment #95427 -
        Flags: review+

    
    

    
  
Comment on attachment 95427 [details] [diff] [review]
Same as above but should be a bit faster.

Checked in.

    
    

    
  
###!!! ASSERTION: nsVoidArray::ElementAt(index past end array) - note on bug 
96108: 'aIndex < Count()', file ./../ds\nsVoidArray.h, line 78 
Break: at file ./../ds\nsVoidArray.h, line 78

nsDebug::Assertion(const char * 0x1010c948 `string', const char * 0x1010c998 
`string', const char * 0x1010ca04 `string', int 78) line 280 + 13 bytes
nsVoidArray::ElementAt(int 0) line 78 + 35 bytes
nsVoidArray::operator[](int 0) line 99 + 19 bytes
nsTimerManager::~nsTimerManager() line 519 + 13 bytes
nsTimerManager::`scalar deleting destructor'(unsigned int 1) + 15 bytes
nsTimerManager::Release(nsTimerManager * const 0x00f98b08) line 501 + 136 bytes
nsCOMPtr_base::assign_assuming_AddRef(nsISupports * 0x00000000) line 436
nsCOMPtr_base::assign_with_AddRef(nsISupports * 0x00000000) line 74
nsCOMPtr<nsISupports>::operator=(nsISupports * 0x00000000) line 796
FreeServiceContractIDEntryEnumerate(PLDHashTable * 0x0027ce6c, PLDHashEntryHdr 
* 0x00ee799c, unsigned int 837, void * 0x00000000) line 1924
PL_DHashTableEnumerate(PLDHashTable * 0x0027ce6c, int (PLDHashTable *, 
PLDHashEntryHdr *, unsigned int, void *)* 0x10067870 
FreeServiceContractIDEntryEnumerate(PLDHashTable *, PLDHashEntryHdr *, unsigned 
int, void *), void * 0x00000000) line 601 + 34 bytes
nsComponentManagerImpl::FreeServices() line 1936 + 19 bytes
NS_ShutdownXPCOM(nsIServiceManager * 0x00000000) line 673
main(int 1, char * * 0x00276ac0) line 1881 + 8 bytes
mainCRTStartup() line 338 + 17 bytes
KERNEL32! 77e8d326()


    
    

    
  
Was that with a build that contains the recent checkin?

    
    

    
  
Sorry, I'm an idiot and should have checked the date of the last comment in 
this bug.

    
    

    
  
More from a debug depend build on XP built with the most recent checkins for 
this bug.

Mozilla asserts on shutdown 9 times with the same stack trace

http://lxr.mozilla.org/seamonkey/source/content/xul/document/src/nsXULDocument.c
pp#1854

NTDLL! 77f7f570()
nsDebug::Assertion(const char * 0x1010ca30 `string', const char * 0x1010ca80 
`string', const char * 0x1010caec `string', int 78) line 280 + 13 bytes
nsVoidArray::ElementAt(int 2) line 78 + 35 bytes
nsSmallVoidArray::ElementAt(int 2) line 1303 + 12 bytes
nsSmallVoidArray::operator[](int 2) line 356 + 19 bytes
ClearBroadcasterMapEntry(PLDHashTable * 0x033ea8d0, PLDHashEntryHdr * 
0x034057d8) line 1854 + 16 bytes
PL_DHashTableFinish(PLDHashTable * 0x033ea8d0) line 322 + 16 bytes
PL_DHashTableDestroy(PLDHashTable * 0x033ea8d0) line 164 + 9 bytes
nsXULDocument::~nsXULDocument() line 459 + 15 bytes
nsXULDocument::`scalar deleting destructor'() + 15 bytes
nsXULDocument::Release(nsXULDocument * const 0x0334c9d0) line 574 + 165 bytes
nsEventStateManager::~nsEventStateManager() line 244 + 36 bytes
nsEventStateManager::`scalar deleting destructor'(unsigned int 1) + 15 bytes
nsEventStateManager::Release(nsEventStateManager * const 0x033b9e68) line 318 + 
161 bytes
nsCOMPtr<nsIEventStateManager>::~nsCOMPtr<nsIEventStateManager>() line 491
nsPresContext::~nsPresContext() line 235 + 57 bytes
GalleyContext::~GalleyContext() line 61 + 8 bytes
GalleyContext::`scalar deleting destructor'(unsigned int 1) + 15 bytes
nsPresContext::Release(nsPresContext * const 0x0333c420) line 237 + 164 bytes
nsDOMEvent::~nsDOMEvent() line 266 + 27 bytes
nsDOMEvent::`scalar deleting destructor'(unsigned int 1) + 15 bytes
nsDOMEvent::Release(nsDOMEvent * const 0x03291608) line 284 + 161 bytes
XPCJSRuntime::GCCallback(JSContext * 0x034d9f08, JSGCStatus JSGC_END) line 546 
+ 18 bytes
DOMGCCallback(JSContext * 0x034d9f08, JSGCStatus JSGC_END) line 1639 + 23 bytes
js_GC(JSContext * 0x034d9f08, unsigned int 0) line 1375 + 12 bytes
js_ForceGC(JSContext * 0x034d9f08, unsigned int 0) line 985 + 13 bytes
JS_GC(JSContext * 0x034d9f08) line 1659 + 11 bytes
nsJSContext::Notify(nsJSContext * const 0x034d9ea8, nsITimer * 0x03548158) line 
1594 + 13 bytes
nsTimerImpl::Fire() line 341
nsTimerManager::FireNextIdleTimer(nsTimerManager * const 0x01181bf8) line 579
nsAppShell::Run(nsAppShell * const 0x0113dca0) line 156
nsAppShellService::Run(nsAppShellService * const 0x011258c8) line 452
main1(int 1, char * * 0x002a7208, nsISupports * 0x00000000) line 1509 + 32 bytes
main(int 1, char * * 0x002a7208) line 1873 + 37 bytes
mainCRTStartup() line 338 + 17 bytes
KERNEL32! 77e7eb69()

    
    

    
  
These are gone with 
http://bugzilla.mozilla.org/show_bug.cgi?id=162947 fixed.



    
    

    
  
This is a recent regression.  Already pinged bug 175440 people.  Dropping a 
copy here in case anybody looks.

Seen with a 1hr old cvs trunk build Win2k:

###!!! ASSERTION: nsVoidArray::ElementAt(index past end array) - note on bug 
96108: 'aIndex < Count()', file 
d:/mozilla/mozilla/xpcom/build/../ds\nsVoidArray.h, line 78

nsVoidArray::ElementAt(int 0x00000001) line 78 + 35 bytes
nsCOMArray_base::ObjectAt(int 0x00000001) line 95
nsCOMArray<nsIRunnable>::ObjectAt(int 0x00000001) line 144
nsThreadPool::GetRequest(nsIThread * 0x02bf9a60) line 588 + 15 bytes
nsThreadPoolRunnable::Run(nsThreadPoolRunnable * const 0x02c6d888) line 896 + 
29 bytes
nsThread::Main(void * 0x02bf9a60) line 120 + 26 bytes
_PR_NativeRunThread(void * 0x037d3b78) line 433 + 13 bytes
_threadstartex(void * 0x02c641b0) line 212 + 13 bytes
KERNEL32! 77e887dd()

    
  
Depends on: 186668
Target Milestone: mozilla0.9.7 → ---

    
    

    
  
I'm starting to think that having a ::FastElementAt is a better solution too.
Maybe we could have that and let operator[] use FastElementAt. there are much
fewer operator[] uses so finding and checking all of those should be much
simpler then checking all ::ElementAt.

    
    

    
  
These were the options we had for checkin when this went in:

  1. Commit this and take the minor win.  There is some risk, though I have
  looked at _every_ ElementAt call and most indirect calls (GetShellAt, etc),
  and we have NS_ASSERTIONs to catch this in debug.
  2. Commit this with bounds-checks for negative and past-end left in for opt
  builds (i.e. a bug in array code will NOT crash it) but leave the asserts in.
  3. Commit this with bounds-checks for negative and past-end left in for opt
  builds (i.e. a bug in array code will NOT crash it) and remove the asserts
  (i.e. as now with inlining -- no need for SafeElementAt).
  4. Commit just the clean-up portions of this (Clear() over loops of
  RemoveElementAt(), algorithm fixes, setting up loops more correctly, etc) and
  leave bounds-checking and inlining as per today.

We committed it as #2 (mostly) - left bounds-check for past-end in, and left
past-end and negative-index assertions in.

We could add FastElementAt and use that for [], though fundamentally that
doesn't change much, and spend time converting some of the ElementAt calls to
[].  As sicking indicates, [] "feels" more dangerous though there's no real
technical reason for that.  The downside of this is no perf win for the change
except in spots where we go in and verify (again) that ElementAt is always safe
(which is pretty much all ElementAt calls currently; I went through every one of
them (hundreds of files) when doing these patches originally).



    
    

    
  
The biggest win i see with removing the checks is the binary-size win. From that
perspective it would defenetly be better to remove the checks from ::ElementAt
since that will affect much more loops.

    
  
Depends on: 217907

    
  
Depends on: 236268

    
    

    
  

      
      
      
      

        Attached patch
          
          
        add FastElementAt, make nsCOMArray use it (obsolete) (deleted)
        — 
          — Splinter Review
      

    


  
This patch adds FastElementAt and makes nsCOMArray<T>::ObjectAt use it, since
nsCOMArray<T>::ObjectAt has always asserted on out-of-bounds.  So at least we
hopefully won't have people relying on this for nsCOMArray.

    
  

        Attachment #158803 -
        Flags: review?(darin)

    
    

    
  

      
      
      
      

        Attached patch
          
          
        add FastElementAt, make nsCOMArray use it (obsolete) (deleted)
        — 
          — Splinter Review
      

    


  
This also removes some mImpl null checks that are unneeded (since a Count()
bounds check ensures mImpl is non-null) but that some compilers might not
optimize away.

        Attachment #158803 -
        Attachment is obsolete: true

    
    

    
  
(The one change the previous patch makes to existing code for nsVoidArray is
that, when not using SafeElementAt, it means a negative-index access of a
zero-length array now crashes -- but a negative-index access of a non-zero
length array has returned garbage and asserted for years, and a negative-index
access of a zero-length array has asserted for years.)

    
  

        Attachment #158803 -
        Flags: review?(darin)

    
  

        Attachment #158805 -
        Flags: review?(darin)

    
    

    
  
IMHO we should with this patch deprecate ElementAt entierly. Since as long as I
can remember it has been misused wrt bounds-safty and it's current state is bad
(halfway boundssafe and unusable as anything other then unboundssafe) and hard
to change.

    
    

    
  
dbaron: i've hit negative array accesses recently. in dom or related code to
boot (weirdal's abacus stuff). please don't switch to crashinig yet.

    
    

    
  
Then we may as well switch to bounds-checking both ends in ElementAt (i.e.,
making it the same as SafeElementAt), since the aIndex >= 0 check shouldn't take
any more CPU or code than the null-check of mImpl.

    
    

    
  


  
Making nsVoidArray::ElementAt safe again doesn't make it any simpler than the
current version, so we may as well -- but I'll leave the assertions to
discourage people from writing bad code.

    
  

        Attachment #158805 -
        Attachment is obsolete: true

        Attachment #158805 -
        Flags: review?(darin)

    
  

        Attachment #158824 -
        Flags: review?(darin)

    
    

    
  
You could actually make both ElementAt and SafeElementAt somewhat faster/smaller
by using the trick in comment 25. And I still think we should deprecate ElementAt.

    
    

    
  
Comment on attachment 158824 [details] [diff] [review]
add FastElementAt, make nsCOMArray use it, make nsVoidArray::ElementAt safe again

r=darin with brendan's suggestion from comment #25 or not if you believe that
compilers will optimize this code to the same thing.

        Attachment #158824 -
        Flags: review?(darin) → review+

    
    

    
  
You might want to check out bug 246586
(http://bugzilla.mozilla.org/show_bug.cgi?id=246586#c31) for further improvments
ie remove some other mImpl null checks

    
    

    
  
Comment on attachment 158824 [details] [diff] [review]
add FastElementAt, make nsCOMArray use it, make nsVoidArray::ElementAt safe again

Checked in to trunk (with change from comment 25) at 2004-09-14 10:17 -0700.

    
    

    
  
Could this have caused the Tp rise on btek?

    
    

    
  
I think it did, although I'm testing now.  There was a drop on luna, so I think
it's particular to that compiler.

Comparison of the disassembly of nsCompositeDataSource.cpp shows that btek was
unable to inline SafeElementAt in two places (where it inlined all the relevant
code before): CompositeEnumeratorImpl::~CompositeEnumeratorImpl and
CompositeEnumeratorImpl::HasMoreElements.  It looks like it was able to inline
everywhere else, though.

    
    

    
  
The code that did get inlined, was it similar or the same as the "before"
inlined code? I mean, looking at the change you made, things should be equally
fast if not faster:

operator[] used to call ElementAt and essentially execute:

    if (aIndex >= Count())
      return nsnull;
    return mImpl ? mImpl->mArray[aIndex] : nsnull;

Now there's an extra level of nesting of function call through SafeElementAt,
and it executes:

    if (PRUint32(aIndex) >= PRUint32(Count()))
      return nsnull;
    return mImpl->mArray[aIndex];

The PRUint32 casts should compile away to an unsigned compare (vs. signed
compare) and a compare and jump should've been removed. Unless the compiler
inlined Count() and had already optimized away the extra compare on mImpl.

So yeah, sounds like the not-inlining is the problem. Could it be the compiler
only inlines two function calls deep, i.e. making operator[] call SafeElementAt
directly would fix the problem?

Also, perhaps we should make operator[] call FastElementAt, reasoning along the
same lines as for std::vector operator[] vs. at(), where at() is required to do
bounds checking, while operator[] isn't required to, for performance reasons
(but can if it wants to).

    
    

    
  
For nsCOMArray_base::operator[] through ObjectAt you're already using FastElementAt.

    
    

    
  
Crash regression in Composer? Click the abs pos button with an new document. It
tries to do arrayOfNodes[0] with a new array.

I've also got it to hang when you remove the abs pos style, the code from
nsHTMLEditRules::WillAbsolutePosition depends on ElementAt returning null when
the index is out of range, here's the code snippet in question:
nsCOMPtr<nsIDOMNode> curNode = arrayOfNodes[0];
while (curNode)
{
  res = mHTMLEditor->DeleteNode(curNode);
  if (NS_FAILED(res)) return res;
  res = arrayOfNodes.RemoveObjectAt(0);
  if (NS_FAILED(res)) return res;
  curNode = arrayOfNodes[0];
}
Ideally this should be fixed to use arrayOfNodes.Count(), but that requires
someone to trawl though the code looking for other abuses of operator[].

    
    

    
  

      
      
      
      

        Attached patch
          
          
        patch to fix editor (obsolete) (deleted)
        — 
          — Splinter Review
      

    


  

    
  

        Attachment #159117 -
        Flags: review?(neil.parkwaycc.co.uk)

    
    

    
  
Comment on attachment 159117 [details] [diff] [review]
patch to fix editor

Not that this is performance critical, but as something that might get copied
as an example (doesn't all our code?), perhaps you could use arrayOfNodes[j]
and RemoveObjectAt(j) to remove from the end?

    
    

    
  
Comment on attachment 159117 [details] [diff] [review]
patch to fix editor

Neil pinged me to get moa=daniel@glazman.org. Here it is. Neil told me he wants
more tests. Thanks all for this patch.

    
    

    
  
Comment on attachment 159117 [details] [diff] [review]
patch to fix editor

I couldn't break it ;-)

        Attachment #159117 -
        Flags: review?(neil.parkwaycc.co.uk) → review+

    
  

        Attachment #159117 -
        Flags: superreview?(bzbarsky)

    
    

    
  
Comment on attachment 159117 [details] [diff] [review]
patch to fix editor

This is a better fix than the one on bug 260771 and I'd like to get it in for
alpha4.

        Attachment #159117 -
        Flags: approval1.8a4?

    
    

    
  
Comment on attachment 159117 [details] [diff] [review]
patch to fix editor

pre-approving for 1.8a4 pending SR.

        Attachment #159117 -
        Flags: approval1.8a4? → approval1.8a4+

    
    

    
  
Comment on attachment 159117 [details] [diff] [review]
patch to fix editor

sr=bzbarsky

        Attachment #159117 -
        Flags: superreview?(bzbarsky) → superreview+

    
    

    
  
Comment on attachment 159117 [details] [diff] [review]
patch to fix editor

Checked in by dbaron 2004/08/25 06:22:48

        Attachment #159117 -
        Attachment is obsolete: true
Depends on: 329889
Assignee: rjesup → nobody
Status: REOPENED → NEW
QA Contact: scc → xpcom
Hardware: PC → All

    
    

    
  
Patches have been applied long time ago, so this bug can be closed?

(Note the followup cleanup patch is partly applied, and the parts that are not applied don't seems valid anymore).
Status: NEW → RESOLVED
Closed: 23 years ago → 17 years ago
Resolution: --- → FIXED

        Attachment #55000 -
        Attachment description: Updated patch - asserts on negative or past-end indexes.  Work in progress, but worth trying.  I have not tried this with mail/news, composer, or chatzilla yet.  Also note I made some minor tweaks and am still recompiling, but wanted this up for people to → Updated patch - asserts on negative or past-end indexes.  Work in progress, but worth trying.

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






  

    
  







  

    

      
Attachment

      

      
      
      
      
    

    

      

        

          

            
General

            

              Creator: 



            

            
Created: 

            
Updated: 

            
Size: