نکات مربوط به پرفورمنس در برنامه‌نویسی Concurrent

یکی از اصلی‌ترین کاربردها و هدف‌های برنامه‌نویسی موازی/همزمان، افزایش پرفورمنس نرم‌افزارمون هست. درواقع، دلیل اصلیِ من برای یادگیری همزمانی در سی++ همین مورد بود چراکه پرفورمنس همیشه برای من اهمیت بسیار بالایی داشته(اگر نگم بیشترین اهمیت) و یکی از اولین معیارهای من برای بررسی کیفیت یک کد، پرفورمنس اون کد هست. اصلا اگر پرفورمنس برامون مهم نیست، چرا باید سی++ رو انتخاب کنیم درحالی که زبان‌های دیگه‌ای وجود دارن که هم پیچیدگی کمتری دارن و هم تر و تمیزتر هستن؟

در این پست، چند نکته و مفهوم کوتاه و ابتدایی که می‌تونن روی پرفورمنس نرم‌افزارمون تاثیر بذارن و باید بهشون توجه کنیم رو به شکل سطحی بررسی می‌کنیم: مفاهیم ابتدایی‌ای مثل اینکه «کدام متغییرها توسط کدام ترد پردازش بشه»، «چندتا هستهٔ پردازشی استفاده کنیم» و چیزهایی از این دست.

این مفاهیم با اینکه مفاهیم ابتدایی‌ای هستن، میتونن تاثیر شگرفی در وضعیت پرفورمنس نرم‌افزار ما داشته باشن و صرفا هم مخصوص سی++ نیستن.

موضوع اولی که بهش می‌پردازیم اینه: «چندتا هستهٔ پردازشی رو باید استفاده کنیم؟»

چندتا پردازنده؟

تعداد و ساختار پردازنده‌ها یکی از اولین و مهم‌ترین فاکتورهایی هست که میتونه روی پرفورمنس یک نرم‌افزار چندنخی تاثیر بذاره. بعضی وقت‌ها ما دقیقا می‌دونیم که سخت‌افزار هدف ما چی هست و میتونیم نرم‌افزارمون رو دقیقا برای همون شکل از سخت‌افزار طراحی کنیم و تست‌ها رو هم روی همون انجام بدیم. در حوزهٔ Packet Processing یا سیستم‌های Trading معمولا این شرط برقراره و این خیلی کمک بزرگیه. اما همهٔ مهندسین نرم‌افزار به این اندازه بخت یارشون نیست. ممکنه سیستمی که طراحی و توسعهٔ نرم‌افزار رو روش انجام میدن با سیستم نهایی که اون نرم‌افزار میخواد روش اجرا بشه تفاوت داشته باشه و در این مورد، حتی تفاوت‌های کوچیک هم میتونن تعیین‌کننده باشن چراکه رفتار و خصیصه‌های یک نرم‌افزار Concurrent میتونه نسبت به محیطی که در اون اجرا میشه، تغییرات بسیاری داشته باشه. توسعه‌دهنده ممکنه روی یک سیستم quad-core نرم‌افزار رو توسعه بده اما کاربرا ممکنه مثلا یک پردازندهٔ multi-core داشته باشن، یا چندتا پردازنده single-core داشته باشن، یا اصلا چندتا پردازندهٔ multi-core داشته باشن!

در این موارد، باید در طراحی و توسعهٔ نرم‌افزار دقت خیلی بیشتری خرج داده بشه و همهٔ جوانبِ تصمیم‌هایی که گرفته میشه، سنجیده بشه.

حالا فرض کنیم که سیستمِ هدفِ ما، میتونه ۱۶ ترد رو به صورت همزمان اجرا بکنه. اگر ما بخوایم که نرم‌افزارمون بیشترین استفاده رو از منابع سیستم داشته باشه، ما هم باید کاری کنیم که نرم‌افزارمون دقیقا از ۱۶ ترد استفاده کنه. اگر تعداد ترد‌هامون کمتر از ۱۶ باشه، اونوقت همهٔ توانِ پردازنده رو استفاده نکردیم. اگر تردهامون بیشتر از ۱۶ باشه، اونوقت باعث میشیم که سیستم به صورت کلی کندتر بشه چراکه پردازنده مجبور هست context switching انجام بده و در نتیجه زمانِ با ارزشِ پردازنده‌مون برای context switching هدر رفته(که از قضا، عملیات سبکی هم نیست). به حالت دومِ oversubscription هم می‌گن.

توی سی++ برای اینکه بدونیم سیستم‌مون میتونه چندتا ترد رو به صورت همزمان اجرا کنه، میتونیم از تابعی که توی کتابخانهٔ استاندارد برامون قرارداده شده استفاده کنیم:

std::thread::hardware_concurrency()

البته، این تابع صرفا میگه که سخت‌افزار ما از چند ترد همزمان پشتیبانی می‌کنه و عددی که به ما میده به این معنی نیست که حتما اون تعداد ترد آزاد هستند. یعنی چی؟ یعنی اگر ما در نرم‌افزار خودمون دوتا ترد داشته باشیم که بخوان وظایف رو بین تردهای دیگه پخش کنن و جفتشون این تابع رو صدا بزنن، هردوتاشون عدد ۱۶ رو خواهند دید(فرض کردیم سخت‌افزارمون ۱۶تا ترد داره). در نتیجه اگه حواسمون نباشه، ممکنه هرکدوم از اون تردها بیان و ۱۶ تا ترد جدید بسازن و به این ترتیب یک oversubscription خیلی بزرگ خواهیم داشت. اگه نخوایم خودمون این مسئله رو مدیریت کنیم، میتونیم از std::async() ‎ استفاده کنیم که خودش این موضوع رو به شکل خودکار حل میکنه. یا اینکه میتونیم از thread poolها استفاده کنیم.

حالا همهٔ این‌ها رو در نظر گرفتیم، یعنی دیگه همه‌چی ردیفه؟ نه! بعضی وقت‌ها، نرم‌افزاری که ما داریم توسعه می‌دیم، تنها نرم‌افزار CPU-intensiveای نیست که میخواد روی سیستم هدف اجرا بشه و نرم‌افزارهای دیگه‌ای هم وجود دارن که دارن از منابع پردازنده و تردها استفاده می‌کنن و در این صورت ما باید ببینیم بقیهٔ نرم‌افزارها از کدوم هسته‌های پردازنده دارن استفاده میکنن، چندتا ترد دارن و چقدر اهمیت دارن و بر این اساس، تعداد تردهای نرم‌افزار خودمون رو تعیین کنیم. معمولا چنین سیستم‌هایی رو طوری تنظیم میکنن که نرم‌افزارها راحت بدونن چه تعدادی ترد باید استفاده کنن(و مثلا زمانی که std::thread::hardware_concurrency()‎ رو صدا می‌زنن، عدد درست رو دریافت میکنن). یا اینکه تعداد هسته‌های پردازشی رو برای نرم‌افزارهاشون از قبل مشخص می‌کنن تا نرم‌افزار نتونه بیشتر از مقدار تعیین شده از هسته‌های پردازشی استفاده کنه.

یک راه دیگه هم هست که من دوستش دارم و اون هم ایزوله کردن هسته‌های پردازنده هست تا scheduler از اون‌ها استفاده نکنه بنابراین ما همیشه مطمئن هستیم که به اندازه‌ای که نیاز داریم، منابع پردازشی موجود هست.

و نکتهٔ آخر، الگوریتمی که برای حل مسئله‌مون هم انتخاب می‌کنیم هم می‌تونه تحت تاثیر تعداد واحدهای پردازشیمون قرار بگیره. به عنوان مثال اگر یک سیستم Massively Parallel داریم که تعداد زیادی واحد پردازشی داره، ممکنه الگوریتمی که به صورت کلی تعداد عملیات‌های بیشتری انجام میده سریعتر از الگوریتمی باشه که عملیات‌های کمتری انجام میده بخاطر اینکه اون عملیات‌های زیاد میتونه بین تعداد زیادی پردازنده پخش بشه و هرکدومشون، بخش کوچیکی از عملیات‌ها رو انجام بدن.

اما زمانی که تعداد واحدهای پردازشیمون زیاد میشه، احتمال اینکه به یک مشکل پرفورمنسی دیگه برخورد کنیم هم بیشتر میشه: چندین پردازنده سعی میکنن که به یک دادهٔ یکسان دسترسی پیدا کنن.

Data Contention & Cache Ping-Pong

زمانی که دوتا ترد روی دوتا پردازندهٔ مختلف درحال اجرا هستند، ممکنه که جفتشون به یک داده در حافظه دسترسی پیدا کنن. این مسئله همیشه مشکل‌ساز نیست. اگه جفتشون فقط بخوان اون داده رو بخونن، همه‌چی خوبه چراکه هر پردازنده اون داده رو کپی میکنه توی Cache خودش و ادامه میده. اما مشکل جایی شروع میشه که یکی از این تردها بخواد اون داده رو تغییر بده. چرا؟ چون اون پردازنده دومی حالا باید صبر کنه تا تغییراتی که توی حافظه انجام شده، به کش خودش propagate بشه و این عملیات propagate کردن داده‌ها در حافظه، ممکنه به اندازهٔ چندصد دستور cpu زمان مصرف کنه!

کد زیر یک مثال ساده از چنین وضعیتی هست:

std::atomic<unsigned long> counter(0);
void processing_loop()
{
  while(counter.fetch_add(1,std::memory_order_relaxed)<100000000)
  {
    do_something();
  }
}

در این کد، متغییر counter یک متغییر جهانی(global) هست بنابراین هر تردی که تابع processing_loop()‎ رو صدا میزنه، یک متغییر یکسان دسترسی پیدا میکنه و سعی می‌کنه که counter رو تغییر بده. نتیجه چیه؟ هربار که یک ترد/پردازنده می‌خواد به متغییر counter دسترسی پیدا کنه، باید مطمئن بشه که حافظهٔ cacheاش، آخرین نسخهٔ به‌روزِ متغییر counter رو داره. بعد تغییرش بده و دوباره به پردازنده‌های دیگه بگه که cache خودشون رو به‌روز کنن. حتی استفاده از std::memory_order_relaxed هم اینجا کمک چندانی نمی‌کنه چون صرفا به کامپایلر میگه که نیاز نیست چیزی رو synchronize کنه اما از اونجایی که عملیات fetch_add، یک عملیات read-modify-write هست، باید همیشه آخرین نسخهٔ counter رو داشته باشه.

بنابراین در حالتی که تردهای دیگه‌ای هم وجود دارن که می‌خوان این کد رو اجرا کنن، دادهٔ مربوط به متغییر counter همش بین پردازنده‌ها و cacheهاشون در حال رفت و آمد خواهد بود. در نتیجه، اگه مثلا زمانِ اجرای تابع do_something()‎ کم باشه، پردازنده‌ها بیشتر زمان‌شون رو صرف این خواهند که منتظر همدیگه باشن تا مقدار به‌روز رو دریافت کنن. به این وضعیت میگن high contention. اگر پردازنده‌ها مجبور نباشن که همش منتظر همدیگه باشن، وضعیت‌مون low contention خواهد بود.

همچنین، در این چنین کدی که داده‌ها بین cacheهای پردازنده‌های مختلف درحال رفت و آمد هست، میگیم که cache ping-pong داریم. به‌صورت کلی، وجود وضعیت high data contention در کد می‌تونه باعث بوجود اومدن cache ping-pong بشه که قاتل مخوف پرفورمنس هست.

یکی از تنها راه‌های موجود برای جلوگیری از بوجود اومدنِ cache ping-pong، این هست که سعی کنیم از یکی از پایه‌ای‌ترین guidelineهای برنامه‌نویسی Concurrent استفاده کنیم: استفاده از دادهٔ sharedشده رو به حداقل برسونیم.

پس اگه تونستیم کاری کنیم که تردهامون به یک متغییر یکسان دسترسی نداشته باشن، مشکل حله دیگه؟ آخِی 😄 معلومه که نه. باز هم ممکنه cache ping-pong داشته باشیم و این‌بار دلیلش false sharing هست!

False Sharing

زمانی که ما به یک متغییر دسترسی پیدا می‌کنیم، صرفا فقط همون یدونه متغییر توسط پردازنده خونده نمیشه. پردازنده‌ها با مکان‌های توی حافظه به‌صورت یکی‌یکی رفتار نمی‌کنن بلکه به شکل بلوکی از چندین مکان باهاشون رفتار می‌کنن که به این بلوک‌ها می‌گیم Cache Line. بنابراین هربار که به یه متغییر که در حافظهٔ اصلی قرار داره دسترسی پیدا می‌کنیم، پردازنده به اندازهٔ Cache Line از حافظه میخونه و داخل cache کپی می‌کنه. یعنی چی؟ یعنی اگر فرض کنیم اندازهٔ cache line ما ۶۴ بایت هست(که معمولا همینقدره) و یک متغییر مثلا از نوع int رو می‌خونیم، پردازنده در اصل بجای ۴ بایت(که اندازهٔ معمول یک int هست)، میاد و ۶۴ بایت رو میخونه و ما صرفا از ۴ بایتِ اول استفاده می‌کنیم.

بنابراین، از اونجایی که سخت‌افزار مربوط به cache فقط با بلوک‌های حافظه‌ای که به اندازهٔ cache line هستند میتونه کار کنه، نتیجه این میشه که داده‌هایی که اندازه‌شون کوچیک هست و مکانشون در حافظهٔ اصلی کنار همه، همشون در یک cache line قرار می‌گیرن. و این در حالت عادی خیلی خیلی چیز خوبیه چون باعث میشه دسترسی به متغییرهای نزدیک‌به‌هم خیلی خیلی سریع باشه.

پس مشکل چیه؟

فرض کنید که یک آرایه از intها داریم که هرکدوم از درایه‌های این آرایه توسط یک ترد مجزا پردازش می‌شه و مقدارش عوض میشه و اینکار به صورت مداوم انجام میگیره. از اونجایی که سایز یک int بسیار کوچیکتر از سایز cache line هست، چندین درایه از آرایه میتونن توی cache line جا بگیرن. در نتیجه با اینکه هرکدوم از تردها به درایه‌های متفاوتی از آرایه دسترسی دارن، هربار که یک ترد یکی از درایه‌ها رو تغییر میده، مقدار cache بقیهٔ تردها که درایه‌شون در اون cache line بوده invalidate میشه و پردازندهٔ مربوط به اون تردها باید دوباره حافظهٔ cache رو بارگزاری کنه تا آخرین تغییرات رو داشته باشه. بنابراین باز هم cache ping-pong خواهیم داشت.

راه‌حل چیست؟ باید کاری کنیم که داده‌هایی که یک ترد نیاز داره همشون کنار همدیگه باشن و از داده‌های مربوط به تردهای دیگه دورتر باشن تا در یک cache line قرار نگیرن. در سی++ متغییری تعریف شده به اسم std::hardware_destructive_interference_size که نشون‌دهندهٔ این هست که تعداد بایت‌های پشت‌سر هم چقدر باید باشه تا false sharing اتفاق بیوفته و در نتیجه داده‌های تردهای مختلف چقدر باید از همدیگه فاصله داشته باشن. مثالش رو در ادامه خواهیم دید.

حواسمون باشه که مشکل false sharing زمانی که داریم از مکانیزم‌های lock مثل Mutex استفاده می‌کنیم هم میتونه بوجود بیاد! فرض کنید یک کلاس یا یک struct ساده داریم که چندتا داده داخلش وجود داره و یک mutex هم برای انجام synchronization و محافظت از داده‌ها در محیط multi-threaded قرار دادیم. اگه مکان داده‌ها و mutexمون در حافظه نزدیک همدیگه باشن، برای تردی که میتونه lock رو انجام بده خوبه چون که با دسترسی به mutex، داده‌ها هم به‌صورت اتوماتیک قبلا خونده شدن و وارد کَش شدن. اما این موضوع یک ضرر هم داره: اگر زمانی که ترد اول lock رو گرفته و داره با داده‌ها کار می‌کنه، یک تردِ دیگه بیاد و بخواد که mutex رو قفل کنه، باید به حافظهٔ اون mutex دسترسی پیدا کنه. قفل‌های mutex معمولا با استفاده از یک عملیات read-modify-write اتمیک پیاده‌سازی میشن. مشکل اینجاست که این عملیات‌ها باعث invalidate شدن cache lineای میشن که میوتکس در اون قرار گرفته! بنابراین اگر فرض کنیم که ترد A قبلا تونسته میوتکس رو بگیره و درحال ادامهٔ کارش با داده‌ها باشه که یک ترد B میاد و سعی می‌کنه که میوتکس رو قفل کنه(و طبیعتا نمیتونه) و این باعث میشه که cache line مربوط به میوتکس invalidate بشه. حالا اگه cache line مربوط به میوتکس و داده‌ها یکسان باشه، اقدام ترد B برای قفل کردن میوتکس عملا باعث میشه که ترد A یکهو stall بشه چون حافظهٔ cacheاش اعتبارش رو از دست داده!

برای اینکه ببینیم آیا چنین چیزی داره واقعا در کد ما اتفاق میوفته یا نه، باید کدمون رو تست بکنیم. مثلا برای امتحان کردن اینکه آیا mutex contention داره به پرفورمنس ما ضربه میزنه یا نه، میتونیم کلاسمون رو به این شکل تغییر بدیم و دوباره پرفورمنس رو تست کنیم:

struct protected_data
{
  std::mutex m;
  char padding[std::hardware_destructive_interference_size];
  my_data data_to_protect;
};

و اگر بخوایم مسئله false sharing بین درایه‌های یک آرایه رو تست کنیم میتونیم از چنین چیزی استفاده کنیم:

struct my_data
{
  data_item1 d1;
  data_item2 d2;
  char padding[std::hardware_destructive_interference_size];
};
my_data some_array[256];

اما اگر این موضوع که تردهای مختلف به داده‌های موجود در یک cache line یکسان دسترسی پیدا کنن چیز بدیه، این نحوهٔ جای‌گیری داده‌ها صرفا برای یدونه ترد چه تاثیری می‌تونه داشته باشه؟

داده‌هامون چقدر نزدیک به همدیگه هستن؟

تا اینجا داشتیم راجع به اینکه چطور طراحی نرم‌افزارمون میتونه روی پرفورمنس چندتا ترد که به صورت همزمان دارن اجرا میشن تاثیر بذاره صحبت می‌کردیم. اما مکانِ داده‌ها برای پرفورمنس تک تکِ تردها هم مهمه.

حافظهٔ cache یک ابزار بسیار با ارزش هست و سرعت دسترسی به داده‌هایی که در cache هستند بسیار بالاست و باید بتونیم از این ابزار باارزش و گرون، بیشترین استفاده رو بکنیم. اگر داده‌هایی که توسط یک ترد استفاده میشن توی جاهای مختلفِ حافظهٔ اصلی پخش شده باشن، احتمالا در چندین cache line مختلف قرار دارن و برای دسترسی بهشون، پردازنده باید cache line رو جابجا کنه تا داده‌ها رو از حافظهٔ اصلی وارد کَش بکنه در نتیجه memory access latencyمون بالا خواهد رفت و پرفورمنسمون کمتر میشه. از طرف دیگه اگر داده‌هامون نزدیک هم باشن، احتمال اینکه باهمدیگه در یک cache line قرار بگیرن بیشتره و پردازنده کمتر نیاز داره که cache line رو جابجا کنه. همچنین، اگر داده‌هامون در مکان‌های مختلفی در حافظه پخش شده باشن، احتمال اینکه حافظه کَش رو هدر بدیم هم زیاده چرا که ممکنه بخش زیادی از داده‌هایی که وارد cache line میشن رو نیاز نداشته باشیم و به صورت کلی میزان cache missمون بالا میره. در سی++ یک متغییر دیگه وجود داره به اسم std::hardware_constructive_interference_size که تعداد بایت‌های پشت‌سرهمی که تضمین میشه در یک cache line قرار بگیرند رو نشون میده. معمولا مقداری که این متغییر برمیگردونه با std::hardware_destructive_interference_size یکی هست(که منطقیه!).

الگوهای دسترسی به داده‌ها

به‌صورت کلی، چیزی که باید بهش توجه کنیم الگوی دسترسی به داده‌ها یا data access patterns هست:

• توزیع داده‌ها رو جوری انجام بدیم که داده‌های مربوط به هر ترد نزدیک همدیگه باشن
• به‌صورت کلی داده‌هایی که توسط تردها نیاز دارن رو کم کنیم.
• سعی کنیم مطمئن بشیم که تردهای مختلف به داده‌هایی دسترسی پیدا می‌کنن که از همدیگه دور هستن تا جلوی false sharing رو بگیریم

و البته، اعمال کردن این الگوها به همین راحتی نیست... به قول خارجیا it is easier said than done.

به‌عنوان مثال، یک درخت باینری به‌صورت طبیعی طوری نیست که بشه این قوانین رو براش اعمال کرد چون مثلا معمولا حافظهٔ گره‌های درخت به‌صورت پویا(dynamic) تخصیص پیدا می‌کنن و بنابراین هرکدومشون در جاهای مختلفی از حافظه در heap قرار دارن.

نتیجه

در این پست متوجه شدیم که به‌صورت کلی برای طراحی یک کد که پرفورمنسش در محیط multi-threaded مهمه، چندتا چیز مهم وجود داره که باید حواسمون بهشون باشه و اونها عبارت‌اند از

• میزان نزدیکی داده‌ها به همدیگه
• موضوع False Sharing
• موضوع Data contention

متوجه شدیم که حتی صرفا عوض کردن layout داده‌ها یا توزیع داده‌ها بین threadها میتونه پرفورمنس رو بهبود ببخشه.

ممنون که خوندید!

عزت زیاد.