Closed Bug 616910 Opened 14 years ago Closed 3 years ago

Don't let a small live dependent string keep a large otherwise-dead string alive

Categories

(Core :: JavaScript Engine, defect)

x86
macOS
defect
Not set
normal

Tracking

()

RESOLVED WONTFIX

People

(Reporter: n.nethercote, Unassigned)

References

Details

This is a follow-up from bug 593659 comment 17 and bug 593659 comment 20.

A small dependent string (or dependent rope, if/when they're added in bug 615280) can keep a large otherwise-dead flat string (or rope) alive.  For example:

      veryLargeString = veryLargeString.substr(5, 10);

The presence of the dependent string ends up being an anti-optimization.

We could detect this sort of thing during GC -- eg. if the large string was greater than a certain length and the dependent string was less than a certain length -- and convert the dependent string into a flat string, thus allowing the large string to be GC'd.
(In reply to comment #0)
> We could detect this sort of thing during GC

This would add extra complexity to the GC as now one would need to distinguish somehow between mark edges comming into the the main string from a dependent string from the rest of edges. Another question is what to do about a string referenced by many dependent strings.

> veryLargeString = veryLargeString.substr(5, 10);

As a short string can hold 11 chars we should consider using short strings for substrings. And even if patterns like this that cannot be dealt with short strings are widespread IMO we should consider reference counting for strings and/or compiler time optimization and avoid allocating the dependent string at all.
(In reply to comment #1)
> (In reply to comment #0)
> > We could detect this sort of thing during GC
> 
> This would add extra complexity to the GC as now one would need to distinguish
> somehow between mark edges comming into the the main string from a dependent
> string from the rest of edges. Another question is what to do about a string
> referenced by many dependent strings.

I think you've got it inverted; this would be local to rope-marking.  Read bug 593659 comment 17.
(In reply to comment #2)
> this would be local to rope-marking.

The comment 0 talks talks about a generic dependent string. And even in case of ropes it would be necessary to deal with arbitrary edges into the rope graph.
(In reply to comment #1)
> 
> As a short string can hold 11 chars we should consider using short strings for
> substrings.

That's a good idea, I've opened bug 617148 for it.
(In reply to comment #3)
> (In reply to comment #2)
> > this would be local to rope-marking.
> 
> The comment 0 talks talks about a generic dependent string.

Oops, you're right.

> And even in case of
> ropes it would be necessary to deal with arbitrary edges into the rope graph.

Ok, I think I see what you mean: even if we determine that a rope is keeping alive huge strings (as it is in bug 593659), if those strings were live *anyway*, we shouldn't flatten.  Is that right?  Another problem I just realized with the naive scheme I suggested earlier is that we could get the same type of O(n^2) situation as with bug 614653.

To fix both issues, I think we would need to integrate string marking more into the GC.  Considering the case of dependent strings, I think it would go like:
 1. when marking a dependent string where our predicate determines we are wasting too much space, don't mark the base string and push the dependent string into a list.
 2. after marking phase and before sweeping, reconsider all the strings in said list.  If the base is still unmarked, then the dependent string is keeping it alive, so undepend and let the base get swept away.

If the "wasting too much space" predicate is appropriately conservative, then the number of strings that take this path should be small.  For ropes, more trickery would be necessary to avoid the O(n^2) flattening case.

So that's more complexity.  I guess the question is: how often does this hit in the wild and is it worth fixing?  (Note, bug 615280 and bug 615290 are only going to exacerbate the problem.)
(In reply to comment #5)
> Ok, I think I see what you mean: even if we determine that a rope is keeping
> alive huge strings (as it is in bug 593659), if those strings were live
> *anyway*, we shouldn't flatten.  Is that right?

If we flatten, then we consume more space. So we should not do that if the involved strings are references externally.
Assignee: general → nobody
Status: NEW → RESOLVED
Closed: 3 years ago
Resolution: --- → WONTFIX
You need to log in before you can comment on or make changes to this bug.