Collection Performance

Semua koleksi yang kita bahas bisa menyimpan sekumpulan data, tetapi biaya operasinya berbeda. Bab Kompleksitas Operasi Koleksi pada section Koleksi Dasar memperkenalkan notasi Big-O untuk koleksi inti; bab ini memperluas tabelnya dengan keluarga immutable, frozen, dan concurrent, lalu menutup dengan satu penghematan yang bisa kita terapkan tanpa benchmark library apa pun: pralokasi capacity pada List<T>.

Tabel Big-O Antar Keluarga Koleksi #

Tanda “—” berarti operasi tidak tersedia karena koleksinya tidak bisa diubah:

Dua pola yang layak dicatat: pertama, ImmutableArray<T> membaca secepat array biasa tetapi membayar salinan penuh setiap kali berubah; kedua, FrozenDictionary menawarkan kompleksitas yang sama dengan Dictionary biasa, dengan konstanta yang lebih kecil untuk pembacaan karena struktur internalnya sudah final.

Pralokasi Capacity pada List #

List<T> menyimpan data dalam array internal. Ketika array penuh, runtime menyalin seluruh isi ke array dua kali lebih besar. Perilaku ini bisa diamati lewat property Capacity:

List<int> tanpaAlokasi = new List<int>();
int kapasitasSebelumnya = 0;

for (int i = 1; i <= 20; i++)
{
    tanpaAlokasi.Add(i);
    if (tanpaAlokasi.Capacity != kapasitasSebelumnya)
    {
        Console.WriteLine($"Count={tanpaAlokasi.Count}, Capacity={tanpaAlokasi.Capacity}");
        kapasitasSebelumnya = tanpaAlokasi.Capacity;
    }
}

List<int> teralokasi = new List<int>(20);
for (int i = 1; i <= 20; i++)
{
    teralokasi.Add(i);
}
Console.WriteLine($"Dengan constructor kapasitas: Count={teralokasi.Count}, Capacity={teralokasi.Capacity}");

Output yang Dihasilkan:

Count=1, Capacity=4
Count=5, Capacity=8
Count=9, Capacity=16
Count=17, Capacity=32
Dengan constructor kapasitas: Count=20, Capacity=20

Mari kita bedah hasilnya:

1. Count=1, Capacity=4: array internal pertama dialokasikan untuk empat slot begitu item pertama masuk.
2. Count=5, Capacity=8 dan seterusnya: setiap kali Count melewati Capacity, runtime menyalin isi ke array berkapasitas dua kali lipat; lima belas item terakhir masuk tanpa penyalinan tambahan.
3. new List<int>(20): constructor menerima kapasitas awal, sehingga seluruh dua puluh item masuk tanpa satu penyalinan pun; Capacity tetap 20 sampai akhir.

Untuk pengukuran yang lebih detail, section LINQ membahas biaya enumerasi berulang, dan topik profiling dibahas pada bagian performa aplikasi.