I have a need to clone an existing list into another, existing list. As the environment demands very high performance, I need to eliminate unnecessary memory reallocation.
The most efficient algorithm I can think of is the following, which will increase the capacity of the destination list to match the source one as required, but will not decrease its own. (This is acceptable behavior for this project.)
public static void CloneInto(this List<T> source, List<T> destination)
{
if (destination.Capacity < source.Capacity)
{
/* Increase capacity in destination */
destination.Capacity = source.Capacity;
}
/* Direct copy of items within the limit of both counts */
for (var i = 0; i < source.Count && i < destination.Count; i++)
{
destination[i] = source[i];
}
if (source.Count > destination.Count)
{
/* Append any extra items from source */
for (var i = destination.Count; i < source.Count; i++ )
{
destination.Add(source[i]);
}
}
else if (source.Count < destination.Count)
{
/* Trim off any extra items from destination */
while (destination.Count > source.Count)
{
destination.RemoveAt(destination.Count - 1);
}
}
}
However this seems a lot of code, logic and loops.
Is there a more efficient way to clone a list into an existing list while avoiding unnecessary memory allocations?
This is probably wrong... The
source.Capacity
could be bigger than necessary...And you are "copying" the elements already contained in
destination
to a "new"destination
"buffer". This copy is unnecessary because then the elements ofdestination
are discardedSo you should at least:
In this way, if the
Capacity
is changed, no elements need to be copied (note that I'm using theCapacity = Count
, because while this would economize memory in the short term, in the long term it could cause multiple allocations of memory). Note that I'm checking against thesource.Count
, but for the assignment ofCapacity
I'm using the samesource.Capacity
. This to minimize reallocations ofdestination
if the method is called multiple times.Small optimization:
This because
List.Clear()
usesArray.Clear()
, so it really zeroes the internal elements, whiledestination.Capacity = 0
is optimized to simply reassign the internal array to astatic _emptyArray
.You could even try:
but by looking at the source code, I think it is slower than necessary (because it first copies the elements to
T[] itemsToInsert = new T[count];
, so it does two copies of the elements...Then:
can be optimized to: