CODEWITHSUNDEEP
c#listperformanceobjectclone
Julien Dinis
Julien Dinis

Reputation: 23

Adding clones to a list is slow

I'm trying to speed up a loop, which is cloning 2_500_000 objects. The clone itself is taking 800 ms for the entire loop but when I'm adding them to a list, it's taking 3 seconds..

List<T> list = new List<T>();

Stopwatch sw = new Stopwatch();
sw.Start();

foreach(T entity in listSource)
{
    T entityCloned = GetEntityClone(entity); // Taking 800ms totally

    if (entityCloned != null)
        list.Add(entityCloned);
}

sw.Stop();

Could you please help me to find out why those Adds are taking so much time?

Upvotes: 2

Views: 211

Answers (3)

Michael Hancock
Michael Hancock

Reputation: 2855

Unfortunately looping over many things and deep copying objects is going to take time. I don't think that 3 seconds is necessarily an unreasonable amount of time for it to take.

But you can potentially improve the speed.

Firstly, if you know how many items the result list will need to hold before hand you can set the internal capacity beforehand to prevent the list from having to resize. Resizing is an expensive activity which can be avoided if necessary. This can be done by manually changing the capacity property of the list or by passing the capacity as a constructor argument for the list.

Once the capacity has been allocated, the complexity of adding to the list should be O(1), no reaollcations (which are a O(n) complexity task see this answer) will be needed. It is unlikely that adding to the list in this case will be the bottleneck.

You could also remove null values from the initial list which you are copying from beforehand to remove the need for the if statement which has to be evaluated every time. Using linq:

var noNulls = listSource.where(o => o != null)

Upvotes: 2

Girish Thanki
Girish Thanki

Reputation: 59

Try the following do the work in parallel: 

ConcurrentBag<T> list = new ConcurrentBag<T>();
Parallel.ForEach(listSource, entity =>
{
    T entityCloned = GetEntityClone(entity); //Taking 800ms totally
    if (entityCloned != null)
        list.Add(entityCloned);

});

var listVersion = list.ToList();

Upvotes: 0

Michal B.
Michal B.

Reputation: 5719

I saved some time (around 33%) by using array instead of list:

MyObject class defitinion:

public class MyObject
{
    public int Id { get; set; }
    public bool Flag { get; set; }

    public static MyObject GetEntityClone(MyObject obj)
    {
        if (obj == null) return null;

        var newObj = new MyObject()
        {
            Id = obj.Id,
            Flag = obj.Flag
        };

        return newObj;
    }
}

Code:

var sourceList = new List<MyObject>();

// let's mock the source data, every 27th element will be null
for (int i = 0; i < 2500000; ++i)
{
    if (i % 27 != 0)
        sourceList.Add(new MyObject { Id = i, Flag = (i % 2 == 0) });
}

var destArray = new MyObject[2500000];

Stopwatch sw = new Stopwatch();
sw.Start();
Console.WriteLine(sw.ElapsedMilliseconds);

var currentElement = 0;
for (int i = 0; i < sourceList.Count; ++i)
{
    MyObject entityCloned = MyObject.GetEntityClone(sourceList[i]);

    if (entityCloned != null)
        destArray[currentElement++] = entityCloned;
}

var result = new MyObject[currentElement];
Array.Copy(destArray, 0, result, 0, currentElement);
sw.Stop();
Console.WriteLine(sw.ElapsedMilliseconds);

Upvotes: 0

Related Questions