আজ আমরা ওপেন সোর্স কোড শেয়ার করছি যা সংখ্যার অ্যারে C++ std::sort-এর চেয়ে প্রায় দশ গুণ দ্রুত সাজাতে পারে এবং সর্বাধুনিক আর্কিটেকচার-নির্দিষ্ট অ্যালগরিদমগুলিকে ছাড়িয়ে যায়, একই সাথে সমস্ত আধুনিক CPU আর্কিটেকচারে পোর্টেবল। নিচে আমরা আলোচনা করছি কীভাবে এটি অর্জন করেছি।

প্রথমে, কিছু পটভূমি। সম্প্রতি কলামনার ডেটাবেসের দিকে একটি প্রবণতা দেখা যাচ্ছে যা একটি নির্দিষ্ট কলামের সমস্ত মান ধারাবাহিকভাবে সংরক্ষণ করে, পরবর্তী রেকর্ডের আগে একটি রেকর্ড বা "সারির" সমস্ত ক্ষেত্র সংরক্ষণ করার পরিবর্তে। এটি ফিল্টার বা সাজানোর জন্য দ্রুততর হতে পারে, যা SQL কোয়েরির মূল বিল্ডিং ব্লক; তাই আমরা এই ডেটা লেউটে মনোযোগ দিই।

যেহেতু সাজানো নিয়ে ব্যাপকভাবে গবেষণা করা হয়েছে, আমরা কীভাবে ১০ গুণ গতি বৃদ্ধি খুঁজে পেতে পারি? উত্তরটি SIMD/ভেক্টর নির্েশনায় রয়েছে। এগুলি একটি একক নির্দেশনায় একাধিক স্বাধীন উপাদানের উপর ক্রিয়া সম্পাদন করে—উদাহরণস্বরূপ, AVX-512 নির্েশনা সেট ব্যবহার করার সময় একবারে ১৬টি float32-এ কাজ করা, বা Arm NEON-এ চারটি।

আপনি যদি ইতিমধ্যে SIMD-এর সাথে পরিচিত হন, তাহলে আপনি শুনে থাকতে পারেন এটি সুপারকম্পিউটার, মেশিন লার্নিং অ্যাপ্লিকেশনের জন্য লিনিয়ার অ্যালজেব্রা, ভিডিও প্রসেসিং, বা JPEG XL-এর মতো ইমেজ কোডেক-এ ব্যবহৃত হয়। কিন্তু যদি SIMD অপারেশনগুলি শুধুমাত্র স্বাধীন উপাদান জড়িত থাকে, তাহলে আমরা কীভাবে সেগুলি সাজাতে পারি, যার মধ্যে সংলগ্ন অ্যারে উপাদান পুনর্বিন্যাস করা জড়িত? কল্পনা করুন আমাদের সাজানোর একটি বিশেষ উপায় আছে, উদাহরণস্বরূপ ২৫৬টি উপাদানের অ্যারে। তারপর, একটি বড় অ্যারে সাজানোর জন্য কুইকসোর্ট অ্যালগরিদম এটিকে দুটি উপ-অ্যারেতে বিভক্ত করে: যেগুলি একটি "পিভট" মান (আদর্শভাবে মধ্যমা) থেকে কম, এবং বাকি সব; তারপর পুনরাবৃত্তি করে যতক্ষণ না একটি উপ-অ্যারে সর্বাধিক ২৫৬টি উপাদান হয়, এবং এগুলি সাজানোর জন্য আমাদের বিশেষ পদ্ধতি ব্যবহার করে। বিভাজন CPU সময়ের বেশিরভাগ অংশ, তাই যদি আমরা SIMD ব্যবহার করে এটিকে গতি দিতে পারি, আমাদের একটি দ্রুত সাজানো আছে।

সৌভাগ্যবশত, আধুনিক নির্েশনা সেট (Arm SVE, RISC-V V, x86 AVX-512) বিভাজনের জন্য উপযুক্ত একটি বিশেষ নির্দেশনা অন্তর্ভুক্ত করে। হ্যাঁ/না মানের একটি পৃথক ইনপুট দেওয়া হলে (একটি উপাদান পিভটের চেয়ে কম কিনা), এই "কম্প্রেস-স্টোর" নির্দেশনাটি শুধুমাত্র সেই উপাদানগুলিকে ধারাবাহিক মেমরিতে সংরক্ষণ করে যাদের সংশ্লিষ্ট ইনপুট "হ্যাঁ"। তারপর আমরা হ্যাঁ/না মানগুলিকে যৌক্তিকভাবে অস্বীকার করতে পারি এবং উপাদানগুলিকে অন্য বিভাজনে লিখতে নির্দেশনাটি আবার প্রয়োগ করতে পারি। এই কৌশলটি একটি AVX-512-নির্দিষ্ট কুইকসোর্টে ব্যবহৃত হয়েছে। কিন্তু AVX2-এর মতো অন্যান্য নির্দেশনা সেট সম্পর্কে কী যা কম্প্রেস-স্টোর নেই? পূর্ববর্তী কাজ দেখিয়েছে কীভাবে পারমিউট নির্দেশনা ব্যবহার করে এই নির্দেশনাটি অনুকরণ করা যায়। আমরা এই কৌশলগুলির উপর নির্মাণ করি প্রথম ভেক্টরাইজড কুইকসোর্ট অর্জন করতে যা তিনটি আর্কিটেকচারে ছয়টি নির্দেশনা সেটে পোর্টেবল, এবং প্রকৃতপক্ষে পূর্ববর্তী আর্কিটেকচার-নির্দিষ্ট সাজানোর চেয়ে ভাল পারফর্ম করে।

আমাদের বাস্তবায়ন Highway-এর পোর্টেবল SIMD ফাংশন ব্যবহার করে, তাই আমাদের প্রতিটি প্ল্যাটফর্মের জন্য প্রায় ৩,০০০ লাইন C++ পুনরায় বাস্তবায়ন করতে হয় না। Highway উপলব্ধ হলে কম্প্রেস-স্টোর ব্যবহার করে এবং অন্যথায় সমতুল্য পারমিউট নির্দেশনা। পূর্ববর্তী সর্বাধুনিক—যা ৩২-বিট পূর্ণসংখ্যার জন্যও নির্দিষ্ট ছিল—এর বিপরীতে, আমরা ১৬-১২৮ বিট ইনপুটের সম্পূর্ণ পরিসর সমর্থন করি। আমাদের একক পোর্টেবল বাস্তবায়ন সত্ত্বেও, আমরা AVX2, AVX-512 (Intel Skylake) এবং Arm NEON (Apple M1) উভয়েই রেকর্ড-স্থাপনকারী গতিতে পৌঁছাই। এক মিলিয়ন ৩২/৬৪/১২৮-বিট সংখ্যার জন্য, Apple M1-এ চলমান আমাদের কোড ৪৯৯/৪৭১/৪৬৬ MB/s হারে সাজানো আউটপুট তৈরি করতে পারে। AVX-512 সহ একটি ৩ GHz Skylake-এ, গতি ১১২৩/১১১৯/১১২০ MB/s। মজার বিষয় হল, AVX-512 AVX2-এর চেয়ে ১.৪-১.৬ গুণ দ্রুত—শূন্য অতিরিক্ত প্রচেষ্টার জন্য একটি মূল্যবান গতি বৃদ্ধি (Highway CPU-তে কোন নির্দেশনাগুলি উপলব্ধ তা পরীক্ষা করে এবং সেরা উপলব্ধগুলি ব্যবহার করে)। AVX2-এ চলার সময়, আমরা ৭৯৮ MB/s পরিমাপ করি, যেখানে AVX2-এর জন্য অপ্টিমাইজ করা পূর্ববর্তী সর্বাধুনিক শুধুমাত্র ৬৯৯ MB/s পরিচালনা করে। তুলনায়, স্ট্যান্ডার্ড লাইব্রেরি একই CPU-তে ৫৮/১২৮/১১৭ MB/s-এ পৌঁছায়, তাই সংখ্যার প্রকারের উপর নির্ভর করে আমরা ৯-১৯ গুণ গতি বৃদ্ধি অর্জন করেছি।

পূর্বে, সাজানো ব্যয়বহুল হিসাবে বিবেচিত হত। আমরা দেখতে আগ্রহী যে একটি একক CPU কোর-এ ১ GB/s-এ সাজাতে সক্ষম হওয়ার মাধ্যমে কী নতুন অ্যাপ্লিকেশন এবং ক্ষমতা উন্মোচিত হবে। Apache2-লাইসেন্সপ্রাপ্ত সোর্স ...