C# Immutable Collection'lar ve Doğru Collection'ı Seçmek

Sürüm notu: Bu yazıdaki kodlar C# 10 ve .NET 6 API'leriyle yazılmıştır; .NET 10 SDK ile derlenip denenmiştir.

Önce Tahmin Et

Sepete bir kitap koyuyoruz, sonra iki kez Add çağırıyoruz. Program derlenir, uyarı da vermez. Ekrana hangi iki sayı yazılır?

using System.Collections.Immutable;

ImmutableList<string> cart = ImmutableList.Create("978-0132350884");
cart.Add("978-0135957059");
ImmutableList<string> updated = cart.Add("978-0321125217");

Console.WriteLine(cart.Count);
Console.WriteLine(updated.Count);

Read-only ile Immutable Aynı Şey Değil

Çıktı:

1
2

cart hâlâ tek kitaplık. ImmutableList<T>.Add listeyi değiştirmez; eklenmiş hâlini yeni bir liste olarak döndürür. İlk Add'in sonucunu hiçbir değişkene atamadığımız için o yeni liste doğduğu satırda çöpe gitti. İkinci çağrının sonucunu updated'e aldık, iki element'i olan o. Immutable bir collection'da değiştiriyormuş gibi görünen her method aslında "değişmiş kopyayı" verir ve dönüş değerini kullanmak senin işin.

Önceki yazıda AsReadOnly() ile read-only bir view vermiştik ve bunun bir pencere olduğunu söylemiştik. Farkı yan yana görmek için aynı listeden hem bir view hem de immutable bir kopya alıp sonra listeyi değiştirelim:

using System.Collections.Immutable;

var stock = new List<string> { "Clean Code" };
IReadOnlyList<string> view = stock.AsReadOnly();
ImmutableList<string> snapshot = stock.ToImmutableList();

stock.Add("Refactoring");

Console.WriteLine($"view: {view.Count}, snapshot: {snapshot.Count}");

view: 2, snapshot: 1

View değişikliği gördü, çünkü arkasındaki liste aynı. ToImmutableList() ise o anın fotoğrafını çekti; kaynak liste sonradan ne yaparsa yapsın snapshot bir element'li kalır. Read-only, "sen değiştiremezsin" demek. Immutable, "kimse değiştiremez" demek. İkinci garanti, elinde tuttuğun veri hakkında kafa yormadan akıl yürütebilmeni sağlar.

System.Collections.Immutable Ailesi

Bu tipler System.Collections.Immutable namespace'inde yaşar. .NET Core ve .NET 5+ projelerinde platformun parçasıdır; .NET Framework'te aynı adlı NuGet paketiyle gelir. Ailenin tanıdık isimleri var: ImmutableArray<T>, ImmutableList<T>, ImmutableDictionary<TKey, TValue>, ImmutableHashSet<T>, ImmutableSortedDictionary<TKey, TValue>, ImmutableSortedSet<T>, ImmutableQueue<T> ve ImmutableStack<T>. Her birinin yanında aynı adlı static bir yardımcı class var (ImmutableList.Create, ImmutableDictionary.CreateBuilder gibi) ve her collection'ı ToImmutableList(), ToImmutableDictionary() gibi extension method'larla dönüştürebilirsin.

Akla ilk gelen soru şu: her Add yeni bir collection döndürüyorsa, milyon element'li bir listeye tek kitap eklemek milyon element'i kopyalamak mı demek? ImmutableList<T> için cevap hayır. İçeride dengeli bir binary tree (AVL tree) tutar. Yeni element eklenirken yalnızca root'tan o noktaya giden yoldaki node'lar yeniden oluşturulur, geri kalan bütün node'lar eski ve yeni liste arasında paylaşılır. Buna structural sharing denir. ImmutableArray<T> ise düz bir array'i sarar ve her değişiklikte array'in tamamını kopyalar. Farkı ayrılan bellekle ölçtük:

using System.Collections.Immutable;
using System.Globalization;

CultureInfo.CurrentCulture = CultureInfo.InvariantCulture;

ImmutableList<int> list = ImmutableList.CreateRange(Enumerable.Range(0, 1_000_000));
ImmutableArray<int> array = ImmutableArray.CreateRange(Enumerable.Range(0, 1_000_000));

long before = GC.GetAllocatedBytesForCurrentThread();
ImmutableList<int> biggerList = list.Add(42);
long listBytes = GC.GetAllocatedBytesForCurrentThread() - before;

before = GC.GetAllocatedBytesForCurrentThread();
ImmutableArray<int> biggerArray = array.Add(42);
long arrayBytes = GC.GetAllocatedBytesForCurrentThread() - before;

Console.WriteLine($"ImmutableList.Add:  {listBytes:N0} bytes");
Console.WriteLine($"ImmutableArray.Add: {arrayBytes:N0} bytes");
Console.WriteLine($"{list.Count:N0} -> {biggerList.Count:N0}, {array.Length:N0} -> {biggerArray.Length:N0}");

ImmutableList.Add:  984 bytes
ImmutableArray.Add: 4,000,032 bytes
1,000,000 -> 1,000,001, 1,000,000 -> 1,000,001

Milyon element'li tree'ye ekleme 984 byte'lık birkaç node üretti. Array tarafında ise 4 byte'lık bir milyon int'in hepsi yeni bir array'e kopyalandı. İki tip de immutable ama değişikliğe bakışları tamamen farklı.

Builder ile Toplu Değişiklik

Bir collection'ı tek tek Add çağrılarıyla kurmak her adımda yeni bir sürüm üretir. Çok sayıda değişikliği bir arada yapacaksan builder kullan. Builder, collection'ın mutable bir taslağıdır; işin bitince ToImmutable() ile mühürlersin:

using System.Collections.Immutable;
using System.Globalization;

CultureInfo.CurrentCulture = CultureInfo.InvariantCulture;

ImmutableDictionary<string, decimal>.Builder builder = ImmutableDictionary.CreateBuilder<string, decimal>();
builder.Add("978-0132350884", 37.90m);
builder.Add("978-0135957059", 42.50m);
builder.Add("978-0321125217", 54.00m);
ImmutableDictionary<string, decimal> prices = builder.ToImmutable();

ImmutableDictionary<string, decimal> discounted = prices
    .SetItem("978-0132350884", 29.90m)
    .Remove("978-0321125217");

Console.WriteLine($"prices:     {prices.Count} books, Clean Code = {prices["978-0132350884"]}");
Console.WriteLine($"discounted: {discounted.Count} books, Clean Code = {discounted["978-0132350884"]}");

ImmutableArray<string>.Builder titles = ImmutableArray.CreateBuilder<string>(3);
titles.Add("Clean Code");
titles.Add("The Pragmatic Programmer");
titles.Add("Domain-Driven Design");
ImmutableArray<string> shelf = titles.MoveToImmutable();

Console.WriteLine($"shelf: {shelf.Length}, builder after move: {titles.Count}");

prices:     3 books, Clean Code = 37.90
discounted: 2 books, Clean Code = 29.90
shelf: 3, builder after move: 0

SetItem ve Remove da birer yeni dictionary döndürüyor ve zincir hâlinde yazılabiliyor; prices üç kitap ve eski fiyatla yerinde duruyor. ImmutableArray<T>'in builder'ında bir incelik daha var. Kapasiteyi baştan doğru verdiysen MoveToImmutable() iç array'i kopyalamadan devreder ve builder boşalır. Kapasite ile element sayısı tutmazsa exception atar; bu durumda ToImmutable() kopyalayarak çalışır.

ImmutableArray mı, ImmutableList mi

İkisi de index ile erişim sunar ama bedelleri farklıdır. ImmutableArray<T>'de indexer düz bir array erişimidir. ImmutableList<T>'de ise her list[i] tree'de root'tan leaf'e doğru bir yürüyüştür, yani O(log n). Microsoft'un dokümantasyonu da ImmutableList<T>'yi for ile index üzerinden dolaşmanın verimsiz olduğunu, foreach'in ise verimli olduğunu açıkça söyler. 10.000 int'i toplayan dört yolu BenchmarkDotNet 0.15.8 ile ölçtük:

using System.Collections.Immutable;
using BenchmarkDotNet.Attributes;
using BenchmarkDotNet.Running;

BenchmarkRunner.Run<IndexerBenchmarks>();

[InProcess]
[MemoryDiagnoser]
public class IndexerBenchmarks
{
    private List<int> _list = null!;
    private ImmutableArray<int> _immutableArray;
    private ImmutableList<int> _immutableList = null!;

    [GlobalSetup]
    public void Setup()
    {
        _list = Enumerable.Range(0, 10_000).ToList();
        _immutableArray = _list.ToImmutableArray();
        _immutableList = _list.ToImmutableList();
    }

    [Benchmark(Baseline = true)]
    public long ListFor()
    {
        long sum = 0;
        for (int i = 0; i < _list.Count; i++)
            sum += _list[i];
        return sum;
    }

    [Benchmark]
    public long ImmutableArrayFor()
    {
        long sum = 0;
        for (int i = 0; i < _immutableArray.Length; i++)
            sum += _immutableArray[i];
        return sum;
    }

    [Benchmark]
    public long ImmutableListFor()
    {
        long sum = 0;
        for (int i = 0; i < _immutableList.Count; i++)
            sum += _immutableList[i];
        return sum;
    }

    [Benchmark]
    public long ImmutableListForeach()
    {
        long sum = 0;
        foreach (int value in _immutableList)
            sum += value;
        return sum;
    }
}

BenchmarkDotNet v0.15.8, macOS 27.0.1 (26A434) [Darwin 27.0.0]
Apple M5, 1 CPU, 10 logical and 10 physical cores
.NET SDK 10.0.402
  [Host] : .NET 8.0.25 (8.0.25, 8.0.2526.11203), Arm64 RyuJIT armv8.0-a
| Method               | Mean       | Error     | StdDev    | Ratio | RatioSD | Allocated | Alloc Ratio |
|--------------------- |-----------:|----------:|----------:|------:|--------:|----------:|------------:|
| ListFor              |   3.142 us | 0.0416 us | 0.0348 us |  1.00 |    0.02 |         - |          NA |
| ImmutableArrayFor    |   3.080 us | 0.0334 us | 0.0312 us |  0.98 |    0.01 |         - |          NA |
| ImmutableListFor     | 103.048 us | 1.8564 us | 2.8902 us | 32.81 |    0.97 |         - |          NA |
| ImmutableListForeach |  32.852 us | 0.6134 us | 0.5437 us | 10.46 |    0.20 |         - |          NA |

Proje net6.0 hedefli ve Release modda derlendi; makinede .NET 6 runtime'ı olmadığı için DOTNET_ROLL_FORWARD=Major ile .NET 8.0.25 üzerinde, in-process çalıştı. BenchmarkDotNet paketi bağımlılık olarak System.Collections.Immutable 9.0.0'ı getirdiği için ölçülen immutable tipler o paketten geliyor. Mutlak sayılar makineden makineye değişir, oranlar ise hikâyeyi anlatır: ImmutableArray<T>'in indexer'ı List<T> ile aynı hızda (3,08 µs'ye karşı 3,14 µs). ImmutableList<T>'yi for ile dolaşmak yaklaşık 33 kat yavaş. foreach bu süreyi üçte birine indiriyor ama yine de List<T>'nin 10 katı. Dördü de hiç bellek ayırmadı.

Kural basit. Bir kez oluşturulup çok okunan, nadiren değişen veriler için ImmutableArray<T> seç. Sık sık element eklenip çıkarılan ve her sürümün saklandığı veriler için ImmutableList<T> seç, onu da foreach ile dolaş.

ImmutableArray<T> bir struct olduğu için bir tuzağı da beraberinde getirir. Hiç atanmamış hâli boş bir array değil, içinde array olmayan bir wrapper'dır:

using System.Collections.Immutable;

var shelf = new Shelf();
Console.WriteLine(shelf.Titles.IsDefault);

try
{
    Console.WriteLine(shelf.Titles.Length);
}
catch (NullReferenceException)
{
    Console.WriteLine("NullReferenceException");
}

class Shelf
{
    public ImmutableArray<string> Titles { get; set; }
}

True
NullReferenceException

Titles property'si struct olduğu için nullable uyarısı da çıkmadı. Bu tür field ve property'leri ImmutableArray<string>.Empty ile başlat, dışarıdan gelen değerler için IsDefault ya da IsDefaultOrEmpty kontrolü yap.

Immutability Ne Zaman İşe Yarar

Immutable collection'ların en güçlü olduğu yer paylaşılan veri. Bir fiyat listesini düşün: bir yerde güncelleniyor, birçok yerde okunuyor. Mutable bir dictionary'de okuyan tarafın dolaşırken listenin değişmesinden korunması gerekir. Immutable bir dictionary'de okuyan, eline aldığı sürümü istediği kadar dolaşır; güncelleme yeni bir sürüm üretir ve referansı değiştirir:

using System.Collections.Immutable;
using System.Globalization;

CultureInfo.CurrentCulture = CultureInfo.InvariantCulture;

var priceList = new PriceList();
priceList.Update("978-0132350884", 37.90m);

ImmutableDictionary<string, decimal> report = priceList.Current;
priceList.Update("978-0132350884", 29.90m);
priceList.Update("978-0135957059", 42.50m);

foreach (KeyValuePair<string, decimal> entry in report)
    Console.WriteLine($"report:  {entry.Key} = {entry.Value}");

Console.WriteLine($"current: {priceList.Current.Count} books, Clean Code = {priceList.Current["978-0132350884"]}");

class PriceList
{
    private ImmutableDictionary<string, decimal> _prices = ImmutableDictionary<string, decimal>.Empty;

    public ImmutableDictionary<string, decimal> Current => _prices;

    public void Update(string isbn, decimal price) =>
        ImmutableInterlocked.AddOrUpdate(ref _prices, isbn, price, (_, _) => price);
}

report:  978-0132350884 = 37.90
current: 2 books, Clean Code = 29.90

report, rapor hazırlanırken alınan sürüm. Sonraki iki güncelleme onu etkilemedi; rapor tutarlı bir anın görüntüsünü basıyor. ImmutableInterlocked.AddOrUpdate, "yeni sürümü hazırla ve referansı atomik olarak değiştir" işini thread-safe şekilde yapar: araya başka bir güncelleme girerse işlemi yeni sürüm üzerinde tekrar dener. Okuyanlar için lock gerekmez. Concurrent collection'ları ve thread-safety'yi asenkron programlama serisinde ayrıca ele alacağız.

Diğer güçlü kullanım alanları da aynı fikrin uzantısı: geri alınabilir işlemler için sürüm geçmişi tutmak (her sürüm ucuzca saklanır), bir method'a "bunu değiştiremezsin, değiştirmeyeceğim de" sözüyle veri vermek, uygulama açılışında okunan ve sonra hiç değişmeyen ayarlar. Bedeli de ortada: mutable karşılıklarına göre yazmaları ve çoğu okuması daha yavaştır. Tek bir method'un içinde doğup ölen bir ara liste için immutable kullanmanın hiçbir faydası yok.

Karmaşıklık Haritası

Doğru collection'ı seçerken ilk bakacağın şey, en sık yapacağın işlemin maliyeti. Bu seride gördüğümüz tiplerin temel işlemlerini bir arada topladım. O(1) "element sayısından bağımsız", O(log n) "her iki katına çıkışta bir adım daha", O(n) "element sayısıyla doğru orantılı" demek:

Type                                Index     Lookup       Add              Insert / Remove
List<T>                             O(1)      O(n)         O(1) amortized   O(n)
LinkedList<T>                       -         O(n)         O(1) first/last  O(1) with a node
Dictionary<TKey, TValue>            -         O(1) by key  O(1) amortized   O(1) by key
HashSet<T>                          -         O(1)         O(1) amortized   O(1)
SortedDictionary<TKey, TValue>      -         O(log n)     O(log n)         O(log n)
SortedList<TKey, TValue>            O(1)      O(log n)     O(n)             O(n)
SortedSet<T>                        -         O(log n)     O(log n)         O(log n)
Queue<T> / Stack<T>                 -         O(n)         O(1) amortized   -
PriorityQueue<TElement, TPriority>  -         -            O(log n)         O(log n) dequeue
ImmutableArray<T>                   O(1)      O(n)         O(n) copy        O(n) copy
ImmutableList<T>                    O(log n)  O(n)         O(log n)         O(log n)
ImmutableHashSet<T>                 -         O(log n)     O(log n)         O(log n)
ImmutableDictionary<TKey, TValue>   -         O(log n)     O(log n)         O(log n)

"amortized" yazan satırlar çoğu zaman O(1)'dir; iç array dolduğunda bir kez büyütülür ve o an O(n) olur. Başlangıçta kapasite vererek bu büyütmeleri azaltabilirsin. Immutable tarafta Microsoft'un dokümantasyonundaki tablo da aynı tabloyu çizer: Dictionary, HashSet ve List'in O(1) işlemleri immutable karşılıklarında O(log n) olur. Bu tablo bir başlangıç noktası; büyük O sabit çarpanları göstermez. 20 element'lik bir listede Contains çağırmak, dictionary kurmaktan genellikle daha ucuzdur.

Doğru Collection'ı Seçmek

Seçimi birkaç soruya indirebilirsin. Element'lere bir key ile mi ulaşıyorsun? Dictionary<TKey, TValue>. Key'ler sıralı mı dolaşılmalı? SortedDictionary<TKey, TValue>; veri bir kez yüklenip çok okunuyorsa SortedList<TKey, TValue> daha az bellek kullanır. Sadece "bu var mı" sorusunu mu soruyorsun ve tekrar istemiyor musun? HashSet<T>. Sıra ve index önemliyse List<T>; çoğu durumda doğru varsayılan budur.

İşlem sırası önemliyse soruyu değiştir. İlk gelen ilk mi çıkıyor? Queue<T>. Son gelen ilk mi? Stack<T>. Önceliği yüksek olan mı? PriorityQueue<TElement, TPriority>. Listenin ortasına sık sık ekleme yapıp elinde zaten bir node referansı tutuyorsan LinkedList<T> düşünülebilir; ama bellekte dağınık durduğu için pratikte çoğu zaman List<T>'den yavaştır, önce ölç.

Son soru, verinin sahipliği. Veri birden fazla yerde paylaşılıyor ve kimse değiştirmemeli mi? Immutable tipler. Birden fazla thread aynı anda yazıyor mu? System.Collections.Concurrent. Sadece dışarıya "dokunma" demek mi istiyorsun? IReadOnlyList<T> ve AsReadOnly() yeterli. C# 12/.NET 8 ile gelen, bir kez kurulup çok okunan Frozen collection'ları ise serinin sürüm yazısında göreceğiz.

Sık Düşülen Tuzaklar

Dönüş değerini atmak. Tahmin sorusundaki hata gerçek projelerde de sık görülür: prices.SetItem(isbn, price); yazıp sonucu atamamak hiçbir şey yapmaz. Değişkene geri ata: prices = prices.SetItem(isbn, price);.

ImmutableList<T>'yi for ile dolaşmak. Her index erişimi O(log n) olduğu için döngü O(n log n)'e çıkar. foreach kullan ya da okuma ağırlıklı veride ImmutableArray<T>'e geç.

Döngü içinde tek tek Add ile immutable collection kurmak. Her adım yeni bir sürüm üretir; ImmutableArray<T>'te bu her adımda tam kopya demek. Builder ya da ToImmutableArray() kullan.

Varsayılan ImmutableArray<T>. Atanmamış bir field ya da property ilk erişimde NullReferenceException fırlatır. Empty ile başlat.

Immutable collection'ın içindekileri de immutable sanmak. ImmutableList<Book> listenin kendisini dondurur; Book mutable property'lere sahip bir class ise kitapların içi hâlâ değişebilir. Tam bir immutability için element'ler de immutable olmalı; record'lar ve init property'ler burada işini kolaylaştırır.

Küçük Bir Deneme

★☆☆ ImmutableStack<string> ile bir "son görüntülenen kitaplar" geçmişi kur. Üç Push yap, her ara sürümü ayrı bir değişkende tut ve en eski sürümün hâlâ tek element'li olduğunu gör.

★★☆ Ölçüm programını ImmutableList<int>.Insert(0, 42) ve ImmutableArray<int>.Insert(0, 42) için tekrarla. Başa eklemek iki tipte ne kadar bellek ayırıyor?

★★★ PriceList'i Dictionary<string, decimal> ve lock ile yeniden yaz; okuyan tarafa tutarlı bir kopya vermek için neler yapman gerektiğini immutable sürümle karşılaştır.

Collection'ları seçmeyi bitirdik ama bir soru açıkta kaldı: IEnumerable<EBook>'yi IEnumerable<Book> isteyen bir method'a verebiliyorken, neden List<EBook>'yi List<Book> isteyen bir yere veremiyoruz? Bir sonraki yazıda generic variance'a, yani covariance ve contravariance'a ve in/out keyword'lerine bakıyoruz.