Mohamad Iraji

شرم بر Object oriented programming! خیلی درباره‌ی بازدهی در برنامه‌نویسی صحبت می‌شه و همیشه درباره‌ی الگوریتم سریعتر یا ساختمان‌داده‌ی مناسب بحث می‌شه. اما نی‌خوام درباره‌ی یه مساله‌ای که کمتر دیدم صحبت بشه موضوعی رو باز کنم. اون هم استفاده از ویژگی‌های cpuهای مدرن مثل prefetching یا SIMD ـه! قبل از همه چیز باید بدونیم پردازش مربوط به خوندن و نوشتن اطلاعات از روی RAM و اعمال دستورات روی CPU مربوط می‌شه. اما سرعت پیشرفت و بازدهی CPUها خیلی بیشتر از RAM بوده. این عکس فاصله‌ی بازدهی پردازنده‌ها رو با رم نشون می‌ده. یعنی اگر درست کد نزنیم پردازنده زمان زیادی رو منتظر اطلاعات می‌مونه تا بتونه کارش رو ادامه بده. در این بین خیلی از ویژگی‌ها مثل سطوح مختلف Caching در پردازنده‌ها ایجاد شده مثل L1, L2, L3 و احتمالاً موقع خرید CPU بهش برخورد کردید. کاری که این Caching انجام میده خوندن اطلاعات از رم و آماده نگه داشتن اونا وقتیه که CPU در حال محاسبه ست. (به صورت فیزیکی واقعاً نزدیکتر می‌شه) از سمت دیگه چندین هسته‌ی CPU و thread استفاده می‌کنیم تا به صورت موازی پردازش‌ها رو انجام بدیم. اما هرکسی تا حالا کد برای سیستم موازی زده باشه می‌دونه اصلاً راحت نیست و الزاماً استفاده از دو خط موازی به معنی دوبرابر شدن سرعت نیست! بسته به سناریویی که قرار داریم ممکنه ۳۰ تا ۵۰ درصد افزایش سرعت داشته باشیم (بله سرعت دو برابر هم می‌رسیم مگر هیچ sync point ایی لازم نباشه اما خیلی محدوده!) اما در پردازنده‌های مدرن پردازش موازی به هسته یا thread محدود نمی‌شه. بلکه قابلیت SIMD وجود داره که کارش انجام یک عمل ریاضی روی چندین داده به صورت همزمانه. Single Instruction Multiple Data. همین‌طور CPUهای امروزی قابلیت خاصی برای پیش‌بینی شاخه در دستوراتی که اجر میشن دارند. به این صورت که وقت شما از if استفاده می‌کنید. CPU هر دو حالت true و false رو محاسبه می‌کنه و هر وقت شرط مشخص شد جواب شاخه‌ی درست رو بر می‌گردونه! حالا این قضیه در خودش یه سری روش اجرای کد و مشکل امنیتی هم داشته که مورد بحث ما نیست. حالا اگر طوری کد بنویسیم که CPU لازم نباشه مداوم branch بررسی کنه باعث افزایش سرعت پایپلاین‌های پردازشی می‌شیم. (جزییات بیشترش رو در uOps باید صحبت کنیم). حالا اگر تمام موارد بالا رو در نظر بگیریم و می‌تونیم بهینه‌ترین حالت ممکن کد بزنیم. فکر می‌کنید این افزایش سرعت تا چه حده؟ بستگی به سناریوی مساله می‌تونه بین ۱۰ تا ۱۰۰ برابر (حتی بیشتر) سریعتر باشه! اصلاً شوخی نمی‌کنم. اول مقاله نوشتم شرم بر object-oriented programming. این رو برای جلب توجه ننوشتم. در حقیقت این پارادایم برنامه‌نویسی حدود سال‌های ۸۰ میلادی محبوب شد و هنوز ادامه داره اما با پیشرفت تکنولوژی شاهد تغییر پارادایم نبودیم. در ابتدا که فاصله‌ی سرعت CPU و RAM به هم نزدیک بود تفاوت چندانی نمی‌دیدیم و همه چیز با OOP اکی بود. اما به مرور زمان که سخت‌افزار به روز شد نرم‌افزار وابسته به تفکر قدیمی باقی موند. مثلاً در OOP ما یه سری کلاس می‌سازیم و اونا رو encapsulate می‌کنیم و از اونا شی می‌سازیم و روشون پردازش انجام می‌دیم. یه چیزی مثل: struct particle { float x, y; float vx, vy; particle(const float x, const float y, const float vx, const float vy) : x(x), y(y), vx(vx), vy(vy) { } virtual ~particle() = default; virtual void update(const float delta_time) =0; }; یه کلاس خیلی ساده ذرات - particle که مختصات محیط دو بعدی x و y داره و به همین منوال سرعت در اون جهت. یه تابع virtual هم داره برای بقیه که ارث ببرند و ویژگی‌های متفاوت اضافه کنند. تو particle system یا سیستم ذارت که برای جلوه‌های ویژه VFX مثل دود، غبار، آب و غیره استفاده می‌شه ممکنه تا چندین میلیون ذره پردازش بشن (فیلم مومیایی رو یادتونه؟ آفرین همون شن‌ها) حالا من از اون کلاس ارث بردم و این تابع خیلی ساده رو پیاده کردم که فقط در هر فریم سرعت ذره رو حساب می‌کنه: void update(const float delta_time) override { volatile float x = this->x; volatile float y = this->y; x += vx * delta_time; y += vy * delta_time; this->x = x; this->y = y; } این که چرا volatile استفاده کردم به خاطر اینه که این مثال خیلی ساده ست و کامپایلر این تابع رو بهینه می‌کنه در اصل کاری که می‌کنه اجازه‌ی ساختن virtual table رو نمی‌ده و تابع بقیه جاها inline می‌شه. اما تو پروژه‌ی بزرگ با چند لایه ارث‌بری همیشه بهره بردن از بهینه‌سازی کامپایلر ممکن نیست. حالا جلوتر این رو هم بر می‌دارم که دعوایی نباشه. بعد هم کلاس particle system رو داریم که خیلی ساده هر ذره رو آپدیت می‌کنه. فقط توجه داشته باشید هر ذره به صورت یک شی در حافظه new می‌شه. حالا اگر ۱۰۰ میلیون پارتیکل رو یک بار آپدیت کنم حدود ۶۵۳ میلی‌ثانیه طول می‌کشه. بد نیست ها؟ افتضاحه! تو بازی ویدیویی که ۶۰ فریم بر ثانیه اجرا می‌شه ما ۱۶ میلی ثانیه وقت داریم تا چند میلیارد محاصبه رو انجام بدیم. (بدون volatile حدود ۵۳۰ میلی‌ثانیه) برای افزایش باذهی من یه کار خیلی ساده می‌کنم به جای این که تمام این ذرات رو new کنم که باعث می‌شه هر کدوم یه جای RAM به صورت تصادفی پخش بشن اونا رو پشت‌سر هم در یک آرایه قرار می‌دم. یعنی تمام آدرس اونا پشت‌سر هم قرار می‌گیره. فقط همین تغییر باعث می‌شه همین تعداد ۱۱۵ میلی‌ثانیه زمان ببره. حدود ۵ برابر سریعتر! همین تغییر کوچیک! چرا چون زمان پیدا کردن هر آبجکت به صورت پراکنده تبدیل شده به آدرس‌های پشت‌سر هم و CPU سریعتر می‌تونه اطلاعات رو بخونه! به این شکل: struct particles_chunk { std::vector > x; std::vector > y; std::vector > vx; std::vector > vy; } حالا در مرحله‌ی بعدی همون کد ساده رو با دستورات SIMD می‌نویسم. نتیجه‌ می‌شه ۱۱۸ میلی ثانیه: void update_simd(const float delta_time) { const size_t num_particles = particles_.x.size(); const size_t simd_end = num_particles - (num_particles % 8); const __m256 dt_v = _mm256_set1_ps(delta_time); for (size_t i = 0; i (1, std::thread::hardware_concurrency()); const size_t base_chunk_size = num_particles / num_threads; const size_t aligned_chunk_size = ((base_chunk_size + 7) / 8) * 8; std::vector threads; threads.reserve(num_threads); for (size_t t = 0; t (&particles_.x[i + prefetch_distance]), _MM_HINT_T0); _mm_prefetch(reinterpret_cast (&particles_.vx[i + prefetch_distance]), _MM_HINT_T0); _mm_prefetch(reinterpret_cast (&particles_.y[i + prefetch_distance]), _MM_HINT_T0); _mm_prefetch(reinterpret_cast (&particles_.vy[i + prefetch_distance]), _MM_HINT_T0); } _mm256_store_ps(&particles_.x[i], _mm256_fmadd_ps(_mm256_load_ps(&particles_.vx[i]), dt_v, _mm256_load_ps(&particles_.x[i]))); _mm256_store_ps(&particles_.y[i], _mm256_fmadd_ps(_mm256_load_ps(&particles_.vy[i]), dt_v, _mm256_load_ps(&particles_.y[i]))); } تا اینجا من هیچ کار عجیب و غریبی نکردم. حافظه مرتب، پشت‌سر هم و با استفاده از SIMD کد نوشتم. نه ساختمان‌داده مطرحه و نه الگوریتم و بیشتر از ۶ برابر افزایش سرعت رسیدیم! مثال بعدی که branch prediction باشه رو آخر تست یادم اومد و نشد با بقیه مقایسه کنم. اما به هر حال. فقط این مثال ساده رو ببینید: for (size_t i = 0; i < num_particles; ++i) { if (particles_.is_active[i]) { particles_.x[i] += particles_.vx[i] * delta_time; particles_.y[i] += particles_.vy[i] * delta_time; } } کاری که می‌کنیم با if چک کنیم اگر ذره فعاله سرعتش رو حساب کنیم اگر نیست هیچی. این مثال ساده حدود ۱۴۱ میلی ثانیه طول می‌کشه. اگر اون if رو حذف کنم و بیام به جاش در محاسبه غیرفعال بودن رو صفر در نظر بگیرم و جلوی branching رو بگیرم: void update_branchless(const float delta_time) { const size_t num_particles = particles_.x.size(); for (size_t i = 0; i < num_particles; ++i) { particles_.x[i] += particles_.vx[i] * delta_time * particles_.is_active[i]; particles_.y[i] += particles_.vy[i] * delta_time * particles_.is_active[i]; } } با این روش ۱۱۹ میلی ثانیه طول می‌کشه تا کدم اجرا بشه. یعنی با وجود if تقریباُ کد ما ۸۰ درصد اجرا می‌شه. این در شرایطیه که فعال بودن ذرات تصادفیه و cpu نمی‌تونه branch perdiction درستی داشته باشه. برای همین کند می‌شه. حالا شاید بگید که تو گفتی چند میلیون محاسبه زیر ۱۶ میلی‌ثانیه. بله درسته. من اینجا از دو thread استفاده کردم. فقط جنبه‌ی نمایش داشت از warmup و اینا هم اجتناب کردم چون در دنیای واقعی این پردازش‌ها می‌ره روی GPU و Compute shader که معرفی اون خودش یه پست دیگه ست. کدها رو روی CPU قدیمی اجرا کردم: Intel Core i7 6700K @ 4.00GHz Skylake 14nm 16.0GB Dual-Channel DDR4 @ 1069MHz اگر دوست داشتید این محاسبه رو با زبان برنامه‌نویسی مورد علاقه‌تون تست کنید و سعی در بهینه کردنش کنید. در ضمن اگر تمام اینا رو کنار هم بذاریم با یه سری مفاهیم شبیه به همین‌هایی که گفتیم با جزییات بیشتر می‌شه Data oriented programming که در زبان‌های مختلف مثل خانواده‌ی C، Rust، Zig و غیره براشون کتابخونه و آموزش موجوده. خلاصه بازدهی فقط به الگوریتم و ساختمان‌داده محدود نمی‌شه.

22,055 Aufrufe