171246 - Replace nsDeque ( 48 + overhead bytes "58") with nsVoidArray (12 + overhead bytes) +4 +32

Status: RESOLVED WONTFIX

(Core :: DOM: HTML Parser, defect)

Description

[harishd]

...or create a wrapper class and make nsDeque light wight

Comment 1

[Alec Flett]

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

Comment 2

[Alec Flett]

consumers: http://lxr.mozilla.org/mozilla/search?string=nsDeque

Comment 3

[harishd]

That's wierd...I submitted the bug only once and I'm not sure how it ended up in
two places.

typo: wight => weight :->

Comment 4

[timeless]

presumably the biggest weight is void*           mBuffer[8]; (32bytes)
the reason this exists is to save an alloc in average low use cases.  Can
someone post usage patterns so I can examine them?
How much stuff is in your deque on average?
How often do you never grow the deque?
How many deques does parser create?

One way to get some numbers would be to define DEBUG_rickg in nsDeque.cpp, add
an extra deque to nsAppShell and put a breakpoint near it. Then examine mCaps
when it reaches the destructor.

Comment 5

[harishd]

Parser creates 
1) One deque for every tokenizer ( pretty much all the tokens that parser
creates live in this deque ).
2) One deque for every parser node that contains attributes! ( BAAAAAA... ).
3) Two deques for every CNavDTD ( for a few tokens that need temporary storage ).
4) One deque in nsParserService ( stores a couple of entries ).
5) One deque for every nsDTDContext ( this deque should be under DEBUG flag ).

Comment 6

[Alec Flett]

wow! it sounds like 2) is the most important thing to fix here. It would be
interesting to contemplate related ideas for this case like:
1) measuring how big (i.e. element count) the nsDeque usually gets.. i.e. does
the nsDeque hold a list of all attributes in the parser node? 
2) Does the parser node contain a pointer to an nsDeque, or a nsDeque directly?
As mentioned in
http://www.mozilla.org/performance/footprint-reduction-techniques.html#member_pointers
maybe we could at least save ourselves 4 bytes and an extra heap allocation?
3) maybe we just want to replace THIS case with an nsVoidArray? The other cases
seem like you're not creating that many nsDeques - 4-10 per document is what I'm
reading, does that sound right?
4) maybe we should be arena-allocating the nsDeques, especially since there are
hundreds (or thousands?) of parser nodes in a document - it could save us
hundreds (or thousands) of 58-byte allocations. What's the lifetime of the
nsDeques? of the parser nodes?

Comment 7

[timeless]

(comments are without reading alecf's, sorry)
For reference, dbradley indicates std::deque is 20bytes, the difference is that
it doesn't have a buffer to save first malloc.

Ok, what are the life spans?
1) I'd imagine this is temporary and goes away when parser finishes parsing a page
2) Do these nodes last until the dom node is destroyed?
3) How many CNavDTD's are there, and how often do you create them? a few tokens
is probably a speed win in the current system since you save a malloc.
4) a couple of entries as in 3 it's probably a speed win saving a malloc
5) I don't think we care about debug :)

One thing I could probably do is use an arena or something, however i'm not sure
that it would be faster than malloc, it might be, and i could use deques to
store them, which would be fun.

1. I can't figure out how you got nsVoidArray to be 8bytes.
145     PRUint32 mBits;
150     PRInt32 mCount;
155     void*   mArray[1];

Using a voidarray as a deque will require at least an origin field, actually
using it will require an array. Accesses to things like Size cost a bit more
(perf). And your initial size is nearly the same as the nsDeque. Surpsingly
enough, if I can figure out where the overhead comes from for nsDeque, i'd say
it has the same footprint as nsVoidArray.

jkeiser points out that nsVoidArray has virtual markers (required for
nsAutoVoidArray) which means there's a bit more space there.
<rocWork> timeless: nsVoidArray is a vtable ptr plus a "Impl*" pointer ... the
Impl contains two words plus the actual array of void*s

So assuming the consumers need 1-8 items on average, the Deque really isn't bad.

So back to how many things are in your average node?

I think quite a few nodes will have at least one thing, <a href>, <script src>,
<img src>, and most things will not have more than 8.

Comment 8

[kinmoz]

For the Editor world ...

Each Composer, Mail Compose, and text widget, creates an editor ... each editor
creates a transaction manager ... each transaction manager creates 3 deques (do,
undo, and redo stacks) right off the bat ... the size these stacks grow to
depends on the number of undoable edits the user has triggered. The number of
undoable edits is currently unbounded ... there are some things that
occassionally clear the stacks, like switching back and forth between normal
edit and source edit in composer, and setting the value on a text widget via JS.

Also, any transactions that have aggregated children also have undo and redo
stacks (deques) though they are only created when needed.

Comment 9

[harishd]

>1) measuring how big (i.e. element count) the nsDeque usually gets.. i.e. does
> the nsDeque hold a list of all attributes in the parser node?

Yes the deque holds an attribute list pertaining to that element.

>2) Does the parser node contain a pointer to an nsDeque, or a nsDeque directly?
>As mentioned in
>http://www.mozilla.org/performance/footprint-reduction-techniques.html#member_pointers
>maybe we could at least save ourselves 4 bytes and an extra heap allocation?

Parser node holds a pointer to nsDeque. Using nsDeque directly could save us 4
bytes but using nsVoidArray instead would save us lot more.

>3) maybe we just want to replace THIS case with an nsVoidArray? The other cases
>seem like you're not creating that many nsDeques - 4-10 per document is what >I'm
reading, does that sound right?

Yeah...that's about right.

>4) maybe we should be arena-allocating the nsDeques, especially since there are
>hundreds (or thousands?) of parser nodes in a document - it could save us
>hundreds (or thousands) of 58-byte allocations. What's the lifetime of the
>nsDeques? of the parser nodes?

The life time of the nsDeque, in the parser node, is equal to the life time of
the parser node. A parser node can live longer if it contained residual style
information!

Comment 10

[harishd]

>2) Do these nodes last until the dom node is destroyed?

Nope...these nodes are not to be confused with DOM nodes.

>3) How many CNavDTD's are there, and how often do you create them? a few tokens
>is probably a speed win in the current system since you save a malloc.

I don't have this number on top of my head...but I don't believe too many
CNavDTDs get created. 

>5) I don't think we care about debug :)

Yes ( note to self: Move nsDTDContext->nsDeque under DEBUG flag )

>1. I can't figure out how you got nsVoidArray to be 8bytes.
>145     PRUint32 mBits;
>150     PRInt32 mCount;
>155     void*   mArray[1];

All I did was sizeof(nsVoidArray) and it said 8 :-<

>So back to how many things are in your average node?
>I think quite a few nodes will have at least one thing, <a href>, <script src>,
><img src>, and most things will not have more than 8.
You're probably right. However, nsDeque, in the parser node, is heap allocated
and may be that can be arena allocated.

Comment 11

[harishd]

Somehow, the summary that timeless added got changed to the old summary. 

Comment 12

[Alec Flett]

ok, harish and I talked this out, and here's how this works:

each tag results in a parser node, which has a pointer to a nsDeque that holds a
list of zero or more attributes. Closing tags also include this pointer, but it
is always null.

What we're going to do instead is split the parser nodes into two seperate
classes, probably something like nsParserNode and nsParserStartNode. When a tag
is opened, we'll create an nsParserStartNode, and when it is closed, we'll
create a basic nsParserNode. The nsParserStartNode will now have an nsDeque
right in the object instead of having a pointer to it, and the nsParserNode
won't have any pointer at all. This should increase the size of the start nodes
by sizeof(nsDeque)-4, and decrease the size of the end nodes by 4. however,
since the start nodes always had a nsDeque pointer to begin with, we're actually
saving 4 bytes because we no longer have the pointer.

The other bonus of this is that since ParserNodes are arena allocated with a
nsFixedSizedAllocator(), and since nsDeques are now a part of parser nodes, the
nsDeques will live in the arena as well. This will save us allocator overhead,
and might even speed us up a little because we'll be thrashing the heap less.

Comment 13

[harishd]

Attachment: patch v1.0 [ Not a final patch! - needs testing etc. ]

Comment 14

[Alec Flett]

any word on this bug? This looked like a good footprint win but there hasn't
been any real activity since october...

Comment 15

[harishd]

Alec: I forgot to mention that the proposed patch ( based on comment #12 ) is
also a part of the patch in bug 177994 ( fix checked in ). However, I haven't
replaced nsDeque with nsVoidArray in the parser node.

Comment 16

[Alec Flett]

awesome! thanks for the update (and bug number!)

Comment 17

[Keith Schwarz [:kschwarz]]

What is the current status of this bug now that we're working on eliminating nsVoidArray (Bug 474369)?  Do we want to get rid of nsDeque as well in favor of nsTArray?  Should we just mark this bug as closed?

Comment 18

[Robert O'Callahan (:roc) (email my personal email if necessary)]

All remaining uses of nsDeque in the parser will probably go away when hsivonen's HTML5 parser lands. There are a few other users of nsDeque but I doubt they're significant for memory consumption. Some kind of nsTDeque<T> and nsAutoTDeque<T,N> would be nice for the remaining users, I guess, but doesn't seem like a high priority ... it could be based on the nsTArray implementation, although directly including an nsTArray member probably is the wrong way to go.

Comment 19

[Ryan VanderMeulen [:RyanVM]]

roc/hsivonen, is this WONTFIX at this point?

Comment 20

[Robert O'Callahan (:roc) (email my personal email if necessary)]

!