C# ile Array ve Dynamic Array: Contiguous Bellek, Index Erişimi ve Kendi List'ini Yazmak

Sürüm notu: Bu yazıdaki kodlar .NET 10 ve C# 14 ile derlenip xUnit v3 4.0.2 testleriyle doğrulanmıştır; ölçümler BenchmarkDotNet 0.15.8 ile alınmıştır.

Önce Tahmin Et

Bookstore'un depo yönetim ekranı 4.000 × 4.000'lik bir int[,] grid'de raf ve gün bazında stok tutuyor. Toplam stoğu iki şekilde hesaplayabilirsin: önce satırları, sonra sütunları gezerek ya da önce sütunları, sonra satırları gezerek. İkisi de tam olarak 16 milyon toplama yapıyor. Aradaki fark ne kadar: yüzde birkaç mı, iki kat mı, daha fazlası mı?

İkinci soru: boş bir List<int>'e tek tek 1.000.000 element ekliyorsun. List<T>, capacity'si dolduğunda element'leri daha büyük bir array'e kopyalıyor. Bu 1.000.000 Add boyunca toplam kaç element kopyalanır: 1 milyon civarı mı, 20 milyon mu, yarım trilyon mu?

Array Bellekte Nasıl Durur?

Array, aynı tipteki element'leri bellekte yan yana, tek bir blok hâlinde tutar. Bu "contiguous" olma hâli array'in bütün avantajlarının kaynağı: prices[i]'nin adresi, array'in başlangıç adresine i × element boyutu eklenerek bulunuyor. Element 10'a da 10 milyona da aynı tek hesapla gidiliyor; index ile erişim O(1).

Element'in ne olduğu belleği değiştiriyor. int[]'de her slot 4 byte ve değerin kendisi orada duruyor. Book[] ya da object[]'de ise her slot 64-bit bir process'te 8 byte'lık bir reference. Kitabın kendisi heap'in başka bir yerinde. Array'i gezmek reference'ları sırayla okumak demek; her reference'ın gösterdiği object'e gitmek ise belleğin rastgele bir yerine zıplamak. Value type ile reference type farkı C# Temelleri serisinin "C# Value Type ve Reference Type" yazısında, array'in kendisi ise "C# Array'ler: Tek ve Çok Boyutlu, Jagged, Index ve Range" yazısında anlatıldı.

Runtime, her erişimde index'in 0 ≤ i < Length aralığında olup olmadığını kontrol eder; bu, bounds check. Aralık dışındaki erişim belleği bozmak yerine IndexOutOfRangeException fırlatır. JIT (Just-In-Time) derleyici, döngünün sınırının array.Length olduğunu görünce bu kontrolü döngüden çıkarabiliyor. Ölçüm bölümünde bunun etkisini göreceğiz.

Ortaya Ekleme ve Silmenin Bedeli

Array'in sabit bir boyutu var. "Ortaya bir element eklemek" aslında sağdaki her element'i bir slot sağa kaydırıp açılan boşluğa yazmak demek; silmek de sağdakileri bir slot sola çekmek. 100.000 elemanlı bir fiyat listesinin başına ekleme yapmak 100.000 kopyalama. Sona eklemek ise kaydırma gerektirmiyor: bir sonraki boş slota yazıyorsun, o kadar.

Bu yüzden array tabanlı her yapıda maliyetler asimetrik: sona ekleme ve sondan silme ucuz, baştan ya da ortadan ekleme ve silme pahalı. Index ile erişim ucuz, değere göre arama (sıralı değilse) baştan sona tarama. List<T>'nin API'si (Application Programming Interface) C# Koleksiyonlar serisinin "C# List<T> Rehberi" yazısında; burada aynı mekanizmayı kendimiz kuruyoruz.

Kendi DynamicArray<T>'imiz

Dynamic array, sabit boyutlu bir array'i sarar ve dolduğunda daha büyük bir array'e taşınır. Dışarıya "sınırsız büyüyen bir liste" görüntüsü verir. Bizim versiyonumuz List<T>'nin temel davranışını taklit ediyor:

using System.Collections;

namespace Algorithms.Linear;

public sealed class DynamicArray<T> : IEnumerable<T>
{
    private const int DefaultCapacity = 4;
    private T[] _items = [];
    private int _count;
    private int _version;

    public int Count => _count;
    public int Capacity => _items.Length;

    public T this[int index]
    {
        get
        {
            // (uint) cast: negatif index çok büyük bir sayıya döner, tek karşılaştırma iki ucu da kapsar
            if ((uint)index >= (uint)_count) throw new ArgumentOutOfRangeException(nameof(index));
            return _items[index];
        }
        set
        {
            if ((uint)index >= (uint)_count) throw new ArgumentOutOfRangeException(nameof(index));
            _items[index] = value;
            _version++;
        }
    }

    public void Add(T item)
    {
        if (_count == _items.Length) Grow();
        _items[_count++] = item;
        _version++;
    }

    public void Insert(int index, T item)
    {
        if ((uint)index > (uint)_count) throw new ArgumentOutOfRangeException(nameof(index));
        if (_count == _items.Length) Grow();
        // [index, count) aralığını bir slot sağa kaydır: O(n - index)
        Array.Copy(_items, index, _items, index + 1, _count - index);
        _items[index] = item;
        _count++;
        _version++;
    }

    public void RemoveAt(int index)
    {
        if ((uint)index >= (uint)_count) throw new ArgumentOutOfRangeException(nameof(index));
        _count--;
        // (index, count] aralığını bir slot sola kaydır
        Array.Copy(_items, index + 1, _items, index, _count - index);
        // son slot hâlâ bir reference tutuyor; GC object'i toplayabilsin diye temizle
        _items[_count] = default!;
        _version++;
    }

    private void Grow()
    {
        int newCapacity = _items.Length == 0 ? DefaultCapacity : _items.Length * 2;
        T[] bigger = new T[newCapacity];
        Array.Copy(_items, bigger, _count);
        _items = bigger;
    }

    public IEnumerator<T> GetEnumerator()
    {
        int version = _version;
        for (int i = 0; i < _count; i++)
        {
            if (version != _version)
                throw new InvalidOperationException("Collection was modified during enumeration.");
            yield return _items[i];
        }
    }

    IEnumerator IEnumerable.GetEnumerator() => GetEnumerator();

    // test kancası: RemoveAt sonrası ham slot'a bakmak için
    internal T RawSlot(int index) => _items[index];
}

Birkaç ayrıntı tasarımın kendisi. Count ile Capacity ayrı: array'in uzunluğu ne kadar yer ayrıldığını, _count ne kadarının dolu olduğunu söyler. Indexer _count'a göre kontrol ediyor, _items.Length'e göre değil; aksi hâlde capacity'nin boş kısmındaki default değerler okunabilirdi. (uint)index >= (uint)_count hilesi BCL (Base Class Library) kaynak kodunda da kullanılıyor: negatif bir int, uint'e çevrilince 2³¹'den büyük olur; böylece hem index < 0 hem index >= count tek karşılaştırmayla yakalanıyor.

_version sayacı, foreach sırasında koleksiyon değişirse enumerator'ın bunu fark etmesini sağlıyor. List<T> de aynı şeyi yapıyor ve "Collection was modified" exception'ı buradan geliyor. IEnumerable<T>'i yield return ile implement etmenin nasıl çalıştığı C# Koleksiyonlar serisinin "C# Collection Interface'leri: IEnumerable, ICollection, IList ve yield return" yazısında.

Büyüme Neden ×2?

Davranışı testlerle sabitleyelim. İlk test 17 element ekliyor ve capacity'nin hangi değerlerden geçtiğini kaydediyor:

[Fact]
public void Add_BeyondCapacity_DoublesCapacity()
{
    DynamicArray<int> array = new();
    List<int> capacities = [];

    for (int i = 0; i < 17; i++)
    {
        array.Add(i);
        if (capacities.Count == 0 || capacities[^1] != array.Capacity)
            capacities.Add(array.Capacity);
    }

    Assert.Equal([4, 8, 16, 32], capacities);
    Assert.Equal(17, array.Count);
}

[Fact]
public void Add_Add_Add_CopiesTotalLessThanTwiceCount()
{
    // n kez Add için ×2 büyümenin yaptığı toplam element kopyalama sayısı
    int n = 1_000_000, capacity = 0, copies = 0;
    for (int count = 0; count < n; count++)
    {
        if (count == capacity)
        {
            copies += count;
            capacity = capacity == 0 ? 4 : capacity * 2;
        }
    }

    Assert.Equal(1_048_572, copies);
    Assert.True(copies < 2 * n);
}

$ dotnet test --project tests/Algorithms.Tests -- --filter-class Algorithms.Tests.DynamicArrayTests
Running tests from tests/Algorithms.Tests/bin/Debug/net10.0/Algorithms.Tests.dll (net10.0|arm64)
tests/Algorithms.Tests/bin/Debug/net10.0/Algorithms.Tests.dll (net10.0|arm64) passed (576ms)

Test run summary: Passed!
  total: 8
  failed: 0
  succeeded: 8
  skipped: 0
  duration: 698ms

İkinci sorunun cevabı burada: 1.000.000 Add boyunca toplam 1.048.572 element kopyalanıyor. Bu, n'nin iki katından az. Her resize o ana kadar eklenen her şeyi kopyalıyor ama resize'lar giderek seyrekleşiyor: 4, 8, 16, ... 524.288. Bu sayıların toplamı, son resize'daki boyutun iki katını geçemez. Element başına ortalama maliyet sabit; buna amortized O(1) deniyor. Neden ×2 gibi geometrik bir büyümenin şart olduğu, sabit "+10" büyümenin neden toplamda O(n²) kopyalamaya yol açtığı ve accounting method ile ispatı Big-O ve Complexity serisinin "Amortized Analysis: List<T>.Add Neden O(1) Sayılır" yazısında.

Bizim kodumuz BCL ile aynı kararı veriyor. dotnet/runtime'daki List.cs'te DefaultCapacity 4 ve büyüme formülü _items.Length == 0 ? DefaultCapacity : 2 * _items.Length; üst sınır Array.MaxLength.

Silinen Slot ve GC

RemoveAt'teki şu satır kolayca unutulur:

[Fact]
public void RemoveAt_LastSlot_IsClearedForGc()
{
    DynamicArray<Book> array = new();
    array.Add(new Book("9780000000001", "Dune", 10m));
    array.Add(new Book("9780000000002", "Emma", 12m));

    array.RemoveAt(0);

    Assert.Equal("Emma", array[0].Title);
    Assert.Null(array.RawSlot(1));
}

Kaydırmadan sonra son dolu slot, artık mantıksal olarak listede olmayan bir element'e hâlâ reference tutuyor: Emma'yı hem index 0 hem index 1 gösteriyor. Slot'u default'a çekmezsen, sonradan Emma'yı listeden de çıkarsan bile array o object'i canlı tutar ve GC (Garbage Collector) onu toplayamaz. Kitap küçük bir record olduğu için fark etmez; ama slot'ta 50 MB'lık bir rapor buffer'ı ya da bir HTTP (Hypertext Transfer Protocol) context'i duruyorsa, bu sessiz bir memory leak. List<T> bunu RuntimeHelpers.IsReferenceOrContainsReferences<T>() true ise yapıyor; int gibi reference içermeyen tiplerde temizlemeye gerek olmadığı için atlıyor.

2D Array'de Row-Major Traversal ve Cache

Açılıştaki ilk soruya dönelim. int[,], .NET'te row-major tutulur: önce satır 0'ın bütün sütunları, sonra satır 1'in bütün sütunları, hepsi tek bir blokta. Jagged array (int[][]) ise her satırı ayrı bir array olarak tutan bir array; satırlar heap'te ayrı bloklar. Dört varyantı ölçen benchmark:

[MemoryDiagnoser]
public class TraversalBenchmarks
{
    private int[,] _grid = null!;
    private int[][] _jagged = null!;

    [Params(1_000, 4_000)]
    public int N;

    [GlobalSetup]
    public void Setup()
    {
        _grid = new int[N, N];
        _jagged = new int[N][];
        for (int r = 0; r < N; r++)
        {
            _jagged[r] = new int[N];
            for (int c = 0; c < N; c++) _grid[r, c] = _jagged[r][c] = r ^ c;
        }
    }

    [Benchmark(Baseline = true)]
    public long RowMajor2D()
    {
        long sum = 0;
        for (int r = 0; r < N; r++)
            for (int c = 0; c < N; c++)
                sum += _grid[r, c];
        return sum;
    }

    [Benchmark]
    public long ColumnMajor2D()
    {
        long sum = 0;
        for (int c = 0; c < N; c++)
            for (int r = 0; r < N; r++)
                sum += _grid[r, c];
        return sum;
    }

    [Benchmark]
    public long RowMajorJagged()
    {
        long sum = 0;
        foreach (int[] row in _jagged)
            foreach (int value in row)
                sum += value;
        return sum;
    }

    [Benchmark]
    public long ColumnMajorJagged()
    {
        long sum = 0;
        for (int c = 0; c < N; c++)
            for (int r = 0; r < N; r++)
                sum += _jagged[r][c];
        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 10.0.13 (10.0.13, 10.0.1326.50504), Arm64 RyuJIT armv8.0-a

| Method            | N    | Mean        | Ratio | Allocated |
|------------------ |----- |------------:|------:|----------:|
| RowMajor2D        | 1000 |    524.5 us |  1.00 |         - |
| ColumnMajor2D     | 1000 |    602.4 us |  1.15 |         - |
| RowMajorJagged    | 1000 |    270.4 us |  0.52 |         - |
| ColumnMajorJagged | 1000 |    589.2 us |  1.12 |         - |
|                   |      |             |       |           |
| RowMajor2D        | 4000 |  8,255.8 us |  1.00 |         - |
| ColumnMajor2D     | 4000 | 25,449.4 us |  3.08 |         - |
| RowMajorJagged    | 4000 |  4,308.8 us |  0.52 |         - |
| ColumnMajorJagged | 4000 | 29,398.9 us |  3.56 |         - |

Aynı sayıda toplama, 4.000'lik grid'de üç kattan fazla fark. İşlemci bellekten tek tek int okumaz; 64 ya da 128 byte'lık cache line'lar hâlinde okur ve sıralı erişimi fark edip sonraki line'ları önceden getirir (prefetch). Satır satır gezerken bir cache line'daki 16 ya da 32 int'in hepsi kullanılıyor. Sütun sütun gezerken her adım 4.000 × 4 = 16.000 byte ileri zıplıyor; getirilen line'ın yalnızca bir int'i kullanılıyor ve line, aynı sütunun bir sonraki turuna kadar cache'ten atılmış oluyor. 1.000'lik grid'de (4 MB) fark yüzde 15'te kalıyor, çünkü verinin büyük kısmı hâlâ cache'e sığıyor; 4.000'lik grid'de (64 MB) sığmıyor ve fark açılıyor.

İkinci sürpriz: jagged array'i satır satır foreach ile gezmek, int[,]'yi gezmekten neredeyse iki kat hızlı. Çok boyutlu array'de her _grid[r, c] erişimi iki boyutun alt ve üst sınırını hesaba katan bir adres hesabı ve bounds check içeriyor. Tek boyutlu bir int[] üzerindeki foreach'te ise JIT, döngü sınırının array'in uzunluğu olduğunu bildiği için bounds check'i kaldırabiliyor. Ölçüm, makinede başka işler de çalışırken alındı; oranlar tutarlı, mutlak değerler senin makinende farklı olacaktır. Cache'in Big-O'nun göstermediği bu etkisi, Big-O ve Complexity serisinin "Big-O'nun Söylemedikleri" yazısının konusu.

Üretimde Dikkat

Kaç element geleceğini biliyorsan capacity'yi baştan ver. Veritabanından 50.000 satır okuyacağını biliyorsan new List<Order>(50_000) ya da EnsureCapacity on dört resize'ı ve 65.532 gereksiz kopyalamayı ortadan kaldırıyor. Daha önemlisi, ara array'ler GC'ye çöp olarak kalmıyor.

Büyük array'lerin ayrı bir hayatı var. 85.000 byte'tan büyük object'ler Large Object Heap'e (LOH) gidiyor; orada toplanmaları daha seyrek ve daha pahalı. Yaklaşık 21.200'den fazla elemanlı bir int[] ya da yaklaşık 10.600'den fazla reference tutan bir Book[] bu sınırı geçiyor. Büyüyüp küçülen büyük list'ler, her büyümede LOH'ta yeni ve daha büyük bir blok ayırıyor. Sık kullanılan büyük buffer'lar için ArrayPool<T> bu yüzden var.

Büyüme anı bir latency spike'ı. 1 milyon elemanlı bir list'in 2 milyonluk array'e taşındığı Add, diğerlerinden binlerce kat pahalı. Ortalama ucuz, ama düşük latency isteyen bir yolda (her çağrının 1 ms'nin altında kalması gereken bir handler) o tek çağrı fark edilir. Capacity'yi önceden ayırmak burada da çözüm.

Çok boyutlu veriyi gezme sırası, verinin bellekteki sırasıyla aynı olmalı. Raporlama kodunda grid'leri satır satır gez; sütun bazlı toplam gerekiyorsa her satırı gezerken sütun toplamlarını ayrı bir array'de biriktir.

Sık Düşülen Tuzaklar

İleri doğru for döngüsünde silmek. Stoku 0 olan kitapları silmek için yazılmış şu döngü bir element'i atlıyor:

[Fact]
public void ForwardLoopRemove_SkipsNeighbours()
{
    List<int> stock = [0, 0, 5, 0, 3];

    // hatalı: RemoveAt(i) sonrası bir sonraki element i'ye kayar ve atlanır
    for (int i = 0; i < stock.Count; i++)
        if (stock[i] == 0) stock.RemoveAt(i);

    Assert.Equal([0, 5, 3], stock);

    List<int> fixedStock = [0, 0, 5, 0, 3];
    for (int i = fixedStock.Count - 1; i >= 0; i--)
        if (fixedStock[i] == 0) fixedStock.RemoveAt(i);

    Assert.Equal([5, 3], fixedStock);
}

Index 0'daki sıfır silinince ikinci sıfır index 0'a kayıyor, döngü ise index 1'e geçiyor. Geriye doğru gezmek kayan element'leri zaten işlenmiş bölgeye taşıdığı için doğru çalışıyor. Daha da iyisi stock.RemoveAll(x => x == 0): her element'i en fazla bir kez kaydırıyor, yani O(n); döngü içinde tek tek RemoveAt ise en kötü durumda O(n²).

Silinen slot'ta reference bırakmak. Kendi array tabanlı yapını yazarken RemoveAt, Pop ya da Dequeue'da boşalan slot'u default'a çekmeyi unutmak, GC'nin object'i toplamasını engelliyor.

Gezerken değiştirmek. foreach içinde aynı list'e Add ya da Remove çağırmak InvalidOperationException ile biter; bu bir koruma, hata değil. Değiştirmen gerekiyorsa önce kopyasını gez ya da yeni bir list üret.

Capacity ile Count'u karıştırmak. new List<int>(100) 100 elemanlı bir list değil, 100 kişilik yer ayrılmış boş bir list; list[0] exception fırlatır.

Küçük Bir Deneme

★☆☆ DynamicArray<T>'e RemoveAll(Predicate<T> match) ekle: tek geçişte, okuma ve yazma index'leriyle, her element'i en fazla bir kez kopyalayarak. Ortadan 1.000 element silen bir benchmark ile döngüdeki RemoveAt'le karşılaştır.

★★☆ Grow'u ×2 yerine ×1,5 büyüyecek şekilde değiştir. Testteki kopyalama sayısı 1.000.000 Add için kaça çıkıyor? Bellekte boş kalan alan (capacity − count) en kötü durumda nasıl değişiyor?

★★★ Insert(0, x) ve RemoveAt(0)'ı da O(1) yapan bir yapı tasarla: array'in başında da boşluk bırak ve bir _start index'i tut. Bu fikrin bir sonraki yazılardan birindeki circular buffer'la ilişkisi ne?

Array'in gücü contiguous olması, zaafı da ortaya eklemenin bedeli. Bir sonraki yazıda tam tersini yapan yapıya bakıyoruz: element'leri bellekte dağınık tutan, araya eklemeyi O(1) yapan ama bunun bedelini her adımda bir cache miss ile ödeyen linked list.