Severe performance issues during search

[Blankwonder]

What happened?

When a user enters search content, if the input is very short (e.g., 1 or 2 characters), it results in an enormous number of search results, causing excessively high CPU usage. This leads to the app freezing for several seconds or even tens of seconds.

The edited file is only a few dozen KB, but there may be 100,000+ hits in the search results. Instruments show the call stack.

2.90 s  99.9%	0 s	                    UITextSearchingHelper.decorate(foundTextRange:document:usingStyle:)
2.89 s  99.6%	0 s	                     TextView.highlightedRanges.modify
2.89 s  99.6%	0 s	                      TextView.highlightedRanges.setter
2.89 s  99.6%	0 s	                       TextInputView.highlightedRanges.setter
2.69 s  92.7%	0 s	                        HighlightService.highlightedRanges.setter
2.69 s  92.7%	0 s	                         HighlightService.highlightedRanges.didset
2.69 s  92.7%	0 s	                          HighlightService.invalidateHighlightedRangeFragments()
2.68 s  92.2%	0 s	                           HighlightService.createHighlightedRangeFragmentsPerLine()
1.76 s  60.6%	1.00 ms	                            LineManager.lines(in:)
1.74 s  59.9%	0 s	                             LineManager.line(containingCharacterAt:)
1.71 s  58.9%	5.00 ms	                              RedBlackTree.node(containingLocation:)
885.00 ms  30.5%	26.00 ms	                               RedBlackTree.node<A>(containingLocation:minimumValue:valueKeyPath:totalValueKeyPath:)

However, I tested the same file with Runestone.app and it seems that no similar issues occurred. Is it because the open-source version itself is not optimized in this regard, or is there a problem with the way I'm using it?

Thank you.

What are the steps to reproduce?

Use the search tool and enter only one character.

What is the expected behavior?

[simonbs]

@Blankwonder Thanks for opening the issue (and for being a sponsor!).

I want to start by emphasizing that the Runestone Text Editor app uses the exact same version of the Runestone framework as this repository, so replicating the app's behavior should be possible.

That said, I noticed a reference to UITextSearchingHelper in your call stack, which suggests you're using the Find & Replace functionality enabled via isFindInteractionEnabled on the text view. The Runestone app doesn't use this property. Instead, it relies on a custom search implementation built around the TextView's search(for:) function.

I can't rule out the possibility of a performance issue with isFindInteractionEnabled.

[Blankwonder]

Yes, I used the native isFindInteractionEnabled to support search and find. Sorry for not making it clear earlier.

[Blankwonder]

May I kindly inquire if there is any need for additional materials, such as sample files or projects, that might assist us further? Additionally, in the event of a confirmed performance issue, I was wondering if there might be any upcoming plans for optimization.

Please take all the time you need; there’s absolutely no rush on my end. I’m willing to wait for any updates if there’s a plan in place to address the issue soon. Alternatively, if immediate optimization isn’t feasible, I could consider developing my own search interface using search(for:).

Thanks for your attention and assistance.

[Blankwonder]

I conducted some research myself, and the root of the problem lies in that for each match, UITextSearching calls the decorate method to mark a new range. However, this method triggers the highlightedRanges setter of HighlightService, which causes HighlightService to recalculate all highlight areas. If there are many highlight areas, this leads to an exponential increase in computational overhead.

I made adjustments to the relevant code by caching changes to highlightedRanges before performTextSearch is completed and setting them all at once after it finishes, which resolved the issue.

    func performTextSearch(queryString: String, options: UITextSearchOptions, resultAggregator: UITextSearchAggregator<AnyHashable?>) {
        _searching = true
        performTextSearch(for: queryString, options: options) { searchResults in
            for searchResult in searchResults {
                let textRange = IndexedRange(searchResult.range)
                resultAggregator.foundRange(textRange, searchString: queryString, document: nil)
            }
            resultAggregator.finishedSearching()
            
            DispatchQueue.main.async {
                self._searching = false
                self.applyHighlightedRanges()
            }
        }
    }

    func decorate(foundTextRange: UITextRange, document: AnyHashable??, usingStyle style: UITextSearchFoundTextStyle) {
        guard let foundTextRange = foundTextRange as? IndexedRange else {
            return
        }
        _highlightedRanges.removeAll { $0.range == foundTextRange.range }
        if let highlightedRange = _textView.theme.highlightedRange(forFoundTextRange: foundTextRange.range, ofStyle: style) {
            _highlightedRanges.append(highlightedRange)
        }
        
        if (!_searching) {
            self.applyHighlightedRanges()
        }
    }
    
    func applyHighlightedRanges() {
        _textView.highlightedRanges = _highlightedRanges;
    }

    func clearAllDecoratedFoundText() {
        _highlightedRanges = []
        _textView.highlightedRanges = []
    }

I'm not sure if this method is the optimal solution to the problem. If needed, I can create a corresponding code pull request.