رفتن به مطلب
مرجع رسمی سی‌پلاس‌پلاس ایران

پست های پیشنهاد شده

ارسال شده در (ویرایش شده)

با سلام !

دو قطعه برنامه ی زیر یکی آرایه ۱۰۰۰۰۰ تایی در حافظه Stack ساخته و به صورت Random مقداردهی شده و Sort میشود. کد اول به زبان ++C و با استاندارد 11 نوشته شده است که حدود ۷ دقیقه و کد دوم به زبان C نوشته شده است که حدود 1 دقیقه زمان میبرد ! 

CPU Intel i7 M 620 (4) @ 2.667GHz

آیا راهی برای بهینه سازی سرعت اجرای برنامه ی نوشته شده به زبان ++C هست ؟

کد نوشته به زبان ++C :

#include <iostream>
#include <functional>
#include <utility>
#include <array>
#include <random>
#include <chrono>
const unsigned int MAX_LENGTH = 100000;

bool Compare(unsigned int FirstVariable,unsigned int SecondVariable){
  if(FirstVariable < SecondVariable)
    return true;
  return false;
}

void SortArray(std::array<unsigned int,MAX_LENGTH> &MyArray,std::function<bool(unsigned int,unsigned int)> function){
  for(unsigned int index=0;index < MAX_LENGTH;++index)
      for(unsigned int AnotherIndex=0;AnotherIndex<MAX_LENGTH;++AnotherIndex)
          if(function(MyArray[index],MyArray[AnotherIndex]))
            std::swap(MyArray[index],MyArray[AnotherIndex]);
}

void PrintArrayElements(const std::array<unsigned int,MAX_LENGTH> &MyArray){
  for(const auto &item : MyArray)
    std::cout << item << std::endl;
}

void RandomizeArray(std::array<unsigned int,MAX_LENGTH> &MyArray){
  std::mt19937_64 Random(static_cast<int>(std::chrono::high_resolution_clock::now().time_since_epoch().count()));
  std::uniform_int_distribution<> RandomGenerator(0,1000);
  for(unsigned int index=0;index<MAX_LENGTH;++index)
    MyArray[index] = static_cast<unsigned int>(RandomGenerator(Random));
}

int main(){
  std::array<unsigned int,MAX_LENGTH> MyOrginalArray;
  RandomizeArray(MyOrginalArray);
  SortArray(MyOrginalArray,Compare);
  PrintArrayElements(MyOrginalArray);
  return 0x0000;
}

کد نوشته شده به زبان C :
 

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <stdbool.h>
#define MAX_LENGTH 100000
bool Compare(unsigned int FirstVariable,unsigned int SecondVariable){
  if(FirstVariable < SecondVariable)
    return true;
  return false;
}
void SortArray(unsigned int *MyArray,bool (*compare)(unsigned int,unsigned int)){
  unsigned int tmp=0;
  for(unsigned int index=0;index < MAX_LENGTH;++index){
      for(unsigned int AnotherIndex=0;AnotherIndex<MAX_LENGTH;++AnotherIndex){
          if(compare(MyArray[index],MyArray[AnotherIndex])){
            tmp = MyArray[index];
            MyArray[index] = MyArray[AnotherIndex];
            MyArray[AnotherIndex] = tmp;
          }
        }
    }
}

void RandomizeArray(unsigned int *MyArray){
  srand(time(NULL));
  for(unsigned int index=0;index < MAX_LENGTH ;++index)
    MyArray[index] = rand() % 1000;
}

void PrintArrayElements(unsigned int *MyArray){
  for(unsigned int index=0;index<MAX_LENGTH;++index)
    fprintf(stdout,"%d\n",MyArray[index]);
}

int main(){
  unsigned int Array[MAX_LENGTH];
  RandomizeArray(Array);
  SortArray(Array,Compare);
  PrintArrayElements(Array);
  return 0x0000;
}

 

ویرایش شده در توسط قاسم رمضانی منش

به اشتراک گذاری این ارسال


لینک به ارسال
به اشتراک گذاری در سایت های دیگر

سلام بر حاج قاسم

با تست اول به طور طبیعی روی لینوکس و لپتاپ خودم با کامپایلر g++-8 خروجی شد :

315 ثانیه معادل 5.25 دقیقه

حالا تست دوم با تنظیم کردن دو تا فلگ برای بهینه سازی فلگ های -O3 و -ffast-math

نتیجه شد :

26 ثانیه

بدون دست بردن توی کد تونستم با ست کردن فلگ بهینه سازی زمان رو کاهش بدم.

 

به اشتراک گذاری این ارسال


لینک به ارسال
به اشتراک گذاری در سایت های دیگر
ارسال شده در (ویرایش شده)
در 19 دقیقه قبل، بهنام صباغی گفته است :

حالا تست دوم با تنظیم کردن دو تا فلگ برای بهینه سازی فلگ های -O3 و -ffast-math

مرسی متشکرم.

بله سرعت رو به شدت بالابرد !

اما !

این فلگ هایی که گفتید فقط فلگ اول O3- برای بهینه سازی هست که باعث افزایش سرعت میشه.

و فلگ دوم ffast-math- به کامپایلر اجازه میده که یک سری از قوانین IEEE و ISO و نقض کنه  :

GCC Command Options

و گفته شده که در صورت استفاده از فلگ ffast-math- از هیچ کدام سطح های بهینه سازی O- استفاده نکنید که باعث خروجی اشتباه میشه !

ویرایش شده در توسط قاسم رمضانی منش
مشخص کردن دقیق فلگ افزایش دهنده سرعت.

به اشتراک گذاری این ارسال


لینک به ارسال
به اشتراک گذاری در سایت های دیگر
در 3 دقیقه قبل، فرهاد شیری گفته است :

آقا نکته ی جالبی گفتی حداقل برای من که جالب بود چون من معمولا این فلگ ها را تغییر نمیدم

تشکر

اره منم تغییر نمیدادم ولی چند روزی هست درگیر بهینه سازی هستیم جالبه که فعال کردن این فلگ ها علاوه بر بالا بردن سرعت باعث میشه کد اسمبلی یکم پیچیده تر بشه و برای مهندسی معکوس سخت تر بشه کار اینطور که شنیدم ولی تست نکردم هنوز .

 

به اشتراک گذاری این ارسال


لینک به ارسال
به اشتراک گذاری در سایت های دیگر
در 7 دقیقه قبل، فرهاد شیری گفته است :
در 2 ساعت قبل، قاسم رمضانی منش گفته است :

 

معمولا خیلی بهتره که اینطور پردازش های سنگین را به صورت موازی انجام بدید مثلا از تکنیک Divide and Concur استفاده کنید.

ولی با تغییراتی که دادم برای 20000 تا تقریبا 3 ثانیه طول کشید که سورت کنه!

مرسی ممنون حتما درباره این تکنیک جستجو میکنم.

با تغییراتی که دادید سرعت را از  ۷ دقیقه به ۱ دقیقه کاهش دادید !. (شما با مقدار ۲۰۰۰۰ هزار اجرا کرده بودید. مقدار پیش فرض ۱۰۰۰۰۰ بود.)

به اشتراک گذاری این ارسال


لینک به ارسال
به اشتراک گذاری در سایت های دیگر
در 6 دقیقه قبل، فرهاد شیری گفته است :

الگوریتم های مرتب سازی های دیگه را هم تست کنید

بله ! صدالبته که عملکرد انواع الگوریتم ها و روششون میتونه توی سرعت تاثیر داشته باشه.

مثل اینکه درست منظور خودم را نگفتم:) هردو کدی که ارسال کردم به یک روش نوشته شده اند ولی یکی به زبان سی پلاس پلاس و با استفاده از کتابخانه های استاندارد و یکی با استفاده از زبان سی و کتابخونه های استاندارد خودش. 

البته این مورد بدیهی هست که سرعت کمی از سی به سی پلاس پلاس کاهش پیدا کنه. که بنده دنبال راهی بودم برای رفع این مشکل که آقا بهنام با معرفی فلگ بهینه سازی O- تا حدود بسیار زیادی این مشکل رو برطرف کردن.

به اشتراک گذاری این ارسال


لینک به ارسال
به اشتراک گذاری در سایت های دیگر
در 9 دقیقه قبل، قاسم رمضانی منش گفته است :

بله ! صدالبته که عملکرد انواع الگوریتم ها و روششون میتونه توی سرعت تاثیر داشته باشه.

مثل اینکه درست منظور خودم را نگفتم:) هردو کدی که ارسال کردم به یک روش نوشته شده اند ولی یکی به زبان سی پلاس پلاس و با استفاده از کتابخانه های استاندارد و یکی با استفاده از زبان سی و کتابخونه های استاندارد خودش. 

البته این مورد بدیهی هست که سرعت کمی از سی به سی پلاس پلاس کاهش پیدا کنه. که بنده دنبال راهی بودم برای رفع این مشکل که آقا بهنام با معرفی فلگ بهینه سازی O- تا حدود بسیار زیادی این مشکل رو برطرف کردن.

اره دیگه اگر صرف زمان مهم بود کتابخونه معرفی میکردم که با پارالل کردن فور بدون تغییر زیاد توی کد بتونی سرعتت رو خیلی زیاد کنی

مثلا استفاده از openmp میتونه خیلی کمک کنه

به اشتراک گذاری این ارسال


لینک به ارسال
به اشتراک گذاری در سایت های دیگر
در در 8 آذر 1397 در 17:46، قاسم رمضانی منش گفته است :

با سلام !

دو قطعه برنامه ی زیر یکی آرایه ۱۰۰۰۰۰ تایی در حافظه Stack ساخته و به صورت Random مقداردهی شده و Sort میشود.

کد اول به زبان ++C و با استاندارد 11 نوشته شده است که حدود ۷ دقیقه و کد دوم به زبان C نوشته شده است که حدود 1 دقیقه زمان میبرد ! 

CPU Intel i7 M 620 (4) @ 2.667GHz

آیا راهی برای بهینه سازی سرعت اجرای برنامه ی نوشته شده به زبان ++C هست ؟

 

کد نوشته به زبان ++C :


#include <iostream>
#include <functional>
#include <utility>
#include <array>
#include <random>
#include <chrono>
const unsigned int MAX_LENGTH = 100000;

bool Compare(unsigned int FirstVariable,unsigned int SecondVariable){
  if(FirstVariable < SecondVariable)
    return true;
  return false;
}

void SortArray(std::array<unsigned int,MAX_LENGTH> &MyArray,std::function<bool(unsigned int,unsigned int)> function){
  for(unsigned int index=0;index < MAX_LENGTH;++index)
      for(unsigned int AnotherIndex=0;AnotherIndex<MAX_LENGTH;++AnotherIndex)
          if(function(MyArray[index],MyArray[AnotherIndex]))
            std::swap(MyArray[index],MyArray[AnotherIndex]);
}

void PrintArrayElements(const std::array<unsigned int,MAX_LENGTH> &MyArray){
  for(const auto &item : MyArray)
    std::cout << item << std::endl;
}

void RandomizeArray(std::array<unsigned int,MAX_LENGTH> &MyArray){
  std::mt19937_64 Random(static_cast<int>(std::chrono::high_resolution_clock::now().time_since_epoch().count()));
  std::uniform_int_distribution<> RandomGenerator(0,1000);
  for(unsigned int index=0;index<MAX_LENGTH;++index)
    MyArray[index] = static_cast<unsigned int>(RandomGenerator(Random));
}

int main(){
  std::array<unsigned int,MAX_LENGTH> MyOrginalArray;
  RandomizeArray(MyOrginalArray);
  SortArray(MyOrginalArray,Compare);
  PrintArrayElements(MyOrginalArray);
  return 0x0000;
}

کد نوشته شده به زبان C :
 


#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <stdbool.h>
#define MAX_LENGTH 100000
bool Compare(unsigned int FirstVariable,unsigned int SecondVariable){
  if(FirstVariable < SecondVariable)
    return true;
  return false;
}
void SortArray(unsigned int *MyArray,bool (*compare)(unsigned int,unsigned int)){
  unsigned int tmp=0;
  for(unsigned int index=0;index < MAX_LENGTH;++index){
      for(unsigned int AnotherIndex=0;AnotherIndex<MAX_LENGTH;++AnotherIndex){
          if(compare(MyArray[index],MyArray[AnotherIndex])){
            tmp = MyArray[index];
            MyArray[index] = MyArray[AnotherIndex];
            MyArray[AnotherIndex] = tmp;
          }
        }
    }
}

void RandomizeArray(unsigned int *MyArray){
  srand(time(NULL));
  for(unsigned int index=0;index < MAX_LENGTH ;++index)
    MyArray[index] = rand() % 1000;
}

void PrintArrayElements(unsigned int *MyArray){
  for(unsigned int index=0;index<MAX_LENGTH;++index)
    fprintf(stdout,"%d\n",MyArray[index]);
}

int main(){
  unsigned int Array[MAX_LENGTH];
  RandomizeArray(Array);
  SortArray(Array,Compare);
  PrintArrayElements(Array);
  return 0x0000;
}

 

من قبلاً در گروه به این مساله اشاره کرده بودم که همیشه نباید از ویژگی‌های جدید انتظار داشت که در هر جایی نتیجهٔ خوبی رو ارائه بدن، چون هر ویژگی در جای مناسب خودش کاربرد داره نه در هر جا!

کد شما با پیشنهاداتی که دوستان دادن می‌تونه بهینه بشه حتی سریع‌تر از C! اما درستش اینه که از ویژگی std::function در چنین مواردی استفاده نکنید! به جاش از روش بهتری مانند template استفاده کنید.

تابع SortArray رو به روش زیر باز‌نویسی کنید:

template<typename T>
void SortArray(std::array<unsigned int,MAX_LENGTH> &MyArray,T function){
  for(unsigned int index=0;index < MAX_LENGTH;++index)
      for(unsigned int AnotherIndex=0;AnotherIndex<MAX_LENGTH;++AnotherIndex)
          if(function(MyArray[index],MyArray[AnotherIndex]))
            std::swap(MyArray[index],MyArray[AnotherIndex]);
}

مشخصات پلتفرم:

پردازنده : Intel® Core™ i5-2400 CPU @ 3.10GHz × 4

سیستم‌عامل‌ : لینوکس ابنتو ۱۸.۱۰

مد کامپایل : Debug

قبل از باز‌نویسی کُد تحت Clang نتیجهٔ زیر رو گرفتم:

photo_2018-11-29_20-08-56.jpg

بعد از باز‌نویسی کُد تحت GCC 8.x نتیجه زیر:

photo_2018-11-29_20-09-42.jpg

در نهایت بهترین نتیحه بدون بهینه سازی کامپایلر و یا تغییر در نحوهٔ پردازش روی Clang 7.x نتیجهٔ زیر رو دریافت می‌کنم.

photo_2018-11-29_20-09-37.jpg

اینم مُد Release برای GCC 8.x

photo_2018-11-29_22-43-35.jpg

اینم مُد Release برای Clang 7.x

photo_2018-11-29_22-43-24.jpg

از پیشنهادات دوستان هم برای بهینه سازی بیشتر می‌تونید استفاده کنید. البته پیشنهاد می‌کنم همیشه تنظیمات پیشفرض کامپایلر رو تغییر ندین، تا جایی که می‌تونید کد‌هارو بهینه‌ بنویسید.

به اشتراک گذاری این ارسال


لینک به ارسال
به اشتراک گذاری در سایت های دیگر
در 22 دقیقه قبل، بهنام صباغی گفته است :

اره دیگه اگر صرف زمان مهم بود کتابخونه معرفی میکردم که با پارالل کردن فور بدون تغییر زیاد توی کد بتونی سرعتت رو خیلی زیاد کنی

مثلا استفاده از openmp میتونه خیلی کمک کنه

من همین الان کدت رو بدون تغییر با openmp تست کردم زمان شگفت انگیز شد :

real 0m6.534s user 0m49.599s sys 0m0.255s

یعنی حدودا 6 ثانیه و نیم

راضی هستی یا بهترش کنم ؟ 

^_^

این هم کد که البته تغییری نکرده فقط سه خط ماکرو برای openmp اضافه شده :


#include <array>
#include <chrono>
#include <functional>
#include <iostream>
#include <random>
#include <utility>
const unsigned int MAX_LENGTH = 100000;

bool Compare(unsigned int FirstVariable, unsigned int SecondVariable)
{
	if (FirstVariable < SecondVariable) return true;
	return false;
}

void SortArray(std::array<unsigned int, MAX_LENGTH> &MyArray,
		   std::function<bool(unsigned int, unsigned int)> function)
{
#pragma omp parallel for
	for (unsigned int index = 0; index < MAX_LENGTH; ++index)
	{
#pragma omp parallel for

		for (unsigned int AnotherIndex = 0; AnotherIndex < MAX_LENGTH;
		 ++AnotherIndex)
		{
			if (function(MyArray[index], MyArray[AnotherIndex]))
			{
				std::swap(MyArray[index], MyArray[AnotherIndex]);
			}
		}
	}
}

void PrintArrayElements(const std::array<unsigned int, MAX_LENGTH> &MyArray)
{
	for (const auto &item : MyArray)
	std::cout << item << std::endl;
}

void RandomizeArray(std::array<unsigned int, MAX_LENGTH> &MyArray)
{
	std::mt19937_64 Random(static_cast<int>(
	std::chrono::high_resolution_clock::now().time_since_epoch().count()));
	std::uniform_int_distribution<> RandomGenerator(0, 1000);
#pragma omp parallel for
	for (unsigned int index = 0; index < MAX_LENGTH; ++index)
	MyArray[index] = static_cast<unsigned int>(RandomGenerator(Random));
}

int main()
{
	std::array<unsigned int, MAX_LENGTH> MyOrginalArray;
	RandomizeArray(MyOrginalArray);
	SortArray(MyOrginalArray, Compare);
	PrintArrayElements(MyOrginalArray);
	return 0x0000;
}

 

به اشتراک گذاری این ارسال


لینک به ارسال
به اشتراک گذاری در سایت های دیگر
در 21 دقیقه قبل، بهنام صباغی گفته است :

یعنی حدودا 6 ثانیه و نیم

راضی هستی یا بهترش کنم ؟

درمورد کتابخونه ای که گفتی دارم الان یه چیز هایی میخونم :X واقعا عالیه ! همین ابزار در کنار قدرت بهینه سازی که خودمون میتونیم توی کد اعمال کنیم مثل مواردی که آقای شیری و اسدزاده گفتن سرعت فوق العاده ای رومیتونیم داشته باشیم  :classic_biggrin:.

مرسی آقا بهنام راضی راضی ام متشکر :classic_ninja:

 

به اشتراک گذاری این ارسال


لینک به ارسال
به اشتراک گذاری در سایت های دیگر

استفاده از توزیع‌های آماری برای تولید اعداد تصادفی سرعت رو پایین میاره. چون مشخهٔ آماری توزیع (مثلاً توی مورد شما توزیع یکسان) باید در هنگام تولید اعداد رعایت بشه. به همین خاطر موقع تولید عدد ممکنه سه یا چهار بار عدد تصادفی تولید بشه. این مسأله موقع استفاده از توزیع‌های آماری پیچیده‌تر مثل توزیع نرمال شدیدتر هم میشه. تولید عدد تصادفی با توزیع نرمال در سی‌پلاس‌پلاس خیلی کنده. در مقابل اگر مشخصهٔ آماری براتون مهم نیست می‌تونید از توابع سادهٔ rand استفاده کنید که از سخت‌افزار هم برای تولید عدد تصادفی کمک می‌گیرند:

cat /dev/urandom | hexdump
 

سرعت تولید عدد تصادفی به این روش خیلی بالاست اما آشفتگی لازم برای رمزنگاری رو نداره. اگه کاربرد خیلی جدی هست باید از randomبه‌جاش استفاده کنید که کندتره. توابع استاندارد هم  از همین‌ها استفاده می‌کنند.

 

 

به اشتراک گذاری این ارسال


لینک به ارسال
به اشتراک گذاری در سایت های دیگر

به گفتگو ملحق شوید

شما همین الآن می‌توانید مطلبی را ارسال و بعداً ثبت‌نام کنید. اگر حساب کاربری دارید، و با حساب کاربری خود مطلب ارسال کنید.
نکته: مطلب شما قبل از انتشار نیاز به بازبینی توسط میانجی‌گر‌ها دارد.

مهمان
ارسال پاسخ به این موضوع ...

×   شما در حال چسباندن محتوایی با قالب بندی هستید.   حذف قالب بندی

  تنها استفاده از ۷۵ اموجی مجاز می باشد.

×   لینک شما به صورت اتوماتیک جای گذاری شد.   نمایش به عنوان یک لینک به جای

×   محتوای قبلی شما بازگردانی شد.   پاک کردن محتوای ویرایشگر

×   شما مستقیما نمی توانید تصویر خود را قرار دهید. یا آن را اینجا بارگذاری کنید یا از یک URL قرار دهید.


  • کاربران آنلاین در این صفحه   0 کاربر

    هیچ کاربر عضوی،در حال مشاهده این صفحه نیست.

×
×
  • جدید...