You are viewing a plain text version of this content. The canonical link for it is here.
Posted to issues@lucene.apache.org by GitBox <gi...@apache.org> on 2021/05/31 18:30:41 UTC
[GitHub] [lucene] zhaih opened a new pull request #162: LUCENE-9983: Stop sorting determinize powersets unnecessarily
zhaih opened a new pull request #162:
URL: https://github.com/apache/lucene/pull/162
<!--
_(If you are a project committer then you may remove some/all of the following template.)_
Before creating a pull request, please file an issue in the ASF Jira system for Lucene:
* https://issues.apache.org/jira/projects/LUCENE
You will need to create an account in Jira in order to create an issue.
The title of the PR should reference the Jira issue number in the form:
* LUCENE-####: <short description of problem or changes>
LUCENE must be fully capitalized. A short description helps people scanning pull requests for items they can work on.
Properly referencing the issue in the title ensures that Jira is correctly updated with code review comments and commits. -->
# Description
In `determinize` function (which truns NFA to DFA), we use `SortedIntSet` to store powerset and it uses a sorted data structure which could be very costly in some cases. And we actually don't need the sorting functionality.
# Solution
Replace usage of `SortedIntSet` by `StateSet`, a wrapper of `IntIntHashMap`. Note I haven't removed `SortedIntSet` but probably we should since it is only used in `determinize`?
# Tests
* Reused old tests that used to test `SortedIntSet`
* I also applied the patch attached in [LUCENE-9981](https://issues.apache.org/jira/projects/LUCENE/issues/LUCENE-9981). Before the commit it runs 6min before throw an exception and after patch it is 1+ sec. (Seems from the error message this has something to do with the order we iterate the key, but I believe it still provides some speedups)
# Checklist
Please review the following and check all that apply:
- [x] I have reviewed the guidelines for [How to Contribute](https://wiki.apache.org/lucene/HowToContribute) and my code conforms to the standards described there to the best of my ability.
- [x] I have created a Jira issue and added the issue ID to my pull request title.
- [x] I have given Lucene maintainers [access](https://help.github.com/en/articles/allowing-changes-to-a-pull-request-branch-created-from-a-fork) to contribute to my PR branch. (optional but recommended)
- [x] I have developed this patch against the `main` branch.
- [x] I have run `./gradlew check`.
- [x] I have added tests for my changes.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
[GitHub] [lucene] zhaih closed pull request #162: LUCENE-9983: Stop sorting determinize powersets unnecessarily
Posted by GitBox <gi...@apache.org>.
zhaih closed pull request #162:
URL: https://github.com/apache/lucene/pull/162
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org
[GitHub] [lucene] zhaih commented on pull request #162: LUCENE-9983: Stop sorting determinize powersets unnecessarily
Posted by GitBox <gi...@apache.org>.
zhaih commented on pull request #162:
URL: https://github.com/apache/lucene/pull/162#issuecomment-851642477
Close this one temporarily for debugging
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org