578189 - Add the invariant that dependent strings must have a flat string as the base

Status: RESOLVED FIXED

(Core :: JavaScript Engine, defect)

Description

[Alan Pierce]

Currently, when we repeatedly take dependent strings of dependent strings, it forms a chain of dependent strings. When accessing the chars of a dependent string, we traverse the chain and make all of them point to the flat string (see MinimizeDependentStrings in jsstr.cpp). It makes chars() a lot simpler if we enforce that dependent strings must depend on flat strings and we eagerly compute the offset when creating a dependent string.

Comment 1

[Alan Pierce]

This isn't easy to do just yet, since flat strings can become dependent in
js_ConcatStrings. After the ropes patch (bug 571549), flat strings can still
become dependent, but pointers into char buffers of flat strings will remain
valid as long as the string is valid (this wasn't true before because
js_ConcatStrings could realloc flat string buffers). So, we can have the
following scheme:

Each dependent string keeps a length and two pointers: one for the base string,
one for the chars pointer. We use the base string pointers for GC marking
purposes (and the base pointers may form chains), and the chars pointer for
fast (and simple) access to chars. The whole point of this bug is to make
chars() not require a function call for dependent strings, so it would have the
same effect.

Comment 2

[Alan Pierce]

Attachment: Patch

This is on top of the ropes patch (bug 571549).

Comment 3

[Alan Pierce]

Attachment: Patch

js_AddAttributePart in jsxml.cpp needed to be changed to not realloc its buffer (since I'm adding the assumption that the buffer for a flat string will never be realloced).

This hurts e4x performance a bit (adding attributes to a tag copies the string every time instead of a realloc, I think, so we could get n^2 performance when building large tags). It wouldn't be too hard to instead build a rope, if performance here is important.

Comment 4

[Andreas Gal :gal]

Comment on attachment 458489 [details] [diff] [review]
Patch

>-static size_t
>-MinimizeDependentStrings(JSString *str, int level, JSString **basep)
>-{
>-    JSString *base;
>-    size_t start, length;
>-
>-    JS_ASSERT(str->isDependent());
>-    base = str->dependentBase();
>-    start = str->dependentStart();
>-    if (base->isDependent()) {
>-        if (level < JSSTRDEP_RECURSION_LIMIT) {
>-            start += MinimizeDependentStrings(base, level + 1, &base);
>-        } else {
>-            do {
>-                start += base->dependentStart();
>-                base = base->dependentBase();
>-            } while (base->isDependent());
>-        }
>-        length = str->dependentLength();
>-        str->initDependent(base, start, length);
>-    }
>-    *basep = base;
>-    return start;
>-}

If you write this as an iteration can we get away without a recursion limit?

>-    base->ensureNotRope();
>+    jschar *chars = base->chars() + start;
>+
>+    /* Try to avoid long chains of dependent strings. */
>+    while (base->isDependent()) {
>+        base = base->dependentBase();
>+    }
>+

No { } needed here.

Comment 5

[Alan Pierce]

(In reply to comment #4)
> Comment on attachment 458489 [details] [diff] [review]
> Patch
> 
> >-}
> 
> If you write this as an iteration can we get away without a recursion limit?
> 

This function is being removed (resolving a chain of dependent strings during chars() is no longer necessary).

Comment 6

[Alan Pierce]

Attachment: Patch, version 3

Comment 7

[Brendan Eich [:brendan]]

(In reply to comment #5)
> (In reply to comment #4)
> > Comment on attachment 458489 [details] [diff] [review] [details]
> > Patch
> > 
> > >-}
> > 
> > If you write this as an iteration can we get away without a recursion limit?
> > 
> 
> This function is being removed (resolving a chain of dependent strings during
> chars() is no longer necessary).

Plus, that function is not tail-recursive, so iteration would require explicit LIFO storage using a heap-allocated stack.

/be

Comment 8

[Andreas Gal :gal]

Comment on attachment 458517 [details] [diff] [review]
Patch, version 3

Nice.

Comment 9

[Alan Pierce]

Attachment: Rebased patch

Comment 10

[Luke Wagner [:luke]]

http://hg.mozilla.org/tracemonkey/rev/f0ba5a3e8c57

Comment 11

[Robert Sayre]

http://hg.mozilla.org/mozilla-central/rev/f0ba5a3e8c57