From ee9aecda46ea610644452d2280cefe3ffd64dcbf Mon Sep 17 00:00:00 2001 From: Florian Bruhin Date: Fri, 12 Jan 2024 18:34:26 +0100 Subject: listcategory: Fix O(n^2) performance if no match With the change in #7955, if the regex did not match, it ended up retrying the lookahead at every position of the string (expected), but then *also* repeated that process for every position in the string. Thus, a non-matching pattern ended up in O(n^2) performance (with n = length of URL). Instead, anchor the pattern at the beginning of the string. This doesn't change behaviour as we use .* at the beginning of every lookahead anyways, but it means we end up with O(n) instead of O(n^2) performance. Co-authored-by: toofar --- qutebrowser/completion/models/listcategory.py | 2 +- tests/unit/completion/test_models.py | 5 +++-- 2 files changed, 4 insertions(+), 3 deletions(-) diff --git a/qutebrowser/completion/models/listcategory.py b/qutebrowser/completion/models/listcategory.py index e46f18c69..226f5e999 100644 --- a/qutebrowser/completion/models/listcategory.py +++ b/qutebrowser/completion/models/listcategory.py @@ -52,7 +52,7 @@ class ListCategory(QSortFilterProxyModel): # Positive lookahead per search term. This means that all search terms must # be matched but they can be matched anywhere in the string, so they can be # in any order. For example "foo bar" -> "(?=.*foo)(?=.*bar)" - val = '(?=.*' + ')(?=.*'.join(map(re.escape, val.split())) + ')' + val = '^(?=.*' + ')(?=.*'.join(map(re.escape, val.split())) + ')' rx = QRegularExpression(val, QRegularExpression.PatternOption.CaseInsensitiveOption) qtutils.ensure_valid(rx) self.setFilterRegularExpression(rx) diff --git a/tests/unit/completion/test_models.py b/tests/unit/completion/test_models.py index 837298550..e0bce8f04 100644 --- a/tests/unit/completion/test_models.py +++ b/tests/unit/completion/test_models.py @@ -1310,11 +1310,11 @@ def test_url_completion_benchmark(benchmark, info, web_history.completion.insert_batch(entries) quickmark_manager_stub.marks = collections.OrderedDict([ - ('title{}'.format(i), 'example.com/{}'.format(i)) + ('title{}'.format('a'*i), 'example.com/{}'.format(i)) for i in range(1000)]) bookmark_manager_stub.marks = collections.OrderedDict([ - ('example.com/{}'.format(i), 'title{}'.format(i)) + ('example.com/{}'.format('a'*i), 'title{}'.format(i)) for i in range(1000)]) def bench(): @@ -1326,6 +1326,7 @@ def test_url_completion_benchmark(benchmark, info, model.set_pattern('ex 1') model.set_pattern('ex 12') model.set_pattern('ex 123') + model.set_pattern('zzzzz') # no match benchmark(bench) -- cgit v1.2.3-54-g00ecf