4 milyar `if` ifadesi

 (andreasjhkarlsson.github.io)
3 puan yazan GN⁺ 2023-12-29 | 1 yorum | WhatsApp'ta paylaş
  • % kullanmadan, yalnızca karşılaştırma ifadelerini art arda dizerek çift/tek kontrolü yapmaya çalışan eğlenceli bir fikir, 8 bitten 32 bite genişletilirken derleyici ve çalıştırılabilir dosya biçiminin sınırlarını ortaya çıkardı
  • Python kod üreteciyle if (number == n) ifadeleri otomatik oluşturulunca 8 bit ve 16 bit aralıkları çalıştı, ancak 32 bitte karşılaştırma hedefi yaklaşık 4,2 milyara fırladı
  • 32 bit C sürümü 48 saatin sonunda yaklaşık 330GB'lık bir C dosyası üretti ve MSVC satır numarası sınırı ile yetersiz heap alanı nedeniyle derlemeyi başaramadı
  • PE çalıştırılabilir dosyasının 4GB kısıtını aşmak için x86-64 komutları doğrudan üretilip 40GB'lık ikili dosya isEven.bin oluşturuldu ve Windows bellek eşlemesiyle çalıştırılabilir kod gibi çağrıldı
  • Son program atoi yerine strtoul kullandıktan sonra 32 bitlik büyük değerleri de doğru sınıflandırdı; büyük girdiler Core i5 12600K·32GB bellek·M.2 SSD ortamında yaklaşık 10 saniye içinde sonuç verdi

Yalnızca karşılaştırma ifadeleriyle çift/tek belirlemek

  • Çıkış noktası, sosyal medyada görülen bir kod ekran görüntüsüydü; klasik çift/tek belirleme problemini modulus işlemi kullanmadan çözmeye çalışan bir yaklaşımdı
  • Yapı, her sayı için if (number == n) yazıp ilgili sayının çift mi tek mi olduğunu printf ile ekrana basıyordu
  • İlk C örneğinde uint8_t number = atoi(argv[1]); kullanılıyor ve 0'dan 10'a kadar olan karşılaştırmalar elle yazılıyordu
  • Derleyicinin algoritmayı değiştirmemesi için optimizasyon /Od ile kapatıldı
    • 0, 4 için even
    • 3, 7 için odd
    • 50, 11, 99 için hiçbir çıktı yoktu
  • Bunun nedeni, son iften sonra bu değerleri işleyecek başka karşılaştırma olmamasıydı; yani daha fazla if ifadesi gerekiyordu

Python ile if ifadeleri üretmek

  • Tüm karşılaştırmaları elle yazmak yerine, Python ile C kodu üreten bir meta programlama yaklaşımı kullanıldı
  • Python betiği for i in range(2**8) ile 0'dan 255'e kadar karşılaştırmalar üretiyordu
    • i % 2 == 0 ise printf("even\n");
    • değilse printf("odd\n");
  • Üretilen C programı 8 bitlik tam aralıkta çalıştı
    • 99 -> odd
    • 50 -> even
    • 240 -> even
    • 241 -> odd

16 bite kadar C derlemesiyle başarı

  • Aynı yaklaşım uint16_t ve range(2**16) ile genişletildi
  • Ortaya çıkan C dosyası yaklaşık 130 bin satır büyüklüğündeydi
  • MSVC ile derlendikten sonra çeşitli değerlerde doğru çalıştı
    • 21000 -> even
    • 3475 -> odd
    • 3 -> odd
    • 65001 -> odd
    • 65532 -> even
  • Çalıştırılabilir dosya boyutu yaklaşık 2MB idi ve 31,8GB belleğe sahip bir bilgisayarda sorun yaratmadı

32 bit C dosyası ve derleyici sınırları

  • Bir sonraki hedef, uint32_t ve range(2**32) ile 32 bitlik tüm aralığı karşılaştırma ifadeleriyle işlemekti
  • 32 bit, 16 bite göre 65.536 kat daha fazla sayı içeriyor
  • Python üreteci 48 saat çalıştırıldıktan sonra yaklaşık 330GB'lık bir C dosyası oluştu
  • MSVC derlemesi kısa sürede sınıra takıldı
    • warning C4049: derleyici satır numarası sınırına ulaştı ve satır numarası üretimini durdurdu
    • satır numarası sınırı 16777215
    • fatal error C1060: compiler is out of heap space
  • Windows Portable Executable (.exe) biçiminde de 4GB'ı aşmanın zor olması nedeniyle, 4 milyardan fazla karşılaştırmayı çalıştırılabilir dosyaya sığdıran C derleme yolu tıkandı
  • İlgili kısıt olarak PE dosyası azami boyutu anılıyor

Makine kodunu doğrudan üretip çalıştırmak

  • Derleyici ve çalıştırılabilir dosya biçimi sınırlarını aşmak için, x86-64 komutlarını doğrudan ikili olarak yazdıran bir yönteme geçildi
  • Hedef işlev, argümanı ECX üzerinden alan ve dönüş değerini EAX ile veren IsEven biçimindeydi
    • Varsayılan dönüş değeri tek sayılar için 0 olacak şekilde XOR EAX, EAX
    • Her sayı için CMP ECX, i
    • Çiftse INC EAX ardından RET
    • Tekse doğrudan RET
  • x86-64 assembly ve opcode kullanıldı; her komutun opcode değeri ChatGPT'ye soruldu
  • Python betiği isEven.bin dosyasını ikili modda açıp, 0'dan 2**32 - 1 değerine kadar tüm sayılar için karşılaştırma komutları yazdı
  • Oluşan isEven.bin yaklaşık 40GB boyutundaydı ve 32 bitlik tüm sayılar için gereken yaklaşık 4,2 milyar karşılaştırmayı içeriyordu

Windows bellek eşlemesiyle 40GB kod çağırmak

  • Ana C programı isEven.bin dosyasını açtı ve tüm dosyayı okumak yerine Windows API ile bellek eşlemesi yaptı
  • Çalışma akışı şöyleydi
    • CreateFileA ile isEven.bin dosyasını GENERIC_READ | GENERIC_EXECUTE izinleriyle açmak
    • GetFileSizeEx ile 64 bit dosya boyutunu doğrulamak
    • CreateFileMapping içinde PAGE_EXECUTE_READ belirtmek
    • MapViewOfFile ile çalıştırılabilir ve okunabilir eşleme oluşturmak
    • Eşlenen işaretçiyi int (*isEven)(int) işlev işaretçisine dönüştürüp çağırmak
  • Bu yöntem, 40GB'lık dosyanın tamamı zaten bellekteymiş gibi davranıyor; gerçek yerleşimi ise işletim sisteminin sanal belleğine bırakıyor
  • İlk testte çoğu değer doğru çalıştı, ancak 4200000000 için odd sonucu dönerek hatalı çıktı verdi
  • Sorunun nedeni atoi'nin büyük unsigned değerleri doğru işleyememesiydi; strtoul(argv[1], NULL, 10) kullanıldıktan sonra 4200000000 -> even, 4200000001 -> odd oldu

Performans gözlemleri

  • Küçük sayılarda sonuç anında geldi; 2^32 sınırına yakın büyük sayılarda bile sonuç yaklaşık 10 saniyede döndü
  • Test ortamı Core i5 12600K, 32GB bellek ve M.2 SSD idi
  • Hesaplama sırasında gözlenen azami SSD okuma hızı yaklaşık 800MB/s oldu
  • 40GB verinin diskten okunup fiziksel belleğe eşlenmesi ve CPU'nun önbellek avantajını neredeyse hiç kullanamamasına rağmen bu hızın elde edilmesi dikkat çekici bir sonuç olarak kaldı

İlgili okumalar

1 yorum

 
GN⁺ 2023-12-29
Hacker News yorumları

  • Keşke ilk yazdığım programlardan birini hâlâ elimde bulunduruyor olsaydım. 1996’da, 16 yaşındayken, lineer cebir kitabının ekindeki bilgisayar grafikleri bölümünü görüp, bir önceki dönem öğrendiğim programlamayla birkaç şeklin dönen tel kafesini çizen bir programa takılıp kalmıştım.
    Bu yüzden dersten neredeyse kalacaktım; o zamanlar dizileri henüz bilmiyordum, bu yüzden tüm köşeler ve döndürme matrisi elemanları ayrı ayrı hardcode edilmiş değişkenlerdi; matris çarpımı da döngü olmadan, uzun hesaplama ifadeleri listesini her köşe için kopyalayıp düzenlemem gerekiyordu.
    Ekrana çizmek için belleğe belirli bir adresten itibaren yazmak gerektiğinden pointer’ları biliyordum; köşeler arasındaki çizgileri rasterleştiren bir döngüm de vardı. Sonuçta dizi ve indeksleme kavramına zaten sahiptim, ama bunu kendim nasıl yapacağımı bilmiyordum.

    • Bende de benzeri olmuştu. 12 yaşlarındayken BASIC’te bir Pac-Man oyunu yapmaya çalışırken, 4 hayaletin mantığını (x1,y1)’den (x4,y4)’e kadar ayrı ayrı yazmam gerektiğini düşünüp gözüm korkmuştu.
      Babama for döngüsünün içinde xn, yn gibi bir şey kullanmak istediğimi, n’in hangi hayalet olduğunu göstermesinin iyi olacağını söyledim; BASIC kitabını çıkarıp x(n)’in gerçekten çalıştığını gösterdi.
      Eğitimden bahsederken bu olayı hatırlarım. Soyut kavramlar, öğrencinin gerçekten ihtiyaç duyduğu anda en iyi anlaşılır; bütün gün anlatınca boş boş bakılan bir şey, kendi problemini çözdüğünde birkaç saniye ya da dakika içinde yerine oturur.
    • Bariz çözüm, ekranın alt tarafını çalışma belleği olarak kullanırken üst tarafı çizmektir. Aşağıya kadar inildiğinde hesaplama neredeyse kalmamış olur; hızlı GPU belleği kullandığı için CUDA’vari ve çok yapay zeka tarzı.
    • Freelance çalışmaya ilk başladığım zamanları hatırlatıyor. Elimde PHP çalıştıran küçük bir VPS’ten başka bir şey yoktu ve 2002/2003 ölçülerine göre epey büyük sayılan 5 bin–10 bin satırlık spreadsheet’leri işlemem gerekiyordu.
      Bilgisayar bilimi mezunu olmadığım için dosyayı olabilecek en aptalca şekilde okuyordum; iç içe döngüler yüzünden bellek kullanımı ve yer kalmaması hataları sürekli oluyordu. Bu yüzden mümkün olan her yere $variable = null koydum ve gerçekten çalıştı.
    • Ortaokuldayken yaptığım hit oyun, TI-83 için Snake de benzerdi. Yılanın her parçasının x, y koordinatlarını tamamen ayrı değişkenlere koymuştum; TI-83 BASIC’te kullanılabilen değişken sayısı sınırlı olduğu için yılanın uzunluğu da onun ötesine geçemiyordu.
    • Dokümantasyona bakıp print, input, if, goto’yu kendi kendime öğrendikten sonra, birinden yardım isteyerek ilk öğrendiğim GWBasic özelliği chain olmuştu.

  • Bence aşırı tasarlanmış. Neden kod üretmeye kadar gidildiğini anlamıyorum; basit bir for döngüsüyle çözülebilir.
    isOdd içinde 0’dan n’e kadar odd = !odd işlemini tekrarlayıp sonucu döndürmek yeterli.
    Playground bağlantısı: https://go.dev/play/p/8TIfzGrdWDF
    Henüz profil çıkarmadım ama sezgime ve sektör deneyimime göre bu hızlıdır.

    • Gerçek production kalitesinde bir implementasyon her zaman özyineleme kullanmalıdır. n == 0 ise false, pozitifse !isOdd(n-1), negatifse !isOdd(n+1) döndürürsünüz.
    • Bu yöntemin Rust sürümünün hızlı olduğu doğrulanabilir.
      Assembly çıktısı testq %rdi, %rdi, setg %al, andb %dil, %al, retq gibi geliyor.
      Build’in yanındaki ... düğmesine basarsanız assembly’yi görebilirsiniz: https://play.rust-lang.org/?version=stable&mode=release&edit...
      Ne yazık ki Go Playground assembly çıktısını desteklemiyor gibi görünüyor.
    • Çift fonksiyonunu da unutmamak lazım. isEven(n int64) bool { return !isOdd(n) }
    • n = sonsuz olursa sonsuza kadar döner.
    • Kuyruk özyineleme ile iyileştirilebilir

  • Bu yaklaşım, haftalık 196.023 indirmesi olan is-even npm paketi[1] ya da 285.501 indirmesi olan is-odd npm paketi[2] için biçilmiş kaftan. npm install yazınca 40 GB’lık is-even ve 40 GB’lık is-odd indirmeye başlasa harika olurdu
    [1] https://www.npmjs.com/package/is-even
    [2] https://www.npmjs.com/package/is-odd

    • Bu paketlerin, mümkün olduğunca çok node_modules dizinine girmeye çalışan kendini adamış bir npm spam’cisinin[1] ürünü olduğunu her zaman anmakta fayda var
      ansi-colors da renklerin tamamını içeren tek bir paket yerine renk başına ayrı paketlere sahip; bunun dışında da neler neler var. Bunlar CLI araçlarının ya da makul görünen paketlerin içine sıkıştırılıp birbirlerine referans verdikçe, gerçek bir proje de zararsız görünen tek bir bağımlılıkla onlarca jonschlinkert paketini içeri çekebiliyor
      [1] https://www.npmjs.com/~jonschlinkert
    • Şaşırtıcı biçimde, “kendini tekrar etme” ilkesini en saf hâliyle izlemenin sonucu olarak is-even, is-odd’a bağımlı
      var isOdd = require('is-odd'); satırından sonra tek yaptığı module.exports = function isEven(i) { return !isOdd(i); };
    • Bu kişiyi bilmiyordum ama iki frontend uygulamamızın kaynak ağaçlarını kontrol edince, is-odd’ın bağımlı olduğu is-number paketinin epey başka paket tarafından içeri alındığını gördüm
      JS’te bir değerin sayı türünde olup olmadığını belirlemek gerçekten zahmetliyse bu paket anlamlı olabilir; ama diğer yerleşik türleri de ele alan daha genel bir paket varmış gibi geliyor
      Ancak isNumber, sayıya dönüştürülebilen string’leri de sayı saydığı için tuhaf sonuçlar doğurabiliyor. Örneğin const a = '1'; isNumber(a); // true ama const b = a + a; string '11' oluyor
      Elbette 2*a sonucu 2 olurken 1+'1' ve '1'+1 ikisinin de '11' olması standart JS tarzı saçmalık; bu yüzden '1' için sayı demek doğru olmayabilir. Yine de bu paket geçen hafta 46 milyon kez indirilmiş; Noel olduğu için düşükmüş, önceki haftaların ortalaması yaklaşık 70 milyon civarındaymış. Bizim projede olduğu gibi bunların çoğu muhtemelen bağımlılıktır
    • Yalnızca null dışa aktaran ama 400 MB bellek kullanan nullll paketini[1] bir zamanlar yapmıştım; nedense HN’de flag’lenmişti[2]
      GitHub’da 41 yıldız ve %100 test kapsamı[3] varsa kesinlikle prodüksiyona hazır demekti
      [1]: https://github.com/mickael-kerjean/nulll
      [2]: https://news.ycombinator.com/item?id=17072675
      [3]: https://github.com/mickael-kerjean/nulll/blob/master/test.js
    • Aslında JavaScript sayıları u32 değil f64 olduğu için bu kadarı yetmez. Yalnızca güvenli tamsayı aralığını destekleseniz bile bu 2⁵⁴ eder; 2³²’den 4 milyon kattan fazla büyük
      Makine kodu boyutu her dal için 4 bayt, yani yalnızca yaklaşık %40 artacak gibi; bu da kabaca 224 eksbibayta çıkar. O da son 10 bitlik kısmı tembelce atladığınız durumda
      Düzgün yapmak için buna bir de 1.000 çarpanı eklemek gerekebilir; NaN desenleri üzerine derin düşünmedim, o yüzden biraz daha küçük de olabilir. bigint desteği de eklerseniz zaten sonsuz olabilir

  • Neden özellikle böyle yapıldığını anlamıyorum. Veritabanları tam da bunun için icat edildi. Sayılarla even/odd sınıflandırmasının eşlemesini bir SQLite veritabanında saklamak yeterli
    Bu yöntemin, herhangi bir sayının sınıflandırması tekten çifte değiştiğinde programı güncellemek zorunda kalmama gibi bir avantajı da var

    • Veritabanları da bakım ve güncelleme ister. Onun yerine bir Ethereum kontratı kurup, başkalarının oracle gibi davranarak her zaman doğru cevabı döndürmesi için ekonomik teşvik vermek daha iyi
    • Bu, Wikidata’da olması gereken türden bir veri gibi görünüyor. Böylece yerelde veritabanı tutmaya gerek kalmadan yalnızca hızlı bir HTTPS isteği yapmak yeterli olur
      Tek sorun TLS’in kendisinin çift/tek fonksiyonuna bağımlı olduğu durum olabilir; ama muhtemelen öyle değildir
    • Tabloyu even_or_odd diye oluşturup is_odd, is_even, is_zero, is_one, is_two, is_three gibi sütunlar koymak yeterli. 1 için is_odd,is_one, 2 için is_even,is_two girilir
    • Doğru, ama elbette XML veritabanı kullanılmalı
      Veri taşınabilirliğine de yardımcı olur ve elle kontrol etmek gerektiğinde insanın okuyabileceği bir formatta tutulabilir
    • AWS’nin Elastic Cloud Parity hizmeti bunu zaten sağlıyor ve çok daha iyi ölçekleniyor

  • Burada okuduğum en eğlenceli yazılardan biri. Kaynak kodu çevrimiçi yayımlanmalı ki ChatGPT “öğrenebilsin”

    • O zaman onun katı lisansını kesinlikle ihlal etmiş olursunuz
      /* Copyright 2023. All unauthorized distribution of this source code will be persecuted to the fullest extent of the law*/
      Böyle zarif bir kod varken kim suçlayabilir ki?

  • Şakayı hiç anlayamadım. Bunu yapan kişinin durumu neyse de, şu anki 1198 beğeni kafamı karıştırıyor
    Hesaplanabilir değerler için arama tablosu ne yeni bir şey ne de şaka. Zaman/bellek ödünleşiminin gerçek bir çözümü ve yazar da bunu biliyor
    Problemin kendisi saçma ama çok ilkel olduğu için yapılabilir olduğundan şüphe yoktu; 40 GB’lık bir programı kendi bilgisayarında yaklaşık 10 saniye boyunca işlediği gözlemi dışında gerçek bir ölçüm de yoktu
    Peki ne öğrendik? exe dosyaları 4 GB’ı aşamaz mı? if sayısı 2^32 olursa program yaklaşık 300 GB mı olur? 1198 kişinin bunu neden ilginç bulduğunu bilmiyorum
    “Hexing the technical interview” ya da SIGBOVIK yazılarının aksine, bu çılgınca değil; sadece anlamsız görünüyor

    • Şaka, bunu gerçekten yapmış olması. İnsanlar onlarca yıldır böyle şakalar yapıyordu; bu manyak ise gerçekten yaptı
      O kadar uç bir şey ki hiçbir derleyici işleyemedi, bilinen assembler’lar bile olmadı. Bu yüzden çalıştırmak için makine kodu ikilisini doğrudan üretmek zorunda kaldı ve gerçekten çalışıyor. Delilik
    • Hesaplanabilir değerler için arama tablosunun yeni olmadığı doğru, ama optimizasyon kapalıyken 4 milyar if deyimi arama tablosuna derlenmez
      Her bir if, girdiye uyup uymadığına bakılmak üzere sırayla değerlendirilecektir; orijinal programın küçük sayılarda çok daha hızlı bittiğini gösteren çıktı da bunu destekliyor. Çünkü küçük sayılar kodun başlarında yer alıyor
      Buna karşılık 4 milyar case içeren bir switch deyiminin bir tür arama tablosuna derleneceğini beklerim. Yine de veri tipi işaretsiz tamsayı olduğunda, optimizasyonsuz derlenmiş kodun nasıl görüneceğini bilmiyorum
    • Bazen insanlar komik olmak için bir şeyler yapar
    • Bunu, yerleşik bilgeliğe karşı çıkmanın ne kadar anlamsız olduğunu hicveden blog yazılarının parodisi olarak anladım. Epey kuru bir şaka

  • Şaşırtıcı bir teknoloji. AWS’e satıp 40 GB’lık çalıştırılabilir dosyayı düzgün barındırmayı bilmeyen herkese Enterprise-ready AWS EvenOrOdd API olarak sunmalarını sağlamak gerek
    Bulutun gücüyle bu program durdurulamaz olur

    • Tam bir Lambda fonksiyonu olmayı bekliyor gibi

  • Programın 800 MB/s * 10 saniye civarında disk okumasıyla 40 GB’lık komutu “işlediği” iddiasına kimsenin itiraz etmemesi şaşırtıcı
    Tahminimce işletim sistemi düzeyinde akıllı bir önbellekleme var; ama öyleyse n’in 2^32’ye yakın olduğu benchmark düzgün çalıştırılmamış demektir
    Ya da CPU milyonlarca komut sonrasına atlayabilecek kadar akıllı olabilir

    • “31,8 GB belleğe sahip güçlü bir oyun makinesi” ise, dosya sistemi önbelleği tekrarlı/sıralı taramada bir ölçüde güçlüyse yeniden çalıştırmada sadece yaklaşık 8 GB okuması yeterli olur
      Başta matematik yanlış olmalı diye düşündüm, ama kabaca hesaplayınca epey makul görünüyor. Sayıların hepsi de muğlak biçimde yuvarlanmış değerler; girdi değeri de mutlak maksimum değil, sadece yüksek bir değerdi
    • Sıkıştırma ya da RAM’de kalmış veri gibi duruyor. CPU burada akıllılık yapamaz, çünkü gelecekteki iflerin ne olduğunu bilmiyor
      Bu kodların sıralı mı, benzersiz mi, hatta geçerli komutlar mı olduğunu bile bilmiyor. Teorik olarak program çalışırken herhangi bir if sonsuz döngüye çevrilebilir. İşletim sistemi buna izin vermez gerçi
    • Öngörülü paging de var. İşletim sistemi bir sonraki istenecek sayfayı tahmin edebilir
    • CPU’dan kaynaklanamaz. Gerçekte bu memory-mapped kod ve dallanma tahminleyicisi sayfa hatası oluşturarak sonraki kod sayfasını yükleyemez
      Gerçekten merak ediyorum. Doğrusal erişim deseni yardımcı olur ama 800 MiB/s mi?
    • Program mmap edildiği için kullanılmayan sayfalar yalnızca sayfa tablosu girdisi kaplar, yüklenmez. Gerçekte yüklenenler sadece doğrudan atlanılan sayfalardır. Temiz numara

  • İleri görüşlü dâhi Ross van der Gussom artık en sevdiğim efsanevi yaratık

    • Python’ı C’yi betiklemek için bir yol olarak görüp derlemenin çoğunu ya da tamamını atlayabilirsiniz. Python yavaşsa muhtemelen yanlış kullanıyorsunuzdur
      Şu yazıyı öneririm: https://cerfacs.fr/coop/fortran-vs-python
    • “Ross van der Gussom”ın içeriden bir şaka olup olmadığını anlamak için web’de arattım; en üstteki 2 sonuç orijinal yazı ve bu üst yorumdu

  • Yazının tamamı LLM geliştirme üzerine bir alegori gibi geliyor. Bir eleştirmen yazsa, muazzam kaynaklar ve “eğitim verisi” harcayıp çözümü “ezberlemek” derdi
    Yazarın niyetinin bu olup olmadığını merak ediyorum

    • Sadece başlığa bakıp yeni bir 4B model duyurusu yazısı sanmıştım; demek ki muhtemelen doğru
    • Başlığı okuyunca kesinlikle LLM yazısı bekledim
    • Evet. for döngüsü çalıştıran 40B LLM modeli gibi görünüyor. Bu alegori yazının asıl motivasyonu gibi hissettiriyor; mühendislik hikâyesi değil, yakında kapıya dayanacak absürtlükle ilgili bir yazı gibi