[
https://issues.apache.org/jira/browse/LUCENE-9983?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=17360495#comment-17360495
]
Haoyu Zhai commented on LUCENE-9983:
------------------------------------
I constructed a file with 235k words that has some part of it randomly replaced
by a regex (like "apple" to "a[pl]*e")
Then warm up 10 rounds and run 20 rounds to measure the average time of
constructing {{RegexpQuery}} for those words. Here's the results I got:
|| ||Baseline ||IntIntHashMap||IntIntWormMap||int[128] + IntIntHashMap||
|Time|23.55|23.61|23.78|23.69|
So in normal case original code and {{IntIntHashMap}} only have a very similar
performance, other choices all has some kind of performance loss seems.
> Stop sorting determinize powersets unnecessarily
> ------------------------------------------------
>
> Key: LUCENE-9983
> URL: https://issues.apache.org/jira/browse/LUCENE-9983
> Project: Lucene - Core
> Issue Type: Improvement
> Reporter: Michael McCandless
> Priority: Major
> Time Spent: 4h 20m
> Remaining Estimate: 0h
>
> Spinoff from LUCENE-9981.
> Today, our {{Operations.determinize}} implementation builds powersets of all
> subsets of NFA states that "belong" in the same determinized state, using
> [this algorithm|https://en.wikipedia.org/wiki/Powerset_construction].
> To hold each powerset, we use a malleable {{SortedIntSet}} and periodically
> freeze it to a {{FrozenIntSet}}, also sorted. We pay a high price to keep
> these growing maps of int key, int value sorted by key, e.g. upgrading to a
> {{TreeMap}} once the map is large enough (> 30 entries).
> But I think sorting is entirely unnecessary here! Really all we need is the
> ability to add/delete keys from the map, and hashCode / equals (by key only –
> ignoring value!), and to freeze the map (a small optimization that we could
> skip initially). We only use these maps to lookup in the (growing)
> determinized automaton whether this powerset has already been seen.
> Maybe we could simply poach the {{IntIntScatterMap}} implementation from
> [HPPC|https://github.com/carrotsearch/hppc]? And then change its
> {{hashCode}}/{{equals }}to only use keys (not values).
> This change should be a big speedup for the kinds of (admittedly adversarial)
> regexps we saw on LUCENE-9981.
>
--
This message was sent by Atlassian Jira
(v8.3.4#803005)
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscr...@lucene.apache.org
For additional commands, e-mail: issues-h...@lucene.apache.org
