Google'ning vektorlashtirilgan Quicksort algoritmi

Quicksort algoritmi yillar davomida ma'lumotlar bazalari va ilmiy hisoblashlarda asosiy tartiblash usuli bo'lib kelgan. Google'ning yaqinda e'lon qilgan vektorlashtirilgan versiyasi esa bu klassik usulni butunlay yangi darajaga olib chiqadi: SIMD (Single Instruction Multiple Data) texnikasidan foydalangan holda, an'anaviy C++ std::sort'ga qaraganda o'n baravar tezroq ishlaydi.

Kolonnali ma'lumotlar bazalari va tartiblash ehtiyoji

So'nggi yillarda kolonnali ma'lumotlar bazalari ommalashib, ma'lumotlarni satr o'rniga ustun bo'yicha saqlashga o'tdi. Bu yondashuv filtratsiya va tartiblash operatsiyalarini sezilarli darajada tezlashtiradi, chunki bir ustundagi barcha qiymatlar birgalikda ishlov berilishi mumkin. Shuning uchun Google'ning yangi algoritmi aynan shu ma'lumot tuzilmasiga mo'ljallangan.

SIMD va partitioning mexanizmi

SIMD instruktsiyalari bir vaqtning o'zida bir nechta mustaqil elementlarga amal qiladi – masalan, AVX-512 instruktsiyasi 16 ta float32 ni, Arm NEON esa 4 ta elementni bir bosqichda qayta ishlaydi. Tartiblashda esa elementlarni qayta joylashtirish (partition) muhim rol o'ynaydi. Google jamoasi "compress‑store" deb nomlangan maxsus instruktsiyani ishlatadi: bu instruktsiya ha/yo'q (yes/no) baytlar ro'yxatiga qarab, mos elementlarni birma‑bir xotiraga joylaydi.

Compress‑store yordamida pivot qiymatidan kichik bo'lgan elementlar birinchi bo'limga, qolganlari ikkinchisiga tezda ajratiladi. Agar ma'lum bir arxitekturada bu instruktsiya mavjud bo'lmasa, avvalgi tadqiqotlarda tavsiya qilingan permute texnikasidan foydalanib, uni emulyatsiya qilish mumkin.

Portativ SIMD kutubxonasi Highway

Google'ning yondashuvi Google Open Source Blogda e'lon qilingan Highway kutubxonasiga asoslanadi. Highway bir nechta arxitekturalar (x86 AVX2/AVX‑512, Arm NEON, Arm SVE, RISC‑V V) uchun bir xil kod bazasini taqdim etadi, shuning uchun har bir platforma uchun alohida 3 000 dan ortiq C++ qatori yozish shart emas.

Highway avtomatik ravishda CPU'ning imkoniyatlarini aniqlaydi va eng samarali instruktsiyalarni tanlaydi. Bu yondashuv quyidagi afzalliklarni beradi:

• Bir kod bazasi orqali turli arxitekturalarda maksimal tezlik.
• Kodning saqlanishi va yangilanishi oson.
• 16‑128 bitli butun sonlar uchun to'liq qo'llab‑quvvatlash.

Amaliy tezlik natijalari

Google jamoasi bir million elementli massivlar uchun quyidagi natijalarni qayd etdi:

• Apple M1 (Arm NEON) – 499 MB/s (32‑bit), 471 MB/s (64‑bit), 466 MB/s (128‑bit).
• Intel Skylake 3 GHz (AVX‑512) – 1123 MB/s, 1119 MB/s, 1120 MB/s mos ravishda.
• AVX2 (Skylake) – 798 MB/s, standart kutubxona esa 58 MB/s (32‑bit) dan 128 MB/s (64‑bit) gacha.

Bu natijalar 9‑19 baravar tezlik oshishini ko'rsatadi, ya'ni bir yadroda 1 GB/s darajasida ma'lumotlarni tartiblash mumkin.

Yangi imkoniyatlar va kelajakda qo'llanilishi

Shu darajadagi tezlik ma'lumotlar bazalari, real‑vaqt analitika, mashina o'rganish pipeline'lari va hatto grafik renderlashda ham sezilarli foyda keltiradi. Masalan, kolonnali OLAP tizimlarida katta hajmdagi ustunlarni bir necha millisekund ichida tartiblash, so'rovlar bajarilishini sezilarli darajada qisqartiradi.

Shuningdek, bu texnika boshqa algoritmlarga ham tatbiq etilishi mumkin: merge‑sort, radix‑sort yoki hatto maxsus filtratsiya operatsiyalari. Google'ning ochiq kodli loyihasi bo'lgani uchun, hamjamiyat ushbu yondashuvni o'z loyihalariga moslashtirishi va yanada optimallashtirishi kutilmoqda.

Cheklovlar va ochiq savollar

Algoritm hali ham "partition" bosqichiga ko'p vaqt sarflaydi, shuning uchun pivot tanlash strategiyasi natijaviy tezlikka ta'sir qiladi. Hozirgi realizatsiyada 256 elementli kichik bloklar uchun maxsus vektorli tartiblash ishlatiladi; bu blok o'lchamini yanada kichik yoki katta qilish orqali yanada samarali natijalar olinishi mumkinmi, degan savol qoladi.

Yana bir muammo – eski CPU'larda (masalan, AVX2 dan oldingi) compress‑store emulyatsiyasi qo'shimcha permute operatsiyalarini talab qiladi, bu esa ba'zi holatlarda samaradorlikni pasaytiradi. Kelajakda yangi instruktsiyalar (masalan, x86-ning yangi BFloat16 qo'llab‑quvvatlashi) qanday qo'shilishi ham qiziqarli.

Xulosa

Google'ning vektorlashtirilgan Quicksort'i SIMD texnikasini keng ko'lamli, portativ kutubxona orqali birlashtirgan holda, an'anaviy sort algoritmlarini tubdan ortda qoldiradi. Bu nafaqat akademik jamoalar, balki sanoat amaliyotchilari uchun ham yangi imkoniyatlar yaratadi. Kode bazasi Apache 2. litsenziyasi ostida GitHubda mavjud, shuning uchun har bir dasturchi uni sinab ko'rishi va o'z loyihalariga qo'shishi mumkin.

Asl manba: opensource.googleblog.com