[
https://issues.apache.org/jira/browse/LUCENE-10268?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=17450118#comment-17450118
]
Robert Muir commented on LUCENE-10268:
--------------------------------------
I ran the first seed (just tacked on {{-Dtests.profile=true}}) and it seems the
issue involves sorting?
{noformat}
PERCENT CPU SAMPLES STACK
22.55% 8935
org.apache.lucene.util.automaton.Automaton$1#swapOne()
12.11% 4798
org.apache.lucene.util.automaton.Automaton$1#compare()
11.05% 4379 org.apache.lucene.util.automaton.Automaton$1#swap()
9.49% 3759
org.apache.lucene.util.automaton.Lev2TParametricDescription#transition()
5.61% 2225 org.apache.lucene.util.Sorter#reverse()
5.46% 2164
org.apache.lucene.util.automaton.Automaton#addTransition()
5.02% 1990 org.apache.lucene.util.Sorter#mergeInPlace()
4.62% 1831
org.apache.lucene.util.automaton.LevenshteinAutomata$ParametricDescription#unpack()
4.06% 1607
org.apache.lucene.util.automaton.LevenshteinAutomata#getVector()
3.70% 1467
org.apache.lucene.util.automaton.LevenshteinAutomata#toAutomaton()
{noformat}
I re-ran with {{-Dtests.profile=true -Dtests.profile.stacksize=20}} to increase
stack depth and try to get a better idea of where all this sorting is coming
from. It is difficult because the sort is working recursively, so you need a
big number to see what is happening.
{noformat}
PERCENT CPU SAMPLES STACK
4.36% 1753
org.apache.lucene.util.automaton.Lev2TParametricDescription#transition()
at
org.apache.lucene.util.automaton.LevenshteinAutomata#toAutomaton()
at
org.apache.lucene.search.FuzzyAutomatonBuilder#buildMaxEditAutomaton()
at
org.apache.lucene.search.TestFuzzyQuery#lambda$testErrorMessage$6()
at
org.apache.lucene.search.TestFuzzyQuery$$Lambda$181+0x000000010025cd28.1457578423#run()
at
org.apache.lucene.util.LuceneTestCase#_expectThrows()
at
org.apache.lucene.util.LuceneTestCase#expectThrows()
at
org.apache.lucene.util.LuceneTestCase#expectThrows()
at
org.apache.lucene.search.TestFuzzyQuery#testErrorMessage()
at
jdk.internal.reflect.NativeMethodAccessorImpl#invoke0()
at
jdk.internal.reflect.NativeMethodAccessorImpl#invoke()
at
jdk.internal.reflect.DelegatingMethodAccessorImpl#invoke()
at java.lang.reflect.Method#invoke()
at
com.carrotsearch.randomizedtesting.RandomizedRunner#invoke()
at
com.carrotsearch.randomizedtesting.RandomizedRunner$8#evaluate()
at
com.carrotsearch.randomizedtesting.RandomizedRunner$9#evaluate()
at
com.carrotsearch.randomizedtesting.RandomizedRunner$10#evaluate()
at
org.apache.lucene.util.TestRuleSetupTeardownChained$1#evaluate()
at
org.apache.lucene.util.AbstractBeforeAfterRule$1#evaluate()
at
org.apache.lucene.util.TestRuleThreadAndTestName$1#evaluate()
4.17% 1675
org.apache.lucene.util.automaton.Lev2TParametricDescription#transition()
at
org.apache.lucene.util.automaton.LevenshteinAutomata#toAutomaton()
at
org.apache.lucene.search.FuzzyAutomatonBuilder#buildAutomatonSet()
at
org.apache.lucene.search.TestFuzzyQuery#lambda$testErrorMessage$7()
at
org.apache.lucene.search.TestFuzzyQuery$$Lambda$185+0x00000001002632d0.1876706731#run()
at
org.apache.lucene.util.LuceneTestCase#_expectThrows()
at
org.apache.lucene.util.LuceneTestCase#expectThrows()
at
org.apache.lucene.util.LuceneTestCase#expectThrows()
at
org.apache.lucene.search.TestFuzzyQuery#testErrorMessage()
at
jdk.internal.reflect.NativeMethodAccessorImpl#invoke0()
at
jdk.internal.reflect.NativeMethodAccessorImpl#invoke()
at
jdk.internal.reflect.DelegatingMethodAccessorImpl#invoke()
at java.lang.reflect.Method#invoke()
at
com.carrotsearch.randomizedtesting.RandomizedRunner#invoke()
at
com.carrotsearch.randomizedtesting.RandomizedRunner$8#evaluate()
at
com.carrotsearch.randomizedtesting.RandomizedRunner$9#evaluate()
at
com.carrotsearch.randomizedtesting.RandomizedRunner$10#evaluate()
at
org.apache.lucene.util.TestRuleSetupTeardownChained$1#evaluate()
at
org.apache.lucene.util.AbstractBeforeAfterRule$1#evaluate()
at
org.apache.lucene.util.TestRuleThreadAndTestName$1#evaluate()
2.37% 953
org.apache.lucene.util.automaton.Automaton$1#compare()
at org.apache.lucene.util.Sorter#comparePivot()
at org.apache.lucene.util.Sorter#binarySort()
at org.apache.lucene.util.Sorter#binarySort()
at
org.apache.lucene.util.InPlaceMergeSorter#mergeSort()
at
org.apache.lucene.util.InPlaceMergeSorter#mergeSort()
at
org.apache.lucene.util.InPlaceMergeSorter#mergeSort()
at
org.apache.lucene.util.InPlaceMergeSorter#mergeSort()
at
org.apache.lucene.util.InPlaceMergeSorter#mergeSort()
at
org.apache.lucene.util.InPlaceMergeSorter#mergeSort()
at
org.apache.lucene.util.InPlaceMergeSorter#mergeSort()
at
org.apache.lucene.util.InPlaceMergeSorter#mergeSort()
at
org.apache.lucene.util.InPlaceMergeSorter#mergeSort()
at
org.apache.lucene.util.InPlaceMergeSorter#sort()
at
org.apache.lucene.util.automaton.Automaton#finishCurrentState()
at
org.apache.lucene.util.automaton.Automaton#addTransition()
at
org.apache.lucene.util.automaton.Automaton#addTransition()
at
org.apache.lucene.util.automaton.LevenshteinAutomata#toAutomaton()
at
org.apache.lucene.search.FuzzyAutomatonBuilder#buildAutomatonSet()
at
org.apache.lucene.search.TestFuzzyQuery#lambda$testErrorMessage$7()
2.37% 951
org.apache.lucene.util.automaton.LevenshteinAutomata#toAutomaton()
at
org.apache.lucene.search.FuzzyAutomatonBuilder#buildMaxEditAutomaton()
at
org.apache.lucene.search.TestFuzzyQuery#lambda$testErrorMessage$6()
at
org.apache.lucene.search.TestFuzzyQuery$$Lambda$181+0x000000010025cd28.1457578423#run()
at
org.apache.lucene.util.LuceneTestCase#_expectThrows()
at
org.apache.lucene.util.LuceneTestCase#expectThrows()
at
org.apache.lucene.util.LuceneTestCase#expectThrows()
at
org.apache.lucene.search.TestFuzzyQuery#testErrorMessage()
at
jdk.internal.reflect.NativeMethodAccessorImpl#invoke0()
at
jdk.internal.reflect.NativeMethodAccessorImpl#invoke()
at
jdk.internal.reflect.DelegatingMethodAccessorImpl#invoke()
at java.lang.reflect.Method#invoke()
at
com.carrotsearch.randomizedtesting.RandomizedRunner#invoke()
at
com.carrotsearch.randomizedtesting.RandomizedRunner$8#evaluate()
at
com.carrotsearch.randomizedtesting.RandomizedRunner$9#evaluate()
at
com.carrotsearch.randomizedtesting.RandomizedRunner$10#evaluate()
at
org.apache.lucene.util.TestRuleSetupTeardownChained$1#evaluate()
at
org.apache.lucene.util.AbstractBeforeAfterRule$1#evaluate()
at
org.apache.lucene.util.TestRuleThreadAndTestName$1#evaluate()
at
org.apache.lucene.util.TestRuleIgnoreAfterMaxFailures$1#evaluate()
2.35% 945
org.apache.lucene.util.automaton.Automaton$1#compare()
at org.apache.lucene.util.Sorter#comparePivot()
at org.apache.lucene.util.Sorter#binarySort()
at org.apache.lucene.util.Sorter#binarySort()
at
org.apache.lucene.util.InPlaceMergeSorter#mergeSort()
at
org.apache.lucene.util.InPlaceMergeSorter#mergeSort()
at
org.apache.lucene.util.InPlaceMergeSorter#mergeSort()
at
org.apache.lucene.util.InPlaceMergeSorter#mergeSort()
at
org.apache.lucene.util.InPlaceMergeSorter#mergeSort()
at
org.apache.lucene.util.InPlaceMergeSorter#mergeSort()
at
org.apache.lucene.util.InPlaceMergeSorter#mergeSort()
at
org.apache.lucene.util.InPlaceMergeSorter#mergeSort()
at
org.apache.lucene.util.InPlaceMergeSorter#mergeSort()
at
org.apache.lucene.util.InPlaceMergeSorter#sort()
at
org.apache.lucene.util.automaton.Automaton#finishCurrentState()
at
org.apache.lucene.util.automaton.Automaton#addTransition()
at
org.apache.lucene.util.automaton.Automaton#addTransition()
at
org.apache.lucene.util.automaton.LevenshteinAutomata#toAutomaton()
at
org.apache.lucene.search.FuzzyAutomatonBuilder#buildMaxEditAutomaton()
at
org.apache.lucene.search.TestFuzzyQuery#lambda$testErrorMessage$6()
2.08% 837
org.apache.lucene.util.automaton.LevenshteinAutomata#getVector()
at
org.apache.lucene.util.automaton.LevenshteinAutomata#toAutomaton()
at
org.apache.lucene.search.FuzzyAutomatonBuilder#buildAutomatonSet()
at
org.apache.lucene.search.TestFuzzyQuery#lambda$testErrorMessage$7()
at
org.apache.lucene.search.TestFuzzyQuery$$Lambda$185+0x00000001002632d0.1876706731#run()
at
org.apache.lucene.util.LuceneTestCase#_expectThrows()
at
org.apache.lucene.util.LuceneTestCase#expectThrows()
at
org.apache.lucene.util.LuceneTestCase#expectThrows()
at
org.apache.lucene.search.TestFuzzyQuery#testErrorMessage()
at
jdk.internal.reflect.NativeMethodAccessorImpl#invoke0()
at
jdk.internal.reflect.NativeMethodAccessorImpl#invoke()
at
jdk.internal.reflect.DelegatingMethodAccessorImpl#invoke()
at java.lang.reflect.Method#invoke()
at
com.carrotsearch.randomizedtesting.RandomizedRunner#invoke()
at
com.carrotsearch.randomizedtesting.RandomizedRunner$8#evaluate()
at
com.carrotsearch.randomizedtesting.RandomizedRunner$9#evaluate()
at
com.carrotsearch.randomizedtesting.RandomizedRunner$10#evaluate()
at
org.apache.lucene.util.TestRuleSetupTeardownChained$1#evaluate()
at
org.apache.lucene.util.AbstractBeforeAfterRule$1#evaluate()
at
org.apache.lucene.util.TestRuleThreadAndTestName$1#evaluate()
2.07% 831
org.apache.lucene.util.automaton.LevenshteinAutomata$ParametricDescription#unpack()
at
org.apache.lucene.util.automaton.Lev2TParametricDescription#transition()
at
org.apache.lucene.util.automaton.LevenshteinAutomata#toAutomaton()
at
org.apache.lucene.search.FuzzyAutomatonBuilder#buildAutomatonSet()
at
org.apache.lucene.search.TestFuzzyQuery#lambda$testErrorMessage$7()
at
org.apache.lucene.search.TestFuzzyQuery$$Lambda$185+0x00000001002632d0.1876706731#run()
at
org.apache.lucene.util.LuceneTestCase#_expectThrows()
at
org.apache.lucene.util.LuceneTestCase#expectThrows()
at
org.apache.lucene.util.LuceneTestCase#expectThrows()
at
org.apache.lucene.search.TestFuzzyQuery#testErrorMessage()
at
jdk.internal.reflect.NativeMethodAccessorImpl#invoke0()
at
jdk.internal.reflect.NativeMethodAccessorImpl#invoke()
at
jdk.internal.reflect.DelegatingMethodAccessorImpl#invoke()
at java.lang.reflect.Method#invoke()
at
com.carrotsearch.randomizedtesting.RandomizedRunner#invoke()
at
com.carrotsearch.randomizedtesting.RandomizedRunner$8#evaluate()
at
com.carrotsearch.randomizedtesting.RandomizedRunner$9#evaluate()
at
com.carrotsearch.randomizedtesting.RandomizedRunner$10#evaluate()
at
org.apache.lucene.util.TestRuleSetupTeardownChained$1#evaluate()
at
org.apache.lucene.util.AbstractBeforeAfterRule$1#evaluate()
2.01% 806
org.apache.lucene.util.automaton.LevenshteinAutomata$ParametricDescription#unpack()
at
org.apache.lucene.util.automaton.Lev2TParametricDescription#transition()
at
org.apache.lucene.util.automaton.LevenshteinAutomata#toAutomaton()
at
org.apache.lucene.search.FuzzyAutomatonBuilder#buildMaxEditAutomaton()
at
org.apache.lucene.search.TestFuzzyQuery#lambda$testErrorMessage$6()
at
org.apache.lucene.search.TestFuzzyQuery$$Lambda$181+0x000000010025cd28.1457578423#run()
at
org.apache.lucene.util.LuceneTestCase#_expectThrows()
at
org.apache.lucene.util.LuceneTestCase#expectThrows()
at
org.apache.lucene.util.LuceneTestCase#expectThrows()
at
org.apache.lucene.search.TestFuzzyQuery#testErrorMessage()
at
jdk.internal.reflect.NativeMethodAccessorImpl#invoke0()
at
jdk.internal.reflect.NativeMethodAccessorImpl#invoke()
at
jdk.internal.reflect.DelegatingMethodAccessorImpl#invoke()
at java.lang.reflect.Method#invoke()
at
com.carrotsearch.randomizedtesting.RandomizedRunner#invoke()
at
com.carrotsearch.randomizedtesting.RandomizedRunner$8#evaluate()
at
com.carrotsearch.randomizedtesting.RandomizedRunner$9#evaluate()
at
com.carrotsearch.randomizedtesting.RandomizedRunner$10#evaluate()
at
org.apache.lucene.util.TestRuleSetupTeardownChained$1#evaluate()
at
org.apache.lucene.util.AbstractBeforeAfterRule$1#evaluate()
1.97% 790
org.apache.lucene.util.automaton.LevenshteinAutomata#toAutomaton()
at
org.apache.lucene.search.FuzzyAutomatonBuilder#buildAutomatonSet()
at
org.apache.lucene.search.TestFuzzyQuery#lambda$testErrorMessage$7()
at
org.apache.lucene.search.TestFuzzyQuery$$Lambda$185+0x00000001002632d0.1876706731#run()
at
org.apache.lucene.util.LuceneTestCase#_expectThrows()
at
org.apache.lucene.util.LuceneTestCase#expectThrows()
at
org.apache.lucene.util.LuceneTestCase#expectThrows()
at
org.apache.lucene.search.TestFuzzyQuery#testErrorMessage()
at
jdk.internal.reflect.NativeMethodAccessorImpl#invoke0()
at
jdk.internal.reflect.NativeMethodAccessorImpl#invoke()
at
jdk.internal.reflect.DelegatingMethodAccessorImpl#invoke()
at java.lang.reflect.Method#invoke()
at
com.carrotsearch.randomizedtesting.RandomizedRunner#invoke()
at
com.carrotsearch.randomizedtesting.RandomizedRunner$8#evaluate()
at
com.carrotsearch.randomizedtesting.RandomizedRunner$9#evaluate()
at
com.carrotsearch.randomizedtesting.RandomizedRunner$10#evaluate()
at
org.apache.lucene.util.TestRuleSetupTeardownChained$1#evaluate()
at
org.apache.lucene.util.AbstractBeforeAfterRule$1#evaluate()
at
org.apache.lucene.util.TestRuleThreadAndTestName$1#evaluate()
at
org.apache.lucene.util.TestRuleIgnoreAfterMaxFailures$1#evaluate()
1.95% 785
org.apache.lucene.util.automaton.LevenshteinAutomata#getVector()
at
org.apache.lucene.util.automaton.LevenshteinAutomata#toAutomaton()
at
org.apache.lucene.search.FuzzyAutomatonBuilder#buildMaxEditAutomaton()
at
org.apache.lucene.search.TestFuzzyQuery#lambda$testErrorMessage$6()
at
org.apache.lucene.search.TestFuzzyQuery$$Lambda$181+0x000000010025cd28.1457578423#run()
at
org.apache.lucene.util.LuceneTestCase#_expectThrows()
at
org.apache.lucene.util.LuceneTestCase#expectThrows()
at
org.apache.lucene.util.LuceneTestCase#expectThrows()
at
org.apache.lucene.search.TestFuzzyQuery#testErrorMessage()
at
jdk.internal.reflect.NativeMethodAccessorImpl#invoke0()
at
jdk.internal.reflect.NativeMethodAccessorImpl#invoke()
at
jdk.internal.reflect.DelegatingMethodAccessorImpl#invoke()
at java.lang.reflect.Method#invoke()
at
com.carrotsearch.randomizedtesting.RandomizedRunner#invoke()
at
com.carrotsearch.randomizedtesting.RandomizedRunner$8#evaluate()
at
com.carrotsearch.randomizedtesting.RandomizedRunner$9#evaluate()
at
com.carrotsearch.randomizedtesting.RandomizedRunner$10#evaluate()
at
org.apache.lucene.util.TestRuleSetupTeardownChained$1#evaluate()
at
org.apache.lucene.util.AbstractBeforeAfterRule$1#evaluate()
at
org.apache.lucene.util.TestRuleThreadAndTestName$1#evaluate()
{noformat}
To me the issue seems to be the sorting called by {{Automaton.addTransition}}
-> {{Automaton.finishCurrentState}}. Maybe we use the wrong sort algorithm or
call {{finishCurrentState}} some unnecessary amount of times, not sure yet.
> TestFuzzyQuery.testErrorMessage can sometimes run for a hundred seconds
> -----------------------------------------------------------------------
>
> Key: LUCENE-10268
> URL: https://issues.apache.org/jira/browse/LUCENE-10268
> Project: Lucene - Core
> Issue Type: Task
> Reporter: Robert Muir
> Priority: Major
>
> I ran 6 test runs, and it happened only in one of them:
> 97.93s TestFuzzyQuery.testErrorMessage (:lucene:core)
> The test is badly named, but I think the intention is to provoke a
> determinize work limit. Funny because with the lev logic we build a DFA from
> the getgo... so it's just the overhead introduced by UTF32toUTF8.
> Still, this seems to indicate something is wrong, or possible adversary.
> To reproduce:
> commit hash: 63c89f678d48deb9a40b90498409ad5656d775ce
> "git checkout 63c89f678d48deb9a40b90498409ad5656d775ce"
> 57.51 second seed: 4DE463858ECD6FA6
> reproduce with: ./gradlew -p lucene/core test --tests
> TestFuzzyQuery.testErrorMessage -Dtests.seed=4DE463858ECD6FA6
> 52.95 second seed: 7DE4CCA6F3A8183
> reproduce with: ./gradlew -p lucene/core test --tests
> TestFuzzyQuery.testErrorMessage -Dtests.seed=7DE4CCA6F3A8183
> 48.21 second seed: 79F0E067AF13B395
> reproduce with: ./gradlew -p lucene/core test --tests
> TestFuzzyQuery.testErrorMessage -Dtests.seed=79F0E067AF13B395
> I used jdk-17:
> openjdk version "17.0.1" 2021-10-19
> OpenJDK Runtime Environment (build 17.0.1+12)
> OpenJDK 64-Bit Server VM (build 17.0.1+12, mixed mode)
--
This message was sent by Atlassian Jira
(v8.20.1#820001)
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]