d3.timer internal queue size when created via transition

[Scott Cameron]

Hi,

I'm profiling some high-volume transitions and I came across something I'm having trouble understanding so I thought I'd ask the experts.

When a new transition is created it invokes an initial d3.timer passing in an anonymous function as a callback.  This anonymous function defines a few internal functions itself (start(), tick() and stop()).  When the function is run by the timer, it invokes multiple other d3.timers -- one per element in the transition's selection -- this time feeding in the internal tick() function as a callback.

Internally, d3.timer keeps a shared queue of current timer information called d3_timer_queue.  For efficiency, before adding a new timer into the queue it searches through the existing entries, and if a callback is found that is identical to the one being added it will just use the existing entry.

What I'm seeing is that this code that handles the case where a matching callback is found never seems to get executed.  Since every d3.timer invoked for a particular transition uses exactly the same tick() closure as described above, I was expecting that there would only be a single timer added to the queue for a transition and it would be used by all timers from that same transition.  But this doesn't happen so my transition of 5000 elements ends up with 5000 entries in the timer queue and the loop runs about 12,000,000 times (n(n+1)/2).

The thing is, I don't understand why this is the case.  If I invoke d3.timer twice and pass in the same function instance it shares a queue entry just fine.  What is it about the tick() closure in the anonymous function inside transition that I'm missing?

Thanks,

scott

[Mike Bostock]

> Since every d3.timer invoked for a particular transition uses exactly the
> same tick() closure as described above, I was expecting that there would
> only be a single timer added to the queue for a transition and it would be
> used by all timers from that same transition.

The thing that you are missing is that each closure is a separate
Function object, so they are all registered as separate timers. So, if
I have a global (static) function, and I register it twice, then the
second registration replaces the first:

function globalCallback() {}
d3.timer(globalCallback); // #1
d3.timer(globalCallback); // #2 replaces #1

However, if you use a closure in a new context, then you have a new
function, so they are registered separately:

function registerTimer() {
function localCallback() {}
d3.timer(localCallback);
}
registerTimer(); // #1
registerTimer(); // #2 does not replace #1

Another way to see this:

function createClosure() {
return function() {};
}
var a = createClosure();
var b = createClosure();
console.log(a === b); // false

Another important detail to note is that functions are hoisted, so
each iteration of a loop would not normally create a new instance of a
function. However, the code here uses d3_selection_each (akin to
array.forEach) to iterate over the elements in the selection; since
the closure is defined within the single execution of the "each"
callback function, each element gets a separate closure which causes
separate timers.

> But this doesn't happen so my transition of 5000 elements ends
> up with 5000 entries in the timer queue and the loop runs about
> 12,000,000 times (n(n+1)/2).

I suspect it would be trivial to optimize this check for the common
case where we're adding a new function to the timer queue, so that you
only have to scan the queue in the rare case where you're replacing an
existing timer.

Mike

[Mike Bostock]

> I suspect it would be trivial to optimize this check for the common
> case where we're adding a new function to the timer queue

A related optimization has been implemented in release 2.10.3:

https://github.com/mbostock/d3/commit/443f0e648eaa9066350935c1058ab771877a3cf7

Mike

[Scott Cameron]

Another important detail to note is that functions are hoisted, so
each iteration of a loop would not normally create a new instance of a
function. However, the code here uses d3_selection_each (akin to
array.forEach) to iterate over the elements in the selection; since
the closure is defined within the single execution of the "each"
callback function, each element gets a separate closure which causes
separate timers.

 Thanks, Mike.  The part about the d3_selection_each made me realize where my confusion was.  I was incorrectly thinking about the relationship between nested functions like tick() and the containing function as analogous to the relationship between properties and their containing object.  Since the "each" callback function is created only once I was thinking that the nested functions were also created only once.  But, of course, that's not how functions work at all.  I actually knew better than this (at some level) so thanks for jarring something loose in there for me. :)

I'll give the 2.10.3 a try to see if it makes a difference.  It looks like it is still going to use a timer function per element in the transition, though, right?  Is there a reason why each element needs to have it's own separate timer as opposed to using a single timer for the entire transition?

Cheers,

scott

[Mike Bostock]

> Is there a reason why each element needs to have it's own separate
> timer as opposed to using a single timer for the entire transition?

Yes; each element can have a different delay and duration. Also, the
transition on some elements (though not necessarily all) may be later
superseded by a new transition. Also, the overhead of one function per
timer is very small.

Mike