اليوم نشارك كودًا مفتوح المصدر يمكنه فرز مصفوفات الأرقام بسرعة تبلغ حوالي عشرة أضعاف سرعة C++ std::sort، ويتفوق على أحدث الخوارزميات الخاصة بالمعمارية، مع كونه محمولًا عبر جميع معماريات CPU الحديثة. نناقش أدناه كيف حققنا ذلك.

أولاً، بعض الخلفية. هناك اتجاه حديث نحو قواعد البيانات العمودية التي تخزن بشكل متتالٍ جميع القيم من عمود معين، بدلاً من تخزين جميع حقول سجل أو "صف" قبل حقول السجل التالي. يمكن أن يكون هذا أسرع في التصفية أو الفرز، وهما لبنات بناء أساسية لاستعلامات SQL؛ لذلك نركز على تخطيط البيانات هذا.

بالنظر إلى أن الفرز قد تمت دراسته بكثافة، كيف يمكننا إيجاد تسريع بمقدار 10 أضعاف؟ تكمن الإجابة في تعليمات SIMD/المتجهات. تنفذ هذه عمليات على عناصر مستقلة متعددة في تعليمة واحدة—على سبيل المثال، العمل على 16 float32 في وقت واحد عند استخدام مجموعة تعليمات AVX-512، أو أربعة على Arm NEON.

إذا كنت معتادًا بالفعل على SIMD، فقد سمعت عن استخدامه في أجهزة الكمبيوتر العملاقة، والجبر الخطي لتطبيقات التعلم الآلي، ومعالجة الفيديو، أو برامج ترميز الصور مثل JPEG XL. ولكن إذا كانت عمليات SIMD تتضمن فقط عناصر مستقلة، فكيف يمكننا فرزها، وهو ما يتضمن إعادة ترتيب عناصر المصفوفة المتجاورة؟ تخيل أن لدينا طريقة خاصة لفرز، على سبيل المثال، مصفوفات من 256 عنصرًا. بعد ذلك، تتكون خوارزمية الفرز السريع لفرز مصفوفة أكبر من تقسيمها إلى مصفوفتين فرعيتين: تلك الأقل من قيمة "محور" (المتوسط المثالي)، وجميع العناصر الأخرى؛ ثم التكرار حتى تصبح المصفوفة الفرعية بحجم 256 عنصرًا على الأكثر، واستخدام طريقتنا الخاصة لفرز هذه. يمثل التقسيم معظم وقت CPU، لذا إذا تمكنا من تسريعه باستخدام SIMD، فلدينا فرز سريع.

لحسن الحظ، تتضمن مجموعات التعليمات الحديثة (Arm SVE، RISC-V V، x86 AVX-512) تعليمة خاصة مناسبة للتقسيم. بالنظر إلى إدخال منفصل لقيم نعم/لا (ما إذا كان العنصر أقل من المحور)، تخزن تعليمة "الضغط والتخزين" هذه في ذاكرة متتالية فقط العناصر التي يكون إدخالها المقابل "نعم". يمكننا بعد ذلك نفي قيم نعم/لا منطقيًا وتطبيق التعليمة مرة أخرى لكتابة العناصر إلى القسم الآخر. تم استخدام هذه الاستراتيجية في الفرز السريع الخاص بـ AVX-512. ولكن ماذا عن مجموعات التعليمات الأخرى مثل AVX2 التي لا تحتوي على ضغط وتخزين؟ أظهرت الأعمال السابقة كيفية محاكاة هذه التعليمة باستخدام تعليمات التبديل. نبني على هذه التقنيات لتحقيق أول فرز سريع متجهي محمول لست مجموعات تعليمات عبر ثلاث معماريات، بل ويتفوق على عمليات الفرز السابقة الخاصة بالمعمارية.

يستخدم تنفيذنا وظائف SIMD المحمولة من Highway، لذلك لا يتعين علينا إعادة تنفيذ حوالي 3,000 سطر من C++ لكل منصة. يستخدم Highway الضغط والتخزين عند توفره، وإلا تعليمات التبديل المكافئة. على النقيض من أحدث ما توصلت إليه التقنية السابق—الذي كان أيضًا خاصًا بالأعداد الصحيحة 32 بت—ندعم مجموعة كاملة من المدخلات 16-128 بت. على الرغم من تنفيذنا المحمول الواحد، نصل إلى سرعات قياسية على كل من AVX2 وAVX-512 (Intel Skylake) وArm NEON (Apple M1). لمليون رقم 32/64/128 بت، يمكن لكودنا الذي يعمل على Apple M1 إنتاج مخرجات مفروزة بمعدلات 499/471/466 ميجابايت/ثانية. على Skylake بسرعة 3 جيجاهرتز مع AVX-512، تكون السرعات 1123/1119/1120 ميجابايت/ثانية. ومن المثير للاهتمام أن AVX-512 أسرع 1.4-1.6 مرة من AVX2—وهو تسريع يستحق الجهد الصفري الإضافي (يتحقق Highway من التعليمات المتاحة على CPU ويستخدم الأفضل المتاح). عند التشغيل على AVX2، نقيس 798 ميجابايت/ثانية، بينما أحدث ما توصلت إليه التقنية السابق المحسن لـ AVX2 يدير فقط 699 ميجابايت/ثانية. بالمقارنة، تصل المكتبة القياسية إلى 58/128/117 ميجابايت/ثانية على نفس CPU، لذا حققنا تسريعًا بمقدار 9-19 ضعفًا اعتمادًا على نوع الأرقام.

سابقًا، كان الفرز يعتبر مكلفًا. نحن مهتمون برؤية التطبيقات والقدرات الجديدة التي سيتم فتحها من خلال القدرة على الفرز بمعدل 1 جيجابايت/ثانية على نواة CPU واحدة. المصدر المرخص بموجب Apache2 ...