Open Bug 1007846 Opened 10 years ago Updated 2 years ago

Consider making nsTArray's internal storage automatically use 16bit or 8bit headers to save memory

Categories

(Core :: XPCOM, defect)

Product:
Core
Component:
XPCOM
Version:
Other Branch
Type:
defect

Tracking

()

People

(Reporter: bjacob, Unassigned)

Details

(Whiteboard: [MemShrink:P2])

Attachments

(1 file)

WIP instrumentation to measure that
18.82 KB, patch
Details | Diff | Splinter Review 
Context: some conversation on bug 1004098. In particular, an instrumentation patch attached there shows that we have roughly 16k to 18k array headers per tab in desktop Firefox. Probably a comparable figure per application process in B2G.

Most of our arrays are of capacity smaller than 32k, so they could use uint16 instead of uint32 for their length and capacity stored in their header.

Doing so would save 4 bytes per header i.e. about 70k per tab.

We could go more crazy and say that in fact a majority of our arrays is of capacity less than 128, so in fact they could use uint8 headers.

Doing so would save 6 bytes per header i.e. about 100k per tab.

We could get these savings by
  1) adding runtime logic to switch header types internally in nsTArray;
  2) making Auto arrays use (at compile time) the smallest header type that they need for the auto size specified as template parameter. E.g. nsAutoTArray<int, 100> would determine at compile time that 100 < 128 therefore a 8bit in-object header is enough.
We need to worry a bit about alignment, right?  Right now a Header is 8 bytes, so as long as it's aligned correctly for the data, the data will be too.  But if Header gets smaller then we need to align things such that the start of the _data_ is at the right alignment...
Right. There are two ways we can make progress here, given that constraint.

Path #1: Only use smaller headers as long as sizeof(Header) >= alignof(ElementType). That should still give us the bulk of the benefits on B2G: there, alignof(void*)==4, and I assume that most our arrays have alignof(ElementType)==alignof(void*), so we could still use uint16 headers without any alignment problems, as then sizeof(Header) == 2*sizeof(uint16) == 4. But we couldn't use uint8 headers very often.

Path #2: Put the length and capacity fields at the _end_ of the array storage, instead of at the beginning. In other words, turn the header into a footer. That would remove alignment worries; we would now only have to ensure alignment of the footer, which is doable while proving that the memory overhead is small (idea: if the alignment padding is not negligibly small compared to the array's size, then that means that the array is small, therefore we can use a small footer with small alignment, so the problem does not exist). The Possible concern (voiced by Nathan on #developers): that could worsen the consequences of buffer overruns.

In any case, what's needed here is not for someone to jump in and write a patch, but rather, for someone to do measurements:
 - what is the distribution of alignof(ElementType)?
 - what is the distribution of array capacities?
 - how far would Path #1 take us?
 - etc, etc.

The instrumentation patch of bug 1004098 might be a starting point. It might also not be correct.
Whiteboard: [MemShrink] → [MemShrink:P2]
> Most of our arrays are of capacity smaller than 32k, so they could use
> uint16 instead of uint32 for their length and capacity stored in their
> header.
> 
> Doing so would save 4 bytes per header i.e. about 70k per tab.

It's more complicated than that.

For nsTArray, we have the header and then |capacity| elements, which sum to take up |n| bytes. |capacity| is usually chosen such that |n| is a power of two, which is good.

|capacity| is typically bigger than |length|, in which case we have some unused bytes. In any array with more than 4 unused bytes, a smaller header won't make any difference. It'll only make a difference when the array is very nearly full, in which case a smaller header might save you from having to reallocate and double the size.

For nsAutoTArray, shrinking the header does give immediate benefits.
Ah, thanks for the explanation. I didn't realize that.

That means that the argument that I gave in bug 1004098 comment 21 was possibly wrong. There, Benjamin asked: given that we're switching the nsTArray interface to size_t, should we also switch its storage type to size_t? And I replied: no, because that would increase memory usage significantly. But according to the same argument has you explained, that might not be the case.
> For nsAutoTArray, shrinking the header does give immediate benefits.

Could you elaborate on that?
oh, sorry. I read "does NOT" instead of "does". We agree :-).
And so, the argument given in bug 1004098 comment 21 does hold at least to the extend that a sufficiently high proportion of our arrays as autoarrays. (That would be useful to measure).
(In reply to Benoit Jacob [:bjacob] from comment #7)
> And so, the argument given in bug 1004098 comment 21 does hold at least to
> the extend that a sufficiently high proportion of our arrays as autoarrays.
> (That would be useful to measure).

almost all if not all of the AutoArrays should be on the stack though, in which this wouldn't matter a whole lot.
The style system data structures described in bug 988266 have autoarrays in hashtable entries (because if the array is empty there is no entry at all, so using an autoarray in fact makes sense).
So I'm still working on the instrumentation to answer these questions, which I hope to post here in a few days, but here are some preliminary results:

 - among all array headers in memory at a given time, the proportion of autoarray inline headers is.... take a guess... two thirds!

 - the majority of arrays have element alignment equal to pointer alignment.

 - The "footer trick" described above is not worth it.

This is going to mean that there is one, reasonably easy, thing that is worth doing here: For AutoArrays where the template-parameter length is less than 32k, use uint16 for the inline header. Do not bother about uint8. Only both about AutoArray inline headers. Only expect significant gains on 32bit platforms, not on 64bit platforms. That should give us the majority of the possible gains to be made here, with only a minority of the effort.
s/Only both/Only bother/
That plan sounds very reasonable!
Severity: normal → S3
You need to log in before you can comment on or make changes to this bug.

Attachment

General

Creator:
Created:
Updated:
Size: