342380 - Finalize native iterators without close hooks

Status: RESOLVED FIXED

(Core :: JavaScript Engine, defect)

Description

[Igor Bukanov]

Currently the native iterator uses a close hook to ensure that the state of the iterator is finalized before the iteratable object. But this is expensive since the close hook requires an extra GC cycle. 

Thus the idea is to finalize the state through a separated loop during GC that release the state before finalizing the objects avoiding close hooks completely. Ideally it would be nice to have API to order finalization of different GC things but for now lets deal with just iterators.

Comment 1

[Igor Bukanov]

Attachment: Implementation

The implementation uses a linked list to know about all iterators with the initialized state. Since there is no available slots left for the link field for the list, the implementation replaces explicit slot manipulations by GC-allocated private structure.

Comment 2

[Brendan Eich [:brendan]]

Is this a premature optimization?  The change to use iterator_close landed without perturbing Ts on the tinderboxes I monitored, which was a concern (you've had to tune the GC triggering thresholds to avoid adding extra GCs to Mozilla and Firefox startup, IIRC).

Do you have any measurements showing that this extra code is worth it?  Alternatively, ordering finalizable objects might take less code if we could arrange to allocate an iterator at a "higher" address than its iterable.

/be

Comment 3

[Igor Bukanov]

(In reply to comment #2)
> Is this a premature optimization?  

This would allow to kill close hooks if they take too long time to execute and not worry about leaks. 

> The change to use iterator_close landed
> without perturbing Ts on the tinderboxes I monitored, which was a concern
> (you've had to tune the GC triggering thresholds to avoid adding extra GCs to
> Mozilla and Firefox startup, IIRC).

Previously iterators have used AddRoot/RemoveRoot which would force double GC loop after any for-in loop since RemoveRoot sets gcPoke. With the close hooks the GC is executed once since the collection of the garbage left after the close hook execution is delayed until the next explicit GC call unless the engine is shutting down. But that leaves perfectly collectable native iterators laying around and taking memory much longer then necessary and that was another reason for the bug. 

> 
> Do you have any measurements showing that this extra code is worth it? 

I will do some benchmarking.

> Alternatively, ordering finalizable objects might take less code if we could
> arrange to allocate an iterator at a "higher" address than its iterable.

That would not work due to new Iterator(new Iterator()).

Comment 4

[Igor Bukanov]

Some benchmarking data

To measure timing I use the following test for an optimized build of js shell:

function test(N)
{
        var array = [];
        for (var i = 0; i != N; ++i) {
                array.push(new Iterator([]));
        }

        array = null;
        var now = Date.now;
        var time0 = now();
        gc();
        var time1 = now();
        gc();
        var time2 = now();
        print("Times: GC1="+(time1-time0)+" GC2="+(time2 - time1)+"
Total="+(time2-time0));
}

test(1000*1000);


Typical output on my Pentium-M 1.1GH laptop with Fedora Core 5:

Before the patch:

Times: GC1=1566 GC2=637 Total=2203

After the patch:

Times: GC1=978 GC2=1 Total=979

That shows that not only that the total time to collect the garbage more then 2
times smaller but also that marking the iterator is almost 2 times longer then
finalizing it. 

Comment 5

[Brendan Eich [:brendan]]

(In reply to comment #3)
> (In reply to comment #2)
> > Is this a premature optimization?  
> 
> This would allow to kill close hooks if they take too long time to execute and
> not worry about leaks. 

Couple of comments on this:

- Instead of yet another struct (JSIter), why not add a JSObject *object; back-pointer to JSNativeIteratorState, to reference the owning iterator object, and sweep rt->nativeIteratorStates?

- Does your patch assume that these iterators all are flagged with JSITER_HIDDEN -- that is, not accessible by script, therefore not subject to close hook being overrridden by a scripted function?

- Given the JSITER_HIDDEN optimization whereby JSOP_ENDITER closes as soon as the loop exits normally, why not take those hidden iterators out of the list of native iterators altogether and avoid having to restart GCs on their account?  That might deal with the problem this bug aims to fix in 99% of cases.

> > Do you have any measurements showing that this extra code is worth it? 
> 
> I will do some benchmarking.

But I was thinking of real Firefox-based benchmarks, not synthetic benchmarks, which I'm sure can (and did, seeing your next comment) show slowdown.

> > Alternatively, ordering finalizable objects might take less code if we could
> > arrange to allocate an iterator at a "higher" address than its iterable.
> 
> That would not work due to new Iterator(new Iterator()).

Yes, but that's not the case to optimize -- that's a hard case.  The common case by far is the hidden one, where a for-in or for-each-in loop creates the iterator and it doesn't "escape".

/be

Comment 6

[Igor Bukanov]

(In reply to comment #5)
> - Instead of yet another struct (JSIter), why not add a JSObject *object;
> back-pointer to JSNativeIteratorState, to reference the owning iterator object,
> and sweep rt->nativeIteratorStates?

nativeIteratorStates is only used by js_Enumerate, any other implementation of the enumerate hook is not covered by this. And unfortunately there is no way AFAICS to know that a particular enumeration state is an instance of JSNativeIteratorState as otherwise the marking of the state can be done from iter_mark.   

> 
> - Does your patch assume that these iterators all are flagged with
> JSITER_HIDDEN -- that is, not accessible by script, therefore not subject to
> close hook being overrridden by a scripted function?

In the current implementation instances of js_IteratorClass never access close property and just close the native iterator from their close hook. Barring a bug the patch does not change this ignorance of the close property but just moves the finalization away from the expensive close hook.  

> 
> - Given the JSITER_HIDDEN optimization whereby JSOP_ENDITER closes as soon as
> the loop exits normally, why not take those hidden iterators out of the list of
> native iterators altogether and avoid having to restart GCs on their account? 
> That might deal with the problem this bug aims to fix in 99% of cases.

That does not work due to 

for (var i in ...) {
    while (true);
}

That would be killed by the long running script detector. Since currently the interpreter does not ensure that for JSITER_HIDDEN iterators the close hook is called in cases like that, I thought the reliance on GC is necessary. Plus due to the intention to copy Python 100% a case like

for (var i in ...) {
    yield i;
}

also assumes that GC would take of leaked native iterators. 

But you are right that it would be worth to make sure that for non-licked trusted iterators their close hook is executed even on branch callback cancellations. 

Still this patch allows to separate a safe to execute destructors for native iterators from untrusted scripted close hooks which may or may not be excecuted depending on the policy or what ever decisions. I would prefer to start optimizing when it is known that for a new feature it is possible to properly recover from denial-of-service rather then to ignore it until it is too late.

Comment 7

[Brendan Eich [:brendan]]

(In reply to comment #6)
> nativeIteratorStates is only used by js_Enumerate, any other implementation of
> the enumerate hook is not covered by this. And unfortunately there is no way
> AFAICS to know that a particular enumeration state is an instance of
> JSNativeIteratorState as otherwise the marking of the state can be done from
> iter_mark.   

Again, let's use the 80-20 (or in this case 99.9%-0%) rule.  The only common case where we should try to avoid GC restarts is the for-in/for-each-in case.

> > - Does your patch assume that these iterators all are flagged with
> > JSITER_HIDDEN -- that is, not accessible by script, therefore not subject to
> > close hook being overrridden by a scripted function?
> 
> In the current implementation instances of js_IteratorClass never access close
> property and just close the native iterator from their close hook. Barring a
> bug the patch does not change this ignorance of the close property but just
> moves the finalization away from the expensive close hook.  

I know, that's why I suggest an even simpler patch, to remove those iterators that are closed by JSOP_ENDITER (99.9% common case, I surmise) from causing any GC action.  Why not finalize as well as close from JSOP_ENDITER, if JSITER_HIDDEN is set?

> That does not work due to 
> 
> for (var i in ...) {
>     while (true);
> }
> 
> That would be killed by the long running script detector. Since currently the
> interpreter does not ensure that for JSITER_HIDDEN iterators the close hook is
> called in cases like that, I thought the reliance on GC is necessary. Plus due
> to the intention to copy Python 100% a case like
> 
> for (var i in ...) {
>     yield i;
> }
> 
> also assumes that GC would take of leaked native iterators. 

Yes, this is the 0.1% case, and since we don't execute JSOP_ENDITER, we can leave such hard cases for the GC to take care of (with restart cost).

> But you are right that it would be worth to make sure that for non-licked
> trusted iterators their close hook is executed even on branch callback
> cancellations.

I was not suggesting breaking the close protocol, just optimizing it for the very common case where JSOP_ENDITER does execute.

> Still this patch allows to separate a safe to execute destructors for native
> iterators from untrusted scripted close hooks which may or may not be excecuted
> depending on the policy or what ever decisions. I would prefer to start
> optimizing when it is known that for a new feature it is possible to properly
> recover from denial-of-service rather then to ignore it until it is too late.

I see -- in that case I'd still hope for some even more eager finalization in the JSITER_HIDDEN + JSOP_ENDITER case.

/be

Comment 8

[Igor Bukanov]

(In reply to comment #7)
> > That does not work due to 
> > 
> > for (var i in ...) {
> >     while (true);
> > }
...
> Yes, this is the 0.1% case, and since we don't execute JSOP_ENDITER, we can
> leave such hard cases for the GC to take care of (with restart cost).

But this is not 0.1% of case, this is 100% of case since any branch can trigger the branch callback. So to make this completely safe either *all* iterators should be prepared for GC including hidden ones or the interpreter should be patched to execute JSOP_ENDITER for trusted (and only for trusted!) iterators  even on branch callback cancellations.

Still without separating the destruction of native iterators from the close hook the engine inherently leaks on shutdown. Just consider:

var iter = (function() {})();

iter.close = function() {
    new Iterator([0,1,2]);
}

Since the close hooks are not allowed to be installed on the shutdown, this would leak the native iterator state. The patch fixes that - this is why I changed the severity from "enhancement" to "normal". Optimization can come later when we would have back an engine that can cleanup own garbage.

Comment 9

[Brendan Eich [:brendan]]

(In reply to comment #8)
> > Yes, this is the 0.1% case, and since we don't execute JSOP_ENDITER, we can
> > leave such hard cases for the GC to take care of (with restart cost).
> 
> But this is not 0.1% of case, this is 100% of case since any branch can trigger
> the branch callback.

My 0.1% was about the actual dynamic frequency of iterators needing GC finalization rather than JSITER_HIDDEN stack-based finalization.

> So to make this completely safe either *all* iterators
> should be prepared for GC including hidden ones or the interpreter should be
> patched to execute JSOP_ENDITER for trusted (and only for trusted!) iterators 
> even on branch callback cancellations.

Why is this either-or?  Why can't JSOP_ENDITER expedite finalization for the common case of cleanly terminated loops, and the GC act as a backstop?

> Still without separating the destruction of native iterators from the close
> hook the engine inherently leaks on shutdown. Just consider:
> 
> var iter = (function() {})();
> 
> iter.close = function() {
>     new Iterator([0,1,2]);
> }
> 
> Since the close hooks are not allowed to be installed on the shutdown, this
> would leak the native iterator state. The patch fixes that - this is why I
> changed the severity from "enhancement" to "normal". Optimization can come
> later when we would have back an engine that can cleanup own garbage.

Ok, I did not mean to hold up a fix here, only to point out that expediting close via JSOP_ENDITER could also finalize (that is, could remove any data structure that would cause a GC restart, this avoiding restarts in the 99%-common case).  Agreed?

Reviewing next.

/be

Comment 10

[Brendan Eich [:brendan]]

Comment on attachment 226616 [details] [diff] [review]
Implementation

>+/*
>+ * Forward declaration for opaque JSRuntime.iterators.
>+ */
>+typedef struct JSIter JSIter;

Naming convention favors JSIterator rather JSIter, but in this case an even longer and more precise name is called for: JSNativeIterator.  Calling the local vars that point to such structs "iter" is fine, I am arguing only for typename consistency.

On this note, though, isn't it possible to avoid the extra private GC-thing by using another reserved slot in the JSObject for native default iterators as the link field?

>@@ -326,16 +331,22 @@ struct JSRuntime {
>     JSObject            *functionNamespaceObject;
> 
>     /*
>      * A helper list for the GC, so it can mark native iterator states. See
>      * js_MarkNativeIteratorStates for details.
>      */
>     JSNativeIteratorState *nativeIteratorStates;
> 
>+    /*
>+     * A helper list for the GC, so it can finalize iterator states before
>+     * the iteratable objects.
>+     */
>+    JSIter *iterators;

Nit: This should be indented to align declarator with the bulk of the JSRuntime structs, as usual.

>+struct JSIter {
>+    JSObject *iterable;
>+    jsval state;
>+    uint8 flags;
>+    JSIter *next;
>+};

Sorry to harp on style, but aligning declarators is prevailing style and seems more readable still.

>+#define GET_ITER(cx, iterobj, iterp)                                          \
>+    JS_BEGIN_MACRO                                                            \
>+        JS_ASSERT(OBJ_GET_CLASS((cx), (iterobj)) == &js_IteratorClass);       \
>+        *(iterp) = (JSIter *)JS_GetPrivate((cx), (iterobj));                  \
>+        JS_ASSERT((*iterp));                                                  \
>+    JS_END_MACRO

To match revised typename, GET_NATIVE_ITERATOR (even though this macro si private).  Besides consistency, this seems less likely to collide in future.

>+static uint32
>+iter_mark(JSContext *cx, JSObject *obj, void *arg)

Nit: Although other private class hooks use abbreviated classname prefixes, this file uses generator_*, so if you can stand it, iterator_mark is more consistent and matches recent revisions of this file.

>+    if ((iter->flags & JSITER_FOREACH) && OBJECT_IS_XML(cx, iterable)) {
>+        ((JSXMLObjectOps *) iterable->map->ops)->
>+            enumerateValues(cx, iterable, JSENUMERATE_DESTROY, &iter->state,
>+                            NULL, NULL);
>         } else

Looks like the } else should be unindented one level.
>-JSExtendedClass js_IteratorClass = {
>-  { "Iterator",
>-    JSCLASS_IS_EXTENDED |
>-    JSCLASS_HAS_RESERVED_SLOTS(2) | /* slots for state and flags */
>-    JSCLASS_HAS_CACHED_PROTO(JSProto_Iterator),
>-    JS_PropertyStub,  JS_PropertyStub,  JS_PropertyStub,  JS_PropertyStub,
>-    JS_EnumerateStub, JS_ResolveStub,   JS_ConvertStub,   JS_FinalizeStub,
>-    JSCLASS_NO_OPTIONAL_MEMBERS },
>-    NULL,             NULL,             NULL,             iterator_close,
>-    JSCLASS_NO_RESERVED_MEMBERS
>+JSClass js_IteratorClass = {
>+  "Iterator",
>+  JSCLASS_HAS_PRIVATE | JSCLASS_HAS_CACHED_PROTO(JSProto_Iterator),
>+  JS_PropertyStub,  JS_PropertyStub,  JS_PropertyStub,  JS_PropertyStub,
>+  JS_EnumerateStub, JS_ResolveStub,   JS_ConvertStub,   JS_FinalizeStub,
>+  NULL,             NULL,             NULL,             NULL,
>+  NULL,             NULL,             iter_mark,        NULL
> };

Somehow class member initializers got unindented by two spaces.

>+    /*
>+     * Everything is initialized, register the iterator with the global list to
>+     * ensure that we always call JSENUMERATE_DESTROY before finalization of
>+     * iterable and iter GC things.

Nit: "so register" after "Everything is initialized, ", and rewrap.

Looks good otherwise, main point above the nit-picking is to avoid allocating a separate private GC-thing.  This should save space and cycles accessing the reserved slots of the native default iterator object.

/be

Comment 11

[Igor Bukanov]

> On this note, though, isn't it possible to avoid the extra private GC-thing by
> using another reserved slot in the JSObject for native default iterators as the
> link field?

An extra slot would require to patch js_NewObject to allocate more then  JS_INITIAL_NSLOTS initially and I wanted to avoid that. And it is not possible to merge the link with flags: there are 3 flags but only 2 bits are spare in the next link pointer after accounting for using one bit for PRIVATE jsval. So a private struct was a natural solution that follows the rest of the code.

Yes, this eats more memory. But a simple optimization in JSObject would give that back for most of for-in cases as there one can merge JSNativeIteratorState with id array and use malloc only once. Moreover, an extension of the patch from bug 331966 would allow to allocate the initial slots and private objects together with JSObject for most sources in js/src/*.c. I.e. why focus on optimizing the iterator when one can do it for all objects?

Comment 12

[Igor Bukanov]

Attachment: Implementation v2

This is a nit resolver. I renamed JSIter to JSIterator, not JSNativeIterator as that clashes with already taken JSNativeIteratorState. The latter does not denote a state of all native iterators but rather the state of JSObject one. 

I agree that JSNativeIterator is a better name, but then JSNativeIteratorState should be renamed as well. JSObjectIteratorState or perhaps even JSObjectCursor?

Comment 13

[Brendan Eich [:brendan]]

(In reply to comment #11)
> An extra slot would require to patch js_NewObject to allocate more then 
> JS_INITIAL_NSLOTS initially and I wanted to avoid that. And it is not possible
> to merge the link with flags: there are 3 flags but only 2 bits are spare in
> the next link pointer after accounting for using one bit for PRIVATE jsval. So
> a private struct was a natural solution that follows the rest of the code.

Yes, it's natural in light of the private data slot, but it is a change from the status quo ante.  Trying to hold the line is better than regressing space usage, even if other wins are in sight. But it's just one goal among several, I agree.

> Yes, this eats more memory. But a simple optimization in JSObject would give
> that back for most of for-in cases as there one can merge JSNativeIteratorState
> with id array and use malloc only once. Moreover, an extension of the patch
> from bug 331966 would allow to allocate the initial slots and private objects
> together with JSObject for most sources in js/src/*.c. I.e. why focus on
> optimizing the iterator when one can do it for all objects?

I'm not, but here we are in this particular bug, necessarily focusing on its patch and trying to avoid regressing space costs for native default iterators.  It's not a big deal.  r+me in a second,

/be

Comment 14

[Brendan Eich [:brendan]]

Comment on attachment 227080 [details] [diff] [review]
Implementation v2

>+/*
>+ * Forward declaration for opaque JSRuntime.iterators.
>+ */
>+typedef struct JSIterator JSIterator;

I like it, mirrors existing Function object / JSFunction, etc., object / private struct naming.

>     JSObject            *functionNamespaceObject;
> 
>     /*
>      * A helper list for the GC, so it can mark native iterator states. See
>      * js_MarkNativeIteratorStates for details.
>      */
>     JSNativeIteratorState *nativeIteratorStates;
> 
>+    /*
>+     * A helper list for the GC, so it can finalize iterator states before
>+     * the iteratable objects.
>+     */
>+    JSIterator            *iterators;
>+
> #ifdef DEBUG
>     /* Function invocation metering. */
>     jsrefcount          inlineCalls;
>     jsrefcount          nativeCalls;
>     jsrefcount          nonInlineCalls;
>     jsrefcount          constructs;

Sorry, don't shoot me -- I meant to return to the standard declarator starting column, not to match the overindented *nativeIteratorStates starting column.

> #if JS_HAS_GENERATORS
>     /* Expose Iterator and initialize the generator internals if configured. */
>-    proto = JS_InitClass(cx, obj, NULL, &js_IteratorClass.base, Iterator, 2,
>+    proto = JS_InitClass(cx, obj, NULL, &js_IteratorClass, Iterator, 2,
>                          NULL, iterator_methods, NULL, NULL);
>-    if (!proto)
>+    if (!proto || !JS_SetPrivate(cx, proto, (void *)&iterPrototypePrivate))
>         return NULL;
>-    proto->slots[JSSLOT_ITER_STATE] = JSVAL_NULL;

Minor hygiene question: if you configure jsconfig.h's JS_VERSION so that JS_HAS_GENERATORS is 0, do for-in loops still work?  We definitely do not want Iterator defined in the global object in such configs, but of course for-in loops must work as before.

r=me with nits picked

/be

Comment 15

[Igor Bukanov]

(In reply to comment #13)
> Yes, it's natural in light of the private data slot, but it is a change from
> the status quo ante.  Trying to hold the line is better than regressing space
> usage, even if other wins are in sight.

Note that this a space regression compared with using close hooks, it is not a space regression compared with the version before that. There the space overhead of AddRoot was enough to allow for JSIterator to have even more fat.

Comment 16

[Brendan Eich [:brendan]]

(In reply to comment #15)
> Note that this a space regression compared with using close hooks, it is not a
> space regression compared with the version before that. There the space
> overhead of AddRoot was enough to allow for JSIterator to have even more fat.

I know -- I was happy to get rid of that js_AddRoot!

Of course, I left bugs in the wake of the landing for bug 326466, which you've kindly run to ground, so I'm in no position to complain.  Let's get on with the further optimizations and call it even ;-).

/be

Comment 17

[Igor Bukanov]

Attachment: Implementation v3

Here is a patch that keeps the original code of using parent/private slots. To register the iterators it uses a table of objects in the same way GC tracks the iterators. I factored table allocation/shrinking into a commom functions in jsgc.c . There is also fixes to consistenly use JSVAL_VOID to indicate a closed iterator state.

Now what is interesting is that the patch emphases that there are 2 types of close hooks, a simple native hooks that never allocate GC things and never make dead things reachable and a complex hooks that can execute arbitrary code. The former can always be executed right before the sweaping phase. Thhe latter must wait until finalization is done and be exceuted outside GC which makes them effectively resurrection, not close hooks.

I suspect that most native close hooks want to belong to the first class and only generators would be a source of the resurrection complexity. Thus perhaps it make sence to define JSObjectOp.close to denote exactly the first class of hooks with asserts enforcing their simple nature?      

For now I do not ask for a review as I have not done any testing of the patch.

Comment 18

[Igor Bukanov]

Attachment: Implementation v4

This is a version of the previous patch wich consistently use JSVAL_NULL to indicate that the state should not be closed so JSENUMERATE_DESTROY is not called when JSENUMERATE_NEXT sets the state to JSVAL_NULL.

Comment 19

[Brendan Eich [:brendan]]

Comment on attachment 227220 [details] [diff] [review]
Implementation v4

>+            /*
>+             * Simplify the overflow detection assuming pointer is bigger then
>+             * byte.

s/then/than/ and put than on the second line.

>+            capacity = (capacity < info->linearGrowthThreshold)
>+                 ? 2 * capacity
>+                 : capacity + info->linearGrowthThreshold;

Prevailing style indents ? and : to starting column of condition.

>+#ifdef DEBUG
>+    memset(table->array + newCount, JS_FREE_PATTERN,
>+               (capacity - newCount) * sizeof table->array[0]);

Overindented second line.

>+js_RegisterClosableIterator(JSContext *cx, JSObject *obj)

Closeable is the right spelling, AFAICT.  Someone correct me if I'm wrong, and tell Python folks too.

>+{
>+    JSRuntime *rt;
>+    JSBool ok;
>+
>+    /*
>+     * Return early without doing anything if shutting down, to prevent a bad
>+     * close hook from ilooping the GC.  This could result in shutdown leaks,
>+     * so printf in DEBUG builds.
>+     */
>+    rt = cx->runtime;
>+    JS_ASSERT(!rt->gcRunning || rt->gcClosePhase);
>+
>+    JS_LOCK_GC(rt);
>+    ok = AddToPtrTable(cx, &rt->gcIteratorTable, &iteratorTableInfo, obj);
>+    JS_UNLOCK_GC(rt);
>+    return ok;
>+}

The comment looks completely stale.

>+        if (js_IsAboutToBeFinalized(cx, obj)) {
>+            js_CloseIteratorState(cx, obj);
>+        } else {
>+            array[newCount++] = obj;
>+        }

Overbraced according to prevailing style.

Generally seems good -- how do codesizes compare between two approaches?  How about average and worst-case dynamic mem usage?

/be

Comment 20

[Igor Bukanov]

Attachment: Implementation v4b

This is the previous patch with nits addressed.

Comment 21

[Igor Bukanov]

(In reply to comment #19 by Brendan)
> How about average and worst-case dynamic mem usage?

The original patch would add 4-word GC-thing to each iterator. For scripts that do not use E4X that would be translated into allocation of a new GC arena for  for-in loops since the iterator would be a single user  of 4-word things. 

With  E4x activated the overhead depends on how often GC is run. Assuming that the iterator table did not hit the linear growth limit, the average overhead would be 1.5 word per iterator  with the table approach versus 4.25 words with private slots. (There 0.25 accounts for GC thing overhead.) When the table size hits the linear growth, then the table overhead, of cause, reduces towards the one word limit.

But this is not a clear win for the new patch since instead of the private slot the code in the original patch can use a separated list with  GC-allocated cells without touching the current code that uses slots.  Then the overhead would be just 1.5 against 2.125 words with simpler code for the list. But since the table growth/shrinking code is shared with the close hooks (or resurrection hook how I prefer to call them), I opted for the table approach.

And BTW, I really like that trick with encoding table capacity as a function of number elements in the table. I did not see that before. Is it something well known?

Comment 22

[Igor Bukanov]

(In reply to comment #19 by Brendan)
> Generally seems good -- how do codesizes compare between two approaches?  

The stripped optimized build of jsshell with either of the patches remains the same 558012 bytes with GCC 4.0.3 on Ubuntu 6.06. The sizes of relevant objects files are:

Original private slot approach:
7668 ./Linux_All_OPT.OBJ/jsgc.o
6448  ./Linux_All_OPT.OBJ/jsiter.o

The new table code:
7668 ./Linux_All_OPT.OBJ/jsgc.o
6416 ./Linux_All_OPT.OBJ/jsiter.o

Comment 23

[Brendan Eich [:brendan]]

(In reply to comment #21)
> Then the overhead
> would be just 1.5 against 2.125 words with simpler code for the list. But since
> the table growth/shrinking code is shared with the close hooks (or resurrection
> hook how I prefer to call them), I opted for the table approach.

Cool, I buy it.

> And BTW, I really like that trick with encoding table capacity as a function of
> number elements in the table. I did not see that before. Is it something well
> known?

I should patent it ;-).

/be

Comment 24

[Brendan Eich [:brendan]]

Comment on attachment 227385 [details] [diff] [review]
Implementation v4b

>-static void
>-iterator_close(JSContext *cx, JSObject *obj)

Just noticed that js_CloseIteratorState diffs against this well, but it's located later, just below its nearest call site in js_CloseNativeIterator.  Not asking to move it up, just wondering whether that diffability is worth more than the aesthetic value of putting it later.

>+static size_t
>+PtrTableCapacity(size_t count, const JSPtrTableInfo *info)
>+{
>+    size_t linear, log, capacity;
>+
>+    JS_ASSERT(info->minCapacity <= info->linearGrowthThreshold);
>+
>+    linear = info->linearGrowthThreshold;

Swap these lines to use linear in the assertion, and crunch them together (i.e., lose the blank line between) since they are coupled by that data dependency and the idea of validating the threshold.

>+    if (count == 0) {
>+        capacity = 0;
>+    } else if (count < linear) {
>+        log = JS_CEILING_LOG2W(count);
>+        JS_ASSERT(log != JS_BITS_PER_WORD);
>+        capacity = 1 << log;

For ultimate portability, this should be (size_t)1 << log.

Looks good otherwise.

/be

Comment 25

[Igor Bukanov]

Attachment: Implementation v4c

Here is a version to address comment 24. I moved js_CloseIteratorState back to the top of jsiter.c to minimize the current and possible future diff if a separated pre-finalization hook  would be added to JSClass.

Comment 26

[Brendan Eich [:brendan]]

Comment on attachment 227471 [details] [diff] [review]
Implementation v4c

Looks good, thanks.

/be

Comment 27

[Igor Bukanov]

I committed the patch from comment 25 to the trunk.