[ 
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]

Reply via email to