fix algorithmic worst-case in regeneration of URL tokenizer [LUCENE-9231]
- Dominant language
- Java
- Stars
- 3.6k
- Forks
- 1.4k
- Avg merge
- 2d 11h
- Merged PRs (30d)
- 88
Description
For the UAX29URLEmailTokenizer, the regeneration task is slow. It also requires a very large amount of heap space (I just increased mine after seeing it struggle under GC).
Maybe we can dig into the worst case and figure out what is happening, it seems to be an automaton issue:
```
"main" `#1` prio=5 os_prio=0 cpu=132097.25ms elapsed=135.75s tid=0x00007fb1d4018000 nid=0x19706 runnable [0x00007fb1db3df000]
java.lang.Thread.State: RUNNABLE
at jflex.StateSet.add(StateSet.java:218)
at jflex.NFA.closure(NFA.java:387)
at jflex.NFA.epsilonFill(NFA.java:410)
at jflex.NFA.complement(NFA.java:737)
at jflex.NFA.insertNFA(NFA.java:1029)
at jflex.NFA.insertNFA(NFA.java:971)
at jflex.NFA.insertNFA(NFA.java:1029)
at jflex.NFA.insertNFA(NFA.java:972)
at jflex.NFA.insertNFA(NFA.java:987)
at jflex.NFA.insertNFA(NFA.java:988)
at jflex.NFA.insertNFA(NFA.java:987)
at jflex.NFA.insertNFA(NFA.java:971)
at jflex.NFA.insertNFA(NFA.java:1041)
at jflex.NFA.insertNFA(NFA.java:987)
at jflex.NFA.insertNFA(NFA.java:971)
at jflex.NFA.insertNFA(NFA.java:971)
at jflex.NFA.addRegExp(NFA.java:151)
at jflex.LexParse$CUP$LexParse$actions.CUP$LexParse$do_action_part00000000(LexParse.java:1401)
at jflex.LexParse$CUP$LexParse$actions.CUP$LexParse$do_action(LexParse.java:3415)
at jflex.LexParse.do_action(LexParse.java:939)
at java_cup.runtime.lr_parser.parse(lr_parser.java:699)
at jflex.Main.generate(Main.java:73)
at jflex.anttask.JFlexTask.execute(JFlexTask.java:72)
```
Stacks seem to be typically in `jflex.StateSet.add(StateSet.java:218)` and `jflex.StateSet.complement(StateSet.java:173)` and many operations, but always come from `addRegExp` .. `insertNFA` .. `complement` codepath.
Feels like something has a bad runtime, I wonder if we can fix it (or at least make it better, e.g. check for some GB ram heap minimum, print a warning how long it will take, etc)
---
Migrated from [LUCENE-9231](https://issues.apache.org/jira/browse/LUCENE-9231) by Robert Muir (@rmuir), updated Feb 18 2020
Attachments: [LUCENE-9231_build_check.patch](https://apache.github.io/lucene-jira-archive/attachments/LUCENE-9231/LUCENE-9231_build_check.patch) (versions: 2)
Contributor guide
Research direction
Start by reproducing the UAX29URLEmailTokenizer regeneration slowdown, then trace the reported path through jflex.NFA.addRegExp, insertNFA, complement, and jflex.StateSet.add or complement. Review the attached LUCENE-9231_build_check.patch and determine a measurable completion condition, such as avoiding the pathological resource usage or providing a validated diagnostic.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- java
- Domain
- build-system
- Issue type
- Bug
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Stale
- Clarity
- Needs clarification
- Newbie friendliness
- 25/100