Heuristics for array-array ops with disjoint bounds

[saik0]

Motivation

For the cost of a few cheap instructions and one branch: we are able to avoid the computation entirely.

I was inspired by the "broad phase" of collision detection used in various physics simulations. First shapes that might collide are detected by checking if their axis-aligned bounded boxes intersect. Only then perform the more expensive computation to check if the shapes intersect. This proposed scheme is similar, but over a single dimension.

Overview

Let the bounds of a container be [min,max]

The bounds of array containers are cheap to compute: They are the first and last elements, both are guaranteed to be in cache.

Determining if the bounds are disjoint should be cheap to compute.

Operators

Intersection

If the bounds are disjoint the intersection is empty. We can return an empty Vec, which is non-allocating. For assignment, clear the existing vec, which equivalent to setting it's len.

Difference

If the bounds are disjoint the difference is equal to the minuend. Either a clone, or a no-op in the case of assignment.

Union

If the bounds are disjoint the union can be computed simply by copying the entire contents of both operands. Of course: beginning with the array with the smaller first element.

Symmetric difference

If the bounds are disjoint it follows that the intersection is empty. This is equivalent to a union.

Extra notes

1. This may also apply to run containers, I am still working on digesting the runs paper
2. This would be applicable to bitsets only if min and max did not require linear scans. It might be worth experimenting to evaluate if tracking min/max on-the-fly as with cardinality to enable this optimization would be a net-perfoamnce gain (but requiring an extra 4 bytes per bitmap). My speculative guess is no, but data sometimes surprises me.

Perhaps @lemire can illuminate us as to whether or not this has been experimented with