You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@lucenenet.apache.org by ni...@apache.org on 2020/07/21 09:48:37 UTC
[lucenenet] 03/24: PERFORMANCE: Lucene.Net.Util.Automaton: Replaced
LinkedList with Queue in areas where copy constructors were not in
use
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 <sh...@shadstorhaug.com>
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;
}
}