IntervalTree search is a bottleneck

[stereokai]

IntervalTree search is a performance bottleneck. I narrowed it down to the methods Node.less_than() & Node.equal_to().

The most obvious optimization would be to simplify the if statements. That leads to the question, is there an integral algorithmic reason to force comparing by both key and value in case the tree holds values (in addition to keys)? Will it break IntervalTree if key & value trees would have the option to only search by key?

Cheers for the great project, looking forward to collaborating on this.

[alexbol99]

Hi, @stereokai

Do you mean that in this code calculation of value_less_than may be skipped when key.less_than() returns true? Does is really cause performance problem?

else {    // if tree stores keys and values
    let value_less_than = this.item.value && other_node.item.value && this.item.value.less_than ? this.item.value.less_than(other_node.item.value) :
        this.item.value < other_node.item.value;
    return this.item.key.less_than(other_node.item.key) ||
        this.item.key.equal_to((other_node.item.key)) && value_less_than;
}

Do you have a use case that I can check?

[stereokai]

Hi @alexbol99

Yes, I mean exactly this code. Unfortunately, I don't have anything public set up right now, but I could try to set something up soon if you need it. In the meanwhile, here is a performance profiling (in the red square is IntervalTree code). As you can see more than half the time is spent in less_then():

[stereokai]

@alexbol99 just for the record, optimizing 12.2ms may seem a bit bothersome, but I'm using IntervalTree in the rendering loop of a graphical interface with hundreds to thousands of elements, so the less time spent in it, the better.

[alexbol99]

Tom, I don't say 12ms is something neglectable, it is worth to improve. I just want to understand what kind of data you store in the index. Can you post here your insertion code?

[stereokai]

@alexbol99 Sure, this is it:

        // event is just a plain old JS object.
        interactionIntervals.insert(label, { event, handle: "label" });
        interactionIntervals.insert(lineEdgeStart, { event, handle: "lineEdgeStart" });
        interactionIntervals.insert(lineEdgeEnd, { event, handle: "lineEdgeEnd" });

This is an interesting direction I haven't considered looking at but at AFAIK, the tree ends up comparing the provided values by reference anyway, because they're plain objects, but I might be overlooking something

[alexbol99]

This is my point too. Value object should support a less_than operator. I will check if comparison of plane objects may effect performance

[stereokai]

@alexbol99 Great, looking forward. My initial question still stands though: Is it necessary for IntervalTree to compare both key and value? Or is it possible to make that behavior optional, so users can choose based on their use case?

[alexbol99]

I remember someone asked values to be ordered. Search indeed may be done only by keys

[stereokai]

Then can I submit a PR? I'd be happy to hear from you how you'd like it to work

On Mon, Jun 26, 2023, 14:33 Alex Bol @.***> wrote:

I remember someone asked values to be ordered. Search indeed may be done only be keys

— Reply to this email directly, view it on GitHub https://github.com/alexbol99/flatten-js/issues/144#issuecomment-1607378127, or unsubscribe https://github.com/notifications/unsubscribe-auth/AAUPTLMHJYQML7CV74MBHJLXNF6TLANCNFSM6AAAAAAZSX2GL4 . You are receiving this because you were mentioned.Message ID: @.***>

[alexbol99]

According to this: https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Operators/Less_than less_than for objects performs"multiple rounds of coercion" and indeed may be time consuming for the objects. I would restrict this comparison only for number type

this.item.value < other_node.item.value

And for any other type return false. Also it is possible to take in under condition that item has value, and do not perform any time. If you want to do this, please go ahead, but this code is in interval-tree repo, not in flatten-js. Or I will do it till the end of the week Best, Alex

[stereokai]

Hi Alex,

Also it is possible to take in under condition that item has value, and do not perform any time.

Not sure I understand what you mean here :)

By the way, both less_than() and equal_to() need to be looked at

[alexbol99]

Hi, Tom,

If performance is our main concern, I think this change will be enough:

    _value_less_than(other_node) {
        return this.item.value && other_node.item.value && this.item.value.less_than ?
            this.item.value.less_than(other_node.item.value) :
            this.item.value < other_node.item.value;
    }

    less_than(other_node) {
        // if tree stores only keys
        if (this.item.value === this.item.key && other_node.item.value === other_node.item.key) {
            return this.item.key.less_than(other_node.item.key);
        }
        else {    // if tree stores keys and values
            return this.item.key.less_than(other_node.item.key) ||
                this.item.key.equal_to((other_node.item.key)) && this._value_less_than(other_node)
        }
    }

Redundant comparison will not be performed if this.item.key.less_than(other_node.item.key) is true, which is the most common case.

For equal_to there is no optimization, because items are equal when both key AND value are equal.

Please look at PR https://github.com/alexbol99/flatten-interval-tree/pull/45, if ok, I will publish and then upgrade flatten-js/core to the new version.

[alexbol99]

Hi, Tom, I merged PR and upgraded dependency to interval-tree in the patch v1.3.9. Please verify if performance improved. Thanks, Alex

[stereokai]

@alexbol99 That turned out great! I tried it out now and your changes made a proper difference. Thank you!

Another bottleneck I found is the insert operation:

This one is trickier however, and I couldn't really figure out anything to optimize. If you can spare some time, maybe you can pull off another magic trick :)