Brute-force süperoptimizasyon, float'un en düşük biti için dallanmasız 4 işlemli formül buldu

Elle değil, aramayla bulunan bir formül

Floating-point kütüphanesi geliştiren bir programcı, elle yazılmış bir yordamı, hiçbir insanın türetmeyi başaramadığı dallanmasız dört işlemli bir formülle değiştirdi — çünkü formül kapsamlı bir bilgisayar aramasıyla keşfedildi. Hacker News ana sayfasında öne çıkan purplesyringa.moe'daki bir gönderiye göre, brute-force enumerable yaklaşık dört dakika sürdü ve geleneksel derleyicilerin hiçbir zaman denemeyeceği bir yeniden yazım ortaya çıkardı.

Sorun

Yordam, f adlı bir float alıyor ve f'deki en düşük set bite karşılık gelen float'u döndürüyor. Basit bit manipülasyonu girdilerin çoğunu hallediyor, ancak açık algoritma ikinin kuvvetlerinde bozuluyor; bu yüzden yazarın özgün Rust uygulaması bunları özel olarak ele almak için koşullu bir dal gerektiriyordu. Gönderide açıklandığı gibi, bu dal iki nedenle istenmiyordu: yaygın durumu yavaşlatıyordu ve dallar yanlış öngörülebiliyordu. Elle tek biçimli bir formül bulma girişimleri sonuç vermedi.

Tüm aday formülleri saymak

Tahmin etmeye devam etmek ya da — yazarın savunmasına göre olanakları gözden kaçırabilen ya da iyi bilinen örüntülere kayabilen — bir dil modeline devretmek yerine izlenen yaklaşım, sabit bir işlem sayısına kadar her ifadeyi saymaktı. Altı işlemlı bir çözüm zaten mevcut olduğundan, yalnızca beş veya daha az işlemlı formüllerin kontrol edilmesi gerekiyordu. Aday işlem kümesi bilinçli olarak küçük tutuldu: tam sayı toplama ve çıkarma, bitwise AND, OR ve XOR ile son konumda bir floating-point çıkarma; karşılaştırmalar da bir olasılık olarak değerlendirildi.

Gönderiye göre kombinatorik yönetilebilir kalıyor: işlemleri seçmenin 7.776 yolu ve parantez yerleşiminin 42 olası konumu var. Her işlemin girdileri ya x değişkeni ya da bir sabit; ve rastgele sabitlere izin vermek yerine yazar, float'un ikili gösteriminin alanlarına — işaret, üstel (exponent) ve mantis sınırlarına — hizalı 64 değerden oluşan bir havuzu özenle seçti. Bu eleme, girdi atama uzayını elle tutulur kılan şey; çünkü kalan kombinasyonların çoğu arama sırasında da budanabiliyor.

Arama nasıl buduyor

İfade kümesi tümevarımlı olarak kuruluyor: n işlemlü formüller, k ve n−1−k işlemlü formüllerin tüm çiftlerinden oluşturuluyor. Yinelenenler, her adayın test durumlarındaki çıktıları karşılaştırılarak eleniyor — süreç sonunda 20 test durumu, ifade başına 80 bayt depolama maliyetiyle. Bu davranışsal tekilleştirme önemli; çünkü iki sabiti herhangi bir sırayla toplamak gibi sözdizimsel olarak farklı ifadeler özdeş değerler üretiyor ve yalnızca bir temsilciyi tutmak sonraki yinelemeleri çarpıcı biçimde ucuzlatıyor — aramanın bütün olarak dakikalar içinde bitmesinin nedeni de bu. Son turda zaman ve bellek tasarrufu için tekilleştirme atlanıyor.

Doğruluk, yazarın çok yavaş bulduğu bir teorem kanıtlayıcı yerine temsili test durumlarıyla kontrol ediliyor. Bir adayda ters örnek bulunursa, bu örnek basitçe test kümesine ekleniyor ve arama yineleniyor.

Sonuç

Arama birkaç geçerli beş işlemlı formül buldu ama kendi modeline göre dört işlemlisi yoktu. Bu modelin kör bir noktası var: bir alt ifadenin her kullanımını ayrı bir işlem olarak sayıyor ve yeniden kullanımı değerlendiremiyor. Her adayı elle inceledikten sonra, en sonuncusu paylaşılan bir ara değere izin veriyor ve dört işleme daralıyordu.

Kazanan hile: mantis bitleri temizlenmiş x olan a'yı hesaplayıp, a eksi x'in ham bitlerini kullanmak. Bu çıkarma, x'in mantis bitlerinin olumsuzlamasına denk geliyor; böylece bir olumsuzlamayı mevcut bir işlemin içine katlıyor ve bir adım tasarruf sağlıyor — yazarın, makine tarafından keşfedilmesi gerçekten şaşırtıcı diye nitelediği bir yeniden yazım. Formül ikinin kuvvetlerinde biraz farklı davranıp işaret bitini ters çeviriyor; yazar bu sapmayı kabul edilebilir buluyor. Kod artık devam eden bir FPU emülatörü çalışmasında yaşıyor.

Neden önemli

Süperoptimizasyon — gönderinin atıf yaptığı Wikipedia tanımına göre, dalsız kod için optimal instruction dizileri bulmak amacıyla derleyici tarzı bir arama kullanmak — ana akım optimizer'ların yapmadığı bir akıl yürütme gerçekleştiriyor: onlar mekanik dönüşümlerde üstündür ama bir probleme yeni bir yaklaşım icat etmeyi nadiren becerirler. Bu anlatım, tekniğin küçük ölçekte pratik olduğunu gösteriyor. İşlem sayısını sınırla, sabit havuzunu özenle seç, gözlemlenen davranışa göre tekilleştir ve ters örneklerle rafine et; sıradan bir makine dakikalar içinde yanıt verir. Bu aynı zamanda gerçek bir sınırlamayı da ortaya koyuyor: ortak alt ifade farkındalığı olmadan yapılan ifade sayımı gerçek optimumu kaçırabilir ve burada makinenin önerdiği adayların kısa bir elle incelemesi düzeltici oldu. Performans açısından kritik sayısal kod için, küçük bir tasarım uzayı üzerinde kapsamlı arama, hem insan zekâsına hem de üretken modellere karşı güvenilir bir alternatif olmaya devam ediyor.