RFR: 8332895: Support interpolation for backgrounds and borders [v3]

[Michael Strauß]

On Sun, 4 Aug 2024 23:01:48 GMT, John Hendrikx <jhendrikx at openjdk.org> wrote:

>> In practice, any list that is passed into this method is already unmodifiable. This isn't a general-purpose method, it's tailored towards its usage for `Border` and `Background` interpolation, and the optimization scheme that is used in these classes.
>
> Alright, I get how it works now, and that there is a lot of reference equality checking going on by callers.

Let me explain how I got here in the first place. My observation is that `Background` and `Border` graphs can be quite large, and they are deeply immutable. But often, only tiny parts of it change during a transition. So my question was: wouldn't it be nice if we could re-use the unmodified parts of the graph, instead of copying it entirely, potentially tens of thousands of times per second?

The `Interpolatable` contract gives us permission to return an existing instance (and thereby reusing unmodified parts of the graph), so that's good. An initial implementation might look like this (note: this is not the implementation of this PR):


public Border interpolate(Border endValue, double t) {
    Objects.requireNonNull(endValue, "endValue cannot be null");

1:  if (t <= 0 || equals(endValue)) {
        return this;
    }

    if (t >= 1) {
        return endValue;
    }

    List<BorderImage> newImages =
        InterpolationUtils.interpolateListsPairwise(images, endValue.images, t);

    List<BorderStroke> newStrokes =
        InterpolationUtils.interpolateListsPairwise(strokes, endValue.strokes, t);

2:  if (this.images.equals(newImages) && this.strokes.equals(newStrokes)) {
        return this;
    }

3:  if (endValue.images.equals(newImages) && endValue.strokes.equals(newStrokes)) {
        return endValue;
    }

    return new Border(newStrokes, newImages);
}


I've marked three important lines with `1:` to `3:`. These equality comparisons traverse through the object graph many times, and unnecessarily so: each of the sub-objects' `interpolate` method will do the same thing, comparing the same objects recursively again.

So instead of doing a "root to leaf" equality comparison (i.e. starting at `Border` and comparing upwards), I figured that a "leaf to root" comparison would be much simpler in terms of the raw amount of computation required. This reduces a complete sub-graph traversal to a simple identity comparison (but requires cooperating `interpolate()` implementations).

I didn't benchmark whether the time spent on naively copying the entire object graph, or doing the "root to leaf" equality comparison amounts to a significant share of computation, or when it starts becoming a problem (is it hundreds or tens of thousands of transitions?). But I do think that the approach is sound.

At this time, I am not inclined to change the implementation, but to improve the code documentation to make it easier to understand what's going on.

-------------

PR Review Comment: https://git.openjdk.org/jfx/pull/1522#discussion_r1703420442