That Infernal Scene Graph Warning Message II

In my earlier post on this topic I hinted that we had found a resolution to the issue surrounding the warning message, I hinted further in some of my replies to comments, and I even left it as sort of a cliffhanger as to what the resolution was. So, here’s the resolution.

We’ve decided that when a node is added to a group, that node is automatically removed from the group that previously owned it, if any. (Let’s call this the “auto-remove” feature.) We’ve also decided to turn off the warning message by default, but to have it be enabled optionally, possibly via a system property, for debugging purposes. Finally, we’ve relaxed the enforcement of some scene graph invariants in cases where the group’s content sequence is bound.

What’s the big deal? Well, there were a bunch of things pulling us in different directions. During the development of 1.2, we added code to prevent nodes from appearing more than once in the scene graph or creating cycles in the scene graph. One case in particular caused us a lot of trouble: adding a node to a group while the node was already a member of another group. We fully intended to disallow this case, and require that code remove a node from its old group before adding it to the new one. Unfortunately this caused a lot of our internal code to break. In versions 1.1 and prior, auto-remove was the specified behavior, and a surprising amount of code relied on this. Given the number of cases we ran across internally, we were sure that this would break a lot of external code. For this reason we decided to relax the restriction for this particular case, continue the auto-remove behavior temporarily, and issue a warning message instead. In a subsequent release, we were going to change the warning to an error and to remove auto-remove behavior.

During the development of our current release, we kept running into this issue. A couple of us wrote code that we thought was reasonable, yet it surprised us when the warning message came out! We had a few hallway conversations from time to time, but a clear-cut answer never emerged. Finally, we realized that we had to get the interested parties in a room and have a knock-down, drag-out meeting to resolve the issue. And so on October 7, 2009, Amy Fowler, Kevin Rushforth, Richard Bair, and I got into a conference room to decide the issue. Three hours later — with no breaks! — we had decided. Actually, it was a great meeting, without a lot of conflict. There were just a lot of issues to cover. Each of us came into the meeting with our initial opinions, but the issues were so close that I think each one of us switched sides at least once during the meeting.

Obviously I can’t reproduce the entire discussion here, but the gist of the arguments went something like this:

1. It’s simpler, more efficient, and more consistent to disallow auto-remove.
2. On the other hand, 1.1 allowed auto-remove, so this is incompatible.
3. On the third hand, we expect people to set up scene graphs at initialization time and modify nodes in-place, instead of doing scene graph surgery.
4. On the gripping hand, some applications really do need to move nodes around in the scene graph.
5. Well, that’s not too difficult, just remove the node from the old group first.
6. Sometimes (especially with bind) it’s difficult or even impossible to remove the node from the old group first.
7. But most of the cases we’ve seen with bind are actually poor coding practices that we want to have emit a warning message.

And so on, back and forth, and around in circles.

Let’s start off with the topic of moving nodes around within the scene graph. What’s the problem? Suppose you have a node n that you wanted to insert into group g. If you do this:

insert n into g.content;

This might generate the warning message if n were already a member of another Group. To avoid this, you’d have to do:

if (n.parent instanceof Group) {
    delete n from (n.parent as Group).content;
}

This is a bit subtle but overall pretty straightforward. First we have to test that n.parent is a Group. (It might be a CustomNode instead.) Note also that if n has no parent, n.parent will be null and the instanceof test will fail. If the test succeeds, we can cast n.parent to a Group and then remove n from the content variable. This is a bit inconvenient but not too bad. We could wrap this up in a nice function and use it in a bunch of places. We even considered adding a utility function to the scene graph to handle this.

Things start to get hairy, though, when when you add bind into the mix. What are people doing with bind that makes it difficult or impossible to remove the node from the old group first? Which uses of bind are “poor coding practices” and which are legitimate?

In order to answer these questions, we’ll need to review the semantics of bind. Consider the following:

var p = bind q + r;

If either q or r changes, the expression is recomputed and assigned to p. The rule is that only the subtree of the expression affected by the variable change is re-evaluated. So if q changes, r isn’t recomputed, and instead its saved value is added to q to get the result that’s then assigned to p. This is hard to see if q and r are simple variables, so let’s make the expression a bit more complicated:

var p = bind f(q) + g(r);

where f() and g() are functions. In this expression, if q changes, f() is called with the new value of q, as one would expect. However, the function g() is not called again. Instead, the saved value of the previous call to g(r) is used, added to the new value of f(q), giving the result assigned to p. You can see this by putting println() statements into f() and g() to see when they’re called. Try it!

Now let’s throw an object literal into the expression:

var xval:Number = ...;
var yval:Number = ...;
var p = bind Point2D { x: f(xval) y: g(yval) };

What does this do? Initially it calls f(xval) and g(yval), then creates a new Point2D instance and initializes its x and y variables to the values obtained by calling the functions. Now suppose xval changes.  Naturally f(xval) has to be called again; as before, the saved value of g(yval) is used and function g() isn’t called again. These values are then used to construct a new instance of a Point2D, which is then assigned to p. What happens to the old instance? Well, it still exists (probably) but if it’s no longer referenced, it’ll eventually get garbage collected.

The important point here is that an object literal is an expression that creates a new instance of an object, not unlike calling a constructor. It’s kind of similar to something like this:

var p = new Point2D(f(xval), g(yval));

except that Point2D, being a JavaFX class, doesn’t actually have a (Number, Number) constructor.

Usually we don’t want to create new instances of objects when the bind-expression is re-evaluated. In some sense we might prefer to do something like this:

var p = Point2D { x: bind f(xval) y: bind g(yval) };

Instead of creating a new Point2D object each time xval or yval changes, it would create one object and mutate its variables in-place. This doesn’t work though, since the x and y variables of Point2D are public-init. To bind to a variable initializer in an object literal, that variable must be declared public so that code outside the class can modify it. So if you want to bind something that has type Point2D, you always end up creating new instances.

Most scene graph objects have public variables that can be bound. Consider this:

var rect = Rectangle {
    x: bind xval
    y: bind yval
    width: bind wval
    height: bind hval
};

This works quite nicely. One Rectangle instance is created and assigned to rect. If any of xval, yval, wval, or hval change, the variables in that single Rectangle instance are mutated, and the effect is that the Rectangle moves or changes size in-place in the scene graph. In turn, if you hook these values up to a Timeline or to one of the Transition classes, that’s how you get animations.

Now instead of writing all those binds, couldn’t we just do this?

var rect = bind Rectangle {
    x: xval
    y: yval
    width: wval
    height: hval
};

We could write this, and it would work, in that we’d get a Rectangle animating in the proper way. But it’s enormously wasteful. Each time any of xval, yval, wval, or hval changes, a new Rectangle instance is created and the old one is thrown away.

It gets worse.

var g = Group {
    content: bind [
        Rectangle {
            x: xval
            y: yval
            width: wval
            height: hval
        }
    ]
];

Now, when any of xval, yval, wval, or hval changes, a new Rectangle is created. Then, because the content sequence of the Group is bound, the old Rectangle is removed from the scene graph and the new Rectangle is inserted in its place. It’s quite common for an operation to change both the width and height of the Rectangle, by changing wval and hval. Let’s say wval changes first. This creates a new Rectangle and replaces the old Rectangle. Then, hval changes, and another new Rectangle is created and replaces the one that had just been created. Furthermore, replacing things in the scene graph is more expensive than moving pointers around. Additional calculations occur, such as recomputing bounds, invalidating and caching transformations, etc. Some of this can be done lazily (indeed, in the next release, more of it will be). But it’s undeniable that creating new objects, generating lots of garbage, and doing scene graph surgery because of where a bind is placed, is very expensive. It would be a lot more efficient to rewrite the above code like so:

var g = Group {
    content: [
        Rectangle {
            x: bind xval
            y: bind yval
            width: bind wval
            height: bind hval
        }
    ]
};

This mutates the Rectangle in-place, doesn’t generate any garbage, and doesn’t do any scene graph surgery. We’ve improved the efficiency of some of our code quite significantly just by moving bind around.

Now, what does this have to do with the auto-remove behavior that we’ve been debating? Let’s take a look at this variation:

var g = bind Group {
    rotate: angle
    content: [
        Rectangle {
            x: xval
            y: yval
            width: wval
            height: hval
        }
    ]
};

Note that the bind is outside the group. This might look convenient, since the scene graph will automatically be updated if any of angle, xval, yval, wval, or hval is modified. But look carefully: suppose that the value of angle changes. Since it’s inside the Group object literal, a new Group object is created and its rotate variable is set to the new the new value of angle. There’s no need to create another Rectangle object, though, since none of its values have changed. Instead, the same Rectangle object is placed into the content variable of the new Group, which is then assigned to g. The old Group is unreferenced and will eventually be garbage collected. Now, who removes the Rectangle from the old Group? Aha!

This is where the auto-remove issue comes up. In the above code fragment, changing the value of angle causes the same Rectangle instance to be placed into the new Group, but it’s not removed from the old Group. As I mentioned previously, in release 1.1 auto-remove was the specified behavior, so placing the Rectangle into the new Group would automatically and silently remove it from the old Group. Furthermore, there’s really no way for application code to get in there and remove the Rectangle from the old Group first; the bind processing pretty much happens all at once. This would seem to be an argument in favor of auto-remove.

But wait, this code is pretty wasteful. It turns out that the auto-remove warning message was actually pretty useful, since it pointed out a bunch of places in our code where we were doing stuff like this: generating useless garbage and performing wasteful scene graph surgery. We ended up rewriting the code along these lines:

var g = Group {
    rotate: bind angle
    content: [
        Rectangle {
            x: bind xval
            y: bind yval
            width: bind wval
            height: bind hval
        }
    ]
};

True, we had to write bind five times. But this made things much more efficient, since it didn’t create any excess objects and it avoided doing any scene graph surgery. It also got rid of the warning message! So that convinced us to leave the warning message in, to get people to fix their bad code, and eventually to turn the warning into an error and effectively disallow auto-remove.

Or did it?