Closed Bug 1012456 Opened 6 years ago Closed 5 years ago

[jsdbg2] Debugger.Memory should provide a function for taking a census of debuggee compartments

Categories

(Core :: JavaScript Engine, defect)

defect
Not set

Tracking

()

RESOLVED FIXED
mozilla34

People

(Reporter: jimb, Assigned: jimb)

References

(Blocks 1 open bug)

Details

Attachments

(8 files, 9 obsolete files)

1.18 KB, patch
sfink
: review+
jimb
: checkin+
Details | Diff | Splinter Review
66.57 KB, patch
Details | Diff | Splinter Review
8.18 KB, text/plain
Details
714 bytes, text/plain
Details
7.17 KB, text/plain
Details
3.55 KB, patch
terrence
: review+
jimb
: checkin+
Details | Diff | Splinter Review
33.88 KB, patch
terrence
: review+
jimb
: checkin+
Details | Diff | Splinter Review
15.17 KB, patch
terrence
: review+
jimb
: checkin+
Details | Diff | Splinter Review
Debugger should provide a method that produces an accurate count of the objects in the debuggee compartments, sorted into various useful categories.

As a first cut, the categories may be fixed, but the interface should evolve to allow more flexibility.

It may be helpful to conduct a census as part of a dominator tree computation, since both entail traversing the heap, and the dominator tree computation can provide retained sizes to the census.
Here's some draft documentation.

Debugger.Memory
===============

`Debugger` can survey the debuggee's memory usage in various ways:

- It can find the path by which a given item is referenced, either from a
  specific starting point, or from any debuggee global.

- It can compute the *retained size* of an item: the total size of all
  items that are reachable only through that item—and thus would be
  freed if the given item were freed.

- It can compute a *census* of items in debuggee compartments, categorizing
  items in various ways, yielding item counts, storage consumed, and "top
  N" item lists for each category.

In this documentation, the term *item* refers to anything that occupies memory
in the browser, including items like JavaScript objects and strings, scripts,
and DOM nodes, which are specified in web standards like HTML5 and the
ECMAScript standard, and should be familiar to web developers; as well as data
structures the browser uses internally to implement those features.


Censuses
--------

A *census* is a complete traversal of the graph of all reachable items
belonging to a particular `Debugger`'s debuggee compartments, producing a
count of those items, broken down by various criteria. `Debugger` can perform
a census as part of the same heap traversal that computes
[retained sizes][retsz], or as an independent operation.

Because performing a census requires traversing the entire graph of objects in
debuggee compartments, it is an expensive operation. On developer hardware in
2014, traversing a memory graph containing roughly 130,000 nodes and 410,000
edges took roughly 100ms. The traversal itself temporarily allocates one a
hash table entry per node, roughly two address-sized words, in addition to the
per-category counts, whose size depends on the number of categories.

`Debugger.Memory.prototype.census()`
:   Carry out a census of the debuggee compartments' contents. Return an
    object of the form:

    <pre class='language-js'><code>
    { "object": { <i>class</i>: <i>tally</i>, ... },
      "string": <i>tally</i>,
      "script": <i>tally</i>,
      "types": <i>tally</i>,
      "shapes": <i>tally</i>,
      "other": <i>tally</i>
    }
    </code></pre>

    Each <i>tally</i> has the form:

    <pre class='language-js'><code>
    { "count": <i>count</i>,
      "size": <i>size</i>,
      "retainedCount": <i>retainedCount</i>,
      "retainedSize": <i>retainedSize</i>
    }
    </code></pre>

    where <i>count</i> is the number of items in the category, and <i>size</i>
    is the items' total size, in bytes. If the census was taken as part of
    retained size computation, the tally will include <i>retainedCount</i> and
    <i>retainedSize</i> properties, which give the number and total byte size
    of all items retained by category members.

    The `"object"` property's value contains the tallies of JavaScript
    objects, broken down by their ECMAScript `[[Class]]` internal property
    values. Each <i>class</i> is a string.

    The `"string"` property's value tallies the debuggee's strings. (Note that
    this tally does not include strings shared with other web pages or browser
    code. The browser may permit such sharing, to save memory, since it cannot
    be detected by content JavaScript code.)

    The `"script"` property's value tallies the in-memory representation of
    JavaScript code.

    The `"types"` property's value tallies the size of JavaScript type
    metadata, maintained by the just-in-time compilers to guide code generation.

    The `"shapes"` property's value tallies the size of shared JavaScript
    object shape metadata.


Memory Use Analysis Exposes Implementation Details
--------------------------------------------------

Memory analysis may yield surprising results, because browser implementation
details that are transparent to content JavaScript often have visible effects
on memory consumption. Web developers need to know their pages' actual memory
consumption on real browsers, so it is correct for the tool to expose these
behaviors, in a way that helps developers make decisions about their own code.

This section covers some areas where Firefox's actual behavior deviates from
what one might expect, given a detailed but naïve understanding of the web
platform.


### Objects

SpiderMonkey objects usually use less memory than the naïve "table of
properties with attributes" model would suggest. For example, it is typical
for many objects to have identical sets of properties, where only the
properties' values vary from one object to the next. To accomodate this
efficiently, SpiderMonkey objects with identical sets of properties share
their property metadata; only the values are stored directly in the object.

Array objects may also be optimized, if the set of live indices is dense.


### Strings

SpiderMonkey has three representations of strings:

- Normal: the string's text is counted in its size.

- Substring: the string is a substring of some other string, and points to
  that string for its storage. This representation may result in a small
  string retaining a very large string. However, the memory consumed by the
  string itself is a constant, since it is simply a reference to the larger
  string, a start position, and a length.

- Concatenations: When asked to concatenate two strings, SpiderMonkey may
  elect to avoid copying, and represent the result as a pointer to the two
  original strings. Again, such a string retains other strings, but the memory
  consumed by the string itself is a constant, since it is simply a pair of
  pointers.

SpiderMonkey converts strings from the more complex representations to the
simpler ones when it pleases. Such conversions usually increase memory
consumption.


### Scripts

SpiderMonkey has a complex, hybrid representation of JavaScript code. There
are four representations kept in memory:

- _Source code_. SpiderMonkey retains a copy of most JavaScript source code.

- _Compressed source code_. SpiderMonkey compresses JavaScript source code,
  and de-compresses it on demand. Heuristics determine how long to retain the
  uncompressed code.

- _Bytecode_. This is SpiderMonkey's parsed representation of JavaScript.
  Bytecode can be interpreted directly, or used as input to a just-in-time
  compiler. Source is parsed into bytecode on demand; functions that are never
  called are never parsed.

- _Machine code_. SpiderMonkey includes several just-in-time compilers, each
  of which translates JavaScript source or bytecode to machine code.
  Heuristics determine which code to compile, and how. Machine code may be
  dropped in response to memory pressure, and regenerated as needed.

Furthermore, SpiderMonkey tracks which types of values have appeared in
variables and object properties. This type information can be large.

In a census, all the various forms of JavaScript code are placed in the
`"script"` category. Type information is accounted to the `"types"` category.
Nick, I'd love your comments on the above.
Flags: needinfo?(nfitzgerald)
Questions For Nick
------------------

- What would it take to compute retained sizes for categories? It's not just
  the sum of the retained sizes of the members of the category, because
  category members may dominate each other, and thus share dominated
  structure.

- Are category retained sizes even useful? "Wow, everything belongs to objects."
  No surprise there === no bits of information conveyed.
(In reply to Jim Blandy :jimb from comment #1)
> ### Strings
> 
> SpiderMonkey has three representations of strings:

Plus atoms.

> ### Scripts
> 
> SpiderMonkey has a complex, hybrid representation of JavaScript code. There
> are four representations kept in memory:
> 
> - _Source code_. SpiderMonkey retains a copy of most JavaScript source code.
> 
> - _Compressed source code_. SpiderMonkey compresses JavaScript source code,
>   and de-compresses it on demand. Heuristics determine how long to retain the
>   uncompressed code.
> 
> - _Bytecode_. This is SpiderMonkey's parsed representation of JavaScript.
>   Bytecode can be interpreted directly, or used as input to a just-in-time
>   compiler. Source is parsed into bytecode on demand; functions that are
> never
>   called are never parsed.

Plus the JSFunction, JSScript, and LazyScript objects themselves.


Atoms, (compressed and uncompressed) script sources, and bytecode are all shared per-runtime. I don't know how important that is for the devtools representation. I think it's not entirely irrelevant, at least: for complex applications consisting of multiple iframes (and, in the future, realms), per-runtime sharing can make a meaningful difference in memory usage, after all.
(In reply to Till Schneidereit [:till] from comment #4)
> (In reply to Jim Blandy :jimb from comment #1)
> > ### Strings
> > 
> > SpiderMonkey has three representations of strings:
> 
> Plus atoms.

You mean, atoms are relevant to discussions of memory use because they're shared? I touched on that in the description of the "string" census tally, but clearly the "exposed implementation details" section is the right place to cover that.

> Plus the JSFunction, JSScript, and LazyScript objects themselves.

Right --- those aren't forgotten, they're omitted because this isn't the place to describe all that in detail.


> Atoms, (compressed and uncompressed) script sources, and bytecode are all
> shared per-runtime. I don't know how important that is for the devtools
> representation. I think it's not entirely irrelevant, at least: for complex
> applications consisting of multiple iframes (and, in the future, realms),
> per-runtime sharing can make a meaningful difference in memory usage, after
> all.

That sharing could be a problem.

If we include shared data in a compartment's count, then that would give the developer the mistaken impression that not using that data would actually reduce memory consumption --- when in fact other users would keep it alive anyway. Using data that's going to be in memory anyway is a *win*, the opposite of what we want to discourage.

If we don't include shared data in a compartment's count, but in fact it's not actually shared, and that compartment is indeed the data's only user (which I'll bet is not uncommon), then we commit the opposite error: not helping developers reduce usage.
(In reply to Jim Blandy :jimb from comment #1)
> `Debugger` can survey the debuggee's memory usage in various ways:
>
> - It can find the path by which a given item is referenced, either from a
>   specific starting point, or from any debuggee global.
>
> - It can compute the *retained size* of an item: the total size of all
>   items that are reachable only through that item&mdash;and thus would be
>   freed if the given item were freed.
>
> - It can compute a *census* of items in debuggee compartments, categorizing
>   items in various ways, yielding item counts, storage consumed, and "top
>   N" item lists for each category.

It will also be able to take snapshots, but I'm not sure how much we want to document things that aren't implemented yet.

> A *census* is a complete traversal of the graph of all reachable items
> belonging to a particular `Debugger`'s debuggee compartments, producing a
> count of those items, broken down by various criteria. `Debugger` can perform
> a census as part of the same heap traversal that computes
> [retained sizes][retsz], or as an independent operation.

I expand on this below, but I don't think retained sizes should be part of a census. I think a census should be purely aggregate / summary info, and if we want details of specific objects, we should take a snapshot.

> `Debugger.Memory.prototype.census()`

I think this should be renamed `takeCensus`.

>    The `"object"` property's value contains the tallies of JavaScript
>    objects, broken down by their ECMAScript `[[Class]]` internal property
>    values. Each <i>class</i> is a string.

We absolutely need to break objects down further than that. We need to break them down via prototype and constructor, and maybe even shape if we can find a way to help developers understand what shapes are. Perhaps by the ordered list of properties?

Fixing this fixes the "oh crap everything is an Object" problem.

> ### Strings
>
> SpiderMonkey has three representations of strings:
>
> - Normal: the string's text is counted in its size.
>
> - Substring: the string is a substring of some other string, and points to
>   that string for its storage. This representation may result in a small
>   string retaining a very large string. However, the memory consumed by the
>   string itself is a constant, since it is simply a reference to the larger
>   string, a start position, and a length.
>
> - Concatenations: When asked to concatenate two strings, SpiderMonkey may
>   elect to avoid copying, and represent the result as a pointer to the two
>   original strings. Again, such a string retains other strings, but the
> memory
>   consumed by the string itself is a constant, since it is simply a pair of
>   pointers.
>
> SpiderMonkey converts strings from the more complex representations to the
> simpler ones when it pleases. Such conversions usually increase memory
> consumption.

I think we shouldn't be quick to gloss over string representations in the API we expose. I'd rather do the glossing over as late as possible in the UI. This would enable us to have a chrome/platform mode that is beneficial to Firefox and Gecko hackers and not just web developers. Advanced webdevs might even dig in and learn more about our internals and this could be of use to them. I just don't want to spec APIs that make it hard to expose this stuff later on. I'd rather do that as late as possible at the UI layer.

>
>
> ### Scripts
>
> SpiderMonkey has a complex, hybrid representation of JavaScript code. There
> are four representations kept in memory:
>
> - _Source code_. SpiderMonkey retains a copy of most JavaScript source code.
>
> - _Compressed source code_. SpiderMonkey compresses JavaScript source code,
>   and de-compresses it on demand. Heuristics determine how long to retain the
>   uncompressed code.
>
> - _Bytecode_. This is SpiderMonkey's parsed representation of JavaScript.
>   Bytecode can be interpreted directly, or used as input to a just-in-time
>   compiler. Source is parsed into bytecode on demand; functions that are
> never
>   called are never parsed.
>
> - _Machine code_. SpiderMonkey includes several just-in-time compilers, each
>   of which translates JavaScript source or bytecode to machine code.
>   Heuristics determine which code to compile, and how. Machine code may be
>   dropped in response to memory pressure, and regenerated as needed.
>
> Furthermore, SpiderMonkey tracks which types of values have appeared in
> variables and object properties. This type information can be large.
>
> In a census, all the various forms of JavaScript code are placed in the
> `"script"` category. Type information is accounted to the `"types"` category.

Ditto regarding scripts. We should expose all this + JSScript/LazyScript/etc at the Debugger API layer, and only gloss over it in the UI layer. This provides the most flexibility.

(In reply to Jim Blandy :jimb from comment #3)
> Questions For Nick
> ------------------
>
> - What would it take to compute retained sizes for categories? It's not just
>   the sum of the retained sizes of the members of the category, because
>   category members may dominate each other, and thus share dominated
>   structure.

I think this is the wrong approach; dominator trees are much too heavy, and should be reserved for snapshots. However, there are interesting computations we can do with the "type graph" (or "category graph" using our terminology for census groups; might have to restrict to only certain categories). The nodes in the graph are distinct categories, depending on whether we use a "points-from" or "points-to" type graph, edges of the form (A, B) exist whenever a thing of type A is referenced from or references a thing of type B in the heap, respectively.

Here is a really cool paper that uses the type points-from graph to find memory leaks in Java with a tool they named Cork: http://www.cs.utexas.edu/ftp/techreports/tr06-07.pdf

Because it is the points-from graph, they can just keep walking along their graph while the edges' rank (growth in number of references) is positive and they find the leak's containing structure (ie likely to be the structure the dev is familiar with as opposed to some framework or library's structure).

Alternatively, I think we could capture the points-to graph and run a dominator tree calculation on that graph, which would tell us retaining structures rather than containing structures.

Not sure which is more usable, I feel we would have to just experiment. My intuition says that the paper's approach is great for finding leaks (especially when they are very slow leaks), while computing the dominator tree on the type graph would be good for optimizing memory overhead.

I'm in a back and forth with the authors of the Cork paper, plan on asking them more about the idea of computing DT on the type points-to graph and also just learning more about the "slices" aka the sub graphs whose type counts are increasing.

Either way, the benefit of working with type graphs is that they are much smaller than the full heap graph, while being a very good approximation / summarization of the heap graph. We can do computations on the type graph that would be too expensive to do in a census on the full heap graph (like the dominator tree computation).

> - Are category retained sizes even useful? "Wow, everything belongs to
> objects."
>   No surprise there === no bits of information conveyed.

See my comments above about a) needing better breakdowns than just "Object" and [[Class]], and b) dominator trees being too expensive for censuses which we want to take at regular intervals.

That said, I think that with a solution for (a), category retained sizes would be very useful; but it belongs in a snapshot, not a census.
Flags: needinfo?(nfitzgerald)
(In reply to Nick Fitzgerald [:fitzgen] from comment #6)
> It will also be able to take snapshots, but I'm not sure how much we want to
> document things that aren't implemented yet.

Absolutely. These are the docs I want to land with the patch, so it only
describes what I want to land.

> > A *census* is a complete traversal of the graph of all reachable items
> > belonging to a particular `Debugger`'s debuggee compartments, producing a
> > count of those items, broken down by various criteria. `Debugger` can perform
> > a census as part of the same heap traversal that computes
> > [retained sizes][retsz], or as an independent operation.
> 
> I expand on this below, but I don't think retained sizes should be part of a
> census. I think a census should be purely aggregate / summary info, and if
> we want details of specific objects, we should take a snapshot.

Completely agree.



> > `Debugger.Memory.prototype.census()`
> 
> I think this should be renamed `takeCensus`.

Done.


> >    The `"object"` property's value contains the tallies of JavaScript
> >    objects, broken down by their ECMAScript `[[Class]]` internal property
> >    values. Each <i>class</i> is a string.
> 
> We absolutely need to break objects down further than that. We need to break
> them down via prototype and constructor, and maybe even shape if we can find
> a way to help developers understand what shapes are. Perhaps by the ordered
> list of properties?
> 
> Fixing this fixes the "oh crap everything is an Object" problem.

Right; as I say in comment 0, we really want takeCensus to take a parameter
that describes how to categorize things. There are so many groupings we
care about. I have some thoughts on that API that I should write down.

But I think we need to show something running, in short order. This seems
enough for a get-something-landed patch that has some value over "no tool".


> > ### Strings
> >
> > SpiderMonkey has three representations of strings:
> >
> > - Normal: the string's text is counted in its size.
> >
> > - Substring: the string is a substring of some other string, and points to
> >   that string for its storage. This representation may result in a small
> >   string retaining a very large string. However, the memory consumed by the
> >   string itself is a constant, since it is simply a reference to the larger
> >   string, a start position, and a length.
> >
> > - Concatenations: When asked to concatenate two strings, SpiderMonkey may
> >   elect to avoid copying, and represent the result as a pointer to the two
> >   original strings. Again, such a string retains other strings, but the
> > memory
> >   consumed by the string itself is a constant, since it is simply a pair of
> >   pointers.
> >
> > SpiderMonkey converts strings from the more complex representations to the
> > simpler ones when it pleases. Such conversions usually increase memory
> > consumption.
> 
> I think we shouldn't be quick to gloss over string representations in the
> API we expose. I'd rather do the glossing over as late as possible in the
> UI. This would enable us to have a chrome/platform mode that is beneficial
> to Firefox and Gecko hackers and not just web developers. Advanced webdevs
> might even dig in and learn more about our internals and this could be of
> use to them. I just don't want to spec APIs that make it hard to expose this
> stuff later on. I'd rather do that as late as possible at the UI layer.

I think this can be handled in the not-yet-specified argument
to takeCensus. I was thinking you could say:

    dbg.memory.takeCensus({ by: 'type',
                            bins: { 'string': { by: 'representation' } }
                            else: 'drop'
                          })

and get a census of only strings, broken down by atom / flat / dependent /
rope / etc. I haven't thought through that expression structure yet;
imagine something much cooler. :)

Or:

    dbg.memory.takeCensus({ by: 'class',
                            bins: { 'RegExp': true }
                            else: 'drop'
                          })

We might have operators like:

    dbg.memory.takeCensus({ by: 'allocationSite' })

that just group things by allocation site; or

    dbg.memory.takeCensus({ by: 'allocationStack' })

to take the whole stack at allocation time into account.

And perhaps even:

    dbg.memory.takeCensus([ { by: 'allocationSite' },
                            { by: 'type' }
                          ])

where [the array] is like a cross-product operator, categorizing by
allocation site and type simultaneously. For more detail:

    dbg.memory.takeCensus([ { by: 'allocationSite' },
                            { by: 'type', bins: { 'object': { by: 'class' } } }
                          ])

to do the same, but take the objects and break them down by class as well.

The shape of the return value would be determined by the shape of the
categorizer argument.

In general, there are lots of different axes of interest; we want to be
able to define new axes over time; and we don't want them all in every
case. So there needs to be a way to choose.

I think this could be implemented in a performant way.

Details aside, I think we have to have a growth path that lets us start
coarse and get finer over time, so that we can land as we go, and refine as
the need arises. I'm just aiming for the dumbest useful C++ patch, to get
landed. If you think we could get more detail out of something dumber, then
by all means let's do that.


> (In reply to Jim Blandy :jimb from comment #3)
> > Questions For Nick
> > ------------------
> >
> > - What would it take to compute retained sizes for categories? It's not just
> >   the sum of the retained sizes of the members of the category, because
> >   category members may dominate each other, and thus share dominated
> >   structure.
> 
> I think this is the wrong approach; dominator trees are much too heavy, and
> should be reserved for snapshots. However, there are interesting
> computations we can do with the "type graph" (or "category graph" using our
> terminology for census groups; might have to restrict to only certain
> categories). The nodes in the graph are distinct categories, depending on
> whether we use a "points-from" or "points-to" type graph, edges of the form
> (A, B) exist whenever a thing of type A is referenced from or references a
> thing of type B in the heap, respectively.
> 
> Here is a really cool paper that uses the type points-from graph to find
> memory leaks in Java with a tool they named Cork:
> http://www.cs.utexas.edu/ftp/techreports/tr06-07.pdf
> 
> Because it is the points-from graph, they can just keep walking along their
> graph while the edges' rank (growth in number of references) is positive and
> they find the leak's containing structure (ie likely to be the structure the
> dev is familiar with as opposed to some framework or library's structure).

I don't quite understand this; I'll read the paper.
(In reply to Jim Blandy :jimb from comment #7)
> And perhaps even:
> 
>     dbg.memory.takeCensus([ { by: 'allocationSite' },
>                             { by: 'type' }
>                           ])
> 
> where [the array] is like a cross-product operator, categorizing by
> allocation site and type simultaneously. For more detail:
> 
>     dbg.memory.takeCensus([ { by: 'allocationSite' },
>                             { by: 'type', bins: { 'object': { by: 'class' }
> } }
>                           ])
> 
> to do the same, but take the objects and break them down by class as well.

Sounds good; I think we definitely need this array-of-by-objects-to-get-a-cross-product or at least the ability to get multiple different types of grouping from a single census (ie a single traversal). The UI we want to create has the ability to change what the table is grouping by, and if we want that to work with censuses we've already taken then we have to have it. Imagine selecting some part of the memory graph from the past, changing the grouping, and then you get a message telling you that we didn't collect that information at that time, try again. :(

> In general, there are lots of different axes of interest; we want to be
> able to define new axes over time; and we don't want them all in every
> case. So there needs to be a way to choose.
> 
> I think this could be implemented in a performant way.
> 
> Details aside, I think we have to have a growth path that lets us start
> coarse and get finer over time, so that we can land as we go, and refine as
> the need arises. I'm just aiming for the dumbest useful C++ patch, to get
> landed. If you think we could get more detail out of something dumber, then
> by all means let's do that.

Sounds good to me.

A final note: I think we should do the grouping not in the top level parameter but under a property (such as "grouping") so that we have room for configuring other parts of the census, like the types graph stuff, if we do end up doing that.

  dbg.memory.takeCensus({
    grouping: [ { by: 'allocationSite' },
                { by: 'type', bins: { 'object': { by: 'class' }
              ],
    typesGraph: {
      foo: bar
    },
    ...
  });

We'd likely group the types graph by only allocation site or only prototype, but *not* all the other groupings that the census is doing because they just might not apply or might balloon the number of nodes in the type graph more than we'd like. We should make sure we have room for evolving the API to allow configuring that stuff down the line.

> > (In reply to Jim Blandy :jimb from comment #3)
> > > Questions For Nick
> > > ------------------
> > >
> > > - What would it take to compute retained sizes for categories? It's not just
> > >   the sum of the retained sizes of the members of the category, because
> > >   category members may dominate each other, and thus share dominated
> > >   structure.
> > 
> > I think this is the wrong approach; dominator trees are much too heavy, and
> > should be reserved for snapshots. However, there are interesting
> > computations we can do with the "type graph" (or "category graph" using our
> > terminology for census groups; might have to restrict to only certain
> > categories). The nodes in the graph are distinct categories, depending on
> > whether we use a "points-from" or "points-to" type graph, edges of the form
> > (A, B) exist whenever a thing of type A is referenced from or references a
> > thing of type B in the heap, respectively.
> > 
> > Here is a really cool paper that uses the type points-from graph to find
> > memory leaks in Java with a tool they named Cork:
> > http://www.cs.utexas.edu/ftp/techreports/tr06-07.pdf
> > 
> > Because it is the points-from graph, they can just keep walking along their
> > graph while the edges' rank (growth in number of references) is positive and
> > they find the leak's containing structure (ie likely to be the structure the
> > dev is familiar with as opposed to some framework or library's structure).
> 
> I don't quite understand this; I'll read the paper.

It's a great read! Really simple/obvious in retrospect, which makes it that much more amazing :)
(In reply to Jim Blandy :jimb from comment #5)
> > > ### Strings
> > > 
> > > SpiderMonkey has three representations of strings:
> > 
> > Plus atoms.
> 
> You mean, atoms are relevant to discussions of memory use because they're
> shared? I touched on that in the description of the "string" census tally,
> but clearly the "exposed implementation details" section is the right place
> to cover that.

I meant both: they should be mentioned in the list of representations, and they're relevant to the discussion of memory use.

> 
> > Plus the JSFunction, JSScript, and LazyScript objects themselves.
> 
> Right --- those aren't forgotten, they're omitted because this isn't the
> place to describe all that in detail.

Fair point, though I think I agree with fitzgen on this.

> 
> 
> > Atoms, (compressed and uncompressed) script sources, and bytecode are all
> > shared per-runtime. I don't know how important that is for the devtools
> > representation. I think it's not entirely irrelevant, at least: for complex
> > applications consisting of multiple iframes (and, in the future, realms),
> > per-runtime sharing can make a meaningful difference in memory usage, after
> > all.
> 
> That sharing could be a problem.
> 
> If we include shared data in a compartment's count, then that would give the
> developer the mistaken impression that not using that data would actually
> reduce memory consumption --- when in fact other users would keep it alive
> anyway. Using data that's going to be in memory anyway is a *win*, the
> opposite of what we want to discourage.
> 
> If we don't include shared data in a compartment's count, but in fact it's
> not actually shared, and that compartment is indeed the data's only user
> (which I'll bet is not uncommon), then we commit the opposite error: not
> helping developers reduce usage.

I think there are three potential cases to consider for shared data:
- the data is theoretically shared, but in practice only one use site exists
- the data has multiple use sites, but all of them are from the same tab or addon
- the data has multiple use sites from multiple tabs/addons/sites. This is probably true for things like jQuery


Ideally, the census would identify how much sharing happens within an app, while ignoring the rest of the world. I.e., an app with a window and two iframes, all of which share some script, would somehow indicate that x bytes of script data are shared by three globals. I don't know how feasible this is, mind you.
(In reply to Till Schneidereit [:till] from comment #9)
> (In reply to Jim Blandy :jimb from comment #5)
> > You mean, atoms are relevant to discussions of memory use because they're
> > shared? I touched on that in the description of the "string" census tally,
> > but clearly the "exposed implementation details" section is the right place
> > to cover that.
> 
> I meant both: they should be mentioned in the list of representations, and
> they're relevant to the discussion of memory use.

Once we've dealt with the sharing, I don't understand how atoms' representation differs significantly from flat strings'.

> I think there are three potential cases to consider for shared data:
> - the data is theoretically shared, but in practice only one use site exists
> - the data has multiple use sites, but all of them are from the same tab or
> addon
> - the data has multiple use sites from multiple tabs/addons/sites. This is
> probably true for things like jQuery

Yes, this is key: it's not sufficient to know that something *can* be shared; we need to know whether it is *actually* shared, and whether it it shared with non-debuggee code.

Taking a census entails traversing the debuggees' portion of the heap. As part of that process, we could count the number of references to an object from the debuggee. If the GC could tell us the total number of edges it has found, then we could compare the two counts to see if the object was shared with non-debuggees.

Note, however, that the mutator (that is, JS) can execute between the time the GC provides its count and the time we perform the census, and the mutator can create or remove references to the shared item, so the GC count may be out of date. If debuggee code removes references, then the GC's count will be higher than the number of edges the census traversal can find, and we will incorrectly assume the item is shared with non-debuggee code.

In the case of atoms, JSAtom is a subtype of JSString, so it's impossible to catch all the places that references to an atom might be created or removed. But SharedScriptData, for example, is only pointed to by JSScript instances; I think only SaveSharedScriptData ever creates references to it, and only JSScript::finalize removes references, so it would be possible to keep an accurate reference count. Perhaps this is possible with ScriptSourceObject and ScriptSource, as well.
Thinking of SharedScriptData more:

Right now, ubi::Node doesn't treat SharedScriptData as a separate node from JSScript. For us to detect this sharing, we would need to break it out. This is doable.
Depends on: 1038315
Depends on: 1038316
Attachment #8455513 - Flags: review?(sphink)
Depends on: 1003302
Not requesting review, but this does produce simple census results for the whole JSRuntime.

Still to do:

- restrict to a given set of compartments

- provide per-[[Class]] breakdown of JSObjects
For Nick, here's a combined patch for the census, including all the prerequisite bugs. This applies on the below, with a little fuzz:

changeset:   193790:340b19c14d3d
tag:         qparent
parent:      193770:415c2a4dc778
parent:      193789:b257f50981e7
user:        Carsten "Tomcat" Book <cbook@mozilla.com>
date:        Mon Jul 14 15:14:40 2014 +0200
summary:     merge fx-team to mozilla-central a=merge
Comment on attachment 8455513 [details] [diff] [review]
Use 'using namespace' in DebuggerMemory.cpp, to avoid wrapping top-level definitions in a namespace { ... } form.

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

https://groups.google.com/forum/#!topic/mozilla.dev.platform/r-WM_8ljqK0/discussion

"""
Now that we have unified builds, writing "using namespace" in the global
scope of a .cpp file is almost as bad as writing it in a header. Regularly
build errors show up like this one:
https://tbpl.mozilla.org/php/getParsedLog.php?id=40010766&tree=Try

What's awesome about these errors is that they typically show up on some
platform but not the others and they come and go as we add files or do
things that can alter the generation of the unified .cpp files.

So, I strongly encourage everyone to stop using "using namespace".
If you really really want to use them, please put them inside the scope of
a namespace. [...]
"""
Humm. It turns out that that combined patch is a little delicate. If the GC nursery isn't empty, JS_TraceRuntime actually causes a GC, which makes the AutoCheckCannotGC in DebuggerMemory::census assert.

I think we can't treat JSRuntimes as ubi::Nodes until JS_TraceRuntime becomes more respectful. I'll try to finish up the Zone-sensitive version of this patch, which won't need the JSRuntime ubi::Node support at all.
(In reply to Nick Fitzgerald [:fitzgen] from comment #15)
> Now that we have unified builds, writing "using namespace" in the global
> scope of a .cpp file is almost as bad as writing it in a header. Regularly
> build errors show up like this one:
> https://tbpl.mozilla.org/php/getParsedLog.php?id=40010766&tree=Try

Yeah. But the rest of SpiderMonkey uses 'using namespace js' and '... JS' everywhere.
Okay, here's a fresh combined patch that avoids the JS_TraceRuntime problems above, and actually supports limiting the traversal to the debuggees:

$ cat js/src/jit-test/tests/debug/Memory-census-01.js 
var dbg = new Debugger;
print(uneval(dbg.memory.census()));

var g1 = newGlobal();
dbg.addDebuggee(g1);
print(uneval(dbg.memory.census()));

var g2 = newGlobal();
dbg.addDebuggee(g2);
print(uneval(dbg.memory.census()));

dbg.removeDebuggee(g1);
print(uneval(dbg.memory.census()));

dbg.removeDebuggee(g2);
print(uneval(dbg.memory.census()));
$ js/src/obj~/js/src/js -f js/src/jit-test/tests/debug/Memory-census-01.js 
({objects:{count:0}, scripts:{count:0}, strings:{count:0}, other:{count:0}})
({objects:{count:338}, scripts:{count:1}, strings:{count:573}, other:{count:500}})
({objects:{count:676}, scripts:{count:2}, strings:{count:573}, other:{count:1000}})
({objects:{count:338}, scripts:{count:1}, strings:{count:573}, other:{count:500}})
({objects:{count:0}, scripts:{count:0}, strings:{count:0}, other:{count:0}})
$
Attachment #8455530 - Attachment is obsolete: true
Depends on: 1038544
Here's the latest version of the Debugger.Memory.prototype.census patch, alone.
Attachment #8455529 - Attachment is obsolete: true
Nick, unless this has horrible bugs, it should be sufficient for you to start playing with. Certainly we still want categorization by Object [[Class]], and that should be easy to add.
(In reply to Jim Blandy :jimb from comment #18)
> $ js/src/obj~/js/src/js -f js/src/jit-test/tests/debug/Memory-census-01.js 
> ({objects:{count:0}, scripts:{count:0}, strings:{count:0}, other:{count:0}})
> ({objects:{count:338}, scripts:{count:1}, strings:{count:573},
> other:{count:500}})
> ({objects:{count:676}, scripts:{count:2}, strings:{count:573},
> other:{count:1000}})
> ({objects:{count:338}, scripts:{count:1}, strings:{count:573},
> other:{count:500}})
> ({objects:{count:0}, scripts:{count:0}, strings:{count:0}, other:{count:0}})
> $

Note that the reasons the strings count is the same regardless of how many globals we add is that, in a freshly created global, all the strings that exist are atoms, which are shared by all compartments. The census is written to count atoms that debuggees use, but count each one only once.
Comment on attachment 8455938 [details] [diff] [review]
Implement Debugger.Memory.prototype.census. Work in progress.

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

Very nice :)

You mention categorizing by [[Class]], and we do need that, but even more important are categorizing by constructor, prototype, and allocation site IMO.

::: js/src/doc/Debugger/Debugger.Memory.md
@@ +171,5 @@
> +
> +- What would it take to compute retained sizes for categories? It's not just
> +  the sum of the retained sizes of the members of the category, because
> +  category members may dominate each other, and thus share dominated
> +  structure.

This is a good question, and something I haven't thought about before.

Off the top of my head, we could create a temporary object that holds a reference to every node in the category, and treat it as one of our GC roots while we do the dominator tree computation. Then, its retained size should be the retained size of the category, IINM. However, this would have to be repeated per category and we couldn't share the computation with finding normal nodes' retained sizes or other categories' retained sizes.

Another option might be to compute the dominator tree of the types graph, but I'd need to think hard to make sure that there isn't a flaw in that plan.

::: js/src/vm/DebuggerMemory.cpp
@@ +119,5 @@
>      JS_PS_END
>  };
>  
>  /* static */ const JSFunctionSpec DebuggerMemory::methods[] = {
> +    JS_FN("census", DebuggerMemory::census, 0, 0),

In the docs, this is known as `takeCensus`. Should either fix the docs or the method name. I kind of prefer `takeCensus` to plain old `census`.
> You mention categorizing by [[Class]], and we do need that, but even
> more important are categorizing by constructor, prototype, and
> allocation site IMO.

Not sure if you want to push that stuff off as a follow up or in this patch. I don't really care, but it is pretty high priority, IMHO.
Okay, this version categorizes by JS type; then breaks down objects by [[Class]], and non-JS nodes by their ubi::Node class name. I agree we want constructor/prototype. It should be quick.

For what it's worth: a census takes 53ms on an Etherpad visiting a small page; and 612ms on Gmail. Below is the gmail census. Remember that objects are broken down by [[Class]], not by prototype. If you look at the patch, you can see that it's pretty easy to reconfigure the breakdowns or add new assorters.

{
  "objects": {
    "ElementPrototype": {
      "count": 2
    },
    "HTMLVideoElement": {
      "count": 3
    },
    "HTMLTableRowElement": {
      "count": 1
    },
    "TextDecoderPrototype": {
      "count": 3
    },
    "HTMLTableCellElementPrototype": {
      "count": 2
    },
    "Math": {
      "count": 2
    },
    "DOMRectReadOnlyPrototype": {
      "count": 1
    },
    "HTMLDocument": {
      "count": 3
    },
    "HTMLStyleElement": {
      "count": 2
    },
    "PerformanceNavigationPrototype": {
      "count": 1
    },
    "MimeTypeArrayPrototype": {
      "count": 2
    },
    "HTMLHeadingElementPrototype": {
      "count": 2
    },
    "HTMLBRElementPrototype": {
      "count": 1
    },
    "NavigatorPrototype": {
      "count": 2
    },
    "Uint32ArrayPrototype": {
      "count": 1
    },
    "HTMLMediaElementPrototype": {
      "count": 1
    },
    "Proxy": {
      "count": 1083
    },
    "HTMLTableRowElementPrototype": {
      "count": 2
    },
    "HTMLInputElement": {
      "count": 2
    },
    "DOMErrorPrototype": {
      "count": 3
    },
    "XMLHttpRequest": {
      "count": 1
    },
    "DOMExceptionPrototype": {
      "count": 1
    },
    "HTMLHtmlElementPrototype": {
      "count": 2
    },
    "HTMLUListElementPrototype": {
      "count": 1
    },
    "CryptoPrototype": {
      "count": 1
    },
    "HTMLHRElementPrototype": {
      "count": 1
    },
    "DOMPrototype": {
      "count": 2
    },
    "MessageEventPrototype": {
      "count": 1
    },
    "KeyboardEventPrototype": {
      "count": 1
    },
    "HTMLScriptElement": {
      "count": 98
    },
    "NodePrototype": {
      "count": 3
    },
    "HTMLIFrameElementPrototype": {
      "count": 1
    },
    "CharacterDataPrototype": {
      "count": 2
    },
    "TextPrototype": {
      "count": 2
    },
    "FocusEventPrototype": {
      "count": 1
    },
    "Error": {
      "count": 5
    },
    "Call": {
      "count": 4468
    },
    "PromisePrototype": {
      "count": 3
    },
    "HTMLUListElement": {
      "count": 2
    },
    "XPC_WN_ModsAllowed_NoCall_Proto_JSClass": {
      "count": 4
    },
    "Array": {
      "count": 20881
    },
    "HTMLButtonElement": {
      "count": 1
    },
    "CSS2Properties": {
      "count": 19
    },
    "HTMLLIElementPrototype": {
      "count": 1
    },
    "AnimationEventPrototype": {
      "count": 1
    },
    "Location": {
      "count": 1
    },
    "WindowPrototype": {
      "count": 3
    },
    "PluginArrayPrototype": {
      "count": 2
    },
    "EventTargetPrototype": {
      "count": 3
    },
    "Array Iterator": {
      "count": 7
    },
    "RegExpStatics": {
      "count": 6
    },
    "MouseEventPrototype": {
      "count": 1
    },
    "HTMLVideoElementPrototype": {
      "count": 1
    },
    "Navigator": {
      "count": 2
    },
    "HTMLTableElementPrototype": {
      "count": 1
    },
    "HTMLTextAreaElement": {
      "count": 1
    },
    "JSON": {
      "count": 2
    },
    "HTMLBodyElementPrototype": {
      "count": 2
    },
    "Promise": {
      "count": 1
    },
    "HTMLLinkElementPrototype": {
      "count": 1
    },
    "MediaQueryList": {
      "count": 2
    },
    "HTMLHeadElement": {
      "count": 1
    },
    "TextEncoderPrototype": {
      "count": 3
    },
    "String": {
      "count": 5
    },
    "HTMLDivElementPrototype": {
      "count": 2
    },
    "UIEventPrototype": {
      "count": 1
    },
    "HashChangeEventPrototype": {
      "count": 1
    },
    "RegExp": {
      "count": 474
    },
    "CSSStyleDeclarationPrototype": {
      "count": 2
    },
    "HTMLFormElementPrototype": {
      "count": 1
    },
    "HTMLLIElement": {
      "count": 17
    },
    "FormDataPrototype": {
      "count": 1
    },
    "ScriptSource": {
      "count": 121
    },
    "PerformanceTimingPrototype": {
      "count": 2
    },
    "Object": {
      "count": 30271
    },
    "NodeList": {
      "count": 2
    },
    "DOMTokenListPrototype": {
      "count": 2
    },
    "HTMLStyleElementPrototype": {
      "count": 1
    },
    "Function": {
      "count": 42468
    },
    "Window": {
      "count": 3
    },
    "MediaQueryListPrototype": {
      "count": 2
    },
    "Boolean": {
      "count": 2
    },
    "LocationPrototype": {
      "count": 2
    },
    "HTMLElementPrototype": {
      "count": 2
    },
    "internal-parse-task-global": {
      "count": 5
    },
    "DocumentPrototype": {
      "count": 3
    },
    "HTMLScriptElementPrototype": {
      "count": 2
    },
    "HTMLBodyElement": {
      "count": 1
    },
    "PageTransitionEventPrototype": {
      "count": 3
    },
    "NodeListPrototype": {
      "count": 2
    },
    "HTMLSpanElement": {
      "count": 7
    },
    "Iterator": {
      "count": 7
    },
    "Text": {
      "count": 25
    },
    "HTMLTableSectionElementPrototype": {
      "count": 1
    },
    "HTMLImageElementPrototype": {
      "count": 2
    },
    "Block": {
      "count": 162
    },
    "HTMLAnchorElement": {
      "count": 31
    },
    "HTMLImageElement": {
      "count": 6
    },
    "HTMLTextAreaElementPrototype": {
      "count": 1
    },
    "HTMLDocumentPrototype": {
      "count": 3
    },
    "HTMLButtonElementPrototype": {
      "count": 1
    },
    "HTMLHtmlElement": {
      "count": 1
    },
    "HTMLInputElementPrototype": {
      "count": 2
    },
    "StorageEventPrototype": {
      "count": 1
    },
    "Crypto": {
      "count": 1
    },
    "HTMLCollectionPrototype": {
      "count": 2
    },
    "XMLHttpRequestEventTargetPrototype": {
      "count": 2
    },
    "NotificationPrototype": {
      "count": 1
    },
    "HTMLAnchorElementPrototype": {
      "count": 1
    },
    "EventPrototype": {
      "count": 3
    },
    "HTMLDivElement": {
      "count": 226
    },
    "CSS2PropertiesPrototype": {
      "count": 2
    },
    "XMLHttpRequestPrototype": {
      "count": 2
    },
    "HTMLFormElement": {
      "count": 1
    },
    "Number": {
      "count": 2
    },
    "DOMRectPrototype": {
      "count": 1
    },
    "HTMLMetaElementPrototype": {
      "count": 1
    },
    "GlobalDebuggee": {
      "count": 1
    },
    "ConsolePrototype": {
      "count": 2
    },
    "String Iterator": {
      "count": 7
    },
    "HTMLSpanElementPrototype": {
      "count": 2
    },
    "Date": {
      "count": 174
    },
    "PluginArray": {
      "count": 1
    },
    "AttrPrototype": {
      "count": 2
    },
    "HTMLIFrameElement": {
      "count": 5
    },
    "PerformancePrototype": {
      "count": 2
    },
    "Storage": {
      "count": 1
    },
    "Console": {
      "count": 1
    },
    "ExternalPrototype": {
      "count": 1
    },
    "StopIteration": {
      "count": 7
    },
    "TransitionEventPrototype": {
      "count": 1
    },
    "HTMLHeadElementPrototype": {
      "count": 1
    }
  },
  "scripts": {
    "count": 31192
  },
  "strings": {
    "count": 63480
  },
  "other": {
    "js::types::TypeObject": {
      "count": 14170
    },
    "js::Shape": {
      "count": 64625
    },
    "js::BaseShape": {
      "count": 7197
    }
  }
}
Attachment #8455938 - Attachment is obsolete: true
Nice!

Object/Function/Array, this is why we need prototype/constructor/allocation-site ;)

600 ms is slower than I'd hoped. Do you know how many nodes and edges your gmail had in the heap graph?
Just to give some relative numbers, here is a dominator tree computation on cnn.com:

130,377 nodes
410,498 edges
605     ms
Comment on attachment 8455513 [details] [diff] [review]
Use 'using namespace' in DebuggerMemory.cpp, to avoid wrapping top-level definitions in a namespace { ... } form.

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

I'm fine with |using namespace| since it seems like everything else is doing it.

Man, here I was gearing myself up for a tricky patch scanning through the whole heap while fighting off a rabid army of garbage collectors, and it turned out to be just this?! :-)
Attachment #8455513 - Flags: review?(sphink) → review+
I haven't instrumented the census to count edges and nodes, but cnn.com takes .2s.  Figures below.

Just as a sanity check: a trivial web page runs in ~ 5ms, so it does seem like the complexity of the page affects the timing.

I tried a trivial census function that just counts nodes; it doesn't seem to have a significant impact on the time. So the time is in the traversal or in ubi::Node itself, not in the assorters.

"time used by census: 0.209s" Scratchpad/1:21
"{
  "objects": {
    "ElementPrototype": {
      "count": 4
    },
    "TextDecoderPrototype": {
      "count": 4
    },
    "HTMLTableCellElementPrototype": {
      "count": 1
    },
    "HTMLOListElement": {
      "count": 1
    },
    "Math": {
      "count": 4
    },
    "DOMRectReadOnlyPrototype": {
      "count": 3
    },
    "With": {
      "count": 38
    },
    "DocumentFragmentPrototype": {
      "count": 1
    },
    "MimeTypeArrayPrototype": {
      "count": 2
    },
    "HTMLHeadingElementPrototype": {
      "count": 1
    },
    "HTMLBRElementPrototype": {
      "count": 1
    },
    "NavigatorPrototype": {
      "count": 4
    },
    "ProgressEventPrototype": {
      "count": 1
    },
    "HTMLMediaElementPrototype": {
      "count": 1
    },
    "HTMLSelectElementPrototype": {
      "count": 1
    },
    "HTMLTableRowElementPrototype": {
      "count": 1
    },
    "HTMLFieldSetElementPrototype": {
      "count": 1
    },
    "XMLSerializerPrototype": {
      "count": 1
    },
    "DOMErrorPrototype": {
      "count": 4
    },
    "DOMExceptionPrototype": {
      "count": 1
    },
    "HTMLHtmlElementPrototype": {
      "count": 2
    },
    "HTMLUListElementPrototype": {
      "count": 1
    },
    "HistoryPrototype": {
      "count": 1
    },
    "CryptoPrototype": {
      "count": 1
    },
    "DOMPrototype": {
      "count": 1
    },
    "MessageEventPrototype": {
      "count": 1
    },
    "PerformanceNavigationPrototype": {
      "count": 1
    },
    "HTMLScriptElement": {
      "count": 40
    },
    "NodePrototype": {
      "count": 4
    },
    "HTMLIFrameElementPrototype": {
      "count": 3
    },
    "CharacterDataPrototype": {
      "count": 1
    },
    "TextPrototype": {
      "count": 1
    },
    "CommentPrototype": {
      "count": 1
    },
    "FocusEventPrototype": {
      "count": 1
    },
    "Iterator": {
      "count": 21
    },
    "Error": {
      "count": 9
    },
    "HTMLParagraphElementPrototype": {
      "count": 1
    },
    "PromisePrototype": {
      "count": 4
    },
    "HTMLCollectionPrototype": {
      "count": 3
    },
    "HTMLDocument": {
      "count": 4
    },
    "Array": {
      "count": 1785
    },
    "CSS2Properties": {
      "count": 1
    },
    "HTMLLIElementPrototype": {
      "count": 1
    },
    "Location": {
      "count": 1
    },
    "WindowPrototype": {
      "count": 4
    },
    "PluginArrayPrototype": {
      "count": 3
    },
    "EventTargetPrototype": {
      "count": 4
    },
    "Array Iterator": {
      "count": 21
    },
    "RegExp": {
      "count": 904
    },
    "XMLSerializer": {
      "count": 1
    },
    "HTMLImageElement": {
      "count": 9
    },
    "HTMLVideoElementPrototype": {
      "count": 1
    },
    "Navigator": {
      "count": 2
    },
    "HTMLTableElementPrototype": {
      "count": 1
    },
    "XPC_WN_ModsAllowed_NoCall_Proto_JSClass": {
      "count": 2
    },
    "JSON": {
      "count": 1
    },
    "HTMLBodyElementPrototype": {
      "count": 4
    },
    "HTMLTitleElementPrototype": {
      "count": 1
    },
    "DOMParser": {
      "count": 1
    },
    "HTMLLinkElementPrototype": {
      "count": 1
    },
    "HTMLHeadElement": {
      "count": 1
    },
    "TextEncoderPrototype": {
      "count": 4
    },
    "String": {
      "count": 4
    },
    "HTMLDivElementPrototype": {
      "count": 1
    },
    "HTMLCollection": {
      "count": 2
    },
    "Function": {
      "count": 27166
    },
    "HTMLOListElementPrototype": {
      "count": 1
    },
    "CSSStyleDeclarationPrototype": {
      "count": 2
    },
    "HTMLFormElementPrototype": {
      "count": 1
    },
    "Uint16ArrayPrototype": {
      "count": 1
    },
    "HTMLLIElement": {
      "count": 5
    },
    "WithTemplate": {
      "count": 37
    },
    "ScriptSource": {
      "count": 126
    },
    "PerformanceTimingPrototype": {
      "count": 2
    },
    "Object": {
      "count": 5113
    },
    "NodeList": {
      "count": 1
    },
    "UIEventPrototype": {
      "count": 1
    },
    "HTMLStyleElementPrototype": {
      "count": 1
    },
    "HTMLHeadingElement": {
      "count": 2
    },
    "Window": {
      "count": 4
    },
    "HTMLSelectElement": {
      "count": 1
    },
    "Boolean": {
      "count": 2
    },
    "LocationPrototype": {
      "count": 4
    },
    "HTMLElementPrototype": {
      "count": 4
    },
    "internal-parse-task-global": {
      "count": 19
    },
    "DocumentPrototype": {
      "count": 4
    },
    "MimeTypePrototype": {
      "count": 1
    },
    "HTMLScriptElementPrototype": {
      "count": 4
    },
    "HTMLBodyElement": {
      "count": 1
    },
    "PageTransitionEventPrototype": {
      "count": 4
    },
    "NodeListPrototype": {
      "count": 2
    },
    "HTMLSpanElement": {
      "count": 44
    },
    "HTMLUnknownElementPrototype": {
      "count": 1
    },
    "Text": {
      "count": 11
    },
    "RegExpStatics": {
      "count": 19
    },
    "HTMLTableSectionElementPrototype": {
      "count": 1
    },
    "MozNamedAttrMapPrototype": {
      "count": 1
    },
    "HTMLImageElementPrototype": {
      "count": 1
    },
    "HTMLLabelElementPrototype": {
      "count": 1
    },
    "HTMLAnchorElement": {
      "count": 5
    },
    "Proxy": {
      "count": 23
    },
    "HTMLTextAreaElementPrototype": {
      "count": 1
    },
    "HTMLDocumentPrototype": {
      "count": 4
    },
    "HTMLVideoElement": {
      "count": 1
    },
    "DOMParserPrototype": {
      "count": 1
    },
    "HTMLInputElementPrototype": {
      "count": 1
    },
    "StorageEventPrototype": {
      "count": 1
    },
    "HTMLTimeElementPrototype": {
      "count": 1
    },
    "XMLDocument": {
      "count": 1
    },
    "XMLDocumentPrototype": {
      "count": 1
    },
    "XMLHttpRequestEventTargetPrototype": {
      "count": 1
    },
    "HTMLInputElement": {
      "count": 1
    },
    "HTMLAnchorElementPrototype": {
      "count": 1
    },
    "EventPrototype": {
      "count": 4
    },
    "PluginArray": {
      "count": 1
    },
    "CSS2PropertiesPrototype": {
      "count": 2
    },
    "XMLHttpRequestPrototype": {
      "count": 1
    },
    "HTMLFormElement": {
      "count": 1
    },
    "Number": {
      "count": 4
    },
    "HTMLHtmlElement": {
      "count": 1
    },
    "PerformanceTiming": {
      "count": 1
    },
    "DOMRectPrototype": {
      "count": 3
    },
    "HTMLMetaElementPrototype": {
      "count": 1
    },
    "GlobalDebuggee": {
      "count": 1
    },
    "ScreenPrototype": {
      "count": 2
    },
    "Block": {
      "count": 76
    },
    "ConsolePrototype": {
      "count": 1
    },
    "String Iterator": {
      "count": 21
    },
    "Call": {
      "count": 1791
    },
    "HTMLSpanElementPrototype": {
      "count": 1
    },
    "Date": {
      "count": 302
    },
    "HTMLOptionElementPrototype": {
      "count": 1
    },
    "HTMLDivElement": {
      "count": 20
    },
    "HTMLIFrameElement": {
      "count": 3
    },
    "PerformancePrototype": {
      "count": 2
    },
    "DocumentFragment": {
      "count": 1
    },
    "Storage": {
      "count": 1
    },
    "Arguments": {
      "count": 1
    },
    "Console": {
      "count": 1
    },
    "ExternalPrototype": {
      "count": 1
    },
    "StopIteration": {
      "count": 21
    },
    "HTMLHeadElementPrototype": {
      "count": 3
    }
  },
  "scripts": {
    "count": 10712
  },
  "strings": {
    "count": 21168
  },
  "other": {
    "js::types::TypeObject": {
      "count": 8060
    },
    "js::Shape": {
      "count": 28408
    },
    "js::BaseShape": {
      "count": 5722
    }
  }
}" Scratchpad/1:10
Use 'using namespace' in DebuggerMemory.cpp, to avoid wrapping top-level definitions in a namespace { ... } form. r=sfink

https://hg.mozilla.org/integration/mozilla-inbound/rev/6852fe1705c0
Whiteboard: [leave open]
Attachment #8455513 - Flags: checkin+
This is the heart of the census traversal. More detailed breakdowns can come later.
Attachment #8458485 - Attachment is obsolete: true
Attachment #8462955 - Flags: review?(sphink)
This patch refines the census, breaking down the count by various categories. This involves no changes to the traversal itself, merely an elaboration of the assorter the census traversal uses, so it is broken out into its own patch.
Attachment #8462958 - Flags: review?(sphink)
Attachment #8462955 - Flags: review?(sphink) → review?(terrence)
Attachment #8462958 - Flags: review?(sphink) → review?(terrence)
Comment on attachment 8462955 [details] [diff] [review]
Implement Debugger.Memory.prototype.census, with trivial categorization (none, just counting).

Changing review? to feedback?; this doesn't have enough tests.
Attachment #8462955 - Flags: review?(terrence) → feedback?(terrence)
Comment on attachment 8462958 [details] [diff] [review]
Add non-trivial breakdowns to Debugger.Memory.prototype.takeCensus.

Similarly; not enough tests.
Attachment #8462958 - Flags: review?(terrence) → feedback?(terrence)
(In reply to Jim Blandy :jimb from comment #17)
> (In reply to Nick Fitzgerald [:fitzgen] from comment #15)
> > Now that we have unified builds, writing "using namespace" in the global
> > scope of a .cpp file is almost as bad as writing it in a header. Regularly
> > build errors show up like this one:
> > https://tbpl.mozilla.org/php/getParsedLog.php?id=40010766&tree=Try
> 
> Yeah. But the rest of SpiderMonkey uses 'using namespace js' and '... JS'
> everywhere.

No, it most certainly doesn't! Where it does, it is certainly a bug, not only for all the reasons Nick lists, but also because it goes against our style guidelines. They've been in place for at least a year now, so I don't feel too guilty asking you to update the patch to that standard.

SM's preferred namespace usage style is: namespace foo {} in headers and use the full namespace when defining methods in cpp files.
Comment on attachment 8462955 [details] [diff] [review]
Implement Debugger.Memory.prototype.census, with trivial categorization (none, just counting).

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

Sorry to butt heads so much on style, but I think the things I've mentioned here are actually rather important.

::: js/src/vm/DebuggerMemory.cpp
@@ +16,5 @@
>  #include "jsobjinlines.h"
>  
>  #include "vm/Debugger-inl.h"
>  
> +using namespace js;

This shouldn't be necessary: most of your definitions are in js::, so have it implicitly.

@@ +17,5 @@
>  
>  #include "vm/Debugger-inl.h"
>  
> +using namespace js;
> +using namespace JS;

Please remove this and either use JS:: where it's needed in the implementation, or limit the namespace creep by |using JS::Foo; using JS::Bar; etc| on an as needed basis, if using JS:: everywhere gets too wordy.

@@ +25,3 @@
>  
>  /* static */ DebuggerMemory *
>  DebuggerMemory::create(JSContext *cx, Debugger *dbg)

You will need to declare this with the namespace, e.g. js::DebuggerMemory::create(...). In my opinion, it also adds quite a bit of clarity in bits of code that are using multiple namespaces together, as does this patch below.

@@ +136,5 @@
> +
> +namespace dbg {
> +
> +// Common data for census traversals.
> +struct Census {

SM style has the { on a newline for class and struct. Only namespace, enum, and members get { on the same line. However, I did notice all of your existing classes/structs use same-line { already, so for consistency I'll look the other way this time. I honestly don't think this particular rule makes much readability difference, but it would probably still be worth standardizing eventually.

@@ +153,5 @@
> +
> +// An *assorter* class is one with the following constructors, destructor,
> +// and member functions:
> +//
> +//   ByHairColor(Census &census);

I really wish that C++ had real interfaces to make this particular use clearer (and easier to debug if you forgot an interface method). As is, I think it would be clearer if you called this particular set of constructors/destructor Assorter, IAssorter, or so, and added a ByHairColor example below.

@@ +174,5 @@
> +// In each of these, |census| provides ambient information needed for assorting,
> +// like a JSContext for reporting errors.
> +
> +// The simplest assorter: count everything, and return a tally form.
> +class Tally {

Although maybe the existence of Tally is an adequate example. I still don't think a second example would hurt, however.

@@ +254,5 @@
> +};
> +
> +
> +// A ubi::BreadthFirst handler that conducts a trivial census.
> +typedef CensusHandler<Tally> SimpleCensusHandler;

I don't think calling this CensusHandler "Simple" is an improvement over "Tally" -- certainly not enough of one to justify adding yet another name to the set needed to understand takeCensus. Rather, the one concept in takeCensus that screams "unneeded implementation detail" to me is |BreadthFirst|. How about we instead do:

typedef ubi::BreadthFirst<dbg::CensusHandler<Tally> > TallyingTraversal;

@@ +284,5 @@
> +        // census.debuggeeZones.
> +        for (GlobalObjectSet::Range r = debugger->debuggees.all(); !r.empty(); r.popFront()) {
> +            if (!census.debuggeeZones.put(r.front()->zone()) ||
> +                !traversal.addStart(static_cast<JSObject *>(r.front())))
> +                return false;

Please add left-aligned braces around the if-statement to offset it from the return. Our 4-space indent makes this case particularly awkward, but it's totally worth it not to have to double-take on code like this.
Attachment #8462955 - Flags: feedback+
Attachment #8462955 - Flags: feedback?(terrence)
(In reply to Terrence Cole [:terrence] from comment #36)
> (In reply to Jim Blandy :jimb from comment #17)
> > Yeah. But the rest of SpiderMonkey uses 'using namespace js' and '... JS'
> > everywhere.
> 
> No, it most certainly doesn't! Where it does, it is certainly a bug, not
> only for all the reasons Nick lists, but also because it goes against our
> style guidelines. They've been in place for at least a year now, so I don't
> feel too guilty asking you to update the patch to that standard.

1) I am happy to update my patches to conform with the style the SpiderMonkey team has agreed upon. I apologize for not having read those guidelines first.

2) I certainly would not be able to infer those guidelines by looking at the code. Note the use of grep -l, to list files containing matches, not matches:

$ grep -l 'using namespace' *.cpp {builtin,frontend,gc,jit,vm}/*.cpp | wc -l
153
$

So this style rule is definitely not enforced or respected.

The fact remains that new patches should follow the team's agreed-upon style. I'll revise.
Here are some interesting results from valgrind's 'callgrind' tool, with profiling restricted to takeCensus's call to traversal.traverse, in a non-debug -O3 build. The top few lines are very interesting; I've trimmed them and included them below:

Note the predominance of jsprf (46% of cycles) and malloc/free (19% of cycles). The census doesn't use the edge names at all. Computing them only on request should be the first thing we try.



--------------------------------------------------------------------------------
         Ir 
--------------------------------------------------------------------------------
355,494,977  PROGRAM TOTALS

--------------------------------------------------------------------------------
        Ir  file:function
--------------------------------------------------------------------------------
85,059,716  jsprf.cpp:dosprintf(SprintfState*, char const*, __va_list_tag*)
46,463,112  jsprf.cpp:LimitStuff(SprintfState*, char const*, unsigned long)
36,477,337  vm/UbiNode.cpp:SimpleEdgeVectorTracer::callback(void**, JSGCTraceKind)
26,673,131  ???:_int_free
22,499,868  ???:_int_malloc
13,959,105  opt~/js/src/../../dist/include/js/HashTable.h:JS::ubi::BreadthFirst<...>::traverse()
13,410,552  jsprf.cpp:fill_n(SprintfState*, char const*, int, int, int, int, int)
12,755,120  ???:malloc
11,205,922  ???:__strlen_sse2_pminub
 8,098,191  ???:free
 6,229,925  opt~/js/src/../../dist/include/js/UbiNodeTraverse.h:JS::ubi::BreadthFirst<...>::traverse()
 6,226,480  jsprf.cpp:JS_vsnprintf(char*, unsigned int, char const*, __va_list_tag*)
 5,073,129  gc/Tracer.cpp:JSTracer::getTracingEdgeName(char*, unsigned long)
 4,596,958  gc/Marking.cpp:js::gc::MarkArraySlots(JSTracer*, unsigned long, js::HeapSlot*, char const*)
 4,550,120  jsprf.cpp:JS_snprintf(char*, unsigned int, char const*, ...)
Here's the test program I ran to exercise D.M.p.takeCensus.
From UbiNode.h:

    // (In real life we'll want a better representation for names, to avoid
    // creating tons of strings when the names follow a pattern; and we'll need
    // to think about lifetimes carefully to ensure traversal stays cheap.)

Real life has arrived!
Here are the results with edge name generation disabled: traversal cycles cut by 71%.

--------------------------------------------------------------------------------
         Ir 
--------------------------------------------------------------------------------
105,430,897  PROGRAM TOTALS

--------------------------------------------------------------------------------
        Ir  file:function
--------------------------------------------------------------------------------
13,933,886  opt~/js/src/../../dist/include/js/HashTable.h:JS::ubi::BreadthFirst<...>::traverse()
10,010,520  vm/UbiNode.cpp:SimpleEdgeVectorTracer::callback(void**, JSGCTraceKind)
 9,176,876  ???:_int_malloc
 6,227,340  opt~/js/src/../../dist/include/js/UbiNodeTraverse.h:JS::ubi::BreadthFirst<...>::traverse()
 5,188,564  ???:free
 4,595,118  gc/Marking.cpp:js::gc::MarkArraySlots(JSTracer*, unsigned long, js::HeapSlot*, char const*)
 4,557,375  ???:_int_free
 4,347,683  opt~/js/src/../../dist/include/js/Value.h:js::gc::MarkArraySlots(JSTracer*, unsigned long, js::HeapSlot*, char const*)
 4,197,960  opt~/js/src/../../dist/include/js/UbiNode.h:SimpleEdgeVectorTracer::callback(void**, JSGCTraceKind)
 3,361,806  gc/Marking.cpp:void MarkInternal<JSObject>(JSTracer*, JSObject**)
 2,906,511  opt~/js/src/../../dist/include/mozilla/Vector.h:SimpleEdgeVectorTracer::callback(void**, JSGCTraceKind)
 2,865,309  vm/UbiNode.cpp:SimpleEdgeRange::popFront()
 2,388,245  opt~/js/src/../../dist/include/mozilla/Vector.h:SimpleEdgeRange::~SimpleEdgeRange()
 2,281,847  opt~/js/src/../../dist/include/mozilla/HashFunctions.h:js::dbg::ByJSType<...>::count(js::dbg::Census&, JS::ubi::Node const&)
 2,260,440  vm/UbiNode.cpp:JS::ubi::Node::Node(JSGCTraceKind, void*)
Okay, here's a new gmail census, built with an optimized, no-DEBUG browser, and the name computation disabled:

"time used by census: 0.163s" Scratchpad/1:21
I think we could get further improvements by not going through JS_TraceChildren, but by implementing the ubi::Node JSObject specialization directly. The structure of ubi::Node allows the JSObject specialization to live in ObjectImpl.h or Tracer.cpp; there's no need to violate modularity boundaries by putting the code in UbiNode.cpp.
(In reply to Jim Blandy :jimb from comment #44)
> I think we could get further improvements by not going through
> JS_TraceChildren, but by implementing the ubi::Node JSObject specialization
> directly. The structure of ubi::Node allows the JSObject specialization to
> live in ObjectImpl.h or Tracer.cpp; there's no need to violate modularity
> boundaries by putting the code in UbiNode.cpp.

Nice >3x win! Could we just call T::traceChilden from the base ubi::Node and implement traceChildren in all of the classes that participate?
A friend lent me his profile directory, and logged me into his Facebook account; a census there took 157ms. So I think we've got some room to play now.
Here's a preparatory patch that cleans up (and simplifies!) namespace usage in Debugger.Memory.
Attachment #8464947 - Flags: review?(terrence)
Actually, that first patch only compiled due to source unification. Here's a correct patch.
Attachment #8464947 - Attachment is obsolete: true
Attachment #8464947 - Flags: review?(terrence)
Attachment #8464950 - Flags: review?(terrence)
Okay, *THIS* version is updated for our conversation about "using namespace" in IRC, and the subsequent revisions to the SpiderMonkey coding standards. Sorry for the churn!
Attachment #8464950 - Attachment is obsolete: true
Attachment #8464950 - Flags: review?(terrence)
Attachment #8465024 - Flags: review?(terrence)
Comment on attachment 8465024 [details] [diff] [review]
Clean up namespace usage in js/src/vm/DebuggerMemory.cpp.

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

\o/
Attachment #8465024 - Flags: review?(terrence) → review+
Attachment #8465024 - Flags: checkin+
Now, with tests!
Attachment #8462955 - Attachment is obsolete: true
Attachment #8469700 - Flags: review?(terrence)
Now, with tests!
Attachment #8462958 - Attachment is obsolete: true
Attachment #8462958 - Flags: feedback?(terrence)
Attachment #8469702 - Flags: review?(terrence)
Comment on attachment 8469700 [details] [diff] [review]
Implement Debugger.Memory.prototype.census, with trivial categorization (none, just counting).

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

r=me
Attachment #8469700 - Flags: review?(terrence) → review+
Comment on attachment 8469702 [details] [diff] [review]
Add non-trivial breakdowns to Debugger.Memory.prototype.takeCensus.

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

::: js/src/vm/DebuggerMemory.cpp
@@ +490,5 @@
> +template<> struct CharTraits<jschar> {
> +    static size_t length(const jschar *s) { return js_strlen(s); }
> +    static int cmp(const jschar *lhs, const jschar *rhs) { return js_strcmp(lhs, rhs); }
> +    static JSAtom *atomize(JSContext *cx, const jschar *name) {
> +        return AtomizeChars(cx, name, js_strlen(name));

I think a better solution here would be to make js_strlen have an overload for char* that calls strlen. That way you can get rid of all the orthogonal bits here and just keep forNull.
Attachment #8469702 - Flags: review?(terrence) → review+
(In reply to Terrence Cole [:terrence] from comment #55)
> Comment on attachment 8469702 [details] [diff] [review]
> Add non-trivial breakdowns to Debugger.Memory.prototype.takeCensus.

Thanks for the review! Based on your comments on IRC, I want to simplify this a bit and re-submit it for review, if that's all right.
This version is not smaller, but much simpler in structure. Functionality is unchanged, except that we unify classes with identical names, instead of letting their counts override each other when we produce a report.
Attachment #8469702 - Attachment is obsolete: true
Attachment #8470297 - Flags: review?(terrence)
Comment on attachment 8470297 [details] [diff] [review]
Add non-trivial breakdowns to Debugger.Memory.prototype.takeCensus.

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

::: js/src/vm/DebuggerMemory.cpp
@@ +391,5 @@
> +            return false;
> +
> +        RootedValue otherReport(cx);
> +        if (!other.report(census, &otherReport) ||
> +            !JSObject::defineProperty(cx, obj, cx->names().other,   otherReport))

Remove extra space.

@@ +615,5 @@
> +typedef ByJSType<ByObjectClass<Tally>, Tally, Tally, ByUbinodeType<Tally> > SimpleAssorter;
> +
> +// A traversal that conducts a census using SimpleAssorter.
> +typedef CensusHandler<SimpleAssorter> SimpleCensusHandler;
> +typedef BreadthFirst<SimpleCensusHandler> SimpleCensusTraversal;

I still do not agree that naming something "Simple" is ever a good idea. Either you're insulting everyone that doesn't immediately understand, or it's totally redundant. Besides, the type declaration you're aliasing here is not exactly trivial, so I think more people will fall into the former than the latter category. Please change SimpleAssorter to TypeNameAssorter and s/Simple/TypeName/ the others as well.
Attachment #8470297 - Flags: review?(terrence) → review+
(In reply to Terrence Cole [:terrence] from comment #58)
> I still do not agree that naming something "Simple" is ever a good idea.
> Either you're insulting everyone that doesn't immediately understand, or
> it's totally redundant. Besides, the type declaration you're aliasing here
> is not exactly trivial, so I think more people will fall into the former
> than the latter category. Please change SimpleAssorter to TypeNameAssorter
> and s/Simple/TypeName/ the others as well.

The "insult" aspect hadn't occurred to me. Per our IRC conversation, I've named it DefaultAssorter, and added a comment about how we're planning to allow dynamic assorters in the future, so it's clear what "Default" is in contrast to.

Thanks for the review!
One last, desperate try push:
https://tbpl.mozilla.org/?tree=Try&rev=469918152c9e
Duplicate of this bug: 961328
Depends on: 1051115
(In reply to Jim Blandy :jimb from comment #60)
> One last, desperate try push:

I forgot to run the style checks. Here's another try push with the header ordering fixed:
https://tbpl.mozilla.org/?tree=Try&rev=3273c9c8f1dc
Whiteboard: [leave open]
Attachment #8469700 - Flags: checkin+
Attachment #8470297 - Flags: checkin+
Depends on: 1103386
You need to log in before you can comment on or make changes to this bug.