Krep - grep से 5 गुना तेज़ स्ट्रिंग सर्च टूल

• परफ़ॉर्मेंस-क्रिटिकल applications के लिए C में लिखा गया अल्ट्रा-फास्ट स्ट्रिंग सर्च टूल
• pattern की विशेषताओं और hardware के अनुसार सबसे उपयुक्त algorithm को dynamically चुनता है
• SSE4.2/AVX2 जैसे hardware का उपयोग करके अधिकतम throughput प्रदान करता है
• बड़े पैमाने के support के लिए फ़ाइलों को chunks में बाँटकर multithreading parallel processing करता है
• pattern के अनुसार सबसे उपयुक्त search algorithm का उपयोग
  • Boyer-Moore-Horspool: सामान्य pattern matching के लिए उपयुक्त
  • Knuth-Morris-Pratt (KMP) algorithm: छोटे pattern के लिए optimized
  • Rabin-Karp: लंबे pattern के लिए प्रभावी
  • SIMD acceleration: SSE4.2, AVX2 समर्थित hardware पर बेहतर performance
• memory-mapped file I/O के उपयोग से system calls को न्यूनतम कर throughput को अधिकतम करता है
• लचीले search options
  • case-sensitive और case-insensitive search
  • फ़ाइल search के अलावा सीधे string search भी संभव
  • केवल matches की संख्या दिखाने वाला mode उपलब्ध

उपयोग का तरीका

krep [OPTIONS] PATTERN [FILE]  

• log file में “error” खोजें: krep "error" system.log
• case-insensitive तरीके से 8 threads का उपयोग करके search: krep -i -t 8 "ERROR" large_logfile.log
• match count दिखाएँ (matched lines प्रिंट नहीं होंगी): krep -c "TODO" *.c
• फ़ाइल नहीं, बल्कि string में सीधे search: krep -s "Hello" "Hello world"

command line options

• -i : case-insensitive search
• -c : matched lines प्रिंट किए बिना केवल match count दिखाएँ
• -t NUM : NUM threads का उपयोग करें (default: 4)
• -s STRING : फ़ाइल के बजाय string में search
• -v : version जानकारी दिखाएँ
• -h : help दिखाएँ

benchmark

• krep का performance सामान्य स्ट्रिंग सर्च टूल्स की तुलना में बहुत उत्कृष्ट है।
  • krep को 1GB text file में सामान्य pattern खोजने में 0.78 सेकंड लगे, जो 1,282MB प्रति सेकंड की गति है
  • grep को उसी काम में 2.95 सेकंड लगे, और इसकी गति 339MB प्रति सेकंड रही
  • ripgrep को 1.48 सेकंड लगे, और इसकी गति 676MB प्रति सेकंड रही
• → krep, grep से लगभग 3.8 गुना तेज़ है, और ripgrep से लगभग 1.9 गुना तेज़ है (hardware और file की विशेषताओं के अनुसार performance बदल सकता है)

नाम की उत्पत्ति

• “krep” आइसलैंडिक शब्द “kreppan” से आया है
• इसका अर्थ है “तेज़ी से पकड़ लेना”
• यह efficient pattern recognition का प्रतीक है
• छोटा और संक्षिप्त command होने से इसे टाइप करना आसान है

[clickin]

अगर regex support छोड़ने के बाद भी यह ripgrep से सिर्फ 2 गुना ही तेज़ हो पाता है, तो इसकी उपयोगिता थोड़ी कम लगती है.
मुझे लगता है मैं regex सपोर्ट वाले ripgrep का ही इस्तेमाल करता रहूंगा.

[GN⁺]

Hacker News राय

• CPU फीचर्स (जैसे: AVX2) को runtime पर detect किया जाना चाहिए

  • ifdef केवल build time पर यह detect करता है कि compiler इसे support करता है या नहीं
  • प्रोग्राम तभी compile होता है जब compiler AVX2 को support करता हो
  • runtime पर यह जांचना चाहिए कि CPU AVX2 को support करता है या नहीं
  • प्रोजेक्ट में "configuration time पर CPUID flags और वास्तविक instruction execution test के जरिए detect" करने वाला हिस्सा है
  • SSE4.2 और AVX2 instructions का अपने-आप उपयोग किया जा सकता है

• krep प्रोजेक्ट पर ब्लॉग पोस्ट का परिचय

  • homepage पर कहा गया है कि यह ripgrep से तेज़ है
  • पूरे ripgrep benchmark से इसकी तुलना देखना चाहूँगा
  • madvise() से जुड़ी error आई, Makefile के CFLAGS में '-D_GNU_SOURCE' जोड़ना ज़रूरी है

• test cases का महत्व

  • multithreaded file search में chunk boundary की समस्या चिंताजनक लगती है
  • साधारण search में नए edge cases आ गए हैं
  • file में एक अक्षर जोड़ने से match टूट सकता है

• build समस्या हल करने के बाद benchmark परिणाम

  • पहले benchmark प्रयास में speed धीमी थी
  • ripgrep, krep से 1.52 गुना तेज़ था

• match frequency ज़्यादा होने वाला benchmark प्रयास

  • krep, ripgrep से 3.40 गुना तेज़ था
  • matches की संख्या में बड़ा अंतर था
  • हो सकता है krep सही परिणाम न दे रहा हो

• अतिरिक्त benchmark प्रयास

  • ripgrep कुछ खास pattern खोजने में ज़्यादा तेज़ था
  • krep कोई match नहीं खोज पाया

• ripgrep का algorithm और memory map का उपयोग

  • ripgrep उन्नत substring search algorithm का उपयोग करता है
  • memory map और parallel processing का उपयोग करता है
  • krep भी parallel processing का उपयोग करता है, single file search में multithreading का उपयोग करता है

• benchmark परिणामों पर संदेह

  • 5GB file में pattern search करने में ripgrep को 40 सेकंड से ज़्यादा लगना अजीब है
  • OP से benchmark को reproduce करने का तरीका साझा करने का अनुरोध

• krep नाम पर राय

  • grep में "re" का मतलब regular expression होता है
  • krep regular expression का उपयोग नहीं करता, इसलिए इसका नाम गलत हो सकता है