[Mono-list] offtopic, but cool

[Cory Nelson]

------=_Part_17_20590784.1084448052548
Content-Type: text/plain; charset=US-ASCII
Content-Transfer-Encoding: 7bit
Content-Disposition: inline

Good point.  I re-coded with that in mind, and it seems as long as you
preallocate the c++ vector, it wins:

vector<rect>: 109ms
vector<rect>(1000000): 15ms

List<Rectangle>: 78.13ms
List<Rectangle>(1000000): 46.88ms

Perhaps std::vector<T> is allocating smaller chunks than List<T>?


On Thu, 13 May 2004 06:54:41 -0400, Jonathan Pryor <jonpryor@vt.edu> wrote:
> 
> 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
> array.)
> 
> 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).
> 
>

------=_Part_17_20590784.1084448052548
Content-Type: text/plain; name="test.cs"
Content-Transfer-Encoding: quoted-printable
Content-Disposition: attachment; filename="test.cs"

#region Using directives

using System;
using System.Collections;
using System.Collections.Generic;
using System.Drawing;

#endregion

namespace SpeedTestNet {
=09class Program {
=09=09static void testlist() {
=09=09=09GC.Collect();
=09=09=09GC.WaitForPendingFinalizers();

=09=09=09List<Rectangle> rl=3Dnew List<Rectangle>();
=09=09=09DateTime start, end;

=09=09=09start=3DDateTime.Now;
=09=09=09for(int i=3D0; i<1000000; i++)
=09=09=09=09rl.Add(new Rectangle(i, i, i, i));
=09=09=09end=3DDateTime.Now;

=09=09=09Console.WriteLine("List<Rectangle>:          {0:F2}ms", (end-start=
).TotalMilliseconds);
=09=09=09rl.Clear();
=09=09}

=09=09static void testlistpa() {
=09=09=09GC.Collect();
=09=09=09GC.WaitForPendingFinalizers();

=09=09=09List<Rectangle> rl=3Dnew List<Rectangle>(1000000);
=09=09=09DateTime start, end;

=09=09=09start=3DDateTime.Now;
=09=09=09for(int i=3D0; i<1000000; i++)
=09=09=09=09rl.Add(new Rectangle(i, i, i, i));
=09=09=09end=3DDateTime.Now;

=09=09=09Console.WriteLine("List<Rectangle>(1000000): {0:F2}ms", (end-start=
).TotalMilliseconds);
=09=09=09rl.Clear();
=09=09}

=09=09static void Main(string[] args) {
=09=09=09testlist();
=09=09=09testlistpa();
=09=09}
=09}
}

------=_Part_17_20590784.1084448052548
Content-Type: text/plain; name="test.cpp"
Content-Transfer-Encoding: quoted-printable
Content-Disposition: attachment; filename="test.cpp"

#include <vector>
#include <iostream>
#include <ctime>
using namespace std;

struct rect {
=09int x;
=09int y;
=09int width;
=09int height;
};

static void testvector(void) {
=09vector<rect> rv;
=09clock_t start, end;

=09start=3Dclock();
=09for(int i=3D0; i<1000000; i++) {
=09=09rect r=3D{i, i, i, i};
=09=09rv.push_back(r);
=09}
=09end=3Dclock();

=09cout << "vector<rect>:          " << (((float)(end-start))/((float)CLOCK=
S_PER_SEC)*1000.0f) << "ms" << endl;
}

static void testvectorpa(void) {
=09vector<rect> rv(1000000);
=09clock_t start, end;

=09start=3Dclock();
=09for(int i=3D0; i<1000000; i++) {
=09=09rect r=3D{i, i, i, i};
=09=09rv[i]=3Dr;
=09}
=09end=3Dclock();

=09cout << "vector<rect>(1000000): " << (((float)(end-start))/((float)CLOCK=
S_PER_SEC)*1000.0f) << "ms" << endl;
}

int main(void) {
=09testvector();
=09testvectorpa();

=09return 0;
}

------=_Part_17_20590784.1084448052548--