I was just browsing through the List<T> implementation and made a few speed
optimisations. I'm not sure if changing from foreach(blah) to for(int i=0;
i< blah, i++) is ok or not, but it does offer a large speed increase. So let
me know if that's ok or not.
Optimised Methods:
RemoveAll - from 0x up to 50x faster
(The reason for the huge speed increase is that if you have a list<int>
containing entirely the number 5, removing from the end will be much more
efficient than removing from the start as you won't have to shift the entire
array over and over. Removing from the end will *always* be faster than
removing from the start, but the exact speed increase is highly dependant on
the number of matches).
Add - 0.3x faster
ConvertAll - 0.5x faster
Exists - 0.04x faster
Find - 0.05x faster
ForEach - 2.7x faster
InsertAt - up to 0.2x faster (if addind at the end)
RemoveAll - 0.11x faster
True For All - 2.3x faster
Patch attached. Let me know if it's good to commit. It still passes the
NUnit tests.
Alan.
Index: C:/programming/mcs/class/corlib/System.Collections.Generic/List.cs
===================================================================
--- C:/programming/mcs/class/corlib/System.Collections.Generic/List.cs (revision 74942)
+++ C:/programming/mcs/class/corlib/System.Collections.Generic/List.cs (working copy)
@@ -82,7 +82,10 @@
}
public void Add (T item)
{
- GrowIfNeeded (1);
+ // If we check to see if we need to grow before trying to grow
+ // we can speed things up by 25%
+ if (this._size == this._items.Length)
+ GrowIfNeeded (1);
_items [_size ++] = item;
_version++;
}
@@ -163,11 +166,7 @@
public bool Contains (T item)
{
- EqualityComparer<T> equalityComparer = EqualityComparer<T>.Default;
- for (int i = 0; i < _size; i++)
- if (equalityComparer.Equals (_items[i], item))
- return true;
- return false;
+ return Array.IndexOf<T>(this._items, item) != -1;
}
public List <TOutput> ConvertAll <TOutput> (Converter <T, TOutput> converter)
@@ -175,8 +174,10 @@
if (converter == null)
throw new ArgumentNullException ("converter");
List <TOutput> u = new List <TOutput> (_size);
- foreach (T t in this)
- u.Add (converter (t));
+ for (int i = 0; i < this._size; i++)
+ u._items[i] = converter(this._items[i]);
+
+ u._size = this._size;
return u;
}
@@ -198,7 +199,8 @@
public bool Exists (Predicate <T> match)
{
- return FindIndex (match) != -1;
+ CheckMatch(match);
+ return GetIndex(0, this._size, match) != -1;
}
public T Find (Predicate <T> match)
@@ -203,7 +205,8 @@
public T Find (Predicate <T> match)
{
- int i = FindIndex (match);
+ CheckMatch(match);
+ int i = GetIndex(0, this._size, match);
return (i != -1) ? _items [i] : default (T);
}
void CheckMatch (Predicate <T> match)
@@ -297,7 +300,8 @@
}
int GetIndex (int startIndex, int count, Predicate <T> match)
{
- for (int i = startIndex; i < startIndex + count; i ++)
+ int end = startIndex + count;
+ for (int i = startIndex; i < end; i ++)
if (match (_items [i]))
return i;
@@ -345,8 +349,8 @@
{
if (action == null)
throw new ArgumentNullException ("action");
- foreach (T t in this)
- action (t);
+ for(int i=0; i < this._size; i++)
+ action(this._items[i]);
}
public Enumerator GetEnumerator ()
@@ -392,8 +396,9 @@
if (delta < 0)
start -= delta;
- Array.Copy (_items, start, _items, start + delta, _size - start);
-
+ if (start < _size)
+ Array.Copy(_items, start, _items, start + delta, _size - start);
+
_size += delta;
}
@@ -405,10 +410,11 @@
public void Insert (int index, T item)
{
- CheckIndex (index);
- GrowIfNeeded (1);
- Shift (index, 1);
- this [index] = item;
+ CheckIndex(index);
+ if (this._size == this._items.Length)
+ GrowIfNeeded(1);
+ Shift(index, 1);
+ this._items[index] = item;
_version++;
}
@@ -486,7 +492,6 @@
return loc != -1;
}
- // FIXME: this could probably be made faster.
public int RemoveAll (Predicate <T> match)
{
CheckMatch (match);
@@ -491,14 +496,16 @@
{
CheckMatch (match);
- int index = 0;
+ int index = this._size;
int c = 0;
- while ((index = GetIndex (index, _size - index, match)) != -1) {
- RemoveAt (index);
+ while ((index = GetLastIndex(0, index, match)) != -1) {
+ Shift(index, -1);
c ++;
}
-
- Array.Clear (_items, _size, c);
+
+ if (c != 0)
+ this._version++;
+
return c;
}
@@ -504,9 +511,9 @@
public void RemoveAt (int index)
{
- CheckIndex (index);
+ if (index < 0 || (uint)index >= (uint)_size)
+ throw new ArgumentOutOfRangeException("index");
Shift (index, -1);
- Array.Clear (_items, _size, 0);
_version++;
}
@@ -573,8 +580,8 @@
{
CheckMatch (match);
- foreach (T t in this)
- if (!match (t))
+ for (int i = 0; i < this._size; i++)
+ if (!match(this._items[i]))
return false;
return true;
_______________________________________________
Mono-devel-list mailing list
Mono-devel-list@lists.ximian.com
http://lists.ximian.com/mailman/listinfo/mono-devel-list
