 Art by @ritwells
• A Christian.
• A geek.
• A hacker.
• A programmer.
Back to Writings

# SIMD.js Rectangle Intersection

January 2017 · 3 minute read

SIMD.js is cool. You can use it with Firefox or Edge nightly.

Can we speed up rectangle intersection checks? Yes we can! …With a big caveat.

``````class Rectangle {
constructor(x1, y1, x2, y2) {
this.items = new Float32Array(4)
this.items = x1
this.items = y1
this.items = x2
this.items = y2
}

get x1() { return this.items }
get y1() { return this.items }
get x2() { return this.items }
get y2() { return this.items }
}

function rectIntersectsSIMD(r1, r2) {

// r1.x1 r1.y1 r1.x2 r1.y2    r2.x1 r2.y1 r2.x2 r2.y2
// 0     1     2     3        4     5     6     7
const c = SIMD.Float32x4.shuffle(a, b, 0, 1, 4, 5)
const d = SIMD.Float32x4.shuffle(a, b, 6, 7, 2, 3)

}
``````

# Results

Benchmark run using jsperf on Firefox Nightly 53.0a2 (2017-01-30).

 Scaler 792,398,034 ±0.74% ops/s SIMD 1,508,427,115 ±2.40% ops/s Speedup ~190% ops/s

# How It Works

The basic rectangle check logic is as follows:

``````function rectIntersectsScaler(r1, r2) {
return r1.x1 <= r2.x2 &&
r1.y1 <= r2.y2 &&
r1.x2 >= r2.x1 &&
r1.y2 >= r2.y1
}
``````

This is equivalent to:

``````function rectIntersectsScaler(r1, r2) {
return r1.x1 <= r2.x2 &&
r1.y1 <= r2.y2 &&
r2.x1 <  r1.x2 &&
r2.y1 <  r1.y2
}
``````

Properly speaking, we can’t do much with this. Yes yes we could compute `r1.x1 <= r2.x2 && r1.y1 <= r2.y2` and `r2.x1 < r1.x2 && r2.y1 < r1.y2` with separate SIMD operations (and indeed, we would have to do this if we wanted 64-bit coordinates), but I’m doubtful that this would be worth it.

Let’s try a slight tweak:

``````function rectIntersectsScaler(r1, r2) {
return r1.x1 <= r2.x2 &&
r1.y1 <= r2.y2 &&
r2.x1 <= r1.x2 &&
r2.y1 <= r1.y2
}
``````

Wait, what?

Yeah, it’s wrong. It’ll yield a false positive if `r2.x1 == r1.x2` or `r2.y1 == r1.y2`. This is OK for my purposes, but it means this won’t be a drop-in replacement.

Now then.

``````const a = SIMD.Float32x4.load(r1.items, 0)
``````

This loads the `items` `Float32Array` into SIMD registers (if the JIT wants to, anyway).

``````// r1.x1 r1.y1 r1.x2 r1.y2    r2.x1 r2.y1 r2.x2 r2.y2
// 0     1     2     3        4     5     6     7
const c = SIMD.Float32x4.shuffle(a, b, 0, 1, 4, 5)
const d = SIMD.Float32x4.shuffle(a, b, 6, 7, 2, 3)
``````

This is the interesting part. The shuffle function lets us rearrange our data so that the we will compare `c <= d`, `c <= d`, etc.

``````const maskLT = SIMD.Float32x4.lessThanOrEqual(c, d)
Now we just compare `c <= d`, and make sure that all bits in the resulting mask are `1`.
`rectIntersectsSIMD()` yields a false positive if `r2.x1 == r1.x2` or `r2.y1 == r1.y2`. This is because the `<` is transformed into `<=` so we can use a single SIMD op.
In practice, you’re probably better served by minimizing memory management overhead. Having an explicit `Rectangle` object is, uh, wasteful.