Rect.intersects() is much slower than necessary

[stijnvermeeren-swisstopo]

Description of the bug

When benchmarking one of my scripts, I noticed that the method Rect.intersects() (which is called thousands of times) is a significant bottleneck.
I was able to replace the PyMuPDF method with a simple custom implementation which behaves the same but is more than 10x faster.

Is there a good reason for the current, slower PyMuPDF implementation, or could this method be made much faster?

Example output of the reproduction script below:

$ time python test.py 
PyMuPDF time: 7.175560788000526
Fast method time: 0.551379568999675

How to reproduce the bug

import pymupdf
import random
import time

def random_rect() -> pymupdf.Rect:
    x0 = random.randint(0, 100)
    y0 = random.randint(0, 100)
    width = random.randint(0, 100)
    height = random.randint(0, 100)
    return pymupdf.Rect(x0, y0, x0 + width, y0 + height)

def fast_intersects(rect1: pymupdf.Rect, rect2: pymupdf.Rect) -> bool:
    return not rect1.is_empty and not rect2.is_empty and (
        (rect1.x0 < rect2.x1) and (rect2.x0 < rect1.x1) and (rect1.y0 < rect2.y1) and (rect2.y0 < rect1.y1)
    )

pymupdf_time = 0
fast_time = 0

random_rects = [random_rect() for _ in range(1000)]
for rect1 in random_rects:
    for rect2 in random_rects:
        a = time.process_time()
        pymupdf_result = rect1.intersects(rect2)
        b = time.process_time()
        fast_result = fast_intersects(rect1, rect2)
        c = time.process_time()

        pymupdf_time += b - a
        fast_time += c - b
        assert(fast_result == pymupdf_result)

print(f"PyMuPDF time: {pymupdf_time}")
print(f"Fast method time: {fast_time}")

PyMuPDF version

1.26.0

Operating system

Linux

Python version

3.12

[JorjMcKie]

Thanks for your observation. You are quite right: we can improve the performance here and will do so in one of the next versions.

[JorjMcKie]

Just took a closer look:
We are actually doing more than what you do in your function:

1. We also check for infiniteness of the rectangles - you do not.
2. We also convert rect2 into a pymupdf.Rect - you assume this to be the case.

When modifying your function accordingly (we cannot go back behind announced prerequisites), then your function is "only" about 3.8 times faster.

I also noticed that a lot depends on the profile of the rectangle population, i.e. if the ratio of empty rectangles is high then the performance difference will melt down significantly. I changed your set of random rectangles such that it contains many more empty ones (like 1 out of 7 or 9), then the new speed is "only" 3 times faster.

But in any case certainly worthwhile improving it.

[stijnvermeeren-swisstopo]

@JorjMcKie Thanks for your investigations. I agree with your comments.
In my personal use case, I already know that all my rectangles are pymupdf.Rect objects, nonempty and finite, so the difference in speed in my particular case is even bigger (as I don't even need the emptiness check at all).
But I of course agree with you that the behavior of the pymupdf library method should not change, as there will be others that rely on the existing checks.
For these reasons, I will probably stick to my custom method in this case, but others might still benefit from an optimization of the Rect.intersects method.

[JorjMcKie]

We definitely will improve the performance here along the lines you have suggested.
So thanks again for spotting this!

[julian-smith-artifex-com]

Fixed in PyMuPDF-1.26.3.