CODEWITHSUNDEEP
c#stringperformancelistcomparison
Leopold Asperger
Leopold Asperger

Reputation: 1015

Why is List<string>.Sort() slow?

So I noticed that a treeview took unusually long to sort, first I figured that most of the time was spent repainting the control after adding each sorted item. But eitherway I had a gut feeling that List<T>.Sort() was taking longer than reasonable so I used a custom sort method to benchmark it against. The results were interesting, List<T>.Sort() took ~20 times longer, that's the biggest disappointment in performance I've ever encountered in .NET for such a simple task.

My question is, what could be the reason for this? My guess is the overhead of invoking the comparison delegate, which further has to call String.Compare() (in case of string sorting). Increasing the size of the list appears to increase the performance gap. Any ideas? I'm trying to use .NET classes as much as possible but in cases like this I just can't.

Edit:

    static List<string> Sort(List<string> list)
    {
        if (list.Count == 0)
        {
            return new List<string>();
        }

        List<string> _list = new List<string>(list.Count);
        _list.Add(list[0]);

        int length = list.Count;

        for (int i = 1; i < length; i++)
        {
            string item = list[i];

            int j;

            for (j = _list.Count - 1; j >= 0; j--)
            {
                if (String.Compare(item, _list[j]) > 0)
                {
                    _list.Insert(j + 1, item);

                    break;
                }
            }

            if (j == -1)
            {
                _list.Insert(0, item);
            }
        }

        return _list;
    }

Upvotes: 6

Views: 2421

Answers (2)

Simon C
Simon C

Reputation: 9508

Answer: It's not.

I ran the following benchmark in a simple console app and your code was slower:

    static void Main(string[] args)
    {
        long totalListSortTime = 0;

        long totalCustomSortTime = 0;

        for (int c = 0; c < 100; c++)
        {
            List<string> list1 = new List<string>();
            List<string> list2 = new List<string>();

            for (int i = 0; i < 5000; i++)
            {
                var rando = RandomString(15);
                list1.Add(rando);
                list2.Add(rando);
            }

            Stopwatch watch1 = new Stopwatch();
            Stopwatch watch2 = new Stopwatch();

            watch2.Start();
            list2 = Sort(list2);
            watch2.Stop();
            totalCustomSortTime += watch2.ElapsedMilliseconds;

            watch1.Start();
            list1.Sort();
            watch1.Stop();
            totalListSortTime += watch1.ElapsedMilliseconds;



        }

        Console.WriteLine("totalListSortTime = " + totalListSortTime);
        Console.WriteLine("totalCustomSortTime = " + totalCustomSortTime);

        Console.ReadLine();
    }

Result:

enter image description here

Upvotes: 9

Saverio Terracciano
Saverio Terracciano

Reputation: 3915

I haven't had the time to fully test it because I had a blackout (writing from phone now), but it would seem your code (from Pastebin) is sorting several times an already ordered list, so it would seem that your algorithm could be faster to...sort an already sorted list. In case the standard .NET implementation is a Quick Sort, this would be natural since QS has its worst case scenario on already sorted lists.

Upvotes: 5

Related Questions