قاسم رمضانی منش 63 ارسال شده در آذر 97 (ویرایش شده) با سلام ! دو قطعه برنامه ی زیر یکی آرایه ۱۰۰۰۰۰ تایی در حافظه 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; } ویرایش شده در آذر 97 توسط قاسم رمضانی منش 1 نقل قول به اشتراک گذاری این ارسال لینک به ارسال به اشتراک گذاری در سایت های دیگر
بهنام صباغی 71 ارسال شده در آذر 97 سلام بر حاج قاسم با تست اول به طور طبیعی روی لینوکس و لپتاپ خودم با کامپایلر g++-8 خروجی شد : 315 ثانیه معادل 5.25 دقیقه حالا تست دوم با تنظیم کردن دو تا فلگ برای بهینه سازی فلگ های -O3 و -ffast-math نتیجه شد : 26 ثانیه بدون دست بردن توی کد تونستم با ست کردن فلگ بهینه سازی زمان رو کاهش بدم. 1 1 نقل قول به اشتراک گذاری این ارسال لینک به ارسال به اشتراک گذاری در سایت های دیگر
قاسم رمضانی منش 63 ارسال شده در آذر 97 (ویرایش شده) در 19 دقیقه قبل، بهنام صباغی گفته است : حالا تست دوم با تنظیم کردن دو تا فلگ برای بهینه سازی فلگ های -O3 و -ffast-math مرسی متشکرم. بله سرعت رو به شدت بالابرد ! اما ! این فلگ هایی که گفتید فقط فلگ اول O3- برای بهینه سازی هست که باعث افزایش سرعت میشه. و فلگ دوم ffast-math- به کامپایلر اجازه میده که یک سری از قوانین IEEE و ISO و نقض کنه : GCC Command Options و گفته شده که در صورت استفاده از فلگ ffast-math- از هیچ کدام سطح های بهینه سازی O- استفاده نکنید که باعث خروجی اشتباه میشه ! ویرایش شده در آذر 97 توسط قاسم رمضانی منش مشخص کردن دقیق فلگ افزایش دهنده سرعت. 1 نقل قول به اشتراک گذاری این ارسال لینک به ارسال به اشتراک گذاری در سایت های دیگر
بهنام صباغی 71 ارسال شده در آذر 97 در 3 دقیقه قبل، فرهاد شیری گفته است : آقا نکته ی جالبی گفتی حداقل برای من که جالب بود چون من معمولا این فلگ ها را تغییر نمیدم تشکر اره منم تغییر نمیدادم ولی چند روزی هست درگیر بهینه سازی هستیم جالبه که فعال کردن این فلگ ها علاوه بر بالا بردن سرعت باعث میشه کد اسمبلی یکم پیچیده تر بشه و برای مهندسی معکوس سخت تر بشه کار اینطور که شنیدم ولی تست نکردم هنوز . 1 نقل قول به اشتراک گذاری این ارسال لینک به ارسال به اشتراک گذاری در سایت های دیگر
قاسم رمضانی منش 63 ارسال شده در آذر 97 در 7 دقیقه قبل، فرهاد شیری گفته است : در 2 ساعت قبل، قاسم رمضانی منش گفته است : معمولا خیلی بهتره که اینطور پردازش های سنگین را به صورت موازی انجام بدید مثلا از تکنیک Divide and Concur استفاده کنید. ولی با تغییراتی که دادم برای 20000 تا تقریبا 3 ثانیه طول کشید که سورت کنه! مرسی ممنون حتما درباره این تکنیک جستجو میکنم. با تغییراتی که دادید سرعت را از ۷ دقیقه به ۱ دقیقه کاهش دادید !. (شما با مقدار ۲۰۰۰۰ هزار اجرا کرده بودید. مقدار پیش فرض ۱۰۰۰۰۰ بود.) نقل قول به اشتراک گذاری این ارسال لینک به ارسال به اشتراک گذاری در سایت های دیگر
قاسم رمضانی منش 63 ارسال شده در آذر 97 در 6 دقیقه قبل، فرهاد شیری گفته است : الگوریتم های مرتب سازی های دیگه را هم تست کنید بله ! صدالبته که عملکرد انواع الگوریتم ها و روششون میتونه توی سرعت تاثیر داشته باشه. مثل اینکه درست منظور خودم را نگفتم:) هردو کدی که ارسال کردم به یک روش نوشته شده اند ولی یکی به زبان سی پلاس پلاس و با استفاده از کتابخانه های استاندارد و یکی با استفاده از زبان سی و کتابخونه های استاندارد خودش. البته این مورد بدیهی هست که سرعت کمی از سی به سی پلاس پلاس کاهش پیدا کنه. که بنده دنبال راهی بودم برای رفع این مشکل که آقا بهنام با معرفی فلگ بهینه سازی O- تا حدود بسیار زیادی این مشکل رو برطرف کردن. نقل قول به اشتراک گذاری این ارسال لینک به ارسال به اشتراک گذاری در سایت های دیگر
بهنام صباغی 71 ارسال شده در آذر 97 در 9 دقیقه قبل، قاسم رمضانی منش گفته است : بله ! صدالبته که عملکرد انواع الگوریتم ها و روششون میتونه توی سرعت تاثیر داشته باشه. مثل اینکه درست منظور خودم را نگفتم:) هردو کدی که ارسال کردم به یک روش نوشته شده اند ولی یکی به زبان سی پلاس پلاس و با استفاده از کتابخانه های استاندارد و یکی با استفاده از زبان سی و کتابخونه های استاندارد خودش. البته این مورد بدیهی هست که سرعت کمی از سی به سی پلاس پلاس کاهش پیدا کنه. که بنده دنبال راهی بودم برای رفع این مشکل که آقا بهنام با معرفی فلگ بهینه سازی O- تا حدود بسیار زیادی این مشکل رو برطرف کردن. اره دیگه اگر صرف زمان مهم بود کتابخونه معرفی میکردم که با پارالل کردن فور بدون تغییر زیاد توی کد بتونی سرعتت رو خیلی زیاد کنی مثلا استفاده از openmp میتونه خیلی کمک کنه 1 نقل قول به اشتراک گذاری این ارسال لینک به ارسال به اشتراک گذاری در سایت های دیگر
کامبیز اسدزاده 618 ارسال شده در آذر 97 در در 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 نتیجهٔ زیر رو گرفتم: بعد از بازنویسی کُد تحت GCC 8.x نتیجه زیر: در نهایت بهترین نتیحه بدون بهینه سازی کامپایلر و یا تغییر در نحوهٔ پردازش روی Clang 7.x نتیجهٔ زیر رو دریافت میکنم. اینم مُد Release برای GCC 8.x اینم مُد Release برای Clang 7.x از پیشنهادات دوستان هم برای بهینه سازی بیشتر میتونید استفاده کنید. البته پیشنهاد میکنم همیشه تنظیمات پیشفرض کامپایلر رو تغییر ندین، تا جایی که میتونید کدهارو بهینه بنویسید. 1 نقل قول به اشتراک گذاری این ارسال لینک به ارسال به اشتراک گذاری در سایت های دیگر
بهنام صباغی 71 ارسال شده در آذر 97 در 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; } 1 نقل قول به اشتراک گذاری این ارسال لینک به ارسال به اشتراک گذاری در سایت های دیگر
قاسم رمضانی منش 63 ارسال شده در آذر 97 در 21 دقیقه قبل، بهنام صباغی گفته است : یعنی حدودا 6 ثانیه و نیم راضی هستی یا بهترش کنم ؟ درمورد کتابخونه ای که گفتی دارم الان یه چیز هایی میخونم :X واقعا عالیه ! همین ابزار در کنار قدرت بهینه سازی که خودمون میتونیم توی کد اعمال کنیم مثل مواردی که آقای شیری و اسدزاده گفتن سرعت فوق العاده ای رومیتونیم داشته باشیم . مرسی آقا بهنام راضی راضی ام متشکر نقل قول به اشتراک گذاری این ارسال لینک به ارسال به اشتراک گذاری در سایت های دیگر
سروش ربیعی 16 ارسال شده در آذر 97 استفاده از توزیعهای آماری برای تولید اعداد تصادفی سرعت رو پایین میاره. چون مشخهٔ آماری توزیع (مثلاً توی مورد شما توزیع یکسان) باید در هنگام تولید اعداد رعایت بشه. به همین خاطر موقع تولید عدد ممکنه سه یا چهار بار عدد تصادفی تولید بشه. این مسأله موقع استفاده از توزیعهای آماری پیچیدهتر مثل توزیع نرمال شدیدتر هم میشه. تولید عدد تصادفی با توزیع نرمال در سیپلاسپلاس خیلی کنده. در مقابل اگر مشخصهٔ آماری براتون مهم نیست میتونید از توابع سادهٔ rand استفاده کنید که از سختافزار هم برای تولید عدد تصادفی کمک میگیرند: cat /dev/urandom | hexdump سرعت تولید عدد تصادفی به این روش خیلی بالاست اما آشفتگی لازم برای رمزنگاری رو نداره. اگه کاربرد خیلی جدی هست باید از randomبهجاش استفاده کنید که کندتره. توابع استاندارد هم از همینها استفاده میکنند. 3 نقل قول به اشتراک گذاری این ارسال لینک به ارسال به اشتراک گذاری در سایت های دیگر