asyml / asyml/forte

`DataPack.get()` has bad performance on large packs

Open
#65 0 comments 0 reactions 0 assignees View on GitHub
enhancement priority: medium topic: data
Dominant language
Python
Stars
253
Forks
59
PR merge metrics
No merged PRs in 30d

Description

The current logic for `.get()` (which internally calls `.get_entries()` can be summarized as:
1. Create sets of valid entry IDs for the given constraints:
- Entry must be of type `entry_type`;
- Entry must be generated by `component`;
- Entry must be within span of `range_annotation` (if coverage index exists).
2. Take the intersection of these sets, denote it as the "valid set".
3. If `entry_type` is Annotation, then a faster code path exists:
1. Find the lower and upper bounds of entry IDs given `range_annotation`. This is done using binary search on the Annotation index.
2. Iterate over all entries within range, further check its span, and yield those that satisfy the check.
4. Otherwise, simply consider every entry in the valid set, and yield those that satisfy the span check.

Corresponding code is as follows:
https://github.com/asyml/forte/blob/beae4e923c9a6873b582588972e6ec9919079271/forte/data/data_pack.py#L676-L735

A couple of performance optimizations:
1. It is not necessary to create new sets for `entry_type` each time. For most of the type sets for `entry_type` and `component` constraints will be very large (containing 30% of all IDs, or even more), and creating such indices may not be faster than iterating over everything.
2. When there is `range_annotation` (the common case), if coverage index exists, further span checks are redundant.
3. The optimization for Annotations can be similarly applied to Links and Groups, since they can also be represented as a single interval in the span check.

Contributor guide

Open the contributing guide

Research direction

Start with DataPack.get() and get_entries() in forte/data/data_pack.py at the linked lines, and trace how the type, component, and coverage constraints are indexed. Compare the current paths for Annotations, Links, and Groups on large packs; done means the listed redundant set creation and span checks are addressed while the same constraints still produce correct entries.

Written by the indexing model from the issue text.

Assessment

Tech stack
python
Domain
performance
Issue type
Bug
Difficulty
4/5
Estimated time
3-5 days
Activity status
Stale
Clarity
Mostly clear
Newbie friendliness
45/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.