- 1BRC में bottleneck CSV तापमान मानों के 1 अरब रिकॉर्ड को बेहद तेज़ी से parse करना था, और Quân Anh Mai का merykitty SWAR code
if के बिना fixed ALU operations से तापमान को integer में बदलने के कारण चर्चा में आया
- यह कोड एक
long में मौजूद 8 bytes को एक साथ संभालने वाली SWAR(SIMD Within A Register) तकनीक का इस्तेमाल करता है, जिसमें सामान्य CPU register पर कई characters को parallel की तरह process किया जाता है
- processing flow इस क्रम में चलता है: minus sign detect करना, sign हटाना, decimal point की position ढूंढना,
XY.Z alignment करना, ASCII digits को numbers में बदलना, magic multiplication, और अंत में sign apply करना
- input format चार तरह के हो सकते हैं:
-XX.X, -X.X, X.X, XX.X; decimal point की position के आधार on bytes को shift करके अलग-अलग लंबाई वाले inputs को एक ही bit layout में फिट किया जाता है
- branches और loops को कम करने की जगह यह तरीका ASCII code की विशेषताओं, 2's complement, bit masks, और multiplication की shift-add properties का घना उपयोग करके high-performance parsing हासिल करता है
1BRC में bottleneck बना तापमान parsing
- One Billion Row Challenge(1BRC) में CSV file के तापमान मानों को बहुत तेज़ी से parse करना एक मुख्य bottleneck बनकर उभरा
- पहले की optimizations से भी conventional parallel Java code की गति 71 seconds से 1.7 seconds तक पहुँच गई थी
- तापमान format भले सरल हो, लेकिन 1 अरब values को 1 second से कम समय में parse करने के लिए बहुत छोटी लागत भी बड़े स्तर पर जुड़ जाती है
- संभव formats हैं
-XX.X, -X.X, X.X, XX.X
- शुरुआती participants ने
Double.parseDouble() का उपयोग किया, लेकिन बाद में loop-free custom parsers सामने आए
- Quân Anh Mai के @merykitty solution का एक हिस्सा
if के बिना single file read से काम करता था और 1BRC की top solutions में लगभग standard component की तरह फैल गया
- winner Thomas Wuerthinger ने अपनी solution में योगदान देने वाली टीम के हिस्से के रूप में Quân Anh का नाम स्पष्ट रूप से दर्ज किया
merykitty code क्या करता है
- यह code 8-byte CSV input वाले
long को लेकर वास्तविक तापमान के 10 गुना के बराबर integer temperature value लौटाता है
- input
mmap किए गए CSV file से direct native memory read द्वारा आता है, और उस हिस्से को अलग concern माना गया है
- operations एक fixed order में चलने वाले 18 ALU steps से बने हैं
- bit shift, AND, NOT, XOR
- addition, subtraction, multiplication
Long.numberOfTrailingZeros()
numberOfTrailingZeros() JDK compiler intrinsic के ज़रिए विशेष CPU instruction का उपयोग करता है- यह dedicated SIMD instruction नहीं, बल्कि सामान्य CPU registers और instructions से कई bytes को संभालता है, इसलिए यह SWAR approach है
- example code को readability के लिए थोड़ा बदला गया है; original CalculateAverage_merykitty.java में है
पूरा processing flow
- code तापमान को इस क्रम में parse करता है
- पहला character
- है या नहीं, यह देखकर negative detect करता है
- sign character हो तो उस byte को 0 बना देता है
- decimal point
. की position ढूंढता है
- digits को
XY.Z template के अनुरूप long के भीतर shift करता है
- ASCII characters को वास्तविक numeric values में बदलता है
- हर digit को
1x, 10x, 100x weight देकर जोड़ता है
- अंत में sign apply करता है
- ऊपर से देखने पर यह high-level parsing problem लगती है, लेकिन हर step सिर्फ ALU operations से लागू किया गया है
चरण 1: minus sign detect करना
- sign detection इस code से शुरू होती है
long negatedInput = ~inputData;
long broadcastSign = (negatedInput << 59) >> 63;
- समझाने के लिए क्रम बदलें तो इसे
( ~(inputData << 59) ) >> 63 की तरह देखा जा सकता है
- ASCII में minus
- की bit 4, 0 होती है, जबकि digits में वही bit 1 होती है; इसी गुण का उपयोग किया जाता है
- input को 59 bits left shift करने पर पहले character की distinguishing bit सबसे ऊपर वाले bit तक पहुँच जाती है
- NOT से bit पलटने के बाद 63-bit arithmetic right shift करने पर top bit पूरे
long में फैल जाती है
- नतीजे में
broadcastSign में minus होने पर सभी bits 1 और न होने पर सभी bits 0 हो जाते हैं
चरण 2: sign character हटाना
- negative होने की जानकारी
broadcastSign में सुरक्षित है, इसलिए input data से sign character हटा दिया जाता है
long maskToRemoveSign = ~(broadcastSign & 0xFF);
long withSignRemoved = inputData & maskToRemoveSign;
- अगर
broadcastSign पूरा 1 है, तो broadcastSign & 0xFF में सिर्फ सबसे निचले 8 bits ही 1 रहते हैं
- इसका NOT लेने पर ऐसा mask बनता है जिसमें सिर्फ lowest 8 bits, 0 होते हैं
inputData के साथ AND करने पर lowest byte में मौजूद - हट जाता है- अगर minus नहीं है, तो
broadcastSign 0 होगा, इसलिए mask के सभी bits 1 रहेंगे और digit bytes जस के तस बने रहेंगे
चरण 3: decimal point की position ढूंढना
- decimal point की position यह code निकालता है
int dotPos = Long.numberOfTrailingZeros(negatedInput & DOT_DETECTOR);
. character में भी minus की तरह bit 4, 0 होती है- केवल संभावित decimal positions की bit 4 जाँचने के लिए
DOT_DETECTOR = 0x10101000 mask का उपयोग होता है
- original input के inverted रूप
negatedInput में decimal point वाली जगह की संबंधित bit 1 बन जाती है
Long.numberOfTrailingZeros() इसी 1-bit की position लौटाता है- उदाहरण
-10.8 में decimal point bit position 28 पर है, इसलिए dotPos = 28 होता है
चरण 4: fixed template के अनुसार alignment
- decimal point की position के आधार पर input को left shift करके हमेशा एक ही template पर लाया जाता है
long alignedToTemplate = withSignRemoved << (28 - dotPos);
0 0 0 Z . Y X 0
- यहाँ
X tens place, Y ones place, और Z first decimal digit है
0 का अर्थ ASCII "0" नहीं, बल्कि value 0 वाला byte है- sign हटाने के बाद input इन चार layouts में से एक हो सकता है
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 में पहले से dotPos = 28 है, इसलिए shift amount 0 है-7.7 में decimal point bit 20 पर होता है, इसलिए इसे 8 bits यानी 1 byte left shift किया जाता है और X की जगह 0 आ जाता है
चरण 5: ASCII digits को values में बदलना
- alignment के बाद ASCII characters से सिर्फ digit values निकाली जाती हैं
long digits = alignedToTemplate & ASCII_TO_DIGIT_MASK;
- ASCII digits
0 से 9 तक hex में 0x30 से 0x39 होते हैं
- केवल निचले 4 bits बचाने पर character code वास्तविक digit value बन जाता है
- template में जहाँ digits हैं, वहीं
F मौजूद रहने वाला mask apply किया जाता है
0 0 0 Z . Y X 0
000000F000F0F00
- उदाहरण
-10.8 में mask के बाद केवल Z=8, Y=0, X=1 को दर्शाने वाली values बचती हैं
चरण 6: magic multiplication से place values जोड़ना
- अंतिम absolute value को
100 * X + 10 * Y + Z के रूप में निकालना होता है
- इस गुण का उपयोग किया जाता है कि multiplication, shifts और additions के संयोजन जैसा होता है; इसलिए कई digits की weighted calculation एक ही multiplication में की जा सकती है
- पहले
X + Y + Z को सोचें तो digits को 0, 16, और 24-bit positions तक shift करके जोड़ा जा सकता है ताकि sums खास bit ranges में इकट्ठे हों
- इस shift-add संयोजन को इस multiplication के रूप में लिखा जा सकता है
0x1 + 0x10000 + 0x1000000
- वास्तव में हर digit का weight अलग है, इसलिए
MAGIC_MULTIPLIER इस तरह बनता है
MAGIC_MULTIPLIER = 0x1 + 10 * 0x10000 + 100 * 0x1000000;
absValue = ((digits * MAGIC_MULTIPLIER) >>> 32) & 0x3FF;
0x3FF एक ऐसा mask है जो 10-bit चौड़े result को अलग करता है100 * X 10 bits तक बड़ा हो सकता है और पास की bits से overlap भी कर सकता है, लेकिन Y * 100 के सबसे दाएँ 2 bits, 0 होने की वजह से ज़रूरी bit space मिल जाता है- merykitty ने इस हिस्से पर
// That was close :) comment छोड़ा था
चरण 7: branch के बिना sign apply करना
- इस बिंदु पर
absValue absolute value है और broadcastSign में sign information है
broadcastSign, positive के लिए 0 और negative के लिए -1 की तरह काम करता है- 2's complement में negative value को इस तरह व्यक्त किया जाता है
-n = NOT(n) + 1
- XOR को conditional NOT की तरह इस्तेमाल किया जा सकता है
n XOR -1 का मतलब NOT(n)n XOR 0 का मतलब n
- optional
+1 को -broadcastSign से संभाला जाता है
temperature = (absValue ^ broadcastSign) - broadcastSign;
- परिणाम यह है कि
if के बिना positive values जस की तस रहती हैं और negative values 2's complement negative form में बदल जाती हैं
बोनस: अगली CSV row की start position निकालना
- पूरी 1BRC solution में अगली CSV line की start position को भी सस्ते में निकालना ज़रूरी होता है
- decimal point के बाद हमेशा एक decimal digit और newline आती है, इसलिए decimal point की position से अगली row की शुरुआत निकाली जाती है
dotPos bit-based position है, इसलिए 8 से भाग देने के लिए 3-bit right shift का उपयोग किया जाता है
nextLineStart = (dotPos >>> 3) + 3;
+3 decimal point, एक decimal digit, और newline के बाद आने वाले पहले byte की ओर इशारा करता है
निष्कर्ष
- merykitty का SWAR code fixed bit operations के ज़रिए तापमान strings के चार formats को एक जैसा बनाकर parse करता है
- इसकी कुंजी है ASCII code की bit properties, decimal point position पर आधारित alignment, mask से digit extraction, multiplication के ज़रिए place-value summation, और 2's complement आधारित sign application
- चरणों में बाँटने पर इसकी कार्यप्रणाली समझी जा सकती है, लेकिन online challenge के कुछ ही दिनों में इन सबको जोड़ लेना अब भी सबसे प्रभावशाली बातों में से एक लगता है
1 टिप्पणियां
Hacker News की राय
2 साल से भी पहले मुझे पता चला था कि byte array view var handle Java/Scala में कुशल SWAR routines बनाने के लिए काफी उपयुक्त है
Base16/64 string parsing,
java.time.*, byte array से सीधे numeric values parse करना आदि SWAR उपयोग के कई उदाहरण यहां भी हैं: https://github.com/plokhotnyuk/jsoniter-scala/blob/master/js...production में परखे हुए parser की बड़ी value कुशल error checking और recovery में होती है
और मौजूदा code style की तरह कोई sentinel error value return कराने के लिए detect करने में कितना काम लगेगा, यह भी जानना चाहूंगा
हालांकि खुद करके देखने जितना दिलचस्प नहीं है ;-)
MULसे shift/add करने की technique काफी जानी-मानी हैLemire का लेख देखें: https://lemire.me/blog/2023/11/28/parsing-8-bit-integers-qui...
Paper: https://arxiv.org/abs/1902.08318
Github: https://github.com/simdjson/simdjson
इसके अलावा official 1BRC ने साफ कहा था कि I/O speed को पूरी तरह बाहर रखने के लिए results को RAM disk से evaluate किया जाता है: 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)”
मेरी सीमित समझ के हिसाब से एक बड़ी text file को sequentially L1 में लाया जाता है और हर value के लिए एक बार पढ़ा जाता है। ज्यादातर processors में ऐसे reads cycle में दो बार किए जा सकते हैं। धीला हिस्सा RAM से L1 में लाना होगा, लेकिन sequential reads काफी तेज होते हैं
फिर हर read पर processing होती है। पहली नजर में optimized version में यह लगभग 4 cycles जैसा लगता है। इसके बाद result कहीं लिखना होगा, और शायद उससे पहले एक या दो random reads चाहिए होंगे। क्या आप इसी हिस्से को I/O bottleneck मान रहे हैं?
मेरा मतलब यह नहीं कि CPU-limited होना स्पष्ट है, लेकिन ऐसा न होना भी स्पष्ट नहीं दिखता
Edit: यह संभावना नहीं सोची कि आपका मतलब “disk I/O” हो सकता है। जैसा दूसरों ने कहा, यहां वह असल में factor नहीं है
यानी सारा data RAM में, ज्यादा सटीक कहें तो page cache में होता है
अगर याद सही है तो overflow handling tricky था। यह लेख सचमुच पसंद आया
अभी भी ऐसे लोग हैं जो CPU को सच में program करना जानते हैं और समझते हैं कि वे क्या कर रहे हैं
असली mystery यह है कि खुद को programmer कहने वाले ज्यादातर लोगों में गहरी समझ की कमी है, और लगता है उन्हें यह भी नहीं पता कि वे गंभीर रूप से कमज़ोर हैं
यह सच में अच्छी तरह काम करता है, यह अब तक publicly available 1BRC में शायद सबसे तेज C# solution से दिखता है: https://hotforknowledge.com/2024/01/13/1brc-in-dotnet-among-...
सवाल यह है कि initial vector बनाना और result extract करना बहुत महंगा तो नहीं पड़ेगा
हालांकि HotSpot अपने आप यह कर पाएगा, इस पर संदेह है; अलग बात यह भी है कि startup overhead कम करने के लिए ज्यादातर 1BRC submissions Graal पर run किए गए थे
basic SSE2 में 32-bit या 64-bit multiplication नहीं है, इसलिए 32×32→64-bit multiplication समस्या बनती है, लेकिन SSE4.1 में ठीक वही जरूरी
pmuldqजोड़ा गया। हालांकि result 64-bit होता है, इसलिए 32-bit integers के पूरे vector को process करने के लिए ऐसी operation दो बार करनी पड़ती हैसाथ ही temperature field variable length का है, इसलिए column-wise stored होने पर भी शायद फायदा न मिले
लेकिन name और temperature के बीच का delimiter ढूंढने में SSE सफलतापूर्वक apply किया गया था