Big-O'nun Söylemedikleri: Sabitler, Cache ve BenchmarkDotNet ile Ölçmek

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 Apple M5 / macOS 27.0.1 / .NET 10.0.13 üzerinde alınmıştır.

Önce Tahmin Et

Bookstore'un ürün sayfası "bu yazarın diğer kitapları" kutusunda en fazla 10 kitabı fiyata göre sıralı gösteriyor. Üç implementasyon var: elle yazılmış bir insertion sort (O(n²)), OrderBy(b => b.Price).ToList() (O(n log n)) ve bir comparison ile Array.Sort (O(n log n)). Hangisi en hızlı? O(n²) olan, diğer ikisinin ne kadar gerisinde kalır?

İkinci soru: bir milyon int'i toplamak. Bir int[], bir List<int> ve bir LinkedList<int> üzerinde, üçü de O(n). Aralarında ne kadar fark olur? Serinin dört yazısı boyunca Big-O'nun söylediklerini konuştuk. Bu yazı söylemediklerini konuşuyor.

Küçük n'de Sabitler Kazanır

Big-O sabitleri atar, çünkü büyük n'de onlar önemsizleşir. Küçük n'de ise sabitlerden başka bir şey kalmaz. Bunu görmek için kendi insertion sort ve merge sort'umuzu .NET'in Array.Sort'u ile 8, 16, 64 ve 256 element'lik rastgele array'lerde ölçtüm (her çağrı önce kaynak array'i kopyalıyor, bu maliyet üçünde de aynı):

| Method    | N   | Mean         | Ratio |
|---------- |---- |-------------:|------:|
| Insertion | 8   |     7.744 ns |  1.00 |
| Merge     | 8   |    46.147 ns |  5.96 |
| ArraySort | 8   |     9.092 ns |  1.17 |
| Insertion | 16  |    27.700 ns |  1.00 |
| Merge     | 16  |   108.943 ns |  3.94 |
| ArraySort | 16  |    29.784 ns |  1.08 |
| Insertion | 64  |   385.940 ns |  1.00 |
| Merge     | 64  |   526.993 ns |  1.37 |
| ArraySort | 64  |   169.315 ns |  0.44 |
| Insertion | 256 | 5,881.215 ns |  1.00 |
| Merge     | 256 | 2,906.835 ns |  0.49 |
| ArraySort | 256 | 1,219.095 ns |  0.21 |

8 element'te O(n²) insertion sort, O(n log n) merge sort'tan altı kat hızlı. 64 element'te bile önde. Merge sort ancak 256'da öne geçiyor. Sebep sabitler: merge sort her seviyede recursion çağrısı yapıyor, bir buffer'a kopyalıyor ve geri kopyalıyor; insertion sort ise yerinde, dallanması tahmin edilebilir, tek bir sıkı döngü.

.NET bunu bildiği için Array.Sort hibrit çalışır. Microsoft Learn'deki Remarks bölümüne göre Array.Sort introsort kullanır: partition boyutu 16 element veya daha azsa insertion sort, recursion derinliği 2·log n'i aşarsa heapsort, diğer durumlarda quicksort. Tablodaki 8 ve 16 element'lik satırlarda Array.Sort'un insertion sort'umuzla neredeyse aynı süreyi vermesi bu yüzden: o boyutta zaten insertion sort çalışıyor. Introsort'un ayrıntıları Algoritmalar ve Data Structures serisinin "Quick Sort, Introsort ve Counting/Radix Sort: .NET'in Array.Sort'u Nasıl Sıralar" yazısında.

Cache ve Pointer Chasing: List ile LinkedList

İkinci tahmin sorusunun ölçümü:

| Method        | N       | Mean     | Ratio |
|-------------- |-------- |---------:|------:|
| ArraySum      | 1000000 | 256.1 us |  1.00 |
| ListSum       | 1000000 | 335.4 us |  1.31 |
| LinkedListSum | 1000000 | 969.4 us |  3.79 |

Üçü de O(n), üçü de bir milyon element'i birer kez ziyaret ediyor. Ama LinkedList<int> array'den 3,8 kat yavaş. Fark donanımdan geliyor. CPU (Central Processing Unit) bellekten tek tek byte değil, cache line denen bloklar halinde okur ve sıradaki erişimi tahmin edip önceden getirir (prefetch). Array'in element'leri bellekte yan yana durduğu için bir cache line birden çok int taşır ve prefetcher bir sonraki bloğu hazır eder. Linked list'te her element ayrı bir node object'i; bir sonrakinin adresini ancak mevcut node'u okuyunca öğrenirsin. Buna pointer chasing denir: her adım bir öncekinin bitmesini bekler ve prefetch'in işi zorlaşır.

List<int>'in array'den yüzde 31 yavaş olması ise başka bir sabit: enumerator'ın her adımda yaptığı ek kontroller, örneğin listenin gezinti sırasında değişip değişmediğine bakan version kontrolü. İkisi de contiguous bellek, ikisi de aynı büyüme sınıfında. Big-O bu farkların hiçbirini görmez. Collection seçimi ile ilgili pratik kurallar C# Koleksiyonlar serisindeki "C# Queue, Stack, LinkedList ve PriorityQueue: Sırayla Çalışan Collection'lar" yazısında.

Average ile Worst Case Arasındaki Uçurum

Serinin ilk yazısında Dictionary'nin O(1)'inin average case olduğunu söylemiş, worst case'i bu yazıya bırakmıştık. Aynı ISBN (International Standard Book Number) değerlerini iki farklı key tipiyle bir dictionary'ye ekledim. Biri record'un ürettiği normal GetHashCode'u kullanıyor, diğeri her key için 42 dönüyor:

public sealed record GoodIsbn(string Value);

public sealed record BadIsbn(string Value)
{
    // Bütün key'ler aynı bucket'a düşer: lookup lineer taramaya döner
    public override int GetHashCode() => 42;
}

| Method   | N    | Mean          | Ratio  | Allocated |
|--------- |----- |--------------:|-------:|----------:|
| GoodHash | 1000 |      26.17 us |   1.00 | 123.18 KB |
| BadHash  | 1000 |   1,739.40 us |  66.57 | 123.18 KB |
| GoodHash | 2000 |      58.61 us |   1.00 |  257.4 KB |
| BadHash  | 2000 |   6,531.16 us | 111.67 |  257.4 KB |
| GoodHash | 4000 |     102.18 us |   1.00 | 304.28 KB |
| BadHash  | 4000 |  26,487.06 us | 259.23 | 304.26 KB |
| GoodHash | 8000 |     228.41 us |   1.00 | 628.33 KB |
| BadHash  | 8000 | 107,184.12 us | 469.39 | 628.27 KB |

Allocation birebir aynı; yapı aynı, yalnızca hash dağılımı farklı. İyi hash ile n'i iki katına çıkarmak süreyi kabaca iki katına çıkarıyor: n insert, her biri O(1). Kötü hash ile her insert, aynı bucket'taki zinciri baştan sona gezip eşitlik kontrolü yapıyor: n insert, her biri O(n), toplam O(n²). Oranlar bunu gösteriyor: 1.739 → 6.531 → 26.487 → 107.184 mikrosaniye, her adımda yaklaşık 4 kat.

Gerçek hayatta 42 dönen bir GetHashCode yazmazsın. Ama yalnızca bir property'yi hash'leyen (her kitap için CategoryId gibi düşük çeşitlilikte bir alan), ya da mutable bir field'a bağlı hash'ler aynı etkiyi kısmen üretir. Saldırgan kontrolündeki key'ler de bir risk: çakışan key'ler gönderip sunucuyu O(n²)'ye zorlamak bilinen bir saldırı (hash flooding). .NET'in string hash'i process başına rastgele bir seed ile hesaplanır ve string key'li Dictionary bir bucket'taki çakışma zinciri uzayınca bu randomized hash'e geçer; kendi key tipinin GetHashCode'unu yazarken HashCode.Combine kullanmak bu korumadan yararlanmanın en kolay yolu.

Aynı uçurum quicksort'ta da var. İlk element'i pivot seçen naive bir quicksort'u rastgele ve zaten sıralı girdilerle ölçtüm:

| Method               | N    | Mean         | Ratio |
|--------------------- |----- |-------------:|------:|
| RandomInput          | 1000 |     9.057 us |  1.00 |
| SortedInput          | 1000 |   131.565 us | 14.53 |
| ArraySortSortedInput | 1000 |     2.131 us |  0.24 |
| RandomInput          | 2000 |    18.427 us |  1.00 |
| SortedInput          | 2000 |   498.132 us | 27.03 |
| ArraySortSortedInput | 2000 |     4.816 us |  0.26 |
| RandomInput          | 4000 |    56.603 us |  1.00 |
| SortedInput          | 4000 | 1,933.289 us | 34.17 |
| ArraySortSortedInput | 4000 |    10.557 us |  0.19 |

Sıralı girdide pivot hep en küçük element; her partition yalnızca bir element ayırıyor ve recursion n derinliğe iniyor. Süre her ikiye katlamada 3,8–3,9 kat artıyor: O(n²). Üstelik recursion derinliği n olduğu için, serinin üçüncü yazısında gördüğümüz gibi, yeterince büyük sıralı bir girdi stack'i de taşırır. Array.Sort aynı sıralı girdiyi 4.000 element'te 10 mikrosaniyede bitiriyor; introsort'un pivot seçimi ve derinlik limiti tam olarak bu senaryo için var. Girdi dağılımı, algoritmanın kendisi kadar önemli: "veri zaten neredeyse sıralı gelir" production'da en sık görülen dağılımlardan biri.

Doubling Experiment: Ölçerek Complexity Tahmin Etmek

Elinde kaynak kodunu okuyamadığın veya analizi zor bir kod varsa, complexity'yi ölçerek tahmin edebilirsin. Sedgewick ve Wayne'in Algorithms kitabının (4. baskı, §1.4) doubling ratio yöntemi şöyle: girdi boyutunu her adımda ikiye katla ve ardışık sürelerin oranına bak. Süre kabaca a·nᵇ ise oran 2ᵇ'ye yaklaşır. Oran 2 civarındaysa lineer, 4 civarındaysa karesel, 8 civarındaysa kübik. O(n log n) için oran 2'nin biraz üstünde kalır.

Bunu yapan küçük bir harness yazdım. Her boyutta 7 kez ölçüp medyanı alıyor:

// Sedgewick'in doubling experiment'i: n^b bir algoritma için time(2n) / time(n) -> 2^b
public static void Doubling(string algorithm)
{
    // ... algoritma ve boyut seçimi
    foreach (var n in sizes)
    {
        var samples = new List<double>();
        for (var round = 0; round < 7; round++)
        {
            var items = (int[])source.Clone();
            var stopwatch = Stopwatch.StartNew();
            run(items);
            stopwatch.Stop();
            samples.Add(stopwatch.Elapsed.TotalMilliseconds);
        }
        var median = samples.Order().ElementAt(samples.Count / 2);
        var ratio = previous == 0 ? "" : $"{median / previous,6:F2}";
        Console.WriteLine($"{algorithm,-13} n={n,11:N0} median={median,10:F3} ms ratio={ratio}");
        previous = median;
    }
}

sum           n=  1,000,000 median=     0.276 ms ratio=
sum           n=  2,000,000 median=     0.563 ms ratio=  2.04
sum           n=  4,000,000 median=     1.087 ms ratio=  1.93
sum           n=  8,000,000 median=     2.284 ms ratio=  2.10
sort          n=  1,000,000 median=    47.682 ms ratio=
sort          n=  2,000,000 median=    94.058 ms ratio=  1.97
sort          n=  4,000,000 median=   215.456 ms ratio=  2.29
sort          n=  8,000,000 median=   415.670 ms ratio=  1.93
pairs         n=      1,000 median=     0.193 ms ratio=
pairs         n=      2,000 median=     0.711 ms ratio=  3.68
pairs         n=      4,000 median=     2.789 ms ratio=  3.92
pairs         n=      8,000 median=    11.387 ms ratio=  4.08

Toplama ~2, her çifti karşılaştıran brute force ~4. Array.Sort için oranlar 1,93 ile 2,29 arasında dalgalanıyor; n log n'in 2'den ancak biraz büyük olan teorik oranı (n = 10⁶'da 2,1) bu gürültüden ayırt edilemiyor. Doubling experiment, lineer ile kareseli kesin ayırır; n ile n log n'i ayırmak için çok daha fazla ölçüm ve daha geniş bir n aralığı gerekir.

BenchmarkDotNet'te aynı şeyi [Params] ile yaparsın: yukarıdaki BadHashBenchmarks ve quicksort benchmark'ları zaten birer doubling experiment. BenchmarkDotNet'in kurulumu ve sonuç sütunları C# İleri serisindeki "C#'ta Performans: Allocation, Struct'lar ve BenchmarkDotNet ile Ölçmek" yazısında; burada önemli olan, tabloyu nasıl okuduğun. Mean sütununu bir satır aşağı inerek böl; oranın ne olduğuna, sabit kalıp kalmadığına bak.

Isınmamış Stopwatch Yanıltır

Aynı harness'ı naive quicksort'un sıralı girdisiyle çalıştırınca şu çıktı geldi:

quick-sorted  n=      1,000 median=     1.051 ms ratio=
quick-sorted  n=      2,000 median=     6.004 ms ratio=  5.71
quick-sorted  n=      4,000 median=    17.306 ms ratio=  2.88
quick-sorted  n=      8,000 median=     8.276 ms ratio=  0.48
quick-sorted  n=     16,000 median=    31.087 ms ratio=  3.76

8.000 element, 4.000 element'ten iki kat hızlı çıktı. Algoritma değişmedi; değişen, ölçümün kendisi. .NET'in tiered compilation'ı bir method'u önce hızlıca ama az optimize edilmiş hâliyle derler, sık çağrılınca arka planda optimize edilmiş hâliyle yeniden derler. Ölçümün ilk boyutları yavaş kodla, sonrakiler hızlı kodla koştu. Aynı 1.000 element'lik sıralama Stopwatch'ta 1,05 milisaniye, BenchmarkDotNet'te 0,13 milisaniye ölçüldü. BenchmarkDotNet'in ayrı bir process açması, warmup iterasyonları koşması ve istatistiksel olarak yeterli sayıda ölçüm alması süs değil; bu tür hataları ayıklamak için. Elle ölçeceksen en azından ölçmeden önce aynı kodu birkaç kez çalıştır ve tutarsız oranlar görürsen önce ölçümünden şüphelen.

"O(n log n) Çözüm O(n²)'den Yavaş Çıktı"

Şimdi ilk tahmin sorusu. 10 kitabı fiyata göre sıralamak:

[Benchmark(Baseline = true)]
public Book InsertionSortByPrice()
{
    _source.CopyTo(_work, 0);
    Sorting.InsertionSortByPrice(_work);
    return _work[0];
}

[Benchmark]
public Book LinqOrderByToList() => _source.OrderBy(b => b.Price).ToList()[0];

[Benchmark]
public Book ArraySortWithComparison()
{
    _source.CopyTo(_work, 0);
    Array.Sort(_work, (a, b) => a.Price.CompareTo(b.Price));
    return _work[0];
}

| Method                  | Mean      | Ratio | Allocated |
|------------------------ |----------:|------:|----------:|
| InsertionSortByPrice    |  51.77 ns |  1.00 |         - |
| LinqOrderByToList       | 104.73 ns |  2.03 |     696 B |
| ArraySortWithComparison |  85.71 ns |  1.66 |         - |

O(n²) insertion sort, LINQ'in (Language Integrated Query) O(n log n) sıralamasından iki kat, comparison'lı Array.Sort'tan yüzde 66 hızlı. Bu, code review'da sık duyulan "O(n log n) olan daha iyi" yorumunun neden her zaman doğru olmadığının küçük bir örneği. Farkı yaratan şeyler Big-O'nun dışında:

• Allocation: OrderBy(...).ToList() 696 byte ayırıyor (key array'i, index map'i, sorter object'leri, sonuç listesi). Insertion sort sıfır.
• Delegate çağrısı: hem key selector hem comparison her karşılaştırmada bir indirect call. Insertion sort'ta karşılaştırma inline bir decimal kıyası.
• Interface dispatch ve genellik: IComparer<T> üzerinden giden kod, JIT (Just-In-Time) derleyicisinin somut tipi bilip inline edebildiği koddan yavaştır. Generic bir collection'da value type'ı object üzerinden işlemek ise boxing ekler.

Bu, "insertion sort yaz" önerisi değil. 10 element'te 50 nanosaniyelik fark, sayfanın geri kalanının yanında görünmez; okunabilirlik için OrderBy doğru tercih. Ama aynı fark saniyede milyonlarca kez çağrılan bir sıcak yolda gerçek olur. Karar her zaman ölçümle verilir.

Üretimde Dikkat

Bu serinin özeti tek bir iş bölümü: analiz hangi kodun büyüdüğünde sorun çıkaracağını söyler, ölçüm bugün hangisinin hızlı olduğunu söyler. Code review'da iç içe döngüyü, döngü içindeki Contains'i ve dışarıdan boyutu belirlenen recursion'ı analizle yakala. Bir sıcak yolu optimize ederken ise tahmin etme, BenchmarkDotNet ile ölç ve sonucu PR'a (pull request) ekle.

Worst case'i production'ın girdisiyle düşün. "Rastgele girdi" laboratuvar varsayımıdır; gerçek sistemlerde veri sıralı gelir, aynı key tekrar eder, tek bir müşterinin on bin siparişi olur. Kendi yazdığın quicksort, hash fonksiyonu veya cache key'i bu dağılımlarda ölçülmediyse ölçülmemiş say.

Ölçümü n'in bir fonksiyonu olarak yap. Tek bir boyutta alınmış "12 ms" bir şey söylemez; iki veya üç boyutta alınmış ölçümler büyüme sınıfını da gösterir. Bu yazıdaki her benchmark'ın en az iki N değeriyle koşmasının sebebi bu.

Sık Düşülen Tuzaklar

Küçük n'de Big-O'ya göre seçim yapmak. 10 element'te sabitler kazanır; okunabilir olanı seç, gerekirse ölç.

Aynı Big-O'yu aynı hız sanmak. Array ile linked list arasında, ikisi de O(n), 3,8 kat fark ölçtük.

Average case'e güvenip girdiyi düşünmemek. Kötü bir hash veya sıralı bir girdi, O(1)'i ve O(n log n)'i O(n) ve O(n²)'ye çevirir.

Isınmamış kodu Stopwatch ile ölçmek. Tiered compilation, GC (Garbage Collector) ve CPU frekansı tek seferlik ölçümleri anlamsız kılar.

Tek bir doubling oranına bakmak. Bir oran gürültü olabilir; eğilim en az üç noktadan okunur.

Küçük Bir Deneme

★☆☆ SmallSortBenchmarks'a 32 ve 128'i ekle. Kendi insertion sort'un ile merge sort'un kesiştiği n'i bul. Bu sayı .NET'in 16'lık eşiğinden neden farklı olabilir?

★★☆ BadIsbn'in GetHashCode'unu Value.Length döndürecek şekilde değiştir. Bütün ISBN'ler 14 karakter olduğu için ne oluyor? Ardından Value[^1] (son karakter) dön: 10 farklı hash değeriyle doubling oranları nasıl değişiyor?

★★★ Doubling harness'ına bir warmup aşaması ekle ve naive quicksort'un sıralı girdisini tekrar ölç. Oranlar BenchmarkDotNet'in 3,8–3,9'una yaklaşıyor mu? Sonra 50.000 element'lik sıralı bir array'i 1,5 MB'lık bir thread'de sırala: ne oluyor ve neden?

Big-O ve Complexity serisi burada bitiyor. Artık bir kodun maliyetini kâğıt üzerinde tahmin edebiliyor, recursion'ın ve allocation'ın bellek bedelini görebiliyor, amortized garantileri okuyabiliyor ve tahminini BenchmarkDotNet ile sınayabiliyorsun. Bu araçları kullanacağın asıl yer Algoritmalar ve Data Structures serisi: orada her data structure'ı ve algoritmayı kendimiz yazacağız ve her yazıda complexity'yi bir satırla verip bu seriye bağlayacağız.