[Mono-list] offtopic, but cool

Jonathan Pryor jonpryor@vt.edu
Thu, 13 May 2004 06:54:41 -0400

It just occurred to me, but this test is really unfair to C++. 
std::list is a linked-list, requiring a heap allocation for each node in
the list.  ArrayList and List<T> both use arrays for their internal
storage, and thus would require far fewer allocations.

I would suggest re-testing the C++ program, but use std::vector instead
of std::list.  std::vector is the array-based implementation, which is
supposed to provide (amortized) O(1) append time.  (Of course, std::list
also provides O(1) append and insert time, but the heap allocation per
node requirement is a killer, as opposed to the probable log(n) heap
allocations an array would require, assuming you don't pre-allocate the

Which reminds me: running the test with the List/vector pre-allocated
would be interesting, as it would help to remove the C++ heap allocator
and the GC from the performance equation, allowing us to see a better
comparison between the two models.

 - Jon

On Wed, 2004-05-12 at 07:56, Cory Nelson wrote:
> Just got done installing the VS.NET 2005 preview and did a small test.
> I compared an ArrayList of Rectangles to a List<Rectangle>, and timed
> inserting 1mil rects into each.  I also wrote an equivalent c++ app. 
> Got some interesting results:
> ArrayList: 265ms
> List<Rectangle>: 62ms
> list<rect>: 141ms
> So it seems with generics .NET is finally faster than c++ (at least,
> in this case).