- 1BRC’deki darboğaz, 1 milyar CSV sıcaklık değerini aşırı hızlı ayrıştırmaktı; Quân Anh Mai’nin merykitty SWAR kodu,
if kullanmadan sabit ALU işlemleriyle sıcaklıkları tam sayıya dönüştürdüğü için dikkat çekti
- Bu kod, tek bir
long içindeki 8 baytı aynı anda işleyen SWAR (SIMD Within A Register) yaklaşımını kullanıyor; normal CPU yazmaçlarında birden çok karakteri paralelmiş gibi işliyor
- İşleme akışı eksi işaretini algılama, işareti kaldırma, ondalık noktanın konumunu bulma,
XY.Z hizalaması, ASCII rakam dönüşümü, sihirli çarpma ve işaretin uygulanması şeklinde ilerliyor
- Girdi biçimleri
-XX.X, -X.X, X.X, XX.X olmak üzere dört tane; ondalık noktanın konumuna göre baytlar kaydırılarak farklı uzunluklar aynı bit yerleşimine getiriliyor
- Dallanma ve döngüleri azaltmak yerine ASCII kod özellikleri, ikinin tümleyeni, bit maskeleri ve çarpmanın kaydırma-toplama niteliği yoğun biçimde kullanılarak yüksek performanslı ayrıştırma gerçekleştiriliyor
1BRC’de darboğaz haline gelen sıcaklık ayrıştırma
- One Billion Row Challenge (1BRC) kapsamında CSV dosyasındaki sıcaklık değerlerini çok hızlı ayrıştırmak temel darboğaz olarak öne çıktı
- Önceki optimizasyonlarla bile idiomatik paralel Java kodu 71 saniyeden 1,7 saniyeye kadar hızlandı
- Sıcaklık biçimi basit olsa da 1 milyar değeri 1 saniyenin altında ayrıştırmak için küçük maliyetler bile büyük ölçüde birikir
- Olası biçimler
-XX.X, -X.X, X.X, XX.X
- İlk katılımcılar
Double.parseDouble() kullandı, ancak daha sonra döngüsüz özel ayrıştırıcılar ortaya çıktı
- Quân Anh Mai’nin @merykitty çözümünün bir bölümü,
if olmadan tek dosya okumasıyla çalıştığı için 1BRC’nin üst sıralardaki çözümlerinde standart bir unsur gibi yayıldı
- Kazanan Thomas Wuerthinger, kendi çözümüne katkıda bulunan ekibin bir parçası olarak Quân Anh’ı özellikle belirtti
merykitty kodu ne yapıyor?
- Kod, 8 baytlık CSV girdisini içeren bir
long alıp gerçek sıcaklığın 10 katı olan tam sayı sıcaklık değerini döndürüyor
- Girdi,
mmap edilmiş CSV dosyasından doğrudan yerel bellek okumasıyla geliyor; bu kısım ayrı bir ilgi alanı olarak ayrılıyor
- İşlemler sabit sıradaki 18 ALU işleminden oluşuyor
- Bit kaydırma, AND, NOT, XOR
- Toplama, çıkarma, çarpma
Long.numberOfTrailingZeros()
numberOfTrailingZeros(), JDK derleyici intrinsic’i aracılığıyla özel CPU komutunu kullanıyor- Genel SIMD’ye özel komutlar yerine normal CPU yazmaçları ve komutlarıyla birden çok bayt işlendiği için bu SWAR yaklaşımına giriyor
- Örnek kod, okunabilirlik için özgün halinden biraz değiştirilmiş; özgün kod CalculateAverage_merykitty.java içinde bulunuyor
Tüm işleme adımları
- Kod sıcaklığı şu sırayla ayrıştırıyor
- İlk karakterin
- olup olmadığını kontrol ederek negatiflik durumunu algılıyor
- İşaret karakteri varsa ilgili baytı 0 yapıyor
- Ondalık nokta
. konumunu buluyor
- Rakamlar
XY.Z şablonuna uyacak şekilde long içindeki bitleri kaydırıyor
- ASCII karakterleri gerçek rakam değerlerine çeviriyor
- Her basamağı
1x, 10x, 100x ağırlıklarıyla çarpıp topluyor
- Son olarak işareti uyguluyor
- Dışarıdan bakınca üst düzey bir ayrıştırma problemi gibi görünse de her adım yalnızca ALU işlemleriyle uygulanıyor
1. adım: eksi işaretini algılama
- İşaret algılama şu kodla başlıyor
long negatedInput = ~inputData;
long broadcastSign = (negatedInput << 59) >> 63;
- Açıklama amacıyla sıra değiştirilirse
( ~(inputData << 59) ) >> 63 gibi düşünülebilir
- ASCII’de eksi
- karakterinin 4. biti 0, rakam karakterlerinde ise bu bitin 1 olması özelliğinden yararlanılıyor
- Girdi 59 bit sola kaydırıldığında ilk karakterin ayırt edici biti en yüksek anlamlı bite taşınıyor
- NOT ile bitler ters çevrildikten sonra 63 bitlik aritmetik sağa kaydırma yapılınca en yüksek anlamlı bit tüm
long boyunca yayılıyor
- Sonuç olan
broadcastSign, eksi varsa tüm bitleri 1, yoksa tüm bitleri 0 oluyor
2. adım: işaret karakterini kaldırma
- Negatiflik durumu
broadcastSign içinde saklandığı için işaret karakteri girdi verisinden kaldırılıyor
long maskToRemoveSign = ~(broadcastSign & 0xFF);
long withSignRemoved = inputData & maskToRemoveSign;
broadcastSign tamamen 1 ise broadcastSign & 0xFF yalnızca en düşük 8 biti 1 yapar- Bunun NOT’u alındığında yalnızca en düşük 8 biti 0 olan bir maske oluşturulur
inputData ile AND yapılınca en düşük bayttaki - kaldırılır- Eksi yoksa
broadcastSign 0 olduğundan maske tüm bitleri 1 olur ve rakam baytları korunur
3. adım: ondalık noktanın konumunu bulma
- Ondalık noktanın konumu şu kodla hesaplanıyor
int dotPos = Long.numberOfTrailingZeros(negatedInput & DOT_DETECTOR);
. karakteri de eksi gibi 4. bitinin 0 olması özelliğine sahip- Olası ondalık nokta konumlarında yalnızca 4. biti kontrol etmek için
DOT_DETECTOR = 0x10101000 maskesi kullanılıyor
- Ters çevrilmiş özgün girdi olan
negatedInput içinde ondalık nokta konumundaki ilgili bit 1 oluyor
Long.numberOfTrailingZeros() bu 1 bitinin konumunu döndürüyor-10.8 örneğinde ondalık nokta bit konumu 28’de olduğundan dotPos = 28 oluyor
4. adım: sabit şablona hizalama
- Ondalık noktanın konumuna göre girdi sola kaydırılarak her zaman aynı şablona uyduruluyor
long alignedToTemplate = withSignRemoved << (28 - dotPos);
0 0 0 Z . Y X 0
- Burada
X onlar basamağı, Y birler basamağı, Z ise onda birler basamağıdır
0, ASCII "0" değil, değeri 0 olan bayt anlamına gelir- İşaret kaldırıldıktan sonra girdi dört yerleşimden biri olabilir
0 0 0 Z . Y X 00 0 0 0 Z . Y 00 0 0 0 Z . Y X0 0 0 0 0 Z . Y
-10.8 için dotPos = 28 olduğundan kaydırma miktarı 0’dır-7.7 için ondalık nokta konumu bit 20’dedir; bu nedenle 8 bit, yani bir bayt sola kaydırılarak X yerine 0 konur
5. adım: ASCII rakamlarını değerlere dönüştürme
- Hizalamadan sonra ASCII karakterlerinden yalnızca rakam değerleri bırakılır
long digits = alignedToTemplate & ASCII_TO_DIGIT_MASK;
- ASCII rakamları
0dan 9a kadar onaltılık olarak 0x30 ile 0x39 arasındadır
- Yalnızca düşük 4 bit bırakıldığında karakter kodu gerçek rakam değerine dönüşür
- Şablondaki rakam konumlarında yalnızca
F bulunan bir maske uygulanır
0 0 0 Z . Y X 0
000000F000F0F00
-10.8 örneğinde maske uygulandıktan sonra yalnızca Z=8, Y=0, X=1 değerlerini temsil eden değerler kalır
6. adım: sihirli çarpmayla basamak değerlerini toplama
- Nihai mutlak değer
100 * X + 10 * Y + Z olarak hesaplanmalıdır
- Çarpmanın kaydırma ve toplamanın bir birleşimi olması özelliğinden yararlanılarak birden çok basamağın ağırlık hesaplaması tek bir çarpmayla yapılır
- Önce
X + Y + Z düşünüldüğünde, digits değerini 0, 16 ve 24 bit konumlarına kaydırılmış halleriyle toplamak, toplamı belirli bir bit aralığında toplayabilir
- Bu kaydırma-toplama birleşimi şu çarpma olarak ifade edilir
0x1 + 0x10000 + 0x1000000
- Gerçekte her basamağın ağırlığı farklı olduğundan
MAGIC_MULTIPLIER şöyle oluşturulur
MAGIC_MULTIPLIER = 0x1 + 10 * 0x10000 + 100 * 0x1000000;
- Hesaplama ifadesi şöyledir
absValue = ((digits * MAGIC_MULTIPLIER) >>> 32) & 0x3FF;
0x3FF, yalnızca 10 bit genişliğindeki sonucu ayıran maskedir100 * X 10 bite kadar büyüyüp komşu bitlerle çakışabilir; ancak Y * 100 değerinin sağdaki iki bitinin 0 olması özelliği sayesinde gerekli bit alanı sağlanır- merykitty bu bölüme
// That was close :) yorumunu bırakmıştır
7. adım: dallanma olmadan işareti uygulama
- Bu noktada mutlak değer
absValue ve işaret bilgisi broadcastSign vardır
broadcastSign pozitif için 0, negatif için -1 gibi davranır- İkinin tümleyeninde negatif sayı şu ifadeyle gösterilir
-n = NOT(n) + 1
- XOR koşullu NOT gibi kullanılabilir
n XOR -1, NOT(n) olurn XOR 0, n olur
- Seçimli
+1, -broadcastSign ile işlenir
temperature = (absValue ^ broadcastSign) - broadcastSign;
- Sonuç olarak
if olmadan pozitif değerler olduğu gibi kalır, negatif değerler ikinin tümleyeni negatif değerlere dönüştürülür
Bonus: bir sonraki CSV satırının başlangıç konumunu hesaplama
- Tüm 1BRC çözümünde bir sonraki CSV satırının başlangıç konumunu da düşük maliyetle hesaplamak gerekir
- Ondalık noktadan sonra her zaman bir ondalık basamak ve satır sonu karakteri geldiğinden, bir sonraki satır başlangıcı ondalık nokta konumuna göre bulunur
dotPos bit düzeyinde bir konum olduğundan 8’e bölmek için 3 bit sağa kaydırma kullanılır
nextLineStart = (dotPos >>> 3) + 3;
+3, ondalık nokta, bir ondalık basamak ve satır sonundan sonraki ilk baytı göstermek içindir
Sonuç
- merykitty’nin SWAR kodu, sabit bit işlemleriyle dört sıcaklık dizgesi biçimini birleştirip ayrıştırıyor
- Temel nokta; ASCII kodunun bit özellikleri, ondalık nokta konumuna dayalı hizalama, maskeyle rakam çıkarma, çarpmayla basamak değerlerini toplama ve ikinin tümleyenine dayalı işaret uygulama
- Adımlara ayrıldığında işleyişi takip etmek mümkün; ancak bunu çevrimiçi bir meydan okumanın birkaç günü içinde bir araya getirmiş olması etkileyici kalan nokta
1 yorum
Hacker News yorumları
İki yılı aşkın süre önce byte array view var handle’ın Java/Scala’da verimli SWAR rutinleri oluşturmak için oldukça uygun olduğunu fark etmiştim
Base16/64 string ayrıştırma,
java.time.*, sayısal değerleri doğrudan bayt dizilerinden ayrıştırma gibi SWAR kullanım örnekleri burada da bolca var: https://github.com/plokhotnyuk/jsoniter-scala/blob/master/js...Pratikte kendini kanıtlamış bir parser’ın büyük değeri, verimli hata denetimi ve toparlanma yeteneğinde
Ayrıca mevcut kod stilindeki gibi bir sentinel hata değeri döndürecek şekilde algılama yapmak için ne kadar iş gerekeceğini de merak ediyorum
Ama bizzat deneyecek kadar ilgimi çekmiyor ;-)
MULile shift/toplama yapma tekniği epey bilinen bir yöntemLemire’in yazısına bakın: https://lemire.me/blog/2023/11/28/parsing-8-bit-integers-qui...
Makale: https://arxiv.org/abs/1902.08318
Github: https://github.com/simdjson/simdjson
Üstelik resmi 1BRC, G/Ç hızını tamamen dışarıda bırakmak için sonuçların RAM disk üzerinden değerlendirildiğini açıkça belirtiyordu: https://github.com/gunnarmorling/1brc?tab=readme-ov-file#eva...
“Programs are run from a RAM disk (i.o. the IO overhead for loading the file from disk is not relevant)”
Sınırlı anladığım kadarıyla büyük bir metin dosyası sıralı biçimde L1’e getiriliyor ve her değer bir kez okunuyor. Çoğu işlemcide bu tür okumalar döngü başına iki kez yapılabiliyor. Yavaş kısım RAM’den L1’e getirmek olurdu, ama sıralı okuma oldukça hızlı
Ardından her okuma için işlem yapılıyor. İlk bakışta optimize edilmiş sürümde bunun yaklaşık 4 döngü civarında olacağını düşünüyorum. Sonra sonucu bir yere yazmak gerekiyor ve muhtemelen ondan önce bir ya da iki rastgele okuma gerekiyor. Bunu mu G/Ç darboğazı olarak görüyorsunuz?
CPU ile sınırlı olduğu bariz demek istemiyorum, ama aksi de bariz görünmüyor
Düzenleme: “disk G/Ç” demek istemiş olabileceğinizi hesaba katmamışım. Başkalarının söylediği gibi burada fiilen bir etken değil
Yani tüm veri RAM’de, daha doğrusu sayfa önbelleğinde olur
Doğru hatırlıyorsam taşma yönetimi zordu. Bu yazıyı gerçekten sevdim
Hâlâ CPU’yu gerçekten programlamayı bilen ve ne yaptığını anlayan insanlar var
Asıl gizem, kendine programcı diyenlerin büyük çoğunluğunda derin anlayışın eksik olması ve hatta ciddi biçimde eksik olduklarının farkında bile değilmiş gibi görünmeleri
Gerçekten iyi çalıştığı da şimdiye kadar yayımlanan 1BRC çözümleri arasında en hızlısı gibi görünen C# çözümünde görülebiliyor: https://hotforknowledge.com/2024/01/13/1brc-in-dotnet-among-...
Sorun, başlangıç vektörünü oluşturma ve sonucu çıkarma maliyetinin aşırı olup olmadığı
Ancak HotSpot’ın bunu kendi başına yapacağından şüpheliyim; ayrıca çoğu 1BRC gönderiminin başlangıç overhead’ini azaltmak için Graal ile çalıştırıldığı da ayrı bir nokta
Temel SSE2’de 32 bit veya 64 bit çarpma olmadığı için 32×32→64 bit çarpma sorun olur, ama SSE4.1’e tam gereken
pmuldqeklendi. Yalnız sonuç 64 bit olduğundan, 32 bit tamsayılardan oluşan tüm vektörü işlemek için bu işlemden iki kez gerekirAyrıca sıcaklık alanının uzunluğu değişken; sütun bazında saklanıyor olsa bile kazanç sağlamama ihtimali yüksek
Yine de ad ile sıcaklık arasındaki ayırıcıyı bulmak için SSE başarıyla uygulanmış