Closed Bug 96108 Opened 24 years ago Closed 19 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
135.76 KB, patch
Details | Diff | Splinter Review
offhand were you using viewer?
1.14 KB, patch
john
: review+
Details | Diff | Splinter Review
fix to nsTimerImpl.cpp
606 bytes, patch
timeless
: review+
Details | Diff | Splinter Review
Same as above but should be a bit faster.
746 bytes, patch
pavlov
: review+
brendan
: superreview+
Details | Diff | Splinter Review
add FastElementAt, make nsCOMArray use it, make nsVoidArray::ElementAt safe again
3.34 KB, 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.
3.47 KB, 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) — — 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.
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) — — 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).
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: 24 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
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 <
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
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.
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.)
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)
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[].
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+
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: 24 years ago → 19 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: