IndexableCollection<T>.Clear performance

Mar 9, 2010 at 10:02 PM

Hi,

I've had a first glance at the source code and it seems to me the Clear implementation could do much better if items were deleted from the end of the list (not to mention just clearing all internal collections, avoiding one-by-one deletion).

Correct me if I am wrong but removing item at the beginning of a List results in moving all the items above the deleted item.

Regs,

Vaso

Developer
Mar 10, 2010 at 12:53 AM

Hello vaso.

I just spiked your suggestion by - if you change the IndexableCollection<T>.Clear implementation to look like

        public void Clear()
        {
            ClearTest(_internalList);
            //while (_internalList.Count > 0)
            //    RemoveAt(0);
        }

        public Action<List<T>> ClearTest;

And then you run this unit test.

 

        [Test]
        public voidRemovalSpeedTest()
        {
            const int sampleSize = 100000;
            var listA = new IndexableCollection<PocoClass>(PocoClass.DefaultIndexSpecification);
            for (int i = 0; i < sampleSize; i++)
                listA.Add(new PocoClass
                {
                    DemoStringNonIndexed = Guid.NewGuid().ToString(),
                    DemoStringIndexed = Guid.NewGuid().ToString()
                });

            var listB = new IndexableCollection<PocoClass>(PocoClass.DefaultIndexSpecification);
            for (int i = 0; i < sampleSize; i++)
                listB.Add(new PocoClass
                {
                    DemoStringNonIndexed = Guid.NewGuid().ToString(),
                    DemoStringIndexed = Guid.NewGuid().ToString()
                });

            listA.ClearTest = (items) =>
            {
                while (items.Count > 0)
                    listA.RemoveAt(0);
            };

            listB.ClearTest = (items) =>
            {
                while (items.Count > 0)
                    listB.RemoveAt(items.Count-1);
            };


            var timeB = timeFor(() => { listB.Clear(); });
            var timeA = timeFor(() => { listA.Clear(); });
            listA.Count.ShouldEqual(0);
            listB.Count.ShouldEqual(0);
            Console.WriteLine("timeA=" + timeA);
            Console.WriteLine("timeB=" + timeB);
            Assert.IsTrue(timeB < timeA);

        }

 

timeA=26842063 (Current implementation)
timeB=334275 (Remove at end implementation)

It appear that you are correct. I can sure see this as a good tweak to the current implementation; however, Aaron is working on a V2 in a different branch. Please keep an eye on us to make sure we get this in the new version. Or better yet could you create an "issue" and tie it back to this discussion so we can track it?

Thanks,

Jason 

Mar 10, 2010 at 1:38 AM

Hi Jason,

Thank you for prompt response.

I created issue for this: WorkItemId=16698 (http://i4o.codeplex.com/WorkItem/View.aspx?WorkItemId=16698).

Regs,

Vaso