docling-project / docling-project/docling

build the page object index once to avoid quadratic scans

Open
#4,223 0 comments 0 reactions 0 assignees View on GitHub
Dominant language
Python
Stars
66.4k
Forks
4.8k
Avg merge
2d 21h
Merged PRs (30d)
84

Description

### Problem

In the `pypdfium2` PDF backend, `PyPdfiumPageBackend._object_rects` / `has_content_in` re-enumerate every object on the page on each call. `has_content_in` is invoked per layout cluster (2-3 times each), so on a page with many objects the cost is O(clusters × objects), and text extraction via `get_text_bounded` is O(rects × chars). A page with a large number of path/text objects makes conversion pathologically slow.

There is also a pre-existing hazard: the old `_object_rects` was a generator that held the process-global `pypdfium2_lock` across its `yield`, so overlap comparisons ran while holding the lock.

### Proposed fix

Build the page object index (bboxes bucketed by type, already mapped to the display frame) once per page and reuse it across all callers; clear it when the native page closes. This makes the object walk O(objects) once per page and lets callers iterate cached pure-Python lists with the lock released. Output is unchanged.

A PR implementing this follows.

Contributor guide

Open the contributing guide

Research direction

Start with PyPdfiumPageBackend._object_rects and has_content_in, then trace the native page close path. Build the per-page object index once, reuse its display-frame bounding-box lists without holding the pypdfium2_lock, and clear it when the page closes. Done means output is unchanged and repeated scans no longer re-enumerate page objects.

Written by the indexing model from the issue text.

Assessment

Tech stack
python
Domain
backend, performance
Issue type
Refactor
Difficulty
3/5
Estimated time
1-2 days
Activity status
Active
Clarity
Mostly clear
Newbie friendliness
48/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.