Shulou(Shulou.com)06/02 Report--

This article mainly explains "how to understand the expansion mechanism of List". The content of the explanation is simple and clear, and it is easy to learn and understand. Please follow the editor's train of thought to study and learn "how to understand the expansion mechanism of List".

One: background

1. Tell a story

In the previous large memory review, we saw that Dictionary was doing a capacity expansion operation. At that time, the count=251w of this dictionary, when you played with 66 of the dictionary, was actually carried by the bottom layer for you, such as the expansion mechanism. When you encounter millions or even tens of millions of large sets, this expansion mechanism really needs to be dug to avoid entering the play too deep and difficult to extricate yourself.

In order to make it easier to tell, I'm going to start with List, because it's the simplest.

Second: List expansion mechanism

1. How to view

To see its expansion mechanism, you can use ILSpy to look at the source code of List, which is very simple.

From the int num = (_ items.Length = = 0)? 4: (_ items.Length * 2) of the source code, you can see very clearly that 4 spaces start, followed by the expansion of * 2, that is to say, when you have 2 ^ (nmur1) + 1 elements, you actually need to occupy 2 ^ n spaces.

Let me demonstrate it in C # code:

Static void Main (string [] args)

{

Var list1 = Enumerable.Range (0, (int) Math.Pow (2,22). ToList ()

Var list2 = new List (list1)

List2.Add (1)

Console.WriteLine ($"list1.Capacity= {list1.Capacity}")

Console.WriteLine ($"list2.Capacity= {list2.Capacity}")

Console.ReadLine ()

}

-output-

List1.Capacity=4194304

List2.Capacity=8388608

As you can see from the code, when there are 4194304 elements in List, insert one element into it, only one more, but double the space at the bottom, oh, it's too exasperating, if you want to look deeper, you can take a look at the size of their respective arrays with windbg.

0 000 >! DumpObj / d 000001ec037d2e20

Name: system. Collections. Generic.List`1 [[System.Int32, mscorlib]]

Fields:

MT Field Offset Type VT Attr Value Name

00007ffde2ac8538 400189e 8 System.Int32 [] 0 instance 000001ec147b9c10 _ items

00007ffde2ac85a0 400189f 18 System.Int32 1 instance 4194304 _ size

00007ffde2ac85a0 40018a0 1c System.Int32 1 instance 4194304 _ version

00007ffde2ac5dd8 40018a1 10 System.Object 0 instance 0000000000000000 _ syncRoot

00007ffde2ac8538 40018a2 0 System.Int32 [] 0 shared static _ emptyArray

> > Domain:Value dynamic statics NYI 000001ec01bc0920:NotInit! do 000001ec147b9c10

Name: System.Int32 []

MethodTable: 00007ffde2ac8538

EEClass: 00007ffde2c35918

Size: 16777240 (0x1000018) bytes

Array: Rank 1, Number of elements 4194304, Type Int32 (Print Array)

Fields:

None0:000 >! do 000001ec037d2e78

Name: system. Collections. Generic.List`1 [[System.Int32, mscorlib]]

MethodTable: 00007ffde2ada068

EEClass: 00007ffde2c3b008

Size: 40 (0x28) bytes

File: C:\ WINDOWS\ Microsoft.Net\ assembly\ GAC_64\ mscorlib\ v4.0_4.0.0.0__b77a5c561934e089\ mscorlib.dll

Fields:

MT Field Offset Type VT Attr Value Name

00007ffde2ac8538 400189e 8 System.Int32 [] 0 instance 000001ec167b9c80 _ items

00007ffde2ac85a0 400189f 18 System.Int32 1 instance 4194305 _ size

00007ffde2ac85a0 40018a0 1c System.Int32 1 instance 1 _ version

00007ffde2ac5dd8 40018a1 10 System.Object 0 instance 0000000000000000 _ syncRoot

00007ffde2ac8538 40018a2 0 System.Int32 [] 0 shared static _ emptyArray

> > Domain:Value dynamic statics NYI 000001ec01bc0920:NotInit! do 000001ec167b9c80

Name: System.Int32 []

MethodTable: 00007ffde2ac8538

EEClass: 00007ffde2c35918

Size: 33554456 (0x2000018) bytes

Array: Rank 1, Number of elements 8388608, Type Int32 (Print Array)

Fields:

None

You can clearly see that one int [] takes up 16777240 byte/1024/1024 = 16m, and one int [] takes up 33554456 byte/1024/1024 = 32m, but this is double the space.

two。 Do you really think it's only doubled?

Why would I say that? Take a closer look at the Set implementation of Capacity, as follows:

Public int Capacity

{

Get {return _ items.Length;}

Set

{

If (value > 0)

{

T [] array = new T [value]

If (_ size > 0)

{

Array.Copy (_ items, 0, array, 0, _ size)

}

_ items = array

}

}

}

We read carefully, this process is to first define the new size array array, and then the old array (_ items) copy to the new array array, and then the reference of array to the old array, it is not difficult to see that the real Size should be array (32m) + _ items (16m) = 48m is the real size, as long as the GC does not recycle the old _ items (16m), then always maintain the 48m size, don't you think?

How do you verify it? You can use windbg to see the int [] in the managed heap.

Var list1 = Enumerable.Range (0, (int) Math.Pow (2,22). ToList ()

List1.Add (1)

0VR 000 >! DumpHeap-mt 00007ffde2ac8538-min 102400

Address MT Size

0000024c103e9ba0 00007ffde2ac8538 4194328

0000024c107e9bd8 00007ffde2ac8538 8388632

0000024c10fe9c10 00007ffde2ac8538 16777240

0000024c11fe9c48 00007ffde2ac8538 33554456

Statistics:

MT Count TotalSize Class Name

00007ffde2ac8538 4 62914656 System.Int32 []

Total 4 objects

From the information, (16777240 + 33554456) byte = 48m, according to the theory just now, the 16777240 int [] should be waiting for the GC to be recycled without referencing the root, so use! gcroot to print out both int [].

0VOU 000 >! gcroot 0000024c10fe9c10

Found 0 unique roots (run'! GCRoot-all' to see all roots).

0VOU 000 >! gcroot 0000024c11fe9c48

Thread 63dc:

0000007b4abfee60 00007ffd85950938 ConsoleApp6.Program.Main (System.String []) [C:\ dream\ Csharp\ ConsoleApp1\ ConsoleApp6\ Program.cs @ 28]

Rbp-38: 0000007b4abfee88

-> 0000024c00002da0 system. Collections. Generic.List`1 [[System.Int32, mscorlib]]

-> 0000024c11fe9c48 System.Int32 []

Found 1 unique roots (run'! GCRoot-all' to see all roots).

You can see: 0000024c10fe9c10 really has no reference root, which verifies that the real root is 48m, not 32m, which has doubled. It's a little scary.

Second: how to compress

1. Compression mechanism provided by the system

Looking back at the expansion mechanism in the Capacity attribute, you just need to flush the Capacity setting with Count, and the excess virtual space of the _ items array is cleared.

Static void Main (string [] args)

{

Var list1 = Enumerable.Range (0, (int) Math.Pow (2,22). ToList ()

List1.Add (1)

List1.Capacity = list1.Count

Console.ReadLine ()

}

As you can see from the figure, 8388608-4194305 = 4194303 int in the array is directly wiped out, optimizing the space.

two。 Custom List

In fact, the root of the problem lies in the capacity expansion mechanism. For example, if the length is greater than 400w, it doubles to 800w by default, and sometimes according to your business, 500w is enough, so 300w can be avoided, so you can implement a list if necessary, and then flexibly control its expansion mechanism.

Thank you for your reading, the above is the content of "how to understand the expansion mechanism of List". After the study of this article, I believe you have a deeper understanding of how to understand the expansion mechanism of List, and the specific use needs to be verified in practice. Here is, the editor will push for you more related knowledge points of the article, welcome to follow!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.