You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@lucene.apache.org by "Robert Muir (JIRA)" <ji...@apache.org> on 2011/03/16 14:04:29 UTC

[jira] Created: (LUCENE-2970) SpecialOperations.isFinite can have TERRIBLE TERRIBLE runtime in certain situations

SpecialOperations.isFinite can have TERRIBLE TERRIBLE runtime in certain situations
-----------------------------------------------------------------------------------

                 Key: LUCENE-2970
                 URL: https://issues.apache.org/jira/browse/LUCENE-2970
             Project: Lucene - Java
          Issue Type: Bug
    Affects Versions: 4.0
            Reporter: Robert Muir
            Assignee: Robert Muir
             Fix For: 4.0


in an application of mine, i experienced some very slow query times with finite automata (all the DFAs are acyclic)

It turned out, the slowdown is some terrible runtime in SpecialOperations.isFinite <-- this is used to determine if the DFA is acyclic or not.

(in this case I am talking about even up to minutes of cpu).


--
This message is automatically generated by JIRA.
For more information on JIRA, see: http://www.atlassian.com/software/jira

---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@lucene.apache.org
For additional commands, e-mail: dev-help@lucene.apache.org


[jira] Commented: (LUCENE-2970) SpecialOperations.isFinite can have TERRIBLE TERRIBLE runtime in certain situations

Posted by "Michael McCandless (JIRA)" <ji...@apache.org>.
    [ https://issues.apache.org/jira/browse/LUCENE-2970?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13007488#comment-13007488 ] 

Michael McCandless commented on LUCENE-2970:
--------------------------------------------

Patch looks correct to me!

The algo you impl'd is the same one described in Cormen, Leiserson, Rivest Algorithms book, as a side effect of doing a depth-first walk through the DFA.  Their description of DFS colors the nodes -- white is unvisited, black is visited, gray is "being visited" (ie on my current path).  A DFA then has a cycle if every you recurse and find a gray node.

In your patch, the combination of "path" and "visited" maps to these colors, and you detect a cycle when path is set and visited is not.

Maybe rename the test-only isFiniteSimple to isFiniteSLOW or something?

Does the new random test case tend not to hit the super-slow cases...?

> SpecialOperations.isFinite can have TERRIBLE TERRIBLE runtime in certain situations
> -----------------------------------------------------------------------------------
>
>                 Key: LUCENE-2970
>                 URL: https://issues.apache.org/jira/browse/LUCENE-2970
>             Project: Lucene - Java
>          Issue Type: Bug
>    Affects Versions: 4.0
>            Reporter: Robert Muir
>            Assignee: Robert Muir
>             Fix For: 4.0
>
>         Attachments: LUCENE-2970.patch
>
>
> in an application of mine, i experienced some very slow query times with finite automata (all the DFAs are acyclic)
> It turned out, the slowdown is some terrible runtime in SpecialOperations.isFinite <-- this is used to determine if the DFA is acyclic or not.
> (in this case I am talking about even up to minutes of cpu).

--
This message is automatically generated by JIRA.
For more information on JIRA, see: http://www.atlassian.com/software/jira

---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@lucene.apache.org
For additional commands, e-mail: dev-help@lucene.apache.org


[jira] Updated: (LUCENE-2970) SpecialOperations.isFinite can have TERRIBLE TERRIBLE runtime in certain situations

Posted by "Robert Muir (JIRA)" <ji...@apache.org>.
     [ https://issues.apache.org/jira/browse/LUCENE-2970?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]

Robert Muir updated LUCENE-2970:
--------------------------------

    Attachment: LUCENE-2970.patch

Attached is a patch: imagine a regexp with lots of "optionals" e.g. [abcd]e?f?[gh]a?b? ...

In this case the code is not linear in number of states... if we are at state A, and it has a transition to B, we determine that B is finite, then later if we are at C and it leads to B too, we need not determine if B is finite again, as we already did so. So, I keep "visited" for this.

Additionally I changed it to use a Bitset instead of a HashSet, which helps the speed (but just a constant-time speedup).

I took the old code, dumped it into AutomatonTestUtil as "isFiniteSimple" and the test just generates random automata and compares this versus the new implementation.

I'd appreciate any reviews/suggestions any automaton-hackers want to give here.


> SpecialOperations.isFinite can have TERRIBLE TERRIBLE runtime in certain situations
> -----------------------------------------------------------------------------------
>
>                 Key: LUCENE-2970
>                 URL: https://issues.apache.org/jira/browse/LUCENE-2970
>             Project: Lucene - Java
>          Issue Type: Bug
>    Affects Versions: 4.0
>            Reporter: Robert Muir
>            Assignee: Robert Muir
>             Fix For: 4.0
>
>         Attachments: LUCENE-2970.patch
>
>
> in an application of mine, i experienced some very slow query times with finite automata (all the DFAs are acyclic)
> It turned out, the slowdown is some terrible runtime in SpecialOperations.isFinite <-- this is used to determine if the DFA is acyclic or not.
> (in this case I am talking about even up to minutes of cpu).

--
This message is automatically generated by JIRA.
For more information on JIRA, see: http://www.atlassian.com/software/jira

---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@lucene.apache.org
For additional commands, e-mail: dev-help@lucene.apache.org


[jira] Resolved: (LUCENE-2970) SpecialOperations.isFinite can have TERRIBLE TERRIBLE runtime in certain situations

Posted by "Robert Muir (JIRA)" <ji...@apache.org>.
     [ https://issues.apache.org/jira/browse/LUCENE-2970?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]

Robert Muir resolved LUCENE-2970.
---------------------------------

    Resolution: Fixed

Committed revision 1082200.

Thanks for the review Mike!

> SpecialOperations.isFinite can have TERRIBLE TERRIBLE runtime in certain situations
> -----------------------------------------------------------------------------------
>
>                 Key: LUCENE-2970
>                 URL: https://issues.apache.org/jira/browse/LUCENE-2970
>             Project: Lucene - Java
>          Issue Type: Bug
>    Affects Versions: 4.0
>            Reporter: Robert Muir
>            Assignee: Robert Muir
>             Fix For: 4.0
>
>         Attachments: LUCENE-2970.patch
>
>
> in an application of mine, i experienced some very slow query times with finite automata (all the DFAs are acyclic)
> It turned out, the slowdown is some terrible runtime in SpecialOperations.isFinite <-- this is used to determine if the DFA is acyclic or not.
> (in this case I am talking about even up to minutes of cpu).

--
This message is automatically generated by JIRA.
For more information on JIRA, see: http://www.atlassian.com/software/jira

---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@lucene.apache.org
For additional commands, e-mail: dev-help@lucene.apache.org


[jira] Commented: (LUCENE-2970) SpecialOperations.isFinite can have TERRIBLE TERRIBLE runtime in certain situations

Posted by "Robert Muir (JIRA)" <ji...@apache.org>.
    [ https://issues.apache.org/jira/browse/LUCENE-2970?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13007524#comment-13007524 ] 

Robert Muir commented on LUCENE-2970:
-------------------------------------

Ok, i feel better now.

I think i have an explanation why the test doesn't "hang".
I think its because the automata we generate are pretty damn small (might are significantly larger).
I think for our testing this is just fine, and actually desirable, as it helps debugging.

The only largeish automata lucene tests through this stuff are for levenshtein, and we supply 'true' 
here (since we know its finite) and avoid this method entirely... and even those are "special" in that
they always have the same general "shape"


> SpecialOperations.isFinite can have TERRIBLE TERRIBLE runtime in certain situations
> -----------------------------------------------------------------------------------
>
>                 Key: LUCENE-2970
>                 URL: https://issues.apache.org/jira/browse/LUCENE-2970
>             Project: Lucene - Java
>          Issue Type: Bug
>    Affects Versions: 4.0
>            Reporter: Robert Muir
>            Assignee: Robert Muir
>             Fix For: 4.0
>
>         Attachments: LUCENE-2970.patch
>
>
> in an application of mine, i experienced some very slow query times with finite automata (all the DFAs are acyclic)
> It turned out, the slowdown is some terrible runtime in SpecialOperations.isFinite <-- this is used to determine if the DFA is acyclic or not.
> (in this case I am talking about even up to minutes of cpu).

--
This message is automatically generated by JIRA.
For more information on JIRA, see: http://www.atlassian.com/software/jira

---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@lucene.apache.org
For additional commands, e-mail: dev-help@lucene.apache.org


[jira] Commented: (LUCENE-2970) SpecialOperations.isFinite can have TERRIBLE TERRIBLE runtime in certain situations

Posted by "Michael McCandless (JIRA)" <ji...@apache.org>.
    [ https://issues.apache.org/jira/browse/LUCENE-2970?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13007517#comment-13007517 ] 

Michael McCandless commented on LUCENE-2970:
--------------------------------------------

bq. well it seems it might work for an NFA too?

Sorry, yes -- the algo doesn't care if it's N or D.  It works for both.

> SpecialOperations.isFinite can have TERRIBLE TERRIBLE runtime in certain situations
> -----------------------------------------------------------------------------------
>
>                 Key: LUCENE-2970
>                 URL: https://issues.apache.org/jira/browse/LUCENE-2970
>             Project: Lucene - Java
>          Issue Type: Bug
>    Affects Versions: 4.0
>            Reporter: Robert Muir
>            Assignee: Robert Muir
>             Fix For: 4.0
>
>         Attachments: LUCENE-2970.patch
>
>
> in an application of mine, i experienced some very slow query times with finite automata (all the DFAs are acyclic)
> It turned out, the slowdown is some terrible runtime in SpecialOperations.isFinite <-- this is used to determine if the DFA is acyclic or not.
> (in this case I am talking about even up to minutes of cpu).

--
This message is automatically generated by JIRA.
For more information on JIRA, see: http://www.atlassian.com/software/jira

---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@lucene.apache.org
For additional commands, e-mail: dev-help@lucene.apache.org


[jira] Commented: (LUCENE-2970) SpecialOperations.isFinite can have TERRIBLE TERRIBLE runtime in certain situations

Posted by "Robert Muir (JIRA)" <ji...@apache.org>.
    [ https://issues.apache.org/jira/browse/LUCENE-2970?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13007511#comment-13007511 ] 

Robert Muir commented on LUCENE-2970:
-------------------------------------

bq. A DFA then has a cycle if every you recurse and find a gray node

well it seems it might work for an NFA too? Though i'm not sure how "great" of NFAs AutomatonTestUtil.randomAutomaton generates?
if all else fails we can det as a side effect (this won't hurt lucene), but I'd like to know for sure, and to send the patch upstream.

{quote}
Maybe rename the test-only isFiniteSimple to isFiniteSLOW or something?

Does the new random test case tend not to hit the super-slow cases...?
{quote}

The test definitely got faster, but maybe the type of DFAs i generate are not represented fairly by the random generator? In other words they are "worst-case" for the old method, but they are "reasonable" as far as queries, finite and contained as far as the number of terms they accept.




> SpecialOperations.isFinite can have TERRIBLE TERRIBLE runtime in certain situations
> -----------------------------------------------------------------------------------
>
>                 Key: LUCENE-2970
>                 URL: https://issues.apache.org/jira/browse/LUCENE-2970
>             Project: Lucene - Java
>          Issue Type: Bug
>    Affects Versions: 4.0
>            Reporter: Robert Muir
>            Assignee: Robert Muir
>             Fix For: 4.0
>
>         Attachments: LUCENE-2970.patch
>
>
> in an application of mine, i experienced some very slow query times with finite automata (all the DFAs are acyclic)
> It turned out, the slowdown is some terrible runtime in SpecialOperations.isFinite <-- this is used to determine if the DFA is acyclic or not.
> (in this case I am talking about even up to minutes of cpu).

--
This message is automatically generated by JIRA.
For more information on JIRA, see: http://www.atlassian.com/software/jira

---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@lucene.apache.org
For additional commands, e-mail: dev-help@lucene.apache.org


[jira] Commented: (LUCENE-2970) SpecialOperations.isFinite can have TERRIBLE TERRIBLE runtime in certain situations

Posted by "Robert Muir (JIRA)" <ji...@apache.org>.
    [ https://issues.apache.org/jira/browse/LUCENE-2970?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13007531#comment-13007531 ] 

Robert Muir commented on LUCENE-2970:
-------------------------------------

i ran the random test for a good hour:
{noformat}
junit-sequential:
    [junit] Testsuite: org.apache.lucene.util.automaton.TestSpecialOperations
    [junit] Tests run: 10000, Failures: 0, Errors: 0, Time elapsed: 3,908.995 sec
    [junit]
{noformat}

I'll rename the old method (in the testUtil for testing correctness) to *Slow as Mike suggested,
with an additional warning that if we ever start generating larger automata for testing, it will
blow up, and commit.


> SpecialOperations.isFinite can have TERRIBLE TERRIBLE runtime in certain situations
> -----------------------------------------------------------------------------------
>
>                 Key: LUCENE-2970
>                 URL: https://issues.apache.org/jira/browse/LUCENE-2970
>             Project: Lucene - Java
>          Issue Type: Bug
>    Affects Versions: 4.0
>            Reporter: Robert Muir
>            Assignee: Robert Muir
>             Fix For: 4.0
>
>         Attachments: LUCENE-2970.patch
>
>
> in an application of mine, i experienced some very slow query times with finite automata (all the DFAs are acyclic)
> It turned out, the slowdown is some terrible runtime in SpecialOperations.isFinite <-- this is used to determine if the DFA is acyclic or not.
> (in this case I am talking about even up to minutes of cpu).

--
This message is automatically generated by JIRA.
For more information on JIRA, see: http://www.atlassian.com/software/jira

---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@lucene.apache.org
For additional commands, e-mail: dev-help@lucene.apache.org