Closed Bug 819090 Opened 11 years ago Closed 9 years ago

Remove nsVoidArray

Categories

(Core :: XPCOM, defect)

defect
Not set
normal

Tracking

()

RESOLVED FIXED
mozilla40
Tracking Status
firefox40 --- fixed

People

(Reporter: mccr8, Assigned: poiru)

References

(Depends on 1 open bug)

Details

Attachments

(6 files, 3 obsolete files)

Outside of the implementation of other arrays, there are very few uses of nsVoidArray and nsAutoVoidArray, which can be converted to nsTArray and nsAutoTArray without too much fuss.

There are a few weirdnesses here:
- nsVoidArray(n) does SetLength(n), while nsTArray(n) does SetCapacity(n)
- nsVoidArray::ElementAt has a bounds check plus an assert, whereas nsTArray::ElementAt as an assert but no bounds check, so I converted it to nsTArray::SafeElementAt, which does a bounds check, but has no assert.

This patch is untested, but compiles. It has some fixes for printf warnings in leaksoup that I need to split out into a separate bug.

nsSmallVoidArray could probably also be converted without too much trouble.
It looks like there may be a bunch of places that include nsVoidArray.h that don't really need to:
http://mxr.mozilla.org/mozilla-central/search?string=nsVoidArray.h&filter=[Nn]sVoidArray.h
I checked all of these files, and none of them contain "Void" anywhere, so I think it is reasonable to remove the include.
Assignee: nobody → continuation
nsSmallVoidArray will be annoying to remove, as it is supposed to be pointer sized when it is only holding a single element, and the other more modern arrays don't seem to have anything like that. Maybe nsAutoTArray is similar?

These are the uses of it:
- entries in some kind of mapping from broadcasters to listeners in nsXULDocument. I guess if you have a lot of these mappings it will save some space.
- A field of nsIdentifierMapEntry in nsDocument.h
- nsIDocument::GetAllElementsForId. Seems slightly silly, as it isn't in a data structure, but maybe it is needed for compatibility with the previous thing.
This segfaults immediately on startup with a stack like 
nsACString_internal::Equals(nsACString_internal const&) const + 9 (nsTSubstring.cpp:613)
nsChromeRegistryChrome::nsProviderArray::SetBase(nsACString_internal const&, nsIURI*) + 81 (nsChromeRegistryChrome.cpp:612)
nsChromeRegistryChrome::ManifestLocale(nsChromeRegistry::ManifestProcessingContext&, int, char* const*, bool, bool) + 251 (nsTSubstring.h:85)
ParseManifest(NSLocationType, mozilla::FileLocation&, char*, bool) + 3449 (ManifestParser.cpp:634)

(nsChromeRegistryChrome is one of the classes I touched)

So clearly there is some work to be done...
There's some work going on in bug 493711 to make nsCOMArray use nsTArray instead of nsVoidArray. There are some subtleties I don't really understand, but looking at patches there might lead to better understanding of what needs to be done to get rid of void array, or at least to implement it using an nsTArray.
Assignee: continuation → nobody
Depends on: 823940
Attached patch *old* patch to nuke some uses (obsolete) — Splinter Review
This is a really old patch that I had laying around that attempted to nuke nsVoidArray. I don't remember if it got rid of all uses, nor if it actually worked.

You'll definitely need to run s/PRUint32/uint32_t/ and s/PRInt32/int32_t/ over it to make it even remotely apply.
It looks like nsAutoVoidArray was removed in bug 823940.  Also, it looks like the only uses of nsVoidArray are in the old cache.
Summary: Eliminate uses of nsVoidArray and nsAutoVoidArray outside of the implementation of nsCOMArray → Remove nsVoidArray
There are some remaining places that use nsSmallVoidArray in DOM-y stuff, for whatever reason.
Assignee: nobody → birunthan
Status: NEW → ASSIGNED
Attachment #8550353 - Flags: review?(michal.novotny)
Attachment #8550353 - Flags: review?(michal.novotny) → review+
bz, since you originally introduced[0] this use of nsSmallVoidArray, does this change have your rubberstamp approval? nsSmallVoidArray is more space efficient when there is a single element, but that probably doesn't matter in the grand scheme of things.

[0]: https://github.com/mozilla/gecko-dev/commit/cc66f0bcb5da48de63311a016217d8aa3afdf5b9#diff-23e71111566e620bfbf0a77d60ac3987R246
Attachment #689380 - Attachment is obsolete: true
Attachment #689427 - Attachment is obsolete: true
Attachment #8377815 - Attachment is obsolete: true
Flags: needinfo?(bzbarsky)
Attachment #8558930 - Flags: review?(nfroyd)
Attachment #8558931 - Flags: review?(nfroyd)
Comment on attachment 8558930 [details] [diff] [review]
Convert nsDocument::mIdContentList to nsTArray

> but that probably doesn't matter in the grand scheme of things.

Have you tried measuring to verify this assumption?
Flags: needinfo?(bzbarsky) → needinfo?(birunthan)
(In reply to Boris Zbarsky [:bz] from comment #16)
> Comment on attachment 8558930 [details] [diff] [review]
> Convert nsDocument::mIdContentList to nsTArray
> 
> > but that probably doesn't matter in the grand scheme of things.
> 
> Have you tried measuring to verify this assumption?

I'd like to echo bz's question for the XULDocument patches.  Replacing nsSmallVoidArray in netwerk/cache/ without this question is reasonable to me, as the old cache is going away at some point (?).  But the XUL stuff isn't, and it'd be good to understand what the perf impact is here.  Can you provide numbers on the usual sizes of these arrays and how many of them exist?
(In reply to Nathan Froyd [:froydnj] [:nfroyd] from comment #17)
> I'd like to echo bz's question for the XULDocument patches.  Replacing
> nsSmallVoidArray in netwerk/cache/ without this question is reasonable to
> me, as the old cache is going away at some point (?).  But the XUL stuff
> isn't, and it'd be good to understand what the perf impact is here.  Can you
> provide numbers on the usual sizes of these arrays and how many of them
> exist?

With the existing nsVoidArray stat collection (DEBUG_VOIDARRAY) fixed to take nsSmallVoidArray's single element case into account, the max sizes of nsSmallVoidArrays were as follows for a 2 minute browser/base/content/general test run:

  0: 8
  1: 23393
  2: 203
  3: 35
  4: 10
  5: 21
  8: 17
  69: 1

Running and shutting down the browser immidiately gives:

  1: 1375
  2: 11
  3: 2
  4: 1
  5: 2
  8: 1

In the single element case, a nsVoidArray only consumes 8 bytes (assuming 64-bit pointers) and is allocation-free. In comparison, a nsTArray<void*> of size 1 requires 8 bytes plus an allocation of 16 bytes. A nsAutoTArray<void*, 1>, too, requires 24 bytes, but wouldn't have the allocation overhead in the single element case.

If the 16 byte overhead is too much, we could also introduce and use something like TinyPtrArray<T>, which would privately inherit from nsTArray_Impl and use the nsTArray_base::mHdr pointer to store a single element like nsSmallVoidArray. We could then expose the necessary nsTArray_Impl functions wrapped to handle the single element case. This ought to let us to reap the benefits with much less code. Any thoughts?
Flags: needinfo?(birunthan) → needinfo?(nfroyd)
> for a 2 minute browser/base/content/general test run:

I'm a lot more interested in data for real-world web pages, honestly.  Including ones with large forms at the very least.  Using browser/base/content for data about fairly HTML-specific data structures like nsIdentifierMapEntry is not that useful.

> In the single element case, a nsVoidArray only consumes 8 bytes (assuming 64-bit
> pointers) 

And 4 bytes on Windows (because 32-bit), right?

> In comparison, a nsTArray<void*> of size 1 requires 8 bytes plus an allocation of 16
> bytes.

What are the relevant numbers on Windows?

Note that there is also an access penalty for the nsTArray case for one element, since you have to pointer-chase and end up with more memory pressure, right?
(In reply to Boris Zbarsky [:bz] from comment #19)
> > for a 2 minute browser/base/content/general test run:
> 
> I'm a lot more interested in data for real-world web pages, honestly. 
> Including ones with large forms at the very least.  Using
> browser/base/content for data about fairly HTML-specific data structures
> like nsIdentifierMapEntry is not that useful.

Are We Slim Yet is now setup to trigger runs from try.  So one can do:

- push a baseline to try with '-b o -p linux64 -u none -t none -awsy nsvoidarray'
- push patch series to try with '-b o -p linux64 -u none -t none -awsy nsvoidarray'
- eventually view results at https://areweslimyet.com/?series=nsvoidarray&evenspacing=1'

While that won't give you hard numbers on how many nsVoidArrays are created and their relative sizes, it will at least tell you if the memory usage differences are noticeable on a suite of real-world-ish web pages.

I don't have any good suggestions on finding pages with large numbers of forms...

I think inventing nsCheapPointerArray (for naming consistency with nsCheapSet), reusing nsTArray_Impl would be reasonable.  But it'd be better to see if we can get by with nsTArray first.
Flags: needinfo?(nfroyd)
So basically, nsIdentifierMapEntry is created in two cases:

1)  There are elements with that id in the document.  In this case, commonly there is only 1, of course.

2)  There are elements with that name in the document.  Names mostly get used for form controls.  In this case, commonly there is nothing in the mIdContentList.

The real questions are how common case #2 is and whether we're willing to just have an nsAutoTArray and burn the space in that case.  I think the allocation size is a lot less relevant here than the perf impact of the out-of-line allocation.
Attachment #8558928 - Flags: review?(nfroyd) → review+
Attachment #8558929 - Flags: review?(nfroyd) → review+
Attachment #8558931 - Flags: review?(nfroyd) → review+
Comment on attachment 8558930 [details] [diff] [review]
Convert nsDocument::mIdContentList to nsTArray

r=me on all the other patches, but canceling review on this one while we get some sort of numbers indicating how much of a memory hit this is.
Attachment #8558930 - Flags: review?(nfroyd)
(In reply to Nathan Froyd [:froydnj] [:nfroyd] from comment #20)
> Are We Slim Yet is now setup to trigger runs from try.  So one can do:
> ...
> While that won't give you hard numbers on how many nsVoidArrays are created
> and their relative sizes, it will at least tell you if the memory usage
> differences are noticeable on a suite of real-world-ish web pages.

Here you go: https://areweslimyet.com/?series=removensvoidarray&evenspacing=1

Does the increase fall within the margin of error?
(In reply to Birunthan Mohanathas [:poiru] from comment #23)
> (In reply to Nathan Froyd [:froydnj] [:nfroyd] from comment #20)
> > Are We Slim Yet is now setup to trigger runs from try.  So one can do:
> > ...
> > While that won't give you hard numbers on how many nsVoidArrays are created
> > and their relative sizes, it will at least tell you if the memory usage
> > differences are noticeable on a suite of real-world-ish web pages.
> 
> Here you go: https://areweslimyet.com/?series=removensvoidarray&evenspacing=1
> 
> Does the increase fall within the margin of error?

Those look a little high to me, but I don't know how noisy AWSY is.  ni?'ing Eric, the resident AWSY expert.
Flags: needinfo?(erahm)
Roughly: it's not worse; most of the variations are w/in the noise. 

The following explicit values did stand out as possibly improved:

- Explicit: Fresh start
- Explicit: After TP5 [+30s]
- Explicit: After TP5, tabs closed
Flags: needinfo?(erahm)
Comment on attachment 8558930 [details] [diff] [review]
Convert nsDocument::mIdContentList to nsTArray

Review of attachment 8558930 [details] [diff] [review]:
-----------------------------------------------------------------

Improvements seem kind of unlikely...but, OK.
Attachment #8558930 - Flags: review+
One problem, nsVoidArray is still used in mailnews core. See Bug 777770
Depends on: 777770
Depends on: 474369
Version: unspecified → Trunk
Comment on attachment 8558930 [details] [diff] [review]
Convert nsDocument::mIdContentList to nsTArray

Review of attachment 8558930 [details] [diff] [review]:
-----------------------------------------------------------------

::: dom/base/nsDocument.h
@@ -232,5 @@
>                             bool aImageOnly = false);
>  
>    // empty if there are no elements with this ID.
>    // The elements are stored as weak pointers.
> -  nsSmallVoidArray mIdContentList;

This pretty significantly increases the memory usage and number of allocations. The by far most common case is that there's just a single entry in this array, and nsSmallVoidArray can do that without allocating extra memory or making the member bigger than 1 word.

Has the memory/performance impact been measured?
Ah, I see that measurements were done. Still seems unfortunate to me to double the number of calls to malloc though. It would probably be worth making this an nsAutoTArray?
Comment on attachment 8605541 [details] [diff] [review]
Follow-up: Make nsIdentifierMapEntry::mIdContentList a nsAutoTArray to save an allocation

Review of attachment 8605541 [details] [diff] [review]:
-----------------------------------------------------------------

Thanks!
Attachment #8605541 - Flags: review?(jonas) → review+
It would probably be possible to make nsTArray<T*> always inline-allocate the first element. It'll be a little more runtime code, but the saved allocations are most likely a bigger perf-win.

Of course, that's definitely a separate bug.

Also, thanks for doing the followup so quickly!
Oh, I bet these things are memmove'd. We can't memmove an nsAutoTArray since it contains a pointer to its internal buffer. That pointer doesn't get updated when the array is memmoved.

So I think we'll just have to live with the extra allocation, do something like comment 35, or implement a new nsSmallTArray<T>.

There might also be ways to get the nsTHashTable to not use a plain memmove.
Depends on: 1164842
> There might also be ways to get the nsTHashTable to not use a plain memmove.

Yes, there are.  Add enum { ALLOW_MEMMOVE = false } to the entry type.
Blocks: 1217436
(In reply to Wes Kocher (:KWierso) from comment #37)
> Backed out in
> https://hg.mozilla.org/integration/mozilla-inbound/rev/ae5df55492a3 for mass
> bustage:

This fell of my radar, sorry! I filed bug 1217436 to get this landed properly.
Flags: needinfo?(birunthan)
You need to log in before you can comment on or make changes to this bug.