Derleyici Sizi Şaşırttığında

 (xania.org)
1 puan yazan GN⁺ 2025-12-26 | 1 yorum | WhatsApp'ta paylaş
  • Basit bir tamsayı toplama fonksiyonu derlenirken GCC ve Clang arasındaki optimizasyon farkının gözlemlendiği bir örnek
  • GCC, döngü içinde iki sayıyı aynı anda toplayan x*2 + 1 biçiminde bir döngü optimizasyonu uygular
  • Clang ise döngüyü tamamen kaldırır ve hesaplamayı v(v - 1)/2 kapalı formülüne dönüştürür
  • Bu dönüşümle kod O(n)'den O(1)'e geçer ve matematiksel sadeleştirme otomatik olarak yapılır
  • 20 yıldan uzun süredir derleyicilerle çalışan yazarı bile şaşırtacak kadar, derleyicilerin akıllı optimizasyon seviyesini gösteren bir örnek

GCC'nin döngü optimizasyonu

  • Basit bir tamsayı toplama fonksiyonu yazıldığında GCC, döngü tabanlı verimli bir toplama kodu üretir
    • Döngü içinde lea edx, [rdx+1+rax*2] komutunu kullanarak iki sayıyı aynı anda toplar
    • Bu, x ile x+1 toplama işleminin x*2 + 1 biçimine dönüştürülmüş hâlidir
  • Optimizasyon seviyesi -O3 değerine çıkarıldığında paralel toplama (vectorization) ile döngü daha hızlı işlenir
  • Bu yaklaşım, döngüyü korurken işlem verimliliğini en üst düzeye çıkaran geleneksel bir optimizasyon biçimidir

Clang'in matematiksel optimizasyonu

  • Aynı kod Clang ile derlendiğinde döngü tamamen ortadan kalkar
    • Clang, giriş değerinin pozitif olup olmadığını kontrol ettikten sonra bir dizi lea, imul, shr komutuyla hesaplama yapar
    • Sonuç olarak (v² - v)/2, yani tamsayı toplamının kapalı formülü elde edilir
  • Bu dönüşüm, döngüyü kaldırıp yerine sabit zamanlı (O(1)) bir hesaplama koyar
  • Yazar bu sonucu, “tamsayı toplamının matematiksel çözümünü kendi kendine bulmuş” diye tanımlıyor

Formülün açılım süreci

  • Clang'in ürettiği assembly kodu matematiksel olarak geriye doğru izlendiğinde şu dönüşüm ortaya çıkıyor
    • v + ((v - 1)(v - 2) / 2) - 1
    • Bu ifade açılıp sadeleştirildiğinde (v² - v)/2 sonucuna ulaşılıyor
  • Sonunda v(v - 1)/2 biçimi elde ediliyor; bu da 1'den v'ye kadar sayıların toplamı formülüyle örtüşüyor
  • Bu süreç, derleyicinin matematiksel örüntüleri tanıyıp optimize etmesine bir örnek olarak sunuluyor

Derleyicinin akıllı davranışı

  • Clang'in bu özel komut dizisini kullanma nedeni olarak taşmayı önleme ve türetilmiş değişkenleri izleme yöntemi gösteriliyor
  • İçeride tam olarak ne olduğunun nedeni net değil, ancak bunun Clang'in iç optimizasyon mantığının birleşik bir sonucu olduğu belirtiliyor
  • Yazar bu sonucu “alçakgönüllü kılan ve ilham veren bir deneyim” olarak ifade ediyor

Kapanış ve seri bağlamı

  • Bu yazı ‘Advent of Compiler Optimisations 2025’ serisinin 24. yazısı
  • Derleyicinin kod dönüşümleriyle matematiksel sadeleştirme ve performans artışı sağlamasını inceliyor
  • Yazar, “derleyiciler hâlâ beni şaşırtıyor” diyerek uzun yıllara dayanan deneyime rağmen süren teknik hayranlığı vurguluyor

İlgili okumalar

1 yorum

 
GN⁺ 2025-12-26
Hacker News yorumları

  • Bu özelliği uygulayan kod ScalarEvolution.cpp ve IndVarSimplify.cpp içinde yer alıyor

    • Tek bir dosyada neredeyse 16.000 satır kod bulunması hem şaşırtıcı hem de biraz tedirgin edici

  • Bu tür optimizasyonlar gerçekten ilgi çekici
    Derleyici optimizasyonları kabaca ikiye ayrılıyor — veri akışı analizi ve örüntü tanıma ile yerine koyma
    İlki çoğu program için etkilidir, ikincisi ise giderek getirisi azalan bir örüntü biriktirme işidir
    Bağlantı verilen örnek akıllıca ve eğlenceli, ama pratikte çok büyük bir değeri yok. 45 yıldır böyle döngüler yazmadım
    Elbette bu tür örüntü dönüşümleri üst düzey koddan otomatik üretildiği için hâlâ önemlidir
    Dürüst olmak gerekirse, benim optimizer bu optimizasyonu yapamadığı için biraz söyleniyor da olabilirim

    • Aslında düşündüğümden daha değerli olabilir. LLVM'nin SCEV(Scalar Evolution) özelliği esas olarak analiz için kullanılıyor ve matematiksel döngüler dışındaki başka optimizasyonları da mümkün kılıyor
    • Hangi optimizasyonun yapıldığı tam olarak net değil. Eskiden niş bir derleyici yaptığımda, benim elle yazdığım optimizasyondan daha akıllıca şeyleri derleyicinin kendi başına yaptığını görüp şaşırdığımı hatırlıyorum

  • Bu, Scalar Evolution(SCEV) denen bir özellik ve LLVM'de oldukça karmaşık biçimde uygulanmış

  • Benzer bir optimizasyon örneği olarak “Do not optimize away” yazısı var

    • Yazının başlarındaki açıklama biraz yanlış. Kod 0'dan N'e kadar topluyor ama N hariç, bu yüzden gerçekte doğru olan N(N-1)/2. Matematiksel olarak 1'den N'e kadar toplam N(N+1)/2 olduğundan, üst sınırı hariç tutmak için N'i (N-1) ile değiştirmek gerekir
    • Derleyicinin bunu yine de optimize edebileceğini düşünüyorum. Sabit katlama yapılan sürümle sabit olmayan sürümü ayrı ayrı üretip çalışma zamanında dallanma yaparsa mümkün olabilir

  • Bu optimizasyonun gerçekten harika yanı genel(geneneric) olması
    Sadece “sonlu tamsayı dizisinin toplamı” örüntüsünü tanımıyor, genel amaçlı biçimde uygulanabiliyor olması etkileyici

  • Derleyici daha fazla closed form da ekleyebilir gibi görünüyor. Buna değip değmeyeceğini merak ediyorum
    İlgili bir kavram olarak Wilf–Zeilberger pair var

  • Bir kez daha GCC'nin Clang'den daha yavaş çıkmasına şaşırdım
    GCC 20 yıl öndeydi ama buna rağmen Clang'in hâlâ daha hızlı kod ürettiği durumlar var
    Eskiden bit çıkarma yaparken Clang iki shift ile işi bitirirken, GCC üç tane yapıyordu

    • GCC ile LLVM/Clang arasında derleyici teknolojisi açısından büyük bir nesil farkı var. GCC hâlâ muazzam bir proje, ama modern optimizasyon tekniklerini uygulamak için yapısal olarak zorlandığını duydum
    • Gerçek performans açısından iki derleyici de benzer. Farklı optimizasyon pass'leri olduğu için sonuca göre durum değişiyor
    • GCC ilk dönemde lisans odaklı idealist bir tasarım yüzünden pek genişletilebilir değildi. Şimdi bu büyük ölçüde hafifledi ama kod üreteci hâlâ karmaşık. Buna karşılık Clang'in yapısı daha basit olduğu için optimizasyonları uygulamak daha kolay. Kişisel olarak MSVC ve ICC çıktılarının da oldukça iyi olduğunu düşünüyorum
    • Acaba bitfield ile ilgili bir kod muydu? GCC bu alandaki optimizasyonlarda özellikle zayıf

  • Birisi hiç graf boyama problemi(graph coloring) için bunu sabitle değiştiren bir optimizasyon denedi mi diye merak ediyorum

    • Graf boyama NP-hard bir problem, bu yüzden bunu O(1)'e çevirmek zor. Düzlemsel graflar için dört renk teoremi geçerli ama her zaman aynı cevap çıkmaz. Sadece biraz grafik teorisi konuşmak istedim

  • Bu, uygulama ile belirtim arasındaki sınırı bulanıklaştıran bir örnek
    Bir uygulama yazdığımızı sanıyoruz ama aslında belirtimin vekilini yazıyoruz
    Yani derleyici, emredici bir makine yanılsaması üretiyor

  • İlk başta Matt'in böyle bir davranışı bilmiyor olmasına şaşırmıştım
    Ben de üniversite yıllarımda LLVM IR ile oynarken özyinelemenin çarpmaya indirgenmesine tanık olup şok olmuştum
    Matt'in bunu bilmiyor olması, bu optimizasyonun onun uğraşmadığı basit durumlara uygulandığı anlamına da gelebilir