En Hızlı Branchless Binary Search

 (mhdm.dev)
1 puan yazan GN⁺ 2023-08-13 | 1 yorum | WhatsApp'ta paylaş
  • sb_lower_bound, std::lower_bound ile aynı arayüzü korurken, karşılaştırma dalı koşullu taşıma (cmov) olarak derlendiğinde standart binary search’e göre 2 kata kadar daha hızlı sonuçlar gösteriyor
  • Binary search’te karşılaştırma sonucunda arama konumu önceden bilinemediği için branch prediction hataları sık yaşanıyor; x86’da clang -mllvm -x86-cmov-converter=false seçeneği bunu azaltmaya yardımcı oluyor
  • Bu uygulama, her döngüde length değerini yarıya indiriyor ve karşılaştırma sonucuna göre yalnızca first değerini güncelleyerek komut sayısını azaltıyor; 2^k <= n < 2^(k+1) aralığında her zaman k+1 karşılaştırma yapıyor
  • clang -cmov benchmark’ında ortalama çalışma süreleri std::lower_bound için 61.30ns, sb_lower_bound için 33.24ns, bb_lower_bound için 32.73ns oldu; geometrik ortalamalar da sırasıyla 39.17ns, 19.81ns ve 21.33ns ile büyük fark gösterdi
  • Karşılaştırma fonksiyonunun yavaş olduğu 8 baytlık string aramalarında std::lower_bound’un biraz önde olduğu durumlar vardı; büyük dizilerde ise prefetching eklenen varyant, std::lower_bound’dan ortalamada yaklaşık 2.3 kat daha hızlıydı

sb_lower_bound’un temel yapısı

  • sb_lower_bound, std::lower_bound ile aynı biçimde bir C++ fonksiyonudur
    • Girdileri first, last, value, comp
    • Dönüş değeri, karşılaştırmanın ilk kez başarısız olduğu konumdaki iterator’dır; tüm elemanlar koşulu sağlıyorsa last döndürür
  • Temel döngü length değerini yarıya indirir ve yalnızca comp(first[length], value) doğru olduğunda first değerini ileri taşır
  • Burada “branchless”, if’in ortadan kalktığı anlamına değil, ilgili if’in koşullu jump yerine cmov gibi koşullu taşıma komutuna derlendiği duruma işaret eder
  • clang’de -mllvm -x86-cmov-converter=false seçeneği kullanılırsa bu biçim koşullu taşımaya derlenebilir

std::lower_bound’un yavaşladığı nokta

  • Standart binary search, ortadaki elemanı value ile karşılaştırdıktan sonra sol veya sağ aralığı seçer
  • Aranan hedefin konumu bilinmediğinde if (comp(first[half], value)) genellikle tahmin edilmesi zor bir branch haline gelir
  • CPU, branch prediction ile sonraki komutları önceden çalıştırır; ancak tahmin yanlışsa yapılan işi atmak zorunda kalır
  • Koşullu taşıma kullanıldığında, karşılaştırma sonucuna göre değer seçilirken koşullu jump’lar azaltılabilir
  • clang -cmov, std::lower_bound içindeki bazı if/else yapılarını da koşullu taşımaya çevirebildiği için yaklaşık %25 hızlanma sağladı
  • gcc’de aynı durumda koşullu taşımayı zorlayan iyi bir seçenek yoktur ve sb_lower_bound da mevcut optimizasyon seviyesinden bağımsız olarak branchless kod üretmez

Karşılaştırma sayısı açısından “optimal” arama

  • Buradaki “optimal”, karşılaştırma sayısı en az olan binary search anlamına gelir
  • Boyutu n olan bir listede std::lower_bound için olası sonuçlar, n adet eleman konumu ve 1 adet son konum olmak üzere toplam n+1 adettir
  • Liste boyutu 2^k - 1 ise olası sonuç sayısı 2^k olur ve her karşılaştırma doğru/yanlış biçiminde 1 bit bilgi verdiğinden optimal karşılaştırma sayısı k olur
  • Uzunluğu 2^k - 1 olan “nice” durumlarda çok kısa bir döngüyle optimal arama mümkündür
  • Uzunluk uygun değilse, [0, 1, 2, 3, 4, 5] içinde value 4 olduğunda olduğu gibi aralık dışı erişim oluşabilir

sb_lower_bound’un performans özellikleri ve sınırlamaları

  • sb_lower_bound, uzunluğu çift olan bir aralığı bölerken karşılaştırma sonucu doğru olsa bile bazı durumlarda yeterince fazla elemanı atlamaz
  • 2^k <= n < 2^(k+1) aralığında her zaman k+1 karşılaştırma yapar
  • Aynı aralıkta std::lower_bound, k veya k+1 karşılaştırma yapar ve ortalama olarak yaklaşık log2(n+1) kez karşılaştırır
  • Karşılaştırma sayısı daha fazla olabilir; ancak döngü içindeki komut sayısı çok daha az olduğu için toplam çalışma süresi daha hızlı çıkar
  • Karşılaştırma fonksiyonu çok yavaşsa k+1 ile log2(n+1) arasındaki fark performansı etkileyebilir
  • gcc’de koşullu taşımayı zorlamak için x86’ya özel inline assembly ile cmov kullanmak mümkündür; ancak basit yaklaşım komut sayısını artırır, alternatif yaklaşımda ise her tip için ayrı assembly yazmak gerekir

Daha hızlı varyant: bb_lower_bound

  • bb_lower_bound, uzunluk 2^k - 1 biçimine gelene kadar aralığı farklı bir yöntemle böler, ardından hızlı ikinci döngüyle arama yapar
  • length & (length + 1), uzunluğun 11..1 biçiminde, yani 2^k - 1 olup olmadığını belirlemek için kullanılır
  • Normal olmayan uzunluklarda “nice” bir aralığa hızla yaklaşmak için auto step = length / 8 * 6 + 1 şeklinde bir MAGIC değer kullanılır
  • Hızlı döngüye sık geçebilmek için step genellikle length / 2 veya daha büyük olmalıdır; ancak length değerine çok yakın olursa binary search’ün avantajı kaybolur
  • break nedeniyle bb_lower_bound branch içeren bir biçime dönüşür
  • Tüm uzunluklar için en hızlı step değerlerini önceden hesaplanmış bir tabloda kullanma yaklaşımı henüz keşfedilmemiş bir yol olarak duruyor

Tamamen branchless uygulama daha hızlı olmadı

  • 64 bit makinelerde sb_lower_bound döngüsü en fazla 64 kez yinelendiği için, switch ve kasıtlı fall-through kullanarak length kontrolünü de kaldıran “tamamen branchless” bir sürüm yapılabilir
  • Bu yaklaşım, std::bit_width(length) ile gereken karşılaştırma sayısı kadar kod konumuna atlayan bir yapıdır
  • Gerçek performans daha hızlı çıkmadı
  • Modern x86 CPU’lar döngü koşulu gibi tahmin edilebilir branch’leri iyi işlediğinden, length kontrolünü kaldırmanın faydası olmadı
  • Template, makro ve 64 case’in kopyalanıp değiştirilmesinden kaçınılabilmesi açısından da standart döngünün daha iyi olduğuna karar verildi

Benchmark sonuçları

  • Ortalama çalışma süresi (ns) açısından clang -cmov temelindeki sonuçlar şöyleydi
    • std::lower_: 61.30
    • branchless_lower_: 43.43
    • asm_lower_: 54.32
    • sb_lower_: 33.24
    • sbm_lower_: 35.54
    • bb_lower_: 32.73
  • Geometrik ortalama çalışma süresinde (ns) de sb_lower_ en düşük değere sahipti
    • std::lower_: 39.17
    • branchless_lower_: 25.14
    • asm_lower_: 31.21
    • sb_lower_: 19.81
    • sbm_lower_: 20.91
    • bb_lower_: 21.33
  • sbm_lower_bound, if yerine first += comp(first[length], value) * (length + rem) biçimini kullanarak gcc’nin koşullu taşıma üretmesini teşvik eden bir varyanttır
  • Bu optimizasyon sonraki gcc sürümünde kaybolabileceğinden yorum ve dikkat gerektirir
  • Benchmark komutlarında g++-10, clang++-10, clang++-10 -mllvm -x86-cmov-converter=false kullanıldı ve -march=haswell eklendi
  • -march=native veya -march belirtilmemesi sıralamayı belirgin biçimde etkilemedi; testler Intel i7 Kaby Lake üzerinde yürütüldü

Branch prediction hatası ölçümü

  • perf ile ölçülen standart clang çalıştırması yaklaşık 6.94 milyar branch ve yaklaşık 1.20 milyar branch-miss kaydetti; branch-miss oranı %17.34 oldu
  • clang -cmov çalıştırması yaklaşık 4.07 milyar branch ve yaklaşık 35.95 milyon branch-miss kaydetti; branch-miss oranı %0.88’e düştü
  • -cmov, yaklaşık 2.9 milyar branch’i ve yaklaşık 1.2 milyar branch hatasını ortadan kaldırdı
  • Ortadan kaldırılan branch’ler yaklaşık %41 olasılıkla yanlış tahmin edilen branch’lerdi
  • Bu değer, tamamen tahmin edilemeyen branch’lerde beklenebilecek %50’ye yakın bir değerdir

Yavaş karşılaştırma fonksiyonlarında sonuç değişiyor

  • Karşılaştırma fonksiyonunun daha yavaş olduğu durumu görmek için 8 baytlık string araması test edildi
  • Ortalama çalışma süresinde (ns), std::lower_bound sb_lower_bound’dan biraz daha hızlı veya ona yakındı
    • gcc: std::lower_ 160.01, sb_lower_ 165.66
    • clang: std::lower_ 157.71, sb_lower_ 162.68, bb_lower_ 157.22
    • clang -cmov: std::lower_ 156.06, sb_lower_ 164.71, bb_lower_ 157.48
  • Bu durumda std::lower_bound, sb_lower_bound’dan çok az ama tutarlı biçimde daha hızlıdır
  • Bir kütüphane, ham tipler üzerinde doğrudan çalışırken sb_lower_bound kullanıp diğer durumlarda std::lower_bound kullanarak en iyi performansı hedefleyebilir

Assembly’de görülen farklar

  • std::lower_bound’un clang -cmov hot loop’u cmova, cmovbe gibi koşullu taşıma komutları içerir; ancak uzunluk ve konum güncellemesi için birden fazla komut kullanır
  • sb_lower_bound’un hot loop’u yarım uzunluğu, kalanı ve taşınacak pointer’ı hesapladıktan sonra cmova ile first değerini günceller
  • branchless_lower_bound’un assembly’si çok kısa ve temizdir; ancak performans testlerinde sb_lower_bound daha düşük overhead ile daha iyi sonuç verdi

Güncelleme: kısaltılmış sb_lower_bound

  • orlp.net yazarı tarafından yapılan yorumdan sonra sb_lower_bound, hot loop assembly komut sayısını 9’dan 8’e düşürecek şekilde refactor edilebilir
  • Temel nokta, length - half değerinin half + length % 2 ile aynı olmasıdır
  • Refactor edilmiş biçim half = length / 2 değerini hesaplar; karşılaştırma doğruysa first += length - half yapar, ardından length = half olarak günceller
  • clang -cmov ile ortalama çalışma süresi yaklaşık 33ns’den yaklaşık 32ns’ye küçük bir iyileşme gösterdi

Büyük dizilerde prefetching etkili

  • Yorumlarda önerilen prefetching, gerekli belleği önceden L1/L2 cache’e getirerek gerçek erişim sırasındaki gecikmeyi azaltma yöntemidir
  • Örnek gecikmeler L1 için yaklaşık 4 cycle, L2 için yaklaşık 12 cycle, L3 için yaklaşık 40 cycle, bellek için yaklaşık 200 cycle’dır
  • Hem gcc hem de clang __builtin_prefetch() destekler
  • length / 4 konumunu prefetch etmek 2 erişimden 1’ini boşa harcar; buna length / 8 de eklenirse 6 erişimden 5’i boşa gider
  • Prefetch konumunun hesaplanması ve çağrının kendisi de overhead oluşturur; kısaltılmış hot loop’ta bu maliyet önemlidir
  • Çeşitli prefetch stratejileri 256KB’den küçük dizilerde fayda sağlamadı
  • 256KB ve üzerindeki dizilerde prefetching eklenmiş sbp_lower_bound, yaklaşık 4 milyon entry’ye, yani 16MB’ye kadar olan testlerde ortalama çalışma süresini yaklaşık 32ns’den yaklaşık 26ns’ye iyileştirdi
  • Daha sonra yaklaşık 128 milyon entry’ye, yani 512MB’ye kadar genişletilen testlerde prefetch sürümü, std::lower_bound’a göre ortalama süre bazında yaklaşık 2.3 kat daha hızlıydı
    • Karşılaştırma ölçütü std::lower_bound için yaklaşık 161ns, prefetch sürümü için yaklaşık 71ns idi

Büyük veri kümelerinde gözlemler ve alternatifler

  • Çok büyük boyutlarda clang -cmov tarafından üretilen branchless std::lower_bound, branch içeren sürümden daha yavaştı
  • Modern CPU’lar tahmin edilmiş branch’i izleyerek bellek yüklemeleri ve speculative execution yapabilir; bu da fiilen prefetch gibi çalışabilir
  • sbpm_lower_bound, sbm_lower_bound’a prefetching eklenmiş sürümdür ve gcc’nin branchless kod üretmesini teşvik etmek için boolean çarpımı kullanır
  • 1 milyon ile 10 milyon eleman arasında performans grafiğinde sıçramalar olduğu için teorik olarak daha hızlı bir uygulama alanı vardır
  • Ancak prefetching kodu giderek karmaşıklaşır ve magic constant sayısı artar; karmaşıklık yükseldikçe gcc/libstdc++ veya llvm/libc++’a katkı olarak kabul edilme olasılığının düştüğü düşünülüyor
  • std::lower_bound kısıtlarını aşan bir alternatif olarak Eytzinger Binary Search vardır; giriş dizisini binary orta değer heap’i biçiminde yeniden düzenleyerek cache dostu arama yapar
  • Sergey Slotin’in CppCon 2022 int 16-ary tree testinde std::lower_bound’dan 7 ila 15 kat hızlı sonuçlar elde edildi

Kod ve kullanım koşulları

  • Arama veya karşılaştırma programın en yavaş kısmıysa ve işlemcinin karşılaştırma sonucunu tahmin etmesi zorsa x86’da clang’in -mllvm -x86-cmov-converter=false seçeneği denenebilir
  • Daha hızlı binary search gerekiyorsa sb_lower_bound denenebilir; gcc için sbm_lower_bound da bir seçenektir
  • Kod MIT lisansıyla yayımlanmıştır
  • Kod ve benchmark’lara github.com/mh-dm/sb_lower_bound/ adresinden ulaşılabilir

İlgili okumalar

1 yorum

 
GN⁺ 2023-08-13
Hacker News yorumları

  • İnsanların dallanmayı ortadan kaldırmayı denediğini her gördüğümde, dallanma tahmin hatasının uzun bir işlem hattını durdurmasına yol açan yapının CPU mimarisinin zorunlu bir unsuru olmadığının farkında olup olmadıklarını merak ediyorum.
    İşlem hattının uzun olmasının nedeni, yürütmeden hemen önce çok sayıda analiz ve dönüşüm yapılması; oysa durum bağımlılığı yüksek bir algoritma da olmadığı için bunların çoğu önceden yapılabilir.
    Transmeta Crusoe CPU bu şekilde çalışıyordu ve dallanmaları dert etmek zorunda kalmadığımız bir dünya hayal edilebilir.
    Daha derine inersek, tüm işlemler bit durumuna bakıp sonucu değiştiren birer dallanmadır; ancak ALU içindeki bu yerel dallanmalar ana işlem hattı üzerindeki dallanmalar olmadığı için performansa büyük zarar vermez.

    • Dave misin? :-) Eskiden superscalar CISC ile uniscalar RISC’i saat başına iş hacmi ve saat başına komut sayısı açısından karşılaştıran bir makale vardı.
      O zamanlar srk’ye de IPC ile iş hacmi arasında hangi metriği seçtiğinin, neyi iyi neyi kötü gördüğünü etkilediğini söylediğimi hatırlıyorum.
      IPC tarafı, daha yüksek IPC elde edilirse üretim sürecinin saat hızını artıracağı ve herkesin kazanacağı görüşünde; iş hacmi tarafı ise Moore yasasının öldüğünü, silikonu daha hızlı çalıştırırsan eriyeceğini, dolayısıyla ISA’yı akıllıca tasarlayan tarafın kazanacağını söyleyen daha gerçekçi bir yaklaşım benimsiyor.
      Son 20 yılda iki taraf da hem başarılar hem de hayal kırıklıkları yaşadı; bugünlerde RISC-V’nin CPU mimarisinde bu sorulara geri dönmesi ilginç.
      Komut kümesinin esnekliği temelinde modern superscalar fikirlerin nasıl eklendiğini izlemek için de iyi bir yer; uzun vadede kazananın bu taraf olacağını düşünüyorum.
    • Bu tamamen yanlış bir fikir.
      Transmeta’nın dönüşümü dallanma maliyetini ortadan kaldırmadı.
      Transmeta’da çalışan Linus’un bir comp.arch başlığında “CPU’nun işi, cache miss’leri mümkün olduğunca hızlı üretmektir” gibi bir şey söylediğini hatırlıyorum.
      Zorunlu cache miss’ler vardır ve hiçbir JIT bunları ortadan kaldıramaz.
      Gerçek dünyada, bugünkü devasa cache’ler olsa bile kapasite kaynaklı miss’lerden de kaçınılamaz.
      Itanium da statik analizle dallanma maliyetinin ortadan kaldırılabileceğini düşünüyordu; sonucunun nasıl olduğunu hatırlamak yeterli.
      Programcıların, modern işlemcilerden daha iyisini kolayca yapabileceklerine güvenle hükmetmeden önce biraz bilgisayar mimarisi kitabı okumasını isterdim.
      Güncel işlemcilere konan zihinsel emeğin ölçeğini en az 7 basamak kadar küçümsediklerini düşünüyorum.
    • Durum olmayabilir ama derleme anında bilinmeyen unsurlara çok bağlıdır.
      Bunlardan biri işlenen girdi verisidir.
      İkili arama tam da böyle bir durumdur; derleyici sonucun hangi konumda bulunacağını bilmez.
      Bir diğeri mikro mimaridir, özellikle cache hiyerarşisi ve yürütme birimlerinin düzeni.
      Mevcut CPU’nun mikro işlemlerine benzeyen komutlara sahip bir ISA’ya geçerseniz, her mikro mimari için yeniden derlemeniz gerekir.
      Ancak bu, teknik olarak mevcut GPU’larda olduğu gibi programların bytecode biçiminde (DXBC, SPIR-V, NVPTX) dağıtıldığı ve kullanıcı modu GPU sürücüsünün bunları gerçek donanım komutlarına yeniden derlediği türden bir OS JIT ile çözülebilir.
      Daha büyük değişken, diğer CPU thread’lerinin bilinmeyen kodlar çalıştırmasıdır.
      Hyper-threading’i kaldırıp çekirdekleri bağımsız hale getirseniz bile L3 cache, harici bellek, I/O bant genişliği, güç ve ısı gibi çip genelinde paylaşılan kaynaklar hâlâ kalır.
    • Bence mesele dallanmanın tanımında yatıyor.
      Her şeyi Branch™ diye yeniden tanımlarsanız, gerçek dallanma olmayan şeyler de dâhil olmak üzere bazı Branch™’ler önceden hesaplanabilir.
      Ama genelde dallanmayı ortadan kaldırma dediğimiz şey, if/else gibi kodlarda hesaplama yolunun gerçekten ayrıldığı durumlarla ilgili değil mi?
      Böyle bir dünyada da faydalı optimizasyonlar mümkün olurdu; fakat bunlar, birden fazla gelecekteki sonucu aynı anda hesaplamaya çalışan Branch™’lerle sınırlı kalırdı.
    • İşlem hattının uzun olmasının nedeni, işlemcinin içinde aynı anda yapılabilecek çok sayıda bağımsız iş bulunması diye de ifade edilebilir.
      Bağımsız olarak yapılabilecek bir işlem olduğunda, onu aynı anda yürütme olasılığı da doğar.
      Sadece decode, fetch ve execute’tan bahsetmiyorum.
      Bağımsız bir ALU ve shifter varsa, toplama yaparken shift de yapabilirsiniz; ayrı bir toplama birimi ve çarpma birimi varsa ikisini aynı anda denememek için bir neden yoktur.
      Bu da birden fazla komutu aynı anda ilerler durumda tutmak istemenize yol açar ve komutları işleme hızından daha hızlı getirip decode edebilmeniz gerektiği anlamına gelir.
      Ayrıca N adet Add komutunun bağımsız bir Shift’i görmesini engellememesi için yeniden sıralama yapmak isteyeceğiniz duruma doğal olarak götürür.
      Mevcut yapının gerekenden fazla karmaşık olduğunu düşünebilirsiniz; haksız da olmayabilirsiniz.
      Yine de bugünkü yapıyı ortaya çıkarmak için muazzam bir mühendislik harcanıyor; bu yol dışında çok daha hızlısının yapılabileceğini düşünüyorsanız, bu iddianın ne kadar doğru olduğunu derinlemesine irdelemek gerekir.

  • “Tüm bunları yazmak için temiz ve hızlı bir bare-metal dil olsaydı…” kısmında yazar “BUT RUST..” ve “BUT ZIG..” dipnotlarını eklemiş, ama Nim nasıl olurdu merak ediyorum
    lowerBound için yerel kütüphane implementasyonu var gibi görünüyor: https://github.com/nim-lang/Nim/blob/version-2-0/lib/pure/al...
    Tam anlamıyla “bare-metal” bir dil değil ama C veya C++’a derlendiği için burada nasıl bir koda derlendiğini görmek ilginç olabilir
    Bir de C’nin sorununun ne olduğunu merak ediyorum

  • Bunun hâlâ lower_bound olup olmadığından pek emin değilim
    Kodu yanlış okumuş olabilirim ama tekrarlar olduğunda ilk eşleşeni değil, herhangi bir eşleşeni döndürüyor gibi görünüyor
    Karşılaştırma fonksiyonu otomatik tamamlama için belirli bir dize önekini arıyorsa, benzersiz bir listede bile birden fazla öğe eşleşebilir; o durumda listedeki en baştaki öğeyi istersiniz

    • Her eşleşmede kalan uzunluğu yarıya indiriyor ve yalnızca uzunluk 0 olduğunda döngüden çıkıyor, dolayısıyla ilk öğeyi döndürmesi gerekir
    • Daha yüksek hız isteyip tam olarak hangi eşleşme olduğu umursanmayan bir seçeneğin olması iyi görünüyor
    • Bana göre en baştaki eşleşen öğeyi döndürüyor
      Neden öyle olmadığını düşündüğünü merak ediyorum

  • Keşke tüm blog yazıları bu yazı gibi başlasa: “Meşgul olduğunuzu biliyorum, o yüzden doğrudan konuya gireceğim. İşte en hızlı, genel ve basit C++ ikili arama implementasyonu”

  • Zig standart kütüphanesi ikili arama için C++ çağırmıyor
    Mevcut ikili arama burada: https://github.com/ziglang/zig/blob/b835fd90cef1447904d3b009...

  • Pek anlayamadım
    İkili aramada dallanma ile ilgili sorun dallanmanın kendisi değil; karşılaştırmayı bitirene kadar diziden bir sonraki hangi bellek konumunun getirileceğini bilmememiz
    Dal kullansanız da başka bir şey kullansanız da, mesele eninde sonunda işlemciden ne yapmasını istediğiniz
    Veri bağımlılığı var
    Orta indeksi okumadan önce üst aralıkta mı, alt aralıkta mı arama yapacağınızı bilemezsiniz
    Tahmin edip iki taraf için de okumaları başlatabilirsiniz; bu bağımlılığı çözer ama bellek trafiğini artırır
    Asıl mesele bunun doğru ödünleşim olup olmadığı; sadece dallanmayı kaldırmak cevap değil

  • Benim Cascade Lake işlemcimde -mllvm -x86-cmov-converter=false, ikili arama performansını neredeyse yarıya düşürüyor
    Sayılar, 100MB’lık uint32 dizisinde bsearch başına nanosaniye
    clang 15.0.7 bu belirli kod optimizasyonunda gcc 13.2.1’den çok daha kötü görünüyor
    Assembly burada görülebilir: https://godbolt.org/z/cbx5Kdjs6
    gcc assembly’si çok daha temiz görünüyor

    Benchmark gcc clang clang -cmov
    slow u32 23.4 46.7 45.8
    fast u32 18.1 19.8 31.4
    • O zaman https://mhdm.dev/posts/sb_lower_bound/#prefetching bölümüne bakmak yeterli
      100MB yeterince büyük olduğu için dallı sürüm biraz avantajlı çıkıyor; daha iyi olduğu için değil, x86’nın spekülatif yürütme özellikleri nedeniyle

  • “BUT RUST” bağlantısının aslında nereye gitmesi gerektiğini bilen var mı?
    Sürüm sabitlenmediği için şimdiden bozulmuş gibi; belki de starts_with dokümantasyon yorumlarının ortasına gitmesi amaçlanmış olabilir

    • Yazı yayımlanmadan hemen önceki [1] ve hemen sonraki [2] archive.org yakalamalarına bakınca, şimdi 2779. satır [3] olan şu kod satırını işaret etmek istedikleri anlaşılıyor
      let mid = left + size / 2;

[1] https://web.archive.org/web/20230602210213/https://doc.rust-...

[2] [https://web.archive.org/web/20230709221353/https://doc.rust-...](<https://web.archive.org/web/20230709221353/…;)

[3] [https://doc.rust-lang.org/src/core/slice/mod.rs.html#2779](<https://doc.rust-lang.org/src/core/slice/mod.rs.html#2779>;)

  • Rust’ın ikili arama uygulamasına bağlantı vermek istemiştim
    https://doc.rust-lang.org/1.71.1/src/core/slice/mod.rs.html#... olarak güncellendi

  • Daha karmaşık comp karşılaştırma işlevlerinde sonucun korunmaması ilginç
    Yazıda ID, telefon numarası, hesap, anahtar kelime gibi karşılaştırma işlevinin yavaş olduğu, nispeten gerçekçi bir ikili arama senaryosu düşünülmüş ve bu yüzden 8 baytlık dizge araması test edilmiş deniyor
    Bu durumda std::lower_bound, sb_lower_bound’dan çok az da olsa tutarlı biçimde daha hızlı; her zaman en iyi performansı almak için kütüphanenin ilkel tipleri doğrudan ele aldığı durumlarda sb_lower_bound, diğerlerinde ise std::lower_bound kullanması gerektiği söyleniyor
    Buradaki analizi görmek isterim

    • Bunun dal tahmini sayesinde birden çok karşılaştırmanın aynı anda boru hattına alınabilmesi ve tahminleyici yanıldığında geri alınabilmesi nedeniyle olduğunu düşünüyorum
      Gerçekten rastgele veri ve girdi söz konusuysa tahminler kabaca yarı yarıya yanlış olur
      CMOV yaklaşımı, karşılaştırma işlevinden sonra veri bağımlılığı nedeniyle tıkanır
      Ortalama olarak dallanmalı yaklaşım aynı anda iki karşılaştırma yapar, CMOV ise bir tane; bu nedenle karşılaştırma süresi dal tahmini hatası cezasını aştığında bir kırılma noktası oluşması beklenir
    • Durum buysa ilkel tipler için çok daha iyi bir ikili arama sürümünün bulunma olasılığı yüksek
      Daha önce SIMD ile kabaca yaptığım bir şey, bellek bant genişliğine takılana kadar std::lower_bound’dan 3 kat hızlıydı: https://github.com/matthewkolbe/ThinkingInSimd/tree/main/alg...
    • Yazıda giriş veri kümesi veya arama anahtarının içeriği hakkında “öngörülemez” denmesi dışında herhangi bir garanti bulamadım
      Tamamen rastgele olduğunu varsayıyorum, ancak bu 8 baytlık dizgeler saf bilgi değilse modern dal tahminleyiciler cmovdan kolayca daha iyi performans gösterebilir

  • unpredictable özniteliği artık cmov dönüşüm geçişini etkiliyor gibi görünüyor
    1 Haziran itibarıyla, muhtemelen clang 17/18’e girecek gibi: https://reviews.llvm.org/D118118