100231 - nsVoidArray extensions

Status: RESOLVED WONTFIX

(Core :: XPCOM, enhancement)

Description

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

This bug is to handle discussion and eventual patches to extend/improve
nsVoidArray and nsAutoVoidArray, etc.

The main ideas:
1) make nsSupportsArray inherit from nsVoidArray.  May not be simple... and the
interfaces conflict slightly.
2) allow for auto nsVoidArrays that have a default size of other than 8.  Either
create alternate variations of nsAutoVoidArray, or allow an array block to be
passed in as a separate structure, or ???
3) refine the interface to allow some additional functionality.  (Requests?)
4) include nsCheapVoidArray or equivalent.  Care needs to be taken not to slow
down execution or add much if any bloat.
5) possibly allow for segmented arrays (complicates the implementation
considerably).
6) Include direct int/etc arrays instead of requiring casts to/from void*. 
Perhaps even (gasp) templates (with scc's approval only).

Comment 1

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

>4) include nsCheapVoidArray or equivalent.  Care needs to be taken not to slow
>down execution or add much if any bloat.

I now have a patch for this (adds nsSmallVoidArray to nsVoidArray.cpp), and also
have switched nsGenericElement over to using it.  It is basically
nsCheapVoidArray with a more complete implementation of nsVoidArray methods. 
There is no extra bloat except for a tiny amount of code for the extra methods,
and it's just as fast as nsCheapVoidArray.

I will post this shortly.  It's not a general-purpose replacement for
ns(Auto)VoidArray because there is (some) extra CPU overhead for arrays larger
than 1 element, though not a lot.  It is appropriate for space-sensitive member
element uses where sizes of 0 or 1 are moderately common or more
(nsGenericElement, probably some style uses, perhaps XUL, etc.)

Comment 2

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

Attachment: Preliminary patch for nsSmallVoidArray, not fully tested yet

Comment 3

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

Attachment: Updated patch. Minor updates. Ready for review.

Comment 4

[Chris Waterson]

The problem with doing this is that nsVoidArray and its ilk are sometimes used
to store non-pointer values, or pointers that may not be 2-byte alignhed. (For
example, someone wanting to use the nsSmallVoidArray to hold an array of indices
into a character strings might be surprised at the results if their first
element is not 2-byte aligned.) Perhaps you ought to assert that the values that
are being assigned into the small array are all 2-byte aligned.

Do you have any specific use cases for this in mind?

Comment 5

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

True, there is a fundamental assumption there, which was shared by
nsCheapVoidArray.  Assertions will be added.  There are a number of other places
this can be used where we have member vars.  We already have the implicit
assumption that memory allocations (and class foo *'s) cannot have a low-bit be
1 (the uses of nsCheapVoidArray depended on that already).

Alternatively, we could increase the overhead from 4 bytes to 5 (which may get
rounded up to 6 or 8) and move the flag out of the low bit, and make it work for
anything.

Comment 6

[Chris Waterson]

nsCheapVoidArray was private to the content classes where it was assumed that
the author would know what to do with it. You are making this a ``publicly
available'' utility class. _Don't_ add size if you're going replace
nsCheapVoidArray with nsSmallVoidArray. _Do_ defend yourself (#ifdef DEBUG,
anyway) against people misusing the code. _Do_ document the assumptions you've
made about the kinds of data that will be stored in this data structure.

Comment 7

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

Added assertions for all ways items can be added to nsSmallVoidArrays, and added
these comments to the .h:

+//===================================================================
+//  nsSmallVoidArray is not a general-purpose replacement for
+//  ns(Auto)VoidArray because there is (some) extra CPU overhead for arrays
+//  larger than 1 element, though not a lot.  It is appropriate for
+//  space-sensitive uses where sizes of 0 or 1 are moderately common or
+//  more, and where we're NOT storing arbitrary integers or arbitrary
+//  pointers.
+
+// NOTE: nsSmallVoidArray can ONLY be used for holding items that always
+// have the low bit as a 0 - i.e. element & 1 == 0.  This happens to be
+// true for allocated and object pointers for all the architectures we run
+// on, but conceivably there might be some architectures/compilers for
+// which it is NOT true.  We know this works for all existing architectures
+// because if it didn't then nsCheapVoidArray would have failed.  Also note
+// that we will ASSERT if this assumption is violated in DEBUG builds.

Comment 8

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

Attachment: Updated with asserts/comments

Comment 9

[Chris Waterson]

Maybe this should be a meta-bug, and you could break each of the tasks into
individual bugs?

Comment 10

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

Ok, for any future patches this will be a meta-bug.  Since 105071 is gated on
this one, shall we get this one approved too?  Still awaiting r/sr

Comment 11

[Chris Waterson]

I'm beginning to regret that I told you to assert stylistic ownership on this
file :-). My out-of-the-box copy of emacs continually wants to re-indent it for
me. Could you either revert to the good old style that pervades the rest of the
code, or figure out a modeline that will not make emacs act so stupid?
Furthermore, and you're inconsistently applying your style here! (Some of the
changes put the brace on the same line as the |if|.)

The explicit |inline| directives are not necessary. Let the compiler do it if it
wants to.

You may need to instantiate an nsSmallVoidArray in
mozilla/xpcom/build/dlldeps.cpp so that it gets exported on Windows. sfraser,
are we still hand-exporting symbols from xpcom.shlb on Mac?

Fix those, and r=waterson.

Comment 12

[Simon Fraser [no longer active]]

Exports in xpcom on Mac clue off of NS_EXPORT. No need for additional files to be 
edited.

Comment 13

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

Fixed style issues (including modeline).  (Mixed style was from importing code
from content.)  Removed inlines.

Added assertions for aIndex < 0 to try to clean up callers so we can remove the
tests.

Added nsSmallVoidArray to dlldeps.cpp.  Someone with a Win32 build will need to
check that for me.

Also already in there (in the previous patch) was something to limit the size
increase of an nsVoidArray to 1024 entries (4KB, 1 page).  This is a tuning
issue, but it means we'll allocate in exact multiples of a page, and since we
use realloc() the system may often be able to do it with VM trickery alone.  We
could raise it to 2048 or 4096, but I don't see much win in that unless we start
using it for really large lists a lot.

New patch to be attached; note that I still need to see how much gets kicked out
by the assertions I added, especially in ElementAt() and ReplaceElementAt().

Comment 14

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

Attachment: Updated patch for style and waterson's comments, with asserts on index < 0

Comment 15

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

See also bug 96108 (inlining ElementAt()).  It's possible this will get checked
in via that bug if people like.  The latest patch there includes this, with an
update for the one added use of nsCheapVoidArray converted to nsSmallVoidArray.

Comment 16

[Cathleen]

hey Randell, is this already fixed with bug 96108?  :-) 

Comment 17

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

Comment on attachment 53975 [details] [diff] [review]
Updated patch for style and waterson's comments, with asserts on index < 0

Patch checked in with bug 96108.  This bug remains the nsvoidarray extensions
bug; see the initial comment.

Comment 18

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

Add another way to improve nsVoidArray:

Make nsCheapVoidArray and nsVoidArray both use nsVoidArrayImpl, and so avoid the
extra indirection when using nsCheapVoidArrays.  nsVoidArrayImpl would be what
is now the Impl structure.