Space Complexity: Ek Bellek, Recursion Stack'i ve Allocation

Sürüm notu: Bu yazıdaki kodlar .NET 10 (C# 14) ile derlenip denenmiştir; ölçümler BenchmarkDotNet 0.15.8, testler xUnit v3 4.0.2 ile, container denemesi mcr.microsoft.com/dotnet/runtime:10.0 image'ı ile yapılmıştır.

Önce Tahmin Et

Bookstore'un sipariş servisi her gün 1 GB'lık bir log dosyası üretiyor: yaklaşık 10,3 milyon satır. Destek ekibi belirli bir müşterinin siparişlerini bulmak için küçük bir araç istiyor. İki geliştirici iki farklı versiyon yazıyor; tek farkları dosyayı nasıl okudukları:

// Versiyon A
var all = File.ReadAllLines(path);
foreach (var line in all) { /* ... */ }

// Versiyon B
foreach (var line in File.ReadLines(path)) { /* ... */ }

İkisinin de time complexity'si O(n). Peki bellek? Araç 512 MB memory limit'i olan bir container'da çalışacak. Hangisi bu limitin içinde kalır, hangisi kalmaz? Kalmayan ne yapar: exception mı fırlatır, container mı öldürülür, yoksa başka bir şey mi olur? Yazının ortasında ikisini de aynı dosyayla, gerçekten 512 MB'lık bir container'da çalıştıracağız.

Total ve Auxiliary Space

Space complexity, bir algoritmanın kullandığı belleğin n ile nasıl büyüdüğünü anlatır. Burada iki ayrı ölçü var ve karıştırılmaları çok yaygın. Total space girdinin kendisi dahil bütün belleği sayar. Auxiliary space ise yalnızca algoritmanın girdiye ek olarak ayırdığı belleği. Bir array'i yerinde ters çeviren method'un total space'i O(n) (array'in kendisi), auxiliary space'i O(1) (iki index ve bir geçici değişken). Gündelik konuşmada "bu algoritma O(1) bellek kullanır" denirken kastedilen auxiliary space.

Ek belleği O(1) olan algoritmalara in-place denir. Insertion sort ve heap sort in-place'tir. Klasik merge sort değildir, çünkü merge sırasında n boyutunda bir buffer ister; önceki yazıdaki MergeSort'un buffer parametresi tam olarak bu ek O(n).

Basit bir karşılaştırma ile başlayalım. Fibonacci'yi iki farklı şekilde hesaplıyoruz. Memoization, daha önce hesaplanmış değerleri bir dictionary'de tutar; iterative versiyon yalnızca son iki değeri:

// Time O(n), space O(n): tekrar hesaplamamak için bellek harcar
public static long MemoFibonacci(int n, Dictionary<int, long> memo)
{
    if (n < 2) return n;
    if (memo.TryGetValue(n, out var cached)) return cached;
    var value = MemoFibonacci(n - 1, memo) + MemoFibonacci(n - 2, memo);
    memo[n] = value;
    return value;
}

// Time O(n), space O(1): yalnızca son iki değeri tutar
public static long IterativeFibonacci(int n)
{
    long previous = 0, current = 1;
    if (n == 0) return 0;
    for (var i = 2; i <= n; i++)
    {
        (previous, current) = (current, previous + current);
    }
    return current;
}

memo      fib(90) = 2,880,067,194,370,816,120  entries = 89  allocated = 4,632 bytes
iterative fib(90) = 2,880,067,194,370,816,120  allocated = 0 bytes

İkisi de aynı sonucu O(n) zamanda buluyor. Memoization 89 entry'lik bir dictionary ve 4.632 byte allocation ile, iterative versiyon sıfır allocation ile. Ama memoization'ın gizli bir bedeli daha var: recursive olduğu için call stack'te de n derinliğe iniyor. Bu, yazının asıl konusu.

Recursion Stack'i: Derinlik Bellektir

Her method çağrısı call stack'te bir frame açar: dönüş adresi, parametreler, local değişkenler. Recursive bir fonksiyon d derinliğe iniyorsa, en dipteki çağrı sırasında d frame aynı anda stack'te durur. Yani recursion'ın space complexity'si en az O(derinlik). Bunu kodda hiçbir new görmeden, hiçbir collection ayırmadan kaybedersin.

Bookstore'un kategori ağacını düşün. Her kategorinin bir parent'ı var ve bir kategorinin derinliğini bulmak istiyoruz. Normalde ağaç birkaç seviye derindir; ama bir import hatası 100.000 seviyelik bir zincir üretirse ne olur?

public sealed class CategoryNode(string name, CategoryNode? parent = null)
{
    public string Name { get; } = name;
    public CategoryNode? Parent { get; } = parent;
}

// O(depth) stack: root'a ulaşana kadar her seviye bir frame tutar
public static int DepthRecursive(CategoryNode node) =>
    node.Parent is null ? 1 : 1 + DepthRecursive(node.Parent);

// O(1) ek bellek: tek bir değişken zincir boyunca yukarı çıkar
public static int DepthIterative(CategoryNode node)
{
    var depth = 1;
    for (var current = node; current.Parent is not null; current = current.Parent)
    {
        depth++;
    }
    return depth;
}

Ne kadar derine inebileceğimizi stack'in boyutu belirler. macOS'ta pthread_get_stacksize_np ile her thread'in stack boyutunu okudum:

main thread          : 7.98 MB
new Thread()         : 1.51 MB
new Thread(.., 16 MB): 16.01 MB
thread pool          : 1.51 MB

Main thread işletim sisteminin verdiği 8 MB'ı kullanıyor (ulimit -s 8176 KB). .NET'in kendi açtığı thread'ler, thread pool dahil, bu makinede 1,5 MB ile başlıyor. ASP.NET Core'da request'ler thread pool'da çalıştığı için production kodun gerçek limiti main thread'inki değil, thread pool'unki. Bu değerler işletim sistemine ve runtime ayarlarına göre değişir; ölçmeden varsayma. Aynı 100.000 derinlikli zinciri iki farklı thread'de çalıştırınca:

$ dotnet Bookstore.Complexity.Demos.dll depth 100000
recursive depth = 100,000

$ dotnet Bookstore.Complexity.Demos.dll depth 100000 thread
Stack overflow.
   at Bookstore.Complexity.CategoryNode.get_Parent()
   at Bookstore.Complexity.SpaceExamples.DepthRecursive(Bookstore.Complexity.CategoryNode)
   at Bookstore.Complexity.SpaceExamples.DepthRecursive(Bookstore.Complexity.CategoryNode)
   ...
   at Post03+<>c__DisplayClass4_0.<Depth>b__0()
   at System.Threading.Thread+StartHelper.Callback(System.Object)
$ echo $?
134

Main thread'de çalışan kod, thread pool'a taşındığı an process'i düşürüyor. Çıktı 49.508 satır; yani 1,5 MB'lık stack'e yaklaşık 49.500 frame sığdı, frame başına 32 byte civarı. Çıkış kodu 134, process'in SIGABRT ile sonlandırıldığını söylüyor.

Burada önemli olan şey: StackOverflowException yakalanamaz. Microsoft dokümanı açıkça "try/catch ile yakalayamazsın, process varsayılan olarak sonlandırılır" der. Bir try bloğu, global exception handler veya middleware seni kurtarmaz; bütün process, içindeki bütün diğer request'lerle birlikte düşer. Bu yüzden derinliği girdiye bağlı olan recursion'lar, yani kullanıcının ya da verinin kontrol ettiği her derinlik, ya iterative yazılır ya da açık bir derinlik limitiyle korunur. Call stack'in kendisi C# Temelleri serisindeki "C# Hata Ayıklama: Breakpoint, Call Stack, Debug.Assert ve Derleyici Uyarıları" yazısında, recursion'ı iterative'e çevirme teknikleri Algoritmalar ve Data Structures serisinin recursion yazısında.

Iterative versiyon ise 1.000.000 seviyelik zinciri sorunsuz geziyor. Bunu bir xUnit testi doğruluyor:

[Fact]
public void IterativeDepth_HandlesChainsTooDeepForRecursion()
{
    var leaf = SpaceExamples.BuildChain(1_000_000);

    Assert.Equal(1_000_000, SpaceExamples.DepthIterative(leaf));
}

Recursion'ın stack maliyeti derinliğe bağlı, toplam çağrı sayısına değil. Merge sort n log n kez çağrılsa da aynı anda en fazla log₂ n frame stack'tedir: 1.000.000 element için 20. Naive Fibonacci 2,7 milyon çağrı yapsa da fib(30) için stack'te en fazla 30 frame olur. Tehlikeli olan, derinliği n ile lineer büyüyen recursion: bağlı listeyi, zinciri veya dengesiz bir tree'yi recursive gezmek.

Kopya Üreten API'ler

İkinci gizli bellek kaynağı, kopya üreten method'lar. ToList() ve ToArray() her çağrıldığında n element'lik yeni bir collection ayırır: O(n) ek bellek. Substring yeni bir string ayırır ve karakterleri kopyalar. Split hem bir array hem de her parça için bir string ayırır.

Log satırlarından fiyat okuyan iki parser yazdım. Biri Split kullanıyor, diğeri span üzerinden son ;'den sonrasını dilimliyor:

// "978-0000000001;Title 1;Author 1;10.50" -> 10.50
// Split bir string[] ve her alan için bir string ayırır
public static decimal WithSplit(string line) =>
    decimal.Parse(line.Split(';')[3], System.Globalization.CultureInfo.InvariantCulture);

// Span'i dilimlemek hiçbir şey ayırmaz
public static decimal WithSpan(string line)
{
    var span = line.AsSpan();
    var lastSeparator = span.LastIndexOf(';');
    return decimal.Parse(span[(lastSeparator + 1)..], provider: System.Globalization.CultureInfo.InvariantCulture);
}

| Method | Mean     | Ratio | Gen0   | Allocated |
|------- |---------:|------:|-------:|----------:|
| Split  | 53.29 ns |  1.00 | 0.0334 |     280 B |
| Span   | 23.57 ns |  0.44 |      - |         - |

Span versiyonu iki kattan fazla hızlı ve sıfır allocation yapıyor; Split her satır için 280 byte ayırıyor. 10 milyon satırlık bir logda bu 2,8 GB allocation demek. ReadOnlySpan<char> mevcut belleğin üzerinde bir pencere; dilimlemek yalnızca başlangıç ve uzunluğu değiştirir, O(1). Span'in kuralları ve sınırları C# İleri serisindeki "C#'ta Span<T> ve Memory<T>: Allocation'sız Parse, stackalloc ve ref struct Kuralları" yazısında.

Time-Space Trade-off

Bellek ile zaman arasında bilinçli bir takas yapmak, algoritma tasarımının en eski hilesi. Memoization aynı alt problemi tekrar çözmemek için sonuçları saklar. Lookup table, pahalı bir hesabı önceden yapıp tabloya yazar. Precomputed index, sorgulanacak veriyi önceden bir Dictionary'e veya sıralı bir array'e koyar.

Önceki yazıdaki sipariş eşleştirme bunun tipik örneği: m müşteri için O(m) ek bellek harcayıp O(n·m) zamanı O(n+m)'e indirdik. Ama ilginç bir ayrıntı var. O benchmark'ta dictionary'li versiyon daha az allocation yaptı: 1.000 kayıtta 84,95 KB'a karşı 140,68 KB. Sebep, naive versiyonda her sipariş için yeni bir closure ve delegate ayrılması; c => c.Id == order.CustomerId lambda'sı order'ı yakaladığı için döngünün her turunda bir object oluşur. Trade-off her zaman "daha çok bellek, daha az zaman" değil; bazen iki taraf da birlikte iyileşir.

Ters yön de geçerli. Bellek kısıtlıysa zamandan feda edebilirsin: her seferinde yeniden hesaplamak, sonuçları diske yazıp oradan okumak, veriyi parça parça işlemek. Bir sonraki bölümün konusu tam olarak bu.

1 GB'lık Log Dosyasını Okumak: O(n) ve O(1) Bellek

Tahmin bölümüne dönelim. 1 GB'lık, 10.288.949 satırlık bir dosya ürettim ve iki versiyonu macOS'un /usr/bin/time -l aracıyla çalıştırdım; bu araç process'in en yüksek resident memory'sini (RSS, Resident Set Size) raporlar:

public static void ReadLog(string path, string mode)
{
    var stopwatch = Stopwatch.StartNew();
    long errors = 0, lines = 0;
    if (mode == "all")
    {
        // Bütün dosya belleğe: O(n) bellek
        var all = File.ReadAllLines(path);
        lines = all.Length;
        foreach (var line in all)
        {
            if (line.Contains("customerId=42 ")) errors++;
        }
    }
    else
    {
        // Satır satır stream: O(1) ek bellek (en uzun satır kadar)
        foreach (var line in File.ReadLines(path))
        {
            lines++;
            if (line.Contains("customerId=42 ")) errors++;
        }
    }
    Console.WriteLine($"{mode,-6} lines={lines:N0} matches={errors:N0} time={stopwatch.ElapsedMilliseconds:N0} ms " +
                      $"totalAllocated={GC.GetTotalAllocatedBytes() / 1024 / 1024:N0} MB");
}

stream lines=10,288,949 matches=1,032 time=604 ms totalAllocated=2,275 MB
            54493184  maximum resident set size
all    lines=10,288,949 matches=1,032 time=2,128 ms totalAllocated=2,609 MB
          2841362432  maximum resident set size

ReadLines ile process'in en yüksek belleği 52 MB, ReadAllLines ile 2.710 MB. 1 GB'lık dosya bellekte 2,7 GB tuttu, çünkü .NET string'leri Unicode Transformation Format (UTF) ailesinden UTF-16 ile, karakter başına 2 byte olarak saklar ve her satır ayrıca kendi object başlığını taşır. Stream versiyonu üç buçuk kat da hızlı: 10 milyon string'i canlı tutmak GC'ye (Garbage Collector) sürekli taşınacak, taranacak bir yük demek.

Şimdi asıl soru. Aynı iki komutu --memory=512m ile sınırlanmış bir container'da çalıştırdım:

$ docker run --rm --name bigowork-oom-stream --memory=512m -v "$B":/app:ro -v "$PWD/data":/data:ro \
    mcr.microsoft.com/dotnet/runtime:10.0 dotnet /app/Bookstore.Complexity.Demos.dll readlog /data/orders.log stream
stream lines=10,288,949 matches=1,032 time=1,167 ms totalAllocated=2,275 MB

$ docker run -d --name bigowork-oom-all --memory=512m -v "$B":/app:ro -v "$PWD/data":/data:ro \
    mcr.microsoft.com/dotnet/runtime:10.0 dotnet /app/Bookstore.Complexity.Demos.dll readlog /data/orders.log all
$ docker logs -t bigowork-oom-all
2026-11-08T09:22:53.541974424Z Out of memory.
$ docker stats --no-stream --format '{{.CPUPerc}} {{.MemUsage}}' bigowork-oom-all
100.65% 388.3MiB / 512MiB
$ docker stop -t 2 bigowork-oom-all
$ docker inspect -f 'exit={{.State.ExitCode}} oom={{.State.OOMKilled}}' bigowork-oom-all
exit=143 oom=false

$ docker run --rm --name bigowork-oom-catch --memory=512m ... readlogcatch /data/orders.log
OutOfMemoryException after 378 MB allocated; GC limit = 384 MB

Stream versiyonu container'da da sorunsuz çalıştı. ReadAllLines versiyonu ise ne bir exception mesajıyla düzgünce çıktı ne de container OOMKilled oldu. Başladıktan bir saniye sonra stderr'e yalnızca Out of memory. yazdı, sonra dokuz dakika boyunca yüzde 100 CPU (Central Processing Unit) kullanımıyla 388 MiB'da asılı kaldı; container'ı sonunda kendim durdurdum (çıkış kodu 143, yani SIGTERM (terminate signal, kapatma sinyali); OOMKilled=false). Aynı kodu ReadAllLines'ı bir try/catch içine alan readlogcatch varyantıyla çalıştırınca tablo netleşti: 378 MB allocation'dan sonra yönetilen bir OutOfMemoryException fırladı ve GC'nin bildirdiği limit 384 MB'tı, yani 512 MB'ın yüzde 75'i. .NET'in GC'si container limit'ini okuyup heap'i onun altında tuttuğu için kernel process'i öldürmedi; yakalanmayan exception'dan sonraki asılı kalma ise bu makinede gözlemlediğim davranış, sebebini burada incelemedim. Ders şu: bellek limitine çarpan bir .NET process'i her zaman temiz bir crash ile ölmez; health check'in ve memory alarm'ın yoksa böyle bir process'i saatlerce fark etmeyebilirsin. Asıl çözüm limiti büyütmek değil, O(n) bellek isteyen kodu O(1)'e çevirmek.

Allocation ve GC Baskısı

Yukarıdaki çıktıda dikkat çekici bir sayı var: stream versiyonu da toplamda 2.275 MB allocation yaptı. Her satır için yeni bir string oluşuyor ve döngünün sonraki turunda çöpe gidiyor. Space complexity'si O(1), çünkü aynı anda bellekte yalnızca bir satır canlı. Ama toplam allocation O(n).

Bu ayrım önemli. Space complexity "aynı anda ne kadar bellek canlı" sorusunun cevabı; process'in memory limit'ine çarpıp çarpmayacağını belirler. Toplam allocation ise GC'nin ne kadar çalışacağını belirler; latency'yi ve CPU'yu etkiler. Kısa ömürlü allocation'lar Gen0'da ucuza toplanır, ama ucuz bedava demek değil. Satırları string yerine bir PipeReader veya buffer üzerinden span olarak işlemek bu allocation'ı da sıfıra yakın indirir; ölçüm ve teknik C# İleri serisindeki "C#'ta Performans: Allocation, Struct'lar ve BenchmarkDotNet ile Ölçmek" yazısında.

Üretimde Dikkat

"Bellek ucuz" sözü geliştirici makinesinde doğru, container'da değil. Kubernetes'te bir pod'un memory limit'i aşıldığında kernel'in OOM (Out Of Memory) killer'ı process'i öldürür ve pod OOMKilled durumuna, çıkış kodu 137'ye düşer. .NET bunu önlemek için container limit'ini okur: GC'nin heap hard limit'i varsayılan olarak container limit'inin yüzde 75'idir (Microsoft'un GC configuration dokümanı). Yukarıdaki denemede GC'nin bildirdiği 384 MB'lık limit tam olarak bu.

Production'da birkaç kural bu sürprizleri azaltır. Dosya, HTTP (Hypertext Transfer Protocol) body, veritabanı sonucu gibi boyutu dışarıdan gelen her şeyi stream olarak işle; ReadAllLines, ReadAllText, ToListAsync() ve ReadAsStringAsync() çağrılarında "bu veri yarın 10 kat büyürse?" diye sor. Recursion derinliğini girdiye bırakma; JSON (JavaScript Object Notation) parser'ların bir max depth ayarı olmasının sebebi bu. Ve bellek ölçümünü GC.GetTotalAllocatedBytes ile değil, peak RSS veya container metriği ile yap; ikisi farklı soruları cevaplıyor.

Sık Düşülen Tuzaklar

Recursion'ı bedava saymak. Kodda new yok diye space complexity'nin O(1) olduğunu düşünmek. Her seviye bir frame.

StackOverflowException'ı yakalamaya çalışmak. Yakalanamaz; process düşer. Önlem derinlik limiti veya iterative koddur.

Main thread'de test edip thread pool'da çalıştırmak. Console demo'su 8 MB stack ile geçer, aynı kod ASP.NET Core'da 1,5 MB ile düşer.

Dosya boyutunu bellek boyutu sanmak. 1 GB'lık UTF-8 dosya bellekte 2,7 GB tuttu.

Peak memory ile toplam allocation'ı karıştırmak. Stream versiyonu 2,2 GB allocation yaptı ama hiçbir anda 52 MB'ı geçmedi.

Gereksiz ToList(). Bir LINQ (Language Integrated Query) zincirinin ortasına "garanti olsun" diye eklenen her ToList() O(n) ek bellek demek. Bir kez gezilecek sonucu materialize etme; birden çok kez gezilecekse bir kez et.

Küçük Bir Deneme

★☆☆ DepthRecursive'i new Thread(..., maxStackSize: 16 * 1024 * 1024) ile açılmış bir thread'de çalıştır. 100.000 derinlik geçiyor mu? Kaba olarak kaç derinliğe kadar inebilirsin?

★★☆ MemoFibonacci(90)'ı 1,5 MB'lık bir thread'de çalıştır, sonra n'i 100.000'e çıkar (sonuç long'a sığmaz, taşmayı umursamadan yalnızca derinliğe bak). Hangi n'de düşüyor? Iterative versiyonun bellek kullanımı n'e göre nasıl değişiyor?

★★★ Log okuyucuyu satırları string'e çevirmeden işleyecek şekilde yaz (FileStream + buffer + ReadOnlySpan<byte> içinde "customerId=42 "u8 araması). Toplam allocation ve süreyi ReadLines versiyonuyla karşılaştır.

Bu yazıya kadar her işlemin maliyetine tek tek baktık. Ama bazı işlemler çoğu zaman ucuz, arada bir pahalı: List<T>.Add dokümanda "bazen O(n)" diye geçiyor ve yine de herkes ona O(1) diyor. Bir sonraki yazıda bunun neden haklı olduğunu amortized analysis ile göstereceğiz.