find pattern of wasteful temporary GC object creation

NEW
Unassigned

Status

--
enhancement
9 years ago
6 months ago

People

(Reporter: luke, Unassigned)

Tracking

Firefox Tracking Flags

(Not tracked)

Details

(Reporter)

Description

9 years ago
If you look at bug 200505 comment 35, we got a 4x speedup in Array.join by removing a lot of temporary JSString objects created.  The temporary JSStrings were being created in array_join_sub for each element of the array (which themselves could be arrays) and then discarded after their contents were copied into the aggregate JSString.  To avoid the temporaries, we pass around a single buffer that child elements write themselves into.

I just saw the same pattern, with the same potential for optimization, in jsxml.cpp with XMLToXMLString.  This led sayrer to point out this could be a widely occurring pattern and a fruitful source of optimizations pointed out by a static analysis.

A basic template would be:

JSString *
js_Foo(...) {
  for (...) {
     JSString *t = js_Foo(...) (directly or transitively)
     ... read t, but do not let alias escape
  }
  JSString *result = js_NewString(...)
  return result;
}

Where JSString could really be any dynamically-allocated type.
This is a good idea, although a couple of higher-level points may limit the win, or really, turn the analysis into a tool to find allocations to get rid of:

* A lot of these temporaries shouldn't even be created, and your patch for bug 200505 got rid of such temp gc-things using JSTempVector buffering.

* E4X is slated for self-hosting, and we really don't care about its perf anyway.

Problem in general once the easy temps have been killed is that the layering in the ECMA-262 specification (and therefore in the code; but not only in the code) defeats static analysis, makes it hard to do the escape analysis. Yet most results of toString, e.g., do not escape to the heap and probably die soon, even in LIFO fashion.

This suggests stack-GC, as sketched in bug 400902 comment 59 and implemented long ago in a rough draft. I'm still looking for it, but it would have bit-rotted. The main work was in an escape barrier for return, and one within the write barrier.

/be
Er, somehow I managed to restate comment 0 in my first bullet. Sorry about that! Was getting ahead of myself.

/be
Self-hosting more memory-unsafe C++ will result in the LIFO allocations being in the generational nursery, or in the local-GC's stack, where most can be reaped. Which isn't to say this bug has lower priority, just to suggest the longer term work is in the GC and related parts of the VM, not in built-ins' C++ impls.

/be
(Reporter)

Comment 4

9 years ago
I totally agree on the low-priority-ness, I just thought it might be nice to contribute to the library of "potential static analyses," which is sometimes nice to have when building a framework like dehydra/treehydra.
No argument, this is a good bug. I wouldn't even guess at priority except maybe in relative future tense terms, which is what comment 3 is about. For E4X, the future is very soon ;-).

/be
Hm. I wonder if the longer-term win is to actually take the GC generational. Still precise, and mark-sweep at the old generation, but make the young-generation a cheney/copying from-space. This is a common hybrid structure for trading performance (young is faster and compacting) against space overhead (old isn't split into half-wasted semispaces).

I suppose, as in bug 400902 comment 59, you could only use young-space solely for leaf GCthings (strings, doubles ... anything else?) and wind up with a simpler algorithm and mechanism. But I'd think there are a lot of short-lived non-leaf allocations too, no? You are still stuck building machinery for tracking inter-generational references even in the double-only approach. I think that's always the case.

(I guess this goes in the bug for "figure out which slightly-more-modern GC algorithms would carry best bang for buck. Do we have one of those bugs open?)

Comment 7

9 years ago
With any moving GC you either have to change the JSAPI to no longer allow raw pointers or you have to make sure young-generation objects don't escape to the JSAPI... but I'm all for it!
(In reply to comment #6)
> Hm. I wonder if the longer-term win is to actually take the GC generational.
> Still precise, and mark-sweep at the old generation, but make the
> young-generation a cheney/copying from-space. This is a common hybrid structure
> for trading performance (young is faster and compacting) against space overhead
> (old isn't split into half-wasted semispaces).

This is what we are heading toward, and single-threaded too -- new API rule would require publishing an ST-from-birth object as MT-accessible -- or more stringent: require new API to create an MT-ab-initio object, all else are ST-only.

> I suppose, as in bug 400902 comment 59, you could only use young-space solely
> for leaf GCthings (strings, doubles ... anything else?) and wind up with a
> simpler algorithm and mechanism. But I'd think there are a lot of short-lived
> non-leaf allocations too, no? You are still stuck building machinery for
> tracking inter-generational references even in the double-only approach. I
> think that's always the case.

The leaf things excluding dependent strings can't reach from young to old space, which helps slightly, but yeah.

> (I guess this goes in the bug for "figure out which slightly-more-modern GC
> algorithms would carry best bang for buck. Do we have one of those bugs open?)

I thought so, but can't find it; probably we could use a clean bug. Igor, what do you think?

(In reply to comment #7)
> With any moving GC you either have to change the JSAPI to no longer allow raw
> pointers or you have to make sure young-generation objects don't escape to the
> JSAPI... but I'm all for it!

That is going to happen, the old rooting API will be ifdef'ed off and embedders will have to enable the ifdefs to get it.

/be

Comment 9

9 years ago
(In reply to comment #7)
> With any moving GC you either have to change the JSAPI to no longer allow raw
> pointers or you have to make sure young-generation objects don't escape to the
> JSAPI...

This is not true in general - an embedding can provide a way to enumerate all memory locations where a raw pointer to GC thing is stored.

Comment 10

9 years ago
(In reply to comment #8)
> > (I guess this goes in the bug for "figure out which slightly-more-modern GC
> > algorithms would carry best bang for buck. Do we have one of those bugs open?)
> 
> I thought so, but can't find it; probably we could use a clean bug. Igor, what
> do you think?

I could not find any suitable existing bug for this. So a new bug is in due.

Updated

6 months ago
Product: Core → Firefox Build System
You need to log in before you can comment on or make changes to this bug.