[ 
https://issues.apache.org/jira/browse/LUCENE-10268?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=17450153#comment-17450153
 ] 

Robert Muir commented on LUCENE-10268:
--------------------------------------

OK, I've got a better understanding of this. The strings are huge (e.g. 2K 
length). In these cases the alphabet used in the strings is also huge (e.g. 
first seed is 1926). 

When building this automaton, we have to do a ton of wasteful sorting because 
of high number of transitions per state. 

It is possible to modify the algorithm to just add the transitions in order in 
the first place, to remove this overhead.

But this is difficult to optimize because of Automaton.finishCurrentState sorts 
*twice* in two different orders:
* first by dest, min, max: this collapses adjacent ranges into a single range.
* next by min, max, dest: this checks determinism and prepares for more 
efficient runtime.

So we can't just simply give the data in sorted order to begin with, and rely 
upon sorting algorithms to be fast, because its gonna sort two different ways 
anyway.

Furthermore, this transition-sorting works lazily (state N is only "finished" 
after you add N+1 or call finishState() at the end).

So the way the underlying representation works makes it challenging to figure 
out the way to bypass the abstractions... I will think about it. 


> 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
>         Attachments: LUCENE-10268_test.patch
>
>
> 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