lucene-dev mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From "Michael McCandless (JIRA)" <>
Subject [jira] [Commented] (LUCENE-6046) RegExp.toAutomaton high memory use
Date Mon, 03 Nov 2014 10:19:34 GMT


Michael McCandless commented on LUCENE-6046:

bq.  Russ Cox wrote a series of excellent articles about different approaches of implementing
regexp scanners. 

Thanks Dawid, these are great.

Switching to NFA based matching would be a very large change ... I don't think we should pursue
it here.  Terms.intersect implementation for block tree is already very complex ... though
I suppose of we could hide the "on the fly subset construction" (and convert regexp to a Thompson
NFA) under an API, then Terms.intersect implementation wouldn't have to change much.

Still, there will always be adversarial cases no matter which approach we choose.  I think
for this issue we should allow passing in a "how much work are you willing to do" to RegExp.toAutomaton,
and it throws an exc when it would exceed that.

> RegExp.toAutomaton high memory use
> ----------------------------------
>                 Key: LUCENE-6046
>                 URL:
>             Project: Lucene - Core
>          Issue Type: Bug
>          Components: core/queryparser
>    Affects Versions: 4.10.1
>            Reporter: Lee Hinman
>            Assignee: Michael McCandless
>            Priority: Minor
> When creating an automaton from an org.apache.lucene.util.automaton.RegExp, it's possible
for the automaton to use so much memory it exceeds the maximum array size for java.
> The following caused an OutOfMemoryError with a 32gb heap:
> {noformat}
> new RegExp("\\[\\[(Datei|File|Bild|Image):[^]]*alt=[^]|}]{50,200}").toAutomaton();
> {noformat}
> When increased to a 60gb heap, the following exception is thrown:
> {noformat}
>   1> java.lang.IllegalArgumentException: requested array size 2147483624 exceeds maximum
array in java (2147483623)
>   1>     __randomizedtesting.SeedInfo.seed([7BE81EF678615C32:95C8057A4ABA5B52]:0)
>   1>     org.apache.lucene.util.ArrayUtil.oversize(
>   1>     org.apache.lucene.util.ArrayUtil.grow(
>   1>     org.apache.lucene.util.automaton.Automaton$Builder.addTransition(
>   1>     org.apache.lucene.util.automaton.Operations.determinize(
>   1>     org.apache.lucene.util.automaton.MinimizationOperations.minimizeHopcroft(
>   1>     org.apache.lucene.util.automaton.MinimizationOperations.minimize(
>   1>     org.apache.lucene.util.automaton.RegExp.toAutomaton(
>   1>     org.apache.lucene.util.automaton.RegExp.toAutomaton(
> {noformat}

This message was sent by Atlassian JIRA

To unsubscribe, e-mail:
For additional commands, e-mail:

View raw message