CODEWITHSUNDEEP
c#.netperformancejit
Mayo
Mayo

Reputation: 909

Different performance in creating class with reference

I found a little strange thing in C# for me.. I have class A, containing only one reference to A. Then I create new object A in every iteration inside for loop, with reference to object created in previous iteration. But If I change reference to object created before for loop, it is much faster. Why it is so?

class A
{
    private A next;

    public A(A next)
    {
        this.next = next;
    }
}

var a = new A(null);

for (int i = 0; i < 10*1000*1000; i++)
    a = new A(a);

// Takes 1.5s

var b = new A(null);
for (int i = 0; i < 10*1000*1000; i++)
    a = new A(b);

// Takes only 0.17s

I found this during implementation of immutable stack in usual way and throught VList which was due to that much faster.

Upvotes: 2

Views: 815

Answers (6)

Hans Passant
Hans Passant

Reputation: 941545

You are measuring the cost of using memory. The slow version allocates 120 megabytes and all objects are referenced through the next object references. Short from the cost of allocating the address space, I see 21 gen #0 collections, 17 gen #1 collections and 2 expensive gen #2 collections. The background GC cannot help because of the high allocation rate.

The buggy fast version gives the garbage collector a very easy time. The allocated objects are not referenced anywhere so the fast gen #0 collection collects all of them. It uses very little memory, just the gen #0 segment and there are no gen #1 and gen #2 collections.

You've otherwise probably discovered a basic truth about immutable objects. The type guarantees are nice but the concept does not translate well to the way the machine works. Processors are heavily optimized to make mutable objects very efficient, immutable ones are cache unfriendly, memory hungry and give the GC a lot of work. Simplest example is String vs StringBuilder, most programmers know when to switch to the mutable version. Also one of the basic reasons, I think, why Roslyn was so late, meeting the perf goal set by the old C# compiler must have been an enormous battle.

Upvotes: 2

Alois Kraus
Alois Kraus

Reputation: 13535

David and Matt are correct. If you take care to profile the application you will find for the first sample

GC Generation GC Count
     0        3 
     1        17 
     2        2

and your second sample

GC Generation  GC Count
   0           28 
   1           0 
   2           0

With your first code you create a large linked list which still contains all objects which are never released until the application terminates. 

• Max GC Heap Size: 119,546 MB

whereas for your second sample you get

• Max GC Heap Size: 4,217 MB

Doing a 

var a = new Container();
loop
{
 a = new Container(a) 
}

will keep the data because a will contain a reference to the "old" a. Whereas 

b = new Container();
loop
{
   a = new Container(b) 
}

will assign onle one container which contains one further instance but not the complete history of previously allocated objects. The moral of the story is to closely look at where you root your objects. If you create a large linked list of nodes it is what you get.

Upvotes: 1

Matt Burland
Matt Burland

Reputation: 45135

This code (your second snippet):

var b = new A(null);
for (int i = 0; i < 10*1000*1000; i++)
    a = new A(b);

Would be functionally equivalent to this code:

 var b = new A(null);
 a = new A(b);

Your first snippet isn't the same:

var a = new A(null);

for (int i = 0; i < 10*1000*1000; i++)
    a = new A(a);

Although it looks like you are throwing away everything but the last reference you, are not. That last instance of A has a reference to the previous one, which has a reference to the one before that, which references the one before that...all the way back through 10,000,000 objects. No wonder it's slower.

So comparing two pieces of code that don't actually achieve the same result is kind of pointless. Use the one that actually works (your first snippet) and not the second one. Slower code that works is definitely better than faster code that doesn't.

Finally, C# has a perfectly good selection of collection classes (like List<T>) that work just fine. Not sure why you want to reinvent the wheel here.

Upvotes: 2

Alexandre Severino
Alexandre Severino

Reputation: 1613

When you run an application under .NET Framework, the memory is allocated on the Heap under the hood using the Managed Code features available on high level programming languages like C#/VB.Net and Java.

When you create an instance of a class by using the keyword new, the programming language tells the compiler that it wants to allocate memory on the heap (dynamic allocation). This allocation demands time because it has to pass OS requests restrictions and processes. When you request memory allocation via a High Level programming language, it will allocate a bigger block (a buffer) under the hood. Thus, future "instantiations" demand less time due to the fact that there is already available memory for the application on the heap.

Upvotes: 1

Gaurav
Gaurav

Reputation: 154

In the first case, you are creating a chain of 10,000,000 connected objects, where as in the second case you are creating 10,000,000 separate objects connected to a single instance of A. My guess is that the slow down is due to the framework having to perform heap management when allocating 10,000,000 connected objects, vs randomly allocating individual objects.

Upvotes: 0

rnofenko
rnofenko

Reputation: 9533

It looks like CLR optimization, because in second case variable a is unused.

Upvotes: 0

Related Questions