List<T>
là một trong những kiểu collection linh hoạt nhất trong .NET. Vì nó được thiết kế cho mục đích sử dụng chung, nó không được tối ưu hóa cho bất kỳ trường hợp sử dụng cụ thể nào. Nếu chúng ta nhìn kỹ hơn, chúng ta sẽ tìm thấy những tình huống mà nó còn hạn chế. Một trong những tình huống đó là khi bạn có rất nhiều dữ liệu. Bài viết này sẽ xem xét chính xác điều này.
Vấn đề
Trong điều kiện bình thường, List<T>
cực kỳ nhanh và gần như không có lý do gì để chuyển sang một kiểu collection khác. Nhưng nếu chúng ta thêm đủ nhiều phần tử vào List<T>
, chúng ta có thể làm giảm hiệu năng của ứng dụng. Điều này là do List<T>
được triển khai như một mảng – một mảng duy nhất.
Do chúng ta chỉ có một mảng phát triển theo thời gian, chúng ta có thể chạm đến một giới hạn kỳ diệu là 85kb và đối tượng của chúng ta sẽ rơi vào Large Object Heap (LOH). Để biết chi tiết, hãy xem hai liên kết mà tôi đã cung cấp. Phiên bản ngắn gọn là LOH không được nén và do đó có thể dẫn đến phân mảnh. Điều này có thể dẫn đến các vấn đề về hiệu năng.
Giải pháp
Chúng ta không phải tìm xa để tìm một giải pháp khả thi. Bản thân .NET Framework có các kiểu sử dụng chunking (phân đoạn) để giữ cho các đối tượng khá nhỏ. Hãy xem xét StringBuilder
. Nó có kích thước chunk là 8000 ký tự. Một khi bạn đạt đến 8000 ký tự, một mảng mới sẽ được tạo ra và sẽ được “gắn” vào mảng cũ, kiểu như một danh sách liên kết. Bằng cách này, chúng ta có thể tránh LOH và giữ cho các đối tượng của chúng ta nhỏ. Vậy hãy triển khai điều này cho List<T>
của chúng ta.
Code:
public class ChunkedList<T>
{
private const int ChunkSize = 8000;
private T[][] _chunks;
public ChunkedList()
{
_chunks = new T[1][];
_chunks[0] = new T[ChunkSize];
Count = 0;
}
public T this[int index]
{
get
{
ArgumentOutOfRangeException.ThrowIfNegative(index);
ArgumentOutOfRangeException.ThrowIfGreaterThanOrEqual(index, Count);
var chunkIndex = index / ChunkSize;
var innerIndex = index % ChunkSize;
return _chunks[chunkIndex][innerIndex];
}
set
{
ArgumentOutOfRangeException.ThrowIfNegative(index);
ArgumentOutOfRangeException.ThrowIfGreaterThanOrEqual(index, Count);
var chunkIndex = index / ChunkSize;
var innerIndex = index % ChunkSize;
_chunks[chunkIndex][innerIndex] = value;
}
}
public void Add(T item)
{
if (Count == _chunks.Length * ChunkSize)
{
// Create a new larger set of chunks
var newChunks = new T[_chunks.Length + 1][];
Array.Copy(_chunks, newChunks, _chunks.Length);
newChunks[_chunks.Length] = new T[ChunkSize];
_chunks = newChunks;
}
var addToChunk = Count / ChunkSize;
var addToIndex = Count % ChunkSize;
_chunks[addToChunk][addToIndex] = item;
Count++;
}
public int Count { get; private set; }
public void Clear()
{
Count = 0;
}
}
Đây là một triển khai rất cơ bản – thậm chí nó còn chưa implements bất kỳ interface nào! Nhưng điểm chính là chúng ta đang sử dụng một mảng jagged (mảng răng cưa) có tối đa 8000 phần tử.
Bây giờ khoan, giả sử chúng ta có một ChunkedList<int>
thì một mảng bên trong mảng jagged đó tối đa là 8000 phần tử * 4 byte (sizeof(int)
) = 32kb – vậy nếu chúng ta có 3 mảng như vậy thì chẳng phải chúng ta đã vượt quá 85kb rồi sao? Về mặt kỹ thuật thì đúng vậy, nhưng mảng jagged khác với mảng đa chiều (int[,]
). Một mảng jagged về cơ bản là nhiều mảng với nhiều địa chỉ khác nhau trên heap.
Benchmark
[MemoryDiagnoser]
public class ListBenchmarks
{
[Params(1000, 20_0000)] public int Items { get; set; }
[Benchmark(Baseline = true)]
public List<int> List()
{
var list = new List<int>();
for (var i = 0; i < Items; i++)
{
list.Add(i);
}
return list;
}
[Benchmark]
public ChunkedList<int> ChunkedList()
{
var list = new ChunkedList<int>();
for (var i = 0; i < Items; i++)
{
list.Add(i);
}
return list;
}
}
Kết quả:
Method | Items | Mean | Error | StdDev | Ratio | RatioSD | Gen0 | Gen1 | Gen2 | Allocated | Alloc Ratio |
---|---|---|---|---|---|---|---|---|---|---|---|
List | 1000 | 1.075 us | 0.0156 us | 0.0146 us | 1.00 | 0.00 | 1.0052 | 0.0019 | – | 8.23 KB | 1.00 |
ChunkedList | 1000 | 2.177 us | 0.0425 us | 0.0418 us | 2.02 | 0.05 | 3.8300 | – | – | 31.34 KB | 3.81 |
List | 200000 | 375.556 us | 6.2286 us | 5.8263 us | 1.00 | 0.00 | 1398.4375 | 1398.4375 | 399.9023 | 2048.67 KB | 1.00 |
ChunkedList | 200000 | 281.725 us | 2.2616 us | 2.1155 us | 0.75 | 0.01 | 95.7031 | 41.9922 | – | 784.99 KB | 0.38 |
Điều này là do ChunkedList<T>
có một số chi phí phụ trội (overhead) mà chỉ đáng giá cho các collection lớn hơn. Và đây là điều chúng ta có thể thấy trong benchmark thứ hai. ChunkedList<T>
nhanh hơn List<T>
và cũng sử dụng ít bộ nhớ hơn. Và quan trọng nhất – không có thứ gì trên LOH. Hãy nhớ rằng ChunkedList<T>
hoàn toàn chưa được tối ưu hóa – vì vậy nếu bạn muốn, bạn có thể tăng thêm hiệu năng.
Việc lặp qua ChunkedList
tất nhiên gắn liền với một số chi phí phụ trội phải tính toán vị trí chính xác của mục nhập. Nếu chúng ta chạy một benchmark kiểm tra điều đó, nó sẽ trở nên rõ ràng hơn:
public class ForBenchmark
{
private readonly List<int> _list = new List<int>();
private readonly ChunkedList<int> _chunkedList = new ChunkedList<int>();
[GlobalSetup]
public void Setup()
{
_list.AddRange(Enumerable.Range(0, 20_000));
foreach (var item in _list)
{
_chunkedList.Add(item);
}
}
[Benchmark(Baseline = true)]
public int ForList()
{
var sum = 0;
for (var i = 0; i < _list.Count; i++)
{
sum += _list[i];
}
return sum;
}
[Benchmark]
public int ForChunkedList()
{
var sum = 0;
for (var i = 0; i < _chunkedList.Count; i++)
{
sum += _chunkedList[i];
}
return sum;
}
}
Kết quả
Method | Mean | Error | StdDev | Ratio | RatioSD |
---|---|---|---|---|---|
ForList | 9.517 us | 0.0878 us | 0.0778 us | 1.00 | 0.00 |
ForChunkedList | 22.239 us | 0.2017 us | 0.1887 us | 2.34 | 0.02 |
Kết
Nếu bạn có một lượng lớn dữ liệu mà bạn muốn lưu trữ trong một List<T>
, hãy lưu ý một số tác động mà sự tăng trưởng liên tục của list có thể gây ra. Nếu bạn muốn tránh điều này, bạn có thể giải quyết bằng cách triển khai riêng của mình để biết cách xử lý mọi thứ. Những đối tượng này còn được gọi là Frugal object. Một Frugal object thường phục vụ tốt mục đích của nó mà không cần thay thế thường xuyên hoặc gây ra chi phí bổ sung. Code base của bạn càng lớn thì càng có khả năng bạn phải triển khai các giải pháp tùy chỉnh của riêng mình.
Tìm Hiểu thêm về BenchmarkDotNet: link
High-performance in C#
: link