Click here to Skip to main content
Click here to Skip to main content

A look at STL/CLR performance for linear containers

, 8 Mar 2008 CDDL
Rate this:
Please Sign up or sign in to vote.
The performance of STL/CLR sequence containers are compared with that of corresponding BCL generic collection classes

test app

Introduction

This article is an attempt to compare the general performance of STL/CLR's sequence containers with the .NET generic List<T> collection class. Before I began work on the article, I strongly believed that the STL/CLR containers would be yards faster. To my utmost surprise, I found that this was not so and that List<T> surpassed the STL/CLR collections with ease.

How I compared performance

I wanted to keep things simple and used the common technique of repeating a specific operation several times. To smoothen the design, I have an interface as follows :-

namespace STLCLRTests 
{
    public interface class IMeasurable 
    {
        Int64 RunCode(int iterations);
    };
}

RunCode would run a specific piece of code as many times as specified by iterations, and would return the time taken in milliseconds. And I have the following abstract class that implements this interface.

namespace STLCLRTests 
{
    public ref class MeasurableDoubleOp abstract : IMeasurable
    {
    private:
        static Stopwatch^ stopWatch = gcnew Stopwatch();

    public:
        virtual Int64 RunCode(int iterations)
        {
            Initialize();

            stopWatch->Reset();
            stopWatch->Start();

            RunCodeFirstOp(iterations);
            RunCodeSecondOp(iterations);

            stopWatch->Stop();

            return stopWatch->ElapsedMilliseconds;
        }

    protected:
        virtual void Initialize() {}
        virtual void RunCodeFirstOp(int iterations) abstract;
        virtual void RunCodeSecondOp(int iterations) abstract;
    };
}

To profile a certain collection class, I just derive from this abstract class and implement RunCodeFirstOp and RunCodeSecondOp. I also have a MeasurableSingleOp class for doing tests that do not involve a two-step operation.

STL vector vs List<T> - basic insertion/removal

Here are the implementations of the vector specific and List<T> specific classes.

namespace STLCLRTests 
{
    public ref class VectorInsertRemove : MeasurableDoubleOp
    {
    private:
        cliext::vector<int> vector;

    protected:
        IEnumerable<int>^ GetVector()
        {
            return %vector;
        }

    public:
        virtual void RunCodeFirstOp(int iterations) override
        {
            for(int count=0; count<iterations; count++)
            {
                vector.push_back(10);
            }
        }

        virtual void RunCodeSecondOp(int iterations) override 
        {
            for(int count=0; count<iterations; count++)
            {
                vector.pop_back();
            }
        }
    };
}
namespace STLCLRTests 
{
    public ref class GenericListInsertRemove : MeasurableDoubleOp
    {
    private:
        List<int> list;

    protected:
        IEnumerable<int>^ GetList()
        {
            return %list;
        }

    public:
        virtual void RunCodeFirstOp(int iterations) override
        {
            for(int count=0; count<iterations; count++)
            {
                list.Add(10);
            }
        }

        virtual void RunCodeSecondOp(int iterations) override 
        {
            for(int count=0; count<iterations; count++)
            {
                list.RemoveAt(list.Count - 1);
            }
        }
    };
}

And here are my test results. As you can see, the BCL class (List<T>) completely outperformed the STL/CLR vector class.

Iterations STL/CLR BCL
100000 15 3
500000 63 32
1000000 122 21
10000000 1311 299

Here's a graphical plot of how the two containers performed. Clearly, the BCL class's performance was quite superior to the STL vector's.

STL vector vs List - basic insertion/removal

As you can imagine I was quite surprised by this result. Just for the heck of it I thought I should also compare the standard STL vector with the STL/CLR vector implementation. Note than I am still using managed code (/clr) - the standard STL code is also compiled as /clr. Here are my surprising results.

Iterations STL/CLR Standard STL
100000 11 39
500000 58 202
1000000 117 391
10000000 1161 3919

STL/CLR vector vs standard vector - basic insertion/removal

Based on that result, you should absolutely avoid compiling native STL code using /clr. Merely porting to STL/CLR would help performance in a big way. You might find that all you need is a namespace change (cliext to std) and you may not have to change too much code elsewhere. And no, I did not conclude this merely on my test results with vector, I compared the standard list and the STL/CLR list containers with the following results.

Iterations STL/CLR Std list
100000 33 101
500000 63 175
1000000 274 349
10000000 2969 3663

STL list vs List - basic insertion/removal

As you can see, the difference in performance is non-trivial. Please note that we are not comparing the native performance of STL here. We are comparing how the native implementation when compiled under /clr compares with the CLR implementation of STL.

STL list vs List<T> - basic insertion/removal

Here's my implementation for the STL list specific class.

namespace STLCLRTests 
{
    public ref class StlListInsertRemove : MeasurableDoubleOp
    {
    private:
        cliext::list<int> list;

    public:
        virtual void RunCodeFirstOp(int iterations) override
        {
            for(int count=0; count<iterations; count++)
            {
                list.push_back(10);
            }
        }

        virtual void RunCodeSecondOp(int iterations) override 
        {
            for(int count=0; count<iterations; count++)
            {
                list.pop_back();
            }
        }
    };
}

And here are my test results. Here, the contrast is even more - not surprising really, as the STL list will always be slower than the STL vector for straight inserts and removals.

Iterations STL/CLR BCL
100000 32 2
500000 149 11
1000000 332 23
10000000 3719 331

And here's a graphical plot of the results.

STL list vs List - basic insertion/removal

STL deque vs List<T> - basic insertion/removal

Here's the deque implementation.

namespace STLCLRTests 
{
    public ref class DequeInsertRemove : MeasurableDoubleOp
    {
    private:
        cliext::deque<int> deque;

    public:
        virtual void RunCodeFirstOp(int iterations) override
        {
            for(int count=0; count<iterations; count++)
            {
                deque.push_back(10);
            }
        }

        virtual void RunCodeSecondOp(int iterations) override 
        {
            for(int count=0; count<iterations; count++)
            {
                deque.pop_back();
            }
        }
    };
}

Here are my results. Nothing's changed in the pattern - the BCL class is way faster here too.

Iterations STL/CLR BCL
100000 33 2
500000 66 13
1000000 83 26
10000000 1061 251

And here's the graph.

STL deque vs List - basic insertion/removal

The BCL equivalent of a queue is the Queue<T> class - so just to be sure we are comparing apples with apples, I went ahead and ran tests comparing the STL/CLR deque with the BCL Queue<T>. My results and the corresponding graph follow.

Iterations STL/CLR BCL
100000 12 6
500000 49 15
1000000 89 28
10000000 1044 335

STL deque vs Queue - basic insertion/removal

The Queue<T> class seems to be marginally slower than List<T> but is still way faster than the STL/CLR deque container.

STL vector vs List<T> - basic iteration

This time, I wanted to test the speed with which we can iterate over a linear collection. Here are the vector and List<T> specific iteration test implementations.

namespace STLCLRTests 
{
    public ref class VectorIterate : MeasurableDoubleOp
    {
    private:
        cliext::vector<int> vector;

    public:
        virtual void RunCodeFirstOp(int iterations) override
        {
            vector.clear();

            for(int count=0; count<iterations; count++)
            {
                vector.push_back(10);
            }
        }

        virtual void RunCodeSecondOp(int iterations) override 
        {
            for(cliext::vector<int>::iterator it = vector.begin(); it != vector.end(); it++)
            {
            }
        }
    };
}
namespace STLCLRTests 
{
    public ref class GenericListIterate : MeasurableDoubleOp
    {
    private:
        List<int> list;

    public:
        virtual void RunCodeFirstOp(int iterations) override
        {
            list.Clear();

            for(int count=0; count<iterations; count++)
            {
                list.Add(10);
            }
        }

        virtual void RunCodeSecondOp(int iterations) override 
        {
            for each(int x in list)
            {
            }
        }
    };
}

Here are my test results. The results further proved the superior efficiency of the List<T> class.

Iterations STL/CLR BCL
100000 24 2
500000 93 16
1000000 194 31
10000000 2009 394

And here's the corresponding graph.

STL vector vs List - basic iteration

STL vector vs List<T> - Linq access (where)

For the Linq tests, I used a C# project (for easier syntax). I derived from the insert tester and merely overrode the RunCodeSecondOp method as I wanted to keep the insertion code intact.

namespace LinqTests
{
    public class VectorLinqWhere : VectorInsertRemove
    {
        public override void RunCodeSecondOp(int iterations)
        {
            IEnumerable<int> _vector = GetVector();
            var newVector = _vector.Where(x => x % 2 == 0);
        }
    }
}
namespace LinqTests
{
    public class GenericListLinqWhere : GenericListInsertRemove
    {
        public override void RunCodeSecondOp(int iterations)
        {
            IEnumerable<int> _list = GetList();
            var newList = _list.Where(x => x % 2 == 0);
        }
    }
}

Here are the results of my test runs. The results here are partially contaminated by the fact that the insertion code speed differences would also come into play. But the difference in performance is large enough to safely ignore that for now, and again LINQ works much faster on the BCL class as compared to the STL/CLR version.

Iterations STL/CLR BCL
100000 18 1
500000 44 7
1000000 79 11
10000000 842 168

And here's the graph.

Linq where test

STL vector vs List<T> - Linq access (take)

This is similar to the previous one except I use Take instead of Where.

namespace LinqTests
{
    public class VectorLinqTake : VectorInsertRemove
    {
        public override void RunCodeSecondOp(int iterations)
        {
            IEnumerable<int> _vector = GetVector();
            var newVector = _vector.Take(_vector.Count() / 2);
        }
    }
}
namespace LinqTests
{
    public class GenericListLinqTake : GenericListInsertRemove
    {
        public override void RunCodeSecondOp(int iterations)
        {
            IEnumerable<int> _list = GetList();
            var newList = _list.Take(_list.Count() / 2);
        }
    }
}

Here's the result of my tests. These results are very similar to the previous test.

Iterations STL/CLR BCL
100000 7 0
500000 35 4
1000000 70 10
10000000 865 205

And the corresponding graph.

Linq take test

Sorting

I ran tests comparing sorting speeds of the List<T> class with the STL/CLR vector and list containers. The code used follows.

namespace STLCLRTests 
{
    public ref class GenericListSort : MeasurableDoubleOp
    {
    private:
        List<int> list;

    protected:
        IEnumerable<int>^ GetList()
        {
            return %list;
        }

    public:
        virtual void RunCodeFirstOp(int iterations) override
        {
            for(int count=0; count<iterations; count++)
            {
                list.Add(10);
            }
        }

        virtual void RunCodeSecondOp(int iterations) override 
        {
            list.Sort();
        }
    };
}

namespace STLCLRTests 
{
    public ref class StlListSort : MeasurableDoubleOp
    {
    private:
        cliext::list<int> list;

    public:
        virtual void RunCodeFirstOp(int iterations) override
        {
            for(int count=0; count<iterations; count++)
            {
                list.push_back(10);
            }
        }

        virtual void RunCodeSecondOp(int iterations) override 
        {
            list.sort();
        }
    };
}
namespace STLCLRTests 
{
    public ref class VectorSort : MeasurableDoubleOp
    {
    private:
        cliext::vector<int> vector;

    protected:
        IEnumerable<int>^ GetVector()
        {
            return %vector;
        }

    public:
        virtual void RunCodeFirstOp(int iterations) override
        {
            for(int count=0; count<iterations; count++)
            {
                vector.push_back(10);
            }
        }

        virtual void RunCodeSecondOp(int iterations) override 
        {
            sort(vector.begin(), vector.end());
        }
    };
}

Here are the results for vector versus List<T>.

Iterations STL/CLR BCL
100000 37 7
500000 136 53
1000000 325 137
10000000 2695 1088
vector sort vs List sort

And here are my results for stl list versus List<T>.

Iterations STL/CLR BCL
100000 138 7
500000 1162 51
1000000 5355 128
10000000 31985 1095
STL list sort vs VCL List sort

Conclusion

One of the features that was strongly marketed before STL/CLR was released was its performance benefits over regular .NET collections. But the .NET generic List<T> seems to be much faster. At this stage all I can think of as a valid case for using STL/CLR would be when doing a first-level port of existing C++ code ( that heavily uses STL) to managed code.

License

This article, along with any associated source code and files, is licensed under The Common Development and Distribution License (CDDL)

Share

About the Author

Nish Sivakumar

United States United States
Nish is a real nice guy who has been writing code since 1990 when he first got his hands on an 8088 with 640 KB RAM. Originally from sunny Trivandrum in India, he has been living in various places over the past few years and often thinks it’s time he settled down somewhere.
 
Nish has been a Microsoft Visual C++ MVP since October, 2002 - awfully nice of Microsoft, he thinks. He maintains an MVP tips and tricks web site - www.voidnish.com where you can find a consolidated list of his articles, writings and ideas on VC++, MFC, .NET and C++/CLI. Oh, and you might want to check out his blog on C++/CLI, MFC, .NET and a lot of other stuff - blog.voidnish.com.
 
Nish loves reading Science Fiction, P G Wodehouse and Agatha Christie, and also fancies himself to be a decent writer of sorts. He has authored a romantic comedy Summer Love and Some more Cricket as well as a programming book – Extending MFC applications with the .NET Framework.
 
Nish's latest book C++/CLI in Action published by Manning Publications is now available for purchase. You can read more about the book on his blog.
 
Despite his wife's attempts to get him into cooking, his best effort so far has been a badly done omelette. Some day, he hopes to be a good cook, and to cook a tasty dinner for his wife.

Comments and Discussions

 
QuestionMemory allocation is also very different... and some more comments. PinmemberPhilippe Mori4-Nov-11 15:22 
I think that one of the main reason (apart from the fact that the debug version of native STL is painfully slow because of all checks) that native is way slower is related to the fact that memoryis garbage collected for BCL.
 
I suspect also that part of the performance problem with native STL compiled with STL/CLR might be related to managed/unmanaged transition. Is there a way to know when such transition occurs.
 
In pratice, I have found that when compiling for .NET and using the debug version of STL, it is much more performant to uses STL/CLR than native STL. I tend to believe that the checking of iterators is much faster in the managed case.
 
What I dislike with STL/CLR is that it is somehow harder to do function objects and we cannot uses lambda so it then become not much more advantageous for code simplicity compared to BCL when for example you want to use a custom sort.
 
I also think that native STL performance is affected by too much locking. Probably related to checked iterators.
 
I would also like if it would be easier to make code more independant on the compilation mode. But some difference between managed and unmanged code seems to make it more complex to write the same code in both cases as their are many differences.
 
Now with C++/CX for Metro Style applications on Windows 8, we will have still more differences to handle.
 
In my opinion, the fact that most of STL was rewritten for .NET is an indication that they are some flaws with the way C++/CLI language was defined. For example ^ instead of * or the fact that a ref class always need to be qualified with the ref modifier severily limit the possibilities for using the powerfulness of templates.
Philippe Mori

AnswerRe: Memory allocation is also very different... and some more comments. PinmvpNishant Sivakumar6-Nov-11 3:26 
GeneralMy vote of 3 PinmemberYuancai (Charlie) Ye12-Jan-11 2:55 
GeneralMy vote of 1 Pinmemberlangolas3-Nov-10 5:08 
GeneralI don't buy this Pinmemberare_all_nicks_taken_or_what19-Jan-10 0:51 
Generalmy results Pinmembervalery trofimov24-Feb-09 1:22 
Generalsource code Pinmemberclintonvanry28-Sep-08 9:24 
Generalyour results looks wrong Pinmemberrm8229-Aug-08 16:57 
Generalstd::list and gcroot Pinmembergooja27-Jun-08 23:50 
QuestionChecked? PinmemberNemanja Trifunovic9-Mar-08 16:01 
AnswerRe: Checked? PinmemberMember 13357349-Mar-08 18:03 
GeneralRe: Checked? Pinmember Randor 25-Apr-08 11:09 
QuestionWhy? PinsitebuilderShog98-Mar-08 9:20 
AnswerRe: Why? PinmvpNishant Sivakumar8-Mar-08 10:47 
GeneralRe: Why? PinmemberRama Krishna Vavilala8-Mar-08 13:35 
GeneralRe: Why? PinmemberMember 13357349-Mar-08 18:05 
GeneralRe: Why? PinmemberWong Shao Voon9-Apr-08 20:10 
QuestionDebug or Release ? PinmemberArgiris Kirtzidis8-Mar-08 5:18 
AnswerRe: Debug or Release ? PinmvpNishant Sivakumar8-Mar-08 5:36 
GeneralThe missing stat... Pinmemberaxelriet8-Mar-08 3:14 
GeneralRe: The missing stat... PinmvpNishant Sivakumar8-Mar-08 3:17 
GeneralRe: The missing stat... PinmemberJim Crafton8-Mar-08 12:11 
GeneralRe: The missing stat... PinmvpNishant Sivakumar8-Mar-08 12:55 
GeneralRe: The missing stat... PinmemberPhilippe Mori4-Nov-11 15:30 
GeneralRe: The missing stat... PinmvpNishant Sivakumar6-Nov-11 3:27 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

| Advertise | Privacy | Mobile
Web02 | 2.8.141015.1 | Last Updated 8 Mar 2008
Article Copyright 2008 by Nish Sivakumar
Everything else Copyright © CodeProject, 1999-2014
Terms of Service
Layout: fixed | fluid