This is an automated email from the ASF dual-hosted git repository. nightowl888 pushed a commit to branch master in repository https://gitbox.apache.org/repos/asf/lucenenet.git
commit fc9d181962a74b90ee3af838776404b4c1d7928a Author: Shad Storhaug <[email protected]> AuthorDate: Fri Jul 17 08:49:12 2020 +0700 PERFORMANCE: Lucene.Net.Util.Automaton: Replaced LinkedList<T> with Queue<T> in areas where copy constructors were not in use --- .../Util/Automaton/AutomatonTestUtil.cs | 26 +++++++--------- src/Lucene.Net/Util/Automaton/Automaton.cs | 31 +++++++++---------- src/Lucene.Net/Util/Automaton/BasicOperations.cs | 35 +++++++++------------- .../Util/Automaton/MinimizationOperations.cs | 27 +++++++++-------- 4 files changed, 52 insertions(+), 67 deletions(-) diff --git a/src/Lucene.Net.TestFramework/Util/Automaton/AutomatonTestUtil.cs b/src/Lucene.Net.TestFramework/Util/Automaton/AutomatonTestUtil.cs index 9bd8484..d7f617e 100644 --- a/src/Lucene.Net.TestFramework/Util/Automaton/AutomatonTestUtil.cs +++ b/src/Lucene.Net.TestFramework/Util/Automaton/AutomatonTestUtil.cs @@ -300,16 +300,15 @@ namespace Lucene.Net.Util.Automaton int[] points = a.GetStartPoints(); // subset construction IDictionary<ISet<State>, ISet<State>> sets = new Dictionary<ISet<State>, ISet<State>>(); - LinkedList<ISet<State>> worklist = new LinkedList<ISet<State>>(); + Queue<ISet<State>> worklist = new Queue<ISet<State>>(); // LUCENENET specific - Queue is much more performant than LinkedList IDictionary<ISet<State>, State> newstate = new Dictionary<ISet<State>, State>(); sets[initialset] = initialset; - worklist.AddLast(initialset); + worklist.Enqueue(initialset); a.initial = new State(); newstate[initialset] = a.initial; while (worklist.Count > 0) { - ISet<State> s = worklist.First.Value; - worklist.Remove(s); + ISet<State> s = worklist.Dequeue(); State r = newstate[s]; foreach (State q in s) { @@ -335,7 +334,7 @@ namespace Lucene.Net.Util.Automaton if (!sets.ContainsKey(p)) { sets[p] = p; - worklist.AddLast(p); + worklist.Enqueue(p); newstate[p] = new State(); } State q_ = newstate[p]; @@ -442,7 +441,7 @@ namespace Lucene.Net.Util.Automaton leadsToAccept = new JCG.Dictionary<Transition, bool?>(IdentityEqualityComparer<Transition>.Default); IDictionary<State, IList<ArrivingTransition>> allArriving = new Dictionary<State, IList<ArrivingTransition>>(); - LinkedList<State> q = new LinkedList<State>(); + Queue<State> q = new Queue<State>(); ISet<State> seen = new JCG.HashSet<State>(); // reverse map the transitions, so we can quickly look @@ -452,9 +451,7 @@ namespace Lucene.Net.Util.Automaton for (int i = 0; i < s.numTransitions; i++) { Transition t = s.TransitionsArray[i]; - IList<ArrivingTransition> tl; - allArriving.TryGetValue(t.to, out tl); - if (tl == null) + if (!allArriving.TryGetValue(t.to, out IList<ArrivingTransition> tl) || tl == null) { tl = new List<ArrivingTransition>(); allArriving[t.to] = tl; @@ -463,7 +460,7 @@ namespace Lucene.Net.Util.Automaton } if (s.Accept) { - q.AddLast(s); + q.Enqueue(s); seen.Add(s); } } @@ -472,18 +469,15 @@ namespace Lucene.Net.Util.Automaton // backwards: while (q.Count > 0) { - State s = q.First.Value; - q.Remove(s); - IList<ArrivingTransition> arriving; - allArriving.TryGetValue(s, out arriving); - if (arriving != null) + State s = q.Dequeue(); + if (allArriving.TryGetValue(s, out IList<ArrivingTransition> arriving) && arriving != null) { foreach (ArrivingTransition at in arriving) { State from = at.from; if (!seen.Contains(from)) { - q.AddLast(from); + q.Enqueue(from); seen.Add(from); leadsToAccept[at.t] = true; } diff --git a/src/Lucene.Net/Util/Automaton/Automaton.cs b/src/Lucene.Net/Util/Automaton/Automaton.cs index 8daef51..51ab8b3 100644 --- a/src/Lucene.Net/Util/Automaton/Automaton.cs +++ b/src/Lucene.Net/Util/Automaton/Automaton.cs @@ -252,25 +252,24 @@ namespace Lucene.Net.Util.Automaton { ExpandSingleton(); JCG.HashSet<State> visited = new JCG.HashSet<State>(); - LinkedList<State> worklist = new LinkedList<State>(); + Queue<State> worklist = new Queue<State>(); // LUCENENET specific - Queue is much more performant than LinkedList State[] states = new State[4]; int upto = 0; - worklist.AddLast(initial); + worklist.Enqueue(initial); visited.Add(initial); initial.number = upto; states[upto] = initial; upto++; while (worklist.Count > 0) { - State s = worklist.First.Value; - worklist.Remove(s); + State s = worklist.Dequeue(); for (int i = 0; i < s.numTransitions; i++) { Transition t = s.TransitionsArray[i]; if (!visited.Contains(t.to)) { visited.Add(t.to); - worklist.AddLast(t.to); + worklist.Enqueue(t.to); t.to.number = upto; if (upto == states.Length) { @@ -328,13 +327,12 @@ namespace Lucene.Net.Util.Automaton ExpandSingleton(); JCG.HashSet<State> accepts = new JCG.HashSet<State>(); JCG.HashSet<State> visited = new JCG.HashSet<State>(); - LinkedList<State> worklist = new LinkedList<State>(); - worklist.AddLast(initial); + Queue<State> worklist = new Queue<State>(); // LUCENENET specific - Queue is much more performant than LinkedList + worklist.Enqueue(initial); visited.Add(initial); while (worklist.Count > 0) { - State s = worklist.First.Value; - worklist.Remove(s); + State s = worklist.Dequeue(); if (s.accept) { accepts.Add(s); @@ -344,7 +342,7 @@ namespace Lucene.Net.Util.Automaton if (!visited.Contains(t.to)) { visited.Add(t.to); - worklist.AddLast(t.to); + worklist.Enqueue(t.to); } } } @@ -468,7 +466,7 @@ namespace Lucene.Net.Util.Automaton map[s.TransitionsArray[i].to.Number].Add(s); } } - LinkedList<State> worklist = new LinkedList<State>(live); + LinkedList<State> worklist = new LinkedList<State>(live); // LUCENENET: Queue would be slower in this case because of the copy constructor while (worklist.Count > 0) { State s = worklist.First.Value; @@ -629,16 +627,15 @@ namespace Lucene.Net.Util.Automaton this.Determinize(); // LUCENENET: should we do this ? Transition[][] transitions = this.GetSortedTransitions(); - LinkedList<State> worklist = new LinkedList<State>(); + Queue<State> worklist = new Queue<State>(); // LUCENENET specific - Queue is much more performant than LinkedList JCG.HashSet<State> visited = new JCG.HashSet<State>(); - State current = this.initial; - worklist.AddLast(this.initial); + State current; + worklist.Enqueue(this.initial); visited.Add(this.initial); while (worklist.Count > 0) { - current = worklist.First.Value; - worklist.Remove(current); + current = worklist.Dequeue(); hash = 31 * hash + current.accept.GetHashCode(); Transition[] t1 = transitions[current.number]; @@ -653,7 +650,7 @@ namespace Lucene.Net.Util.Automaton State next = t1[n1].to; if (!visited.Contains(next)) { - worklist.AddLast(next); + worklist.Enqueue(next); visited.Add(next); } } diff --git a/src/Lucene.Net/Util/Automaton/BasicOperations.cs b/src/Lucene.Net/Util/Automaton/BasicOperations.cs index 0e862e5..afddcf9 100644 --- a/src/Lucene.Net/Util/Automaton/BasicOperations.cs +++ b/src/Lucene.Net/Util/Automaton/BasicOperations.cs @@ -396,15 +396,14 @@ namespace Lucene.Net.Util.Automaton Transition[][] transitions1 = a1.GetSortedTransitions(); Transition[][] transitions2 = a2.GetSortedTransitions(); Automaton c = new Automaton(); - LinkedList<StatePair> worklist = new LinkedList<StatePair>(); + Queue<StatePair> worklist = new Queue<StatePair>(); // LUCENENET specific - Queue is much more performant than LinkedList Dictionary<StatePair, StatePair> newstates = new Dictionary<StatePair, StatePair>(); StatePair p = new StatePair(c.initial, a1.initial, a2.initial); - worklist.AddLast(p); + worklist.Enqueue(p); newstates[p] = p; while (worklist.Count > 0) { - p = worklist.First.Value; - worklist.Remove(p); + p = worklist.Dequeue(); p.s.accept = p.s1.accept && p.s2.accept; Transition[] t1 = transitions1[p.s1.number]; Transition[] t2 = transitions2[p.s2.number]; @@ -419,12 +418,10 @@ namespace Lucene.Net.Util.Automaton if (t2[n2].max >= t1[n1].min) { StatePair q = new StatePair(t1[n1].to, t2[n2].to); - StatePair r; - newstates.TryGetValue(q, out r); - if (r == null) + if (!newstates.TryGetValue(q, out StatePair r) || r is null) { q.s = new State(); - worklist.AddLast(q); + worklist.Enqueue(q); newstates[q] = q; r = q; } @@ -492,15 +489,14 @@ namespace Lucene.Net.Util.Automaton a2.Determinize(); Transition[][] transitions1 = a1.GetSortedTransitions(); Transition[][] transitions2 = a2.GetSortedTransitions(); - LinkedList<StatePair> worklist = new LinkedList<StatePair>(); + Queue<StatePair> worklist = new Queue<StatePair>(); // LUCENENET specific - Queue is much more performant than LinkedList JCG.HashSet<StatePair> visited = new JCG.HashSet<StatePair>(); StatePair p = new StatePair(a1.initial, a2.initial); - worklist.AddLast(p); + worklist.Enqueue(p); visited.Add(p); while (worklist.Count > 0) { - p = worklist.First.Value; - worklist.Remove(p); + p = worklist.Dequeue(); if (p.s1.accept && !p.s2.accept) { return false; @@ -533,7 +529,7 @@ namespace Lucene.Net.Util.Automaton StatePair q = new StatePair(t1[n1].to, t2[n2].to); if (!visited.Contains(q)) { - worklist.AddLast(q); + worklist.Enqueue(q); visited.Add(q); } } @@ -792,10 +788,10 @@ namespace Lucene.Net.Util.Automaton a.initial = new State(); SortedInt32Set.FrozenInt32Set initialset = new SortedInt32Set.FrozenInt32Set(initNumber, a.initial); - LinkedList<SortedInt32Set.FrozenInt32Set> worklist = new LinkedList<SortedInt32Set.FrozenInt32Set>(); + Queue<SortedInt32Set.FrozenInt32Set> worklist = new Queue<SortedInt32Set.FrozenInt32Set>(); // LUCENENET specific - Queue is much more performant than LinkedList IDictionary<SortedInt32Set.FrozenInt32Set, State> newstate = new Dictionary<SortedInt32Set.FrozenInt32Set, State>(); - worklist.AddLast(initialset); + worklist.Enqueue(initialset); a.initial.accept = initAccept; newstate[initialset] = a.initial; @@ -812,13 +808,10 @@ namespace Lucene.Net.Util.Automaton // like SortedMap<Integer,Integer> SortedInt32Set statesSet = new SortedInt32Set(5); - // LUCENENET NOTE: The problem here is almost certainly - // due to the conversion to FrozenIntSet along with its - // differing equality checking. while (worklist.Count > 0) { - SortedInt32Set.FrozenInt32Set s = worklist.First.Value; - worklist.Remove(s); + SortedInt32Set.FrozenInt32Set s = worklist.Dequeue(); + //worklist.Remove(s); // Collate all outgoing transitions by min/1+max: for (int i = 0; i < s.values.Length; i++) @@ -857,7 +850,7 @@ namespace Lucene.Net.Util.Automaton q = new State(); SortedInt32Set.FrozenInt32Set p = statesSet.Freeze(q); - worklist.AddLast(p); + worklist.Enqueue(p); if (newStateUpto == newStatesArray.Length) { // LUCENENET: Resize rather than copy diff --git a/src/Lucene.Net/Util/Automaton/MinimizationOperations.cs b/src/Lucene.Net/Util/Automaton/MinimizationOperations.cs index 3c626a5..13ec9f3 100644 --- a/src/Lucene.Net/Util/Automaton/MinimizationOperations.cs +++ b/src/Lucene.Net/Util/Automaton/MinimizationOperations.cs @@ -1,6 +1,7 @@ using J2N; using System.Collections; using System.Collections.Generic; +using System.Runtime.InteropServices; using JCG = J2N.Collections.Generic; /* @@ -83,7 +84,7 @@ namespace Lucene.Net.Util.Automaton int[] block = new int[statesLen]; StateList[,] active = new StateList[statesLen, sigmaLen]; StateListNode[,] active2 = new StateListNode[statesLen, sigmaLen]; - LinkedList<Int32Pair> pending = new LinkedList<Int32Pair>(); + Queue<Int32Pair> pending = new Queue<Int32Pair>(); // LUCENENET specific - Queue is much more performant than LinkedList OpenBitSet pending2 = new OpenBitSet(sigmaLen * statesLen); OpenBitSet split = new OpenBitSet(statesLen), refine = new OpenBitSet(statesLen), refine2 = new OpenBitSet(statesLen); @@ -132,17 +133,16 @@ namespace Lucene.Net.Util.Automaton for (int x = 0; x < sigmaLen; x++) { int j = (active[0, x].Count <= active[1, x].Count) ? 0 : 1; - pending.AddLast(new Int32Pair(j, x)); + pending.Enqueue(new Int32Pair(j, x)); pending2.Set(x * statesLen + j); } // process pending until fixed point int k = 2; while (pending.Count > 0) { - Int32Pair ip = pending.First.Value; - pending.Remove(ip); - int p = ip.N1; - int x = ip.N2; + Int32Pair ip = pending.Dequeue(); + int p = ip.n1; + int x = ip.n2; pending2.Clear(x * statesLen + p); // find states that need to be split off their blocks for (StateListNode m = active[p, x].First; m != null; m = m.Next) @@ -197,12 +197,12 @@ namespace Lucene.Net.Util.Automaton if (!pending2.Get(ofs + j) && 0 < aj && aj <= ak) { pending2.Set(ofs + j); - pending.AddLast(new Int32Pair(j, c)); + pending.Enqueue(new Int32Pair(j, c)); } else { pending2.Set(ofs + k); - pending.AddLast(new Int32Pair(k, c)); + pending.Enqueue(new Int32Pair(k, c)); } } k++; @@ -250,14 +250,15 @@ namespace Lucene.Net.Util.Automaton /// <summary> /// NOTE: This was IntPair in Lucene /// </summary> - internal sealed class Int32Pair + [StructLayout(LayoutKind.Sequential)] + internal struct Int32Pair { - internal int N1 { get; private set; } - internal int N2 { get; private set; } + internal int n1; + internal int n2; internal Int32Pair(int n1, int n2) { - this.N1 = n1; - this.N2 = n2; + this.n1 = n1; + this.n2 = n2; } }
