apache / apache/lucene

fix algorithmic worst-case in regeneration of URL tokenizer [LUCENE-9231]

Open
#10,271 13 comments 0 reactions 0 assignees View on GitHub
legacy-jira-priority:Major type:enhancement
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

Open the contributing 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

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.