الصفحة الرئيسية>المتعلقة بالبرمجة>شفرة المصدر الأخرى
تنزيل

انتزاع - grep بسيط ولكنه سريع جدًا

غريبين

هذه هي نسختي التجريبية والمتوازية من grep حتى أتمكن من اختبار استراتيجيات مختلفة لتسريع الوصول إلى أشجار الدليل الكبيرة. على وحدة تخزين الفلاش أو محركات أقراص SSD، يمكنك بسهولة التغلب على الـ greps الشائعة بمعامل يصل إلى 8.

خيارات: 

 Usage: ./greppin [-rIOLlsSH] [-n <cores>] <regex> <path>

	-2	-- use PCRE2 instead of PCRE
	-O	-- print file offset of match
	-l	-- do not print the matching line (Useful if you want
		   to see _all_ offsets; if you also print the line, only
		   the first match in the line counts)
	-s	-- single match; dont search file further after first match
		   (similar to grep on a binary)
	-H	-- use hyperscan lib for scanning
	-S	-- only for hyperscan: interpret pattern as string literal instead of regex
	-L	-- machine has low mem; half chunk-size (default 2GB)
		   may be used multiple times
	-I	-- enable highlighting of matches (useful)
	-n	-- Use multiple cores in parallel (omit for single core)
	-r	-- recurse on directory

يستخدم Grap مكتبة pcre ، لذا فهو يعادل في الأساس grep -P -a . يعد -P مهمًا، نظرًا لأن التعبيرات العادية المتوافقة مع Perl لها خصائص مختلفة عن التعبيرات العادية الأساسية.

يبني

هناك فرعين. master greppin . Master هو الاستيلاء "التقليدي" الذي يجب تجميعه وتشغيله على معظم أنظمة POSIX. يأتي greppin مع نسخته المحسنة والمتوازية من nftw() و readdir() ، والتي تضاعف السرعة مرة أخرى في الجزء العلوي من التسريع الذي يوفره الفرع master بالفعل. يعمل فرع greppin على أنظمة التشغيل Linux وBSD وOSX. يأتي greppin أيضًا مع دعم لمكتبات الفحص الفائق من Intel التي تحاول استغلال تعليمات SIMD الخاصة بوحدة المعالجة المركزية إن أمكن (AVX2، AVX512 وما إلى ذلك) عند تجميع نمط regex في كود JIT.

سوف ترغب على الأرجح في بناء فرع greppin : 

 $ git checkout greppin
[...]
$ cd src; make
[...]

تأكد من تثبيت حزم مكتبة pcre و pcre2 . في أنظمة BSD تحتاج إلى gmake بدلاً من make . إذا كنت ترغب في القيام بأحدث التقنيات باستخدام محرك regex المتعدد الخاص بـ greppin ودعم الفحص الفائق، فأنت بحاجة أولاً إلى الحصول على ما يلي وإنشائه: 

 $ git clone https://github.com/intel/hyperscan
[...]
$ cd hyperscan
$ mkdir build; cd build
$ cmake -DFAT_RUNTIME=1 -DBUILD_STATIC_AND_SHARED=1 ..
[...]
$ make
[...]

سيؤدي هذا إلى إنشاء ما يسمى بوقت التشغيل الدهني لمكتبات Hyperscan التي تحتوي على دعم لجميع عائلات وحدة المعالجة المركزية من أجل تحديد نمط التجميع الصحيح في وقت التشغيل لتحقيق أقصى قدر من الأداء. بمجرد انتهاء البناء، يمكنك إنشاء greppin مقابل ذلك:

(داخل انتزاع الريبو المستنسخ) 

 $ cd src
$ HYPERSCAN_BUILD=/path/to/hyperscan/build make -f Makefile.hs
[...]

سيؤدي هذا إلى إنتاج ثنائي greppin الذي يمكّن الخيار -H من تحميل محرك مختلف في وقت التشغيل، ومحاولة استغلال جميع بتات الأداء الممكنة.

يمكنك ربطها بالمكتبات المثبتة بالفعل، لكن واجهة برمجة التطبيقات (API) أضافت مؤخرًا بعض الوظائف في الإصدار 5.x ومعظم التوزيعات تأتي مع 4.x.

لماذا هو أسرع؟

Grap يستخدم mmap(2) ويطابق الملف blob بأكمله دون حساب الأسطر الجديدة (وهو ما يفعله grep حتى لو لم يكن هناك تطابق [اعتبارًا من مراجعة كود grep الخاصة بي في عام 2012؛ قد تكون الأمور مختلفة اليوم]) وهو أمر كثير أسرع من read(2) - تقسيم الملف إلى أجزاء صغيرة وإحصاء الأسطر الجديدة. إذا كان ذلك متاحًا، يستخدم الاستيلاء أيضًا ميزة PCRE JIT. ومع ذلك، لا يمكن قياس عمليات التسريع إلا على أشجار الملفات الكبيرة أو محركات الأقراص الثابتة السريعة أو محركات أقراص الحالة الثابتة (SSD). في الحالة اللاحقة، يمكن أن يكون التسريع كبيرًا جدًا (أسرع بما يصل إلى 3 مرات) في حالة المطابقة بشكل متكرر وبالتوازي. نظرًا لأن التخزين هو عنق الزجاجة، فإن موازنة البحث على محركات الأقراص الثابتة ليس لها أي معنى، حيث يستغرق البحث وقتًا أطول من مجرد القيام بالأشياء بشكل خطي.

بالإضافة إلى ذلك، Grab هو تخطي الملفات الصغيرة جدًا بحيث لا تحتوي على التعبير العادي. بالنسبة إلى التعبيرات العادية الأكبر حجمًا في البحث العودي، يمكن أن يؤدي ذلك إلى تخطي كمية لا بأس بها من الملفات دون فتحها.

مطلوب pcre lib جديد تمامًا، في بعض الأنظمة القديمة يمكن أن يفشل البناء بسبب فقدان PCRE_INFO_MINLENGTH و pcre_study() .

يتم تجميع الملفات ومطابقتها في أجزاء بحجم 1Gig. بالنسبة للملفات الأكبر حجمًا، يتم تراكب آخر 4096 بايت (صفحة واحدة) من المجموعة، بحيث يمكن العثور على التطابقات على حدود 1 جيجا. في هذه الحالة، ترى التطابق مضاعفًا (ولكن بنفس الإزاحة).

إذا قمت بقياس grep مقابل Grab ، فضع في اعتبارك إسقاط ذاكرة التخزين المؤقت للصفحة وذاكرة التخزين المؤقت بين كل عملية تشغيل: echo 3 > /proc/sys/vm/drop_caches

لاحظ أن grep سيطبع فقط "تطابقات الملف الثنائي"، إذا اكتشف الملفات الثنائية، بينما سيطبع Grap جميع المطابقات، ما لم يتم إعطاء -s . لذلك، لإجراء اختبار السرعة، يجب عليك البحث عن تعبير غير موجود في البيانات، من أجل فرض البحث في الملفات بأكملها.

تم إجراء Grab للتنقل بسرعة عبر أشجار الدليل الكبيرة دون فهرسة. يحتوي grep الأصلي على مجموعة خيارات أكثر اكتمالاً. يعد تسريع مطابقة ملف واحد صغيرًا جدًا، إذا كان قابلاً للقياس على الإطلاق.

بالنسبة لمحركات أقراص SSD، فإن الخيار متعدد النواة منطقي. بالنسبة لمحركات الأقراص الصلبة، لا يحدث ذلك، نظرًا لأنه يجب وضع الرأس ذهابًا وإيابًا بين الخيوط، مما قد يؤدي إلى تدمير مبدأ المنطقة المحلية وقتل الأداء.

يتميز فرع greppin بإصداره المتوازي الخالي من القفل من nftw() ، لذا يمكن أيضًا استخدام وقت الخمول للنوى N - 1 عندما يقوم النواة الأولى ببناء شجرة الدليل للعمل.

ما تبقى للملاحظة: سوف يجتاز Grab الدلائل فعليًا ، أي أنه لن يتبع الروابط الرمزية.

بقعة

spot هي النسخة الموازية من find . وهو يدعم الخيارات الأكثر استخدامًا كما تعلم. ليس هناك الكثير لنقوله عنه، فقط جربه.

أمثلة

يوضح هذا التسريع على جهاز رباعي النواة مع البحث على SSD: 

 root@linux:~# echo 3 > /proc/sys/vm/drop_caches
root@linux:~# time grep -r foobardoesnotexist /source/linux

real	0m34.811s
user	0m3.710s
sys	0m10.936s
root@linux:~# echo 3 > /proc/sys/vm/drop_caches
root@linux:~# time grab -r foobardoesnotexist /source/linux

real	0m31.629s
user	0m4.984s
sys	0m8.690s
root@linux:~# echo 3 > /proc/sys/vm/drop_caches
root@linux:~# time grab -n 2 -r foobardoesnotexist /source/linux

real	0m15.203s
user	0m3.689s
sys	0m4.665s
root@linux:~# echo 3 > /proc/sys/vm/drop_caches
root@linux:~# time grab -n 4 -r foobardoesnotexist /source/linux

real	0m13.135s
user	0m4.023s
sys	0m5.581s

مع فرع greppin : 

 root@linux:~# echo 3 > /proc/sys/vm/drop_caches
root@linux:~# time grep -a -P -r linus /source/linux/|wc -l
16918

real    1m12.470s
user    0m49.548s
sys     0m6.162s
root@linux:~# echo 3 > /proc/sys/vm/drop_caches
root@linux:~# time greppin -n 4 -r linus /source/linux/|wc -l
16918

real    0m8.773s
user    0m4.670s
sys     0m5.837s
root@linux:~#

نعم! ~ 9s مقابل ~ 72s! هذا أسرع بمقدار 8 مرات على جهاز SSD رباعي النواة مثل grep التقليدي.

فقط لإثبات أنه أدى إلى نفس الناتج: 

 root@linux:~# echo 3 > /proc/sys/vm/drop_caches
root@linux:~# greppin -n 4 -r linus /source/linux/|sort|md5sum
a1f9fe635bd22575a4cce851e79d26a0  -
root@linux:~# echo 3 > /proc/sys/vm/drop_caches
root@linux:~# grep -P -a -r linus /source/linux/|sort|md5sum
a1f9fe635bd22575a4cce851e79d26a0  -
root@linux:~#

في مقارنة النواة الواحدة، يعتمد التسريع أيضًا على وحدة المعالجة المركزية التي تقوم النواة بجدولة grep بها، لذلك قد يكون الالتقاط أسرع أو لا يكون (في الغالب يكون كذلك). إذا كان الحمل متساويًا بين الاختبارات أحادية النواة، فسوف يشهد الاستيلاء تسريعًا في حالة البحث على أشجار الملفات الكبيرة. في الإعدادات متعددة النواة، يمكن أن يستفيد الاستيلاء من الأمر.

مقارنة ripgrep

يمكن العثور على المشروع هنا.

ينبع التسريع الرئيسي الموجود داخل جداول القياس الخاصة بهم من حقيقة أن ripgrep يتجاهل الكثير من الملفات (لا سيما ملفات dotfiles) عند استدعائها بدون خيارات خاصة بالإضافة إلى التعامل مع الملفات الثنائية كهدف مطابقة واحدة (على غرار grep ). للحصول على نتائج قابلة للمقارنة، ضع في اعتبارك (4 هو عدد النوى):

  • echo 3 > /proc/sys/vm/drop_caches بين كل عملية تشغيل
  • أضف -j 4 -a --no-unicode --no-pcre2-unicode -uuu --mmap إلى ripgrep ، نظرًا لأنه سيطابق افتراضيًا Unicode الذي يكون أبطأ بثلاث مرات، ويحاول تعويض فقدان السرعة عن طريق تخطي "تجاهل" الملفات المستندة إلى. -e أسرع من -P ، لذا من الأفضل أن تختار -e ، لكنها ليست بنفس قوة PCRE
  • أعد توجيه الإخراج إلى /dev/null لتجنب التأثيرات المستندة إلى tty
  • أضف -H -n 4 إلى greppin إذا كنت تريد أفضل أداء. -H متوافق مع PCRE مع استثناءات قليلة جدًا (وفقًا لـ Hyperscan docu)
  • setfattr -n user.pax.flags -v "m" /path/to/binary إذا كنت تعمل على أنظمة grsec وتتطلب تعيينات rwx JIT

ثم المضي قدما والتحقق من التوقيتات. حتى عند عدم استخدام الفحص الفائق، يكون greppin أسرع بشكل ملحوظ من rg عند استخدام تعبيرات PCRE2 (PCRE2 مقابل PCRE2) ولا يزال أسرع عند مقارنة أسرع التعبيرات (-e مقابل Hyperscan).

يوسع
معلومات إضافية
تطبيقات ذات صلة
نوصي لك
أخبار ذات صلة الكل