512046 - TM: avoid maintaing a per-runtime iterator list

Status: RESOLVED FIXED

(Core :: JavaScript Engine, defect)

Description

[Andreas Gal :gal]

This avoids having to lock/unlock the runtime. This is an 8% speedup for fasta (around 7ms).

Comment 1

[Andreas Gal :gal]

Attachment: patch

Comment 2

[Brendan Eich [:brendan]]

Nice!

/be

Comment 3

[Brendan Eich [:brendan]]

Comment on attachment 396044 [details] [diff] [review]
patch

>diff --git a/js/src/jscntxt.cpp b/js/src/jscntxt.cpp
>--- a/js/src/jscntxt.cpp
>+++ b/js/src/jscntxt.cpp
>@@ -89,16 +89,17 @@ InitThreadData(JSThreadData *data)
> 
> static void
> FinishThreadData(JSThreadData *data)
> {
> #ifdef DEBUG
>     /* All GC-related things must be already removed at this point. */
>     for (size_t i = 0; i != JS_ARRAY_LENGTH(data->scriptsToGC); ++i)
>         JS_ASSERT(!data->scriptsToGC[i]);
>+    JS_ASSERT(!data->gcIteratorTable.array);
> #endif

The asymmetry between JS_THREADSAFE and single-threaded code is a bit jarring at first, but right -- worth a comment?

>@@ -3574,17 +3570,17 @@ js_GC(JSContext *cx, JSGCInvocationKind 
>      * entry can be freed. Note that even after the entry is freed, JSObject
>      * finalizers can continue to access the corresponding jsdouble* and
>      * JSString* assuming that they are unique. This works since the
>      * atomization API must not be called during GC.
>      */
>     js_SweepAtomState(cx);
> 
>     /* Finalize iterator states before the objects they iterate over. */
>-    CloseNativeIterators(cx);
>+    ForAllThreads<CloseNativeIterators>(cx);

Nice, we could use this elsewhere.

>+extern void
>+js_DestroyIteratorTable(JSThreadData *data);

s/Destroy/Finish/ for inline member dtor.

/be

Comment 4

[Igor Bukanov]

Comment on attachment 396044 [details] [diff] [review]
patch

I shoud have seen this before, but the patch does not work due to thread-safety issues. Even in Firefox a single thread worker can migrate from one native thread to another. Thus with generators or explicit iterator manipulation one can have an iterator attached to multiple JSThread instances.

Comment 5

[Andreas Gal :gal]

No problem, I can make the lists context local.

Comment 6

[Andreas Gal :gal]

Attachment: patch

Comment 7

[Brendan Eich [:brendan]]

(In reply to comment #4)
> (From update of attachment 396044 [details] [diff] [review])
> I shoud have seen this before, but the patch does not work due to thread-safety
> issues.

Iterators aren't threadsafe anyway, per bug 349263.

> Even in Firefox a single thread worker can migrate from one native
> thread to another.

I didn't know -- how does this work? Must be when the C stack is empty of any JS code.

> Thus with generators or explicit iterator manipulation one
> can have an iterator attached to multiple JSThread instances.

If true, I don't see how the latest patch can help -- cx <= thread <= runtime.

/be

Comment 8

[Andreas Gal :gal]

If the context moves to a different thread, it takes the iterator list with it. I am still not sure what the problem is here though. And changing threads on contexts seems very sketchy to me.

Comment 9

[Brendan Eich [:brendan]]

Igor didn't say the context moves, and indeed if anything native is on its stack, it can't move.

Yeah, we haven't supported cx changing threads.

I think we should keep iterators ST per bug 349263.

/be

Comment 10

[Andreas Gal :gal]

So whats the verdict? Can we keep the list per thread?

Comment 11

[Brendan Eich [:brendan]]

(In reply to comment #10)
> So whats the verdict? Can we keep the list per thread?

We can in Firefox AFIAK (bent please comment) but bug 349263 needs to be fixed.

/be

Comment 12

[Igor Bukanov]

Iterator(obj) or generator's yield from inside a for-in loop creates an open iterator that can exist with no native code on the stack. Such iterator can survive the original JSContext object.

AFAIK a thread worker can run on different native threads. Thus JSThread also cannot store the state of the iterator.

Comment 13

[Igor Bukanov]

> we haven't supported cx changing threads.

What about long existing and working JS_SetContextThread?

Comment 14

[Brendan Eich [:brendan]]

(In reply to comment #13)
> > we haven't supported cx changing threads.
> 
> What about long existing and working JS_SetContextThread?

Sure, but I meant while the cx is in use.

Turn-based ST access to an iterator indeed would leave refs in a thread-based iterator-tables that would be prematurely closed. But if we expect turn-based ST access we should be able to migrate the iterator table entry when the closeable iterator object changes thread affinity.

/be

Comment 15

[Brendan Eich [:brendan]]

I don't expect turn-based ST access, of course. It is possible, and it should not lead to crashes or other problems. It's unlikely and it would be great to bias the design so that we don't pay locking overhead for ST single-turn-lifetime (i.e., almost every) closeable iterator.

/be

Comment 16

[Andreas Gal :gal]

Attachment: patch

Ok, this patch takes a different approach that should be agnostic to whatever insane gymnastics embeddings want to do with contexts and threads. Instead of registering iterators, we re-create the list as we mark. Since we don't want to rely on allocation during GC, I use a reserved slot for the list link. I am not a big fan of making the mark phase slower either, but this overhead should be minimal, and its well hidden in the general awesome slowness for our mark phase.

Comment 17

[Ben Turner (not reading bugmail, use the needinfo flag!)]

(In reply to comment #11)
> We can in Firefox AFIAK (bent please comment) but bug 349263 needs to be fixed.

We currently only use JSVERSION_DEFAULT on workers (which I believe means 1.5?) so this isn't really an issue yet.

The worker implementation uses one context per thread that never changes. Each worker has a global object that can be set/unset on any of those contexts (and, hence, threads). If iterators cannot be used across contexts then we would have a problem, yes.

Comment 18

[Brendan Eich [:brendan]]

(In reply to comment #17)
> (In reply to comment #11)
> > We can in Firefox AFIAK (bent please comment) but bug 349263 needs to be fixed.
> 
> We currently only use JSVERSION_DEFAULT on workers (which I believe means 1.5?)

No, DEFAULT means default version, which includes extensions such as JS1.6's Array extras (map, forEach, etc.). The default version does not include opt-in syntactic changes that break compatibility.

> so this isn't really an issue yet.

Someone could call Iterator(obj) to get a registered closeable native iterator. Still a contrived issue, granted -- but it's a bug.

> The worker implementation uses one context per thread that never changes. Each
> worker has a global object that can be set/unset on any of those contexts (and,
> hence, threads). If iterators cannot be used across contexts then we would have
> a problem, yes.

How does a worker migrate from thread to thread?

/be

Comment 19

[Igor Bukanov]

The global list exists as a workaround for deficiency of the enumeration protocol that does not have a hook for the marking phase of the GC.

IMO we should either fix the protocol and add JSENUMERATE_GC_TRACE. Alternatively, if breaking the compatibility would not be acceptable, we can at least do it for the particular got path  with explicit check for js_Enumerate.

Comment 20

[Igor Bukanov]

(In reply to comment #16)
> 
> Ok, this patch takes a different approach that should be agnostic to whatever
> insane gymnastics embeddings want to do with contexts and threads.

I think we should really remove the need for any global lists at least when classes defaults to js_Enumerate implementation.

Comment 21

[Andreas Gal :gal]

I completely agree. Is this a short term patch we can create? If not, I would like to apply this patch. Its a 100% improvement. Its shorter, its more memory efficient, and its faster than the old code.

Comment 22

[Igor Bukanov]

I do not see any significant roadblockers with avoiding adding the iterators to the global list and i can have a patch in 2-3 days. But first I would like to know if it is ok to extend the enumeration protocol with JSENUM_GC_TRACE? That would be the simplest.

Comment 23

[Brendan Eich [:brendan]]

(In reply to comment #22)
> I do not see any significant roadblockers with avoiding adding the iterators to
> the global list and i can have a patch in 2-3 days. But first I would like to
> know if it is ok to extend the enumeration protocol with JSENUM_GC_TRACE? That
> would be the simplest.

You mean the JSNewEnumerate API? JSENUMERATE_GC_TRACE, or JSENUMERATE_MARK if we want to de-generalize and avoid overloading trace further, is fine with me.

/be

Comment 24

[Igor Bukanov]

Attachment: thread-local enumerator cache v1

The patch removes the need for enumerators's lists and uses thread-local cache for the iterators. This avoids the need for any locking or CompareAndSwap calls on cache hit. 

To mark for the GC enumerator's state the code explicitly checks if the enumerator uses js_Enumerate and mark the private data as JSNativeEnumerator. Initially I tried to avoid this hack and add JSENUMERATE_MARK. But that was a dead end. The main obstacle was not switches over the three currently defined enumeration constants that defaults to  JSENUMERATE_DESTROY but rather the need to pass JSTracer*, not JSContext*, to object enumeration hook.

The current patch is work in progress and is not tested.

Comment 25

[Igor Bukanov]

Attachment: thread-local enumerator cache v2

This passes the try server and shell tests.

Comment 26

[Brendan Eich [:brendan]]

I will review this tonight.

/be

Comment 27

[Brendan Eich [:brendan]]

Sorry, missed the boat on that review time -- trying for "by end of tomorrow".

/be

Comment 28

[Igor Bukanov]

Attachment: thread-local enumerator cache v3

syncing the patch with the tip

Comment 29

[Igor Bukanov]

Attachment: v4

Here is another merge with the tip.

Comment 30

[Brendan Eich [:brendan]]

Comment on attachment 401491 [details] [diff] [review]
v4

JSTVU_ENUMERATOR comment says "a pointer is an instance of JSAutoEnumStateRoot" but pointers cannot be instances -- suggest s/is/points to/

s/JSAutoEnumStateRoot/JSAutoEnumStateRooter/g for consistency

Get rid of goto out/out: in obj_getCount.

"We cache the enumerators during the initialization in the JSENUMERATE_INIT" comment is not wrapped uniformly -- also s/during the initialization//

js_MarkEnumeratorState nit: JSVAL_IS_NULL and JSVAL_IS_VOID to match JSVAL_IS_INT.

/be

Comment 31

[Igor Bukanov]

(In reply to comment #30)
> Get rid of goto out/out: in obj_getCount.

That goto implements:

    /* Get the number of properties to enumerate. */
    ok = obj->enumerate(cx, JSENUMERATE_INIT, &iter_state, &num_properties);
    if (!ok)
        goto out;
...
out:
    if (!JSVAL_IS_NULL(iter_state))
        ok &= obj->enumerate(cx, JSENUMERATE_DESTROY, &iter_state, 0);
    return ok;

That is, the code calls JSENUMERATE_DESTROY even if JSENUMERATE_INIT fails unless the state is null. The same pattern exists JS_Enumerate. Just replacing that "goto out" with "return false" means an API change, however minuscule. I prefer keep such changes for a different bug.

Comment 32

[Igor Bukanov]

Attachment: v5

addressing comment 30

Comment 33

[Igor Bukanov]

http://hg.mozilla.org/tracemonkey/rev/9f54556ff6f0

Comment 34

[Igor Bukanov]

nominating for 1.9.2 as optimization and code simplification

Comment 35

[Igor Bukanov]

followup to fix the bug 517795 - http://hg.mozilla.org/tracemonkey/rev/9401fad04f30

Comment 36

[Robert Sayre]

http://hg.mozilla.org/mozilla-central/rev/9f54556ff6f0

Comment 37

[Robert Sayre]

http://hg.mozilla.org/releases/mozilla-1.9.2/rev/7cc988d29546