Код, варіант 1:
double hamiltonian(const FK_GA_c::Individual & _indi) { double sum = 0; for (unsigned i = 0; i < _indi.size(); i=i+2) { //i -- n_f, //i+1 -- n_d double n_f_i = _indi[i]; double n_d_i = _indi[i+1]; sum-=defparams.mu_f*n_f_i; sum-=defparams.mu_d*n_d_i; sum+=defparams.U*n_f_i*n_d_i; // auto i_plus_1 = i+2; //i+1 в математичному сенсі --- наступний вузол // Циклічні граничні умови if(i_plus_1>=_indi.size()-1) i_plus_1=0; double n_f_i_1 = _indi[i_plus_1]; double n_d_i_1 = _indi[i_plus_1+1]; double base_hopping = (1-n_d_i)*n_d_i_1; double hopping=defparams.t1; hopping+=defparams.t2*(n_f_i+n_f_i_1); hopping+=defparams.t3*(n_f_i*n_f_i_1); hopping*=base_hopping; sum+=hopping; } return -sum; }
Це давня робоча версія, яка має ряд фундаментальних недоліків, але навряд чи мені буде охота повторювати весь цей цикл модифікацій, про які розповідатиму, заново -- треба зразу нормально писати :-), тому ілюструвати буду на ній. Сподіваюся, пробачите деякі вульгарності.
Перша із них --- функція використовує глобальну змінну defparams. Справа в тому, що бібліотека, яку використовую (ParadisEO) вимагає або функцію, яка приймає лише один параметр, або хитрий об'єкт-функцію, який мені на той момент було лінь писати --- перевіряв придатність самого підходу.
Перша із них --- функція використовує глобальну змінну defparams. Справа в тому, що бібліотека, яку використовую (ParadisEO) вимагає або функцію, яка приймає лише один параметр, або хитрий об'єкт-функцію, який мені на той момент було лінь писати --- перевіряв придатність самого підходу.
Для тих, кому цікаво: Функція рахує енергію конкретної "конфігурації" одномірної моделі Фалікова-Кімбала. Це така ґраткова модель, де на кожному вузлі може бути (а може не бути) одна нерухома f-частинка, і одна рухома, d-частинка:
\( |n^f_1, n^d_1; n^f_2, n^d_2; n^f_3, n^d_3; \ldots n^f_N, n^d_N > \)
Наприклад:
\( |0, 0; 1, 1; 0, 1; 0, 0; \ldots 1, 0>\)
Або:
Функція, про яку мова, отримує масив, де є кількості (0 або 1) цих частинок для кожного вузла і розраховує наступну величину, так-званий гамільтоніан:
\( \begin{array}{rcl}
E &=& \displaystyle \sum_{i}\left( -\mu_f n^f_{i}-\mu_d n^d_{i} + U n^d_{i} n^f_{i} \right) \\
& & \displaystyle + \sum_{i} n^d_{i+1} (1-n^d_{i}) \left( t_1 + t_2 (n^f_{i}+n^f_{i+1})+ t_3 n^f_{i} n^f_{i+1} \right)
\end{array}
\)
Структура defparams всього лиш містить значення всіх параметрів:
class FK_params { public: double mu_f, mu_d, U, t1, t2, t3; };
Задача програми -- пошук мінімуму цієї функції. Для пошуку використовуються генетичні алгоритми. Якщо коротко, генерується популяція --- набір особин із різними наборами \(n^d\) та \(n^f\). Далі в цій популяції запускаємо еволюцію -- за певних правил, спарюємо, мутуємо і т. д., намагаючись збільшити пристосованість. Природно, пристосованість -- це якась величина, обернено пропорційна до енергії.
І про модель Ф-К і про генетичні алгоритми напишу колись окремо, а поки цих відомостей достатньо для подальшого викладу.
Код отримує певний контейнер _indi, до якого можна звертатися за індексом, як до звичайного масиву, в яком за парними індексами (з нуля починаючи) -- число f-частинок, з непарними --- число d-частинок:
for (unsigned i = 0; i < _indi.size(); ===> i=i+2 <===) {
double n_f_i = _indi[i]; double n_d_i = _indi[i+1];
Всередині потроху використовую C++11.
Запускаємо, скомпільований з оптимізацією код, в режимі профілювання (профіль не повний --- щоб не засмічувати):
% cumulative self self total time seconds seconds calls ms/call ms/call name 49.03 9.33 9.33 7650000 0.00 0.00 eoBitMutation>::operator()(eoBit &) ==>35.16 16.02 6.69 6860386 0.00 0.00 hamiltonian(eoBit const&) 7.72 17.49 1.47 3060969 0.00 0.00 eo1PtBitXover >::operator()(eoBit &, eoBit &) 1.94 17.86 0.37 _mcount_private 1.42 18.13 0.27 22512369 0.00 0.00 eoRng::rand() 1.37 18.39 0.26 __fentry__ 1.31 18.64 0.25 7650000 0.00 0.00 eoDetTournamentSelect >::operator()(eoPop > const&) 1.21 18.87 0.23 51 4.51 360.40 eoSGA >::operator()(eoPop >&) 0.53 18.97 0.10 153000 0.00 0.00 eoSelectPerc >::operator()(eoPop > const&, eoPop >&) 0.26 19.02 0.05 7650000 0.00 0.00 eoEvalFuncPtr , double, eoBit const&>::operator()(eoBit &) 0.05 19.03 0.01 memmove 0.00 19.03 0.00 153000 0.00 0.00 eoSelectOne , double>::setup(eoPop > const&) 0.00 19.03 0.00 153000 0.00 0.00 eoGenContinue >::operator()(eoPop > const&) 0.00 19.03 0.00 8313 0.00 0.00 eoBit ::~eoBit()
Час виконання нашої функції виділено стрілкою. 35.16% часу або 6.69 секунд за 6860386 виконань.В майбутньому буде зручно використовувати проценти та секунди за одне виконання: \( 5.12\cdot 10^{-6} \)%, \(9.75\cdot 10^{-7}\) с.
Спочатку згадав, що тип елементів масиву _indi-- bool, вирішив скористатися тим фактом, що false завжди приводиться до 0, true --- до одиниці. Щоб не допустити випадкових помилок, коли, наприклад, тип цього контейнера зміниться, використав уніфіковану ініціалізацію C++11 --- вона не робить неявних перетворень типів.
Код, варіант 2:
double hamiltonian(const FK_GA_c::Individual & _indi) { double sum = 0; for (unsigned i = 0; i < _indi.size(); i=i+2) { //i -- n_f, //i+1 -- n_d bool n_f_i{_indi[i]}; bool n_d_i{_indi[i+1]}; sum-=defparams.mu_f*n_f_i; sum-=defparams.mu_d*n_d_i; sum+=defparams.U*n_f_i*n_d_i; // auto i_plus_1 = i+2; //i+1 в математичному сенсі --- наступний вузол // Циклічні граничні умови if(i_plus_1>=_indi.size()-1) i_plus_1=0; bool n_f_i_1{_indi[i_plus_1]}; bool n_d_i_1{_indi[i_plus_1+1]}; double base_hopping = (1-n_d_i)*n_d_i_1; double hopping=defparams.t1; hopping+=defparams.t2*(n_f_i+n_f_i_1); hopping+=defparams.t3*(n_f_i*n_f_i_1); hopping*=base_hopping; sum+=hopping; } return -sum; }
Запускаємо:
% cumulative self self total time seconds seconds calls ms/call ms/call name 47.38 9.12 9.12 7650000 0.00 0.00 eoBitMutationСтало гірше. 37.40% часу, або 7.20 секунд, 6860386 викликів -- те ж число, що і раніше, або, в перерахунку на одне використання функції: \( 5.45\cdot 10^{-6} \)%, \(1.05\cdot 10^{-6}\) с.>::operator()(eoBit &) ==>37.40 16.32 7.20 6860386 0.00 0.00 hamiltonian(eoBit const&) 7.01 17.67 1.35 3060969 0.00 0.00 eo1PtBitXover >::operator()(eoBit &, eoBit &) 1.77 18.01 0.34 _mcount_private 1.61 18.32 0.31 22512369 0.00 0.00 eoRng::rand() 1.56 18.62 0.30 7650000 0.00 0.00 eoDetTournamentSelect >::operator()(eoPop > const&) 1.25 18.86 0.24 51 4.71 365.88 eoSGA >::operator()(eoPop >&) 1.19 19.09 0.23 __fentry__ 0.62 19.21 0.12 153000 0.00 0.00 eoSelectPerc >::operator()(eoPop > const&, eoPop >&) 0.10 19.23 0.02 7650000 0.00 0.00 eoEvalFuncPtr , double, eoBit const&>::operator()(eoBit &) 0.05 19.24 0.01 153000 0.00 0.00 eoSelectOne , double>::setup(eoPop > const&) 0.05 19.25 0.01 memmove 0.00 19.25 0.00 153000 0.00 0.00 eoGenContinue >::operator()(eoPop > const&) 0.00 19.25 0.00 8313 0.00 0.00 eoBit ::~eoBit()
Однак, булівські величини відкривають широкий простір для оптимізації. Раз ми знаємо, що n_f чи n_d -- нуль або одиниця, множити відповідні параметри на них немає сенсу:
Код, варіант 3:
double hamiltonian(const FK_GA_c::Individual & _indi) { double sum = 0; for (unsigned i = 0; i < _indi.size(); i=i+2) { //i -- n_f, //i+1 -- n_d bool n_f_i{_indi[i]}; bool n_d_i{_indi[i+1]}; sum-= n_f_i ? defparams.mu_f : 0; sum-= n_d_i ? defparams.mu_d : 0 ; sum+= n_f_i && n_d_i ? defparams.U : 0 ; // auto i_plus_1 = i+2; //i+1 в математичному сенсі --- наступний вузол // Циклічні граничні умови if(i_plus_1>=_indi.size()-1) i_plus_1=0; bool n_f_i_1{_indi[i_plus_1]}; bool n_d_i_1{_indi[i_plus_1+1]}; auto base_hopping = !n_d_i && n_d_i_1; double hopping=defparams.t1; hopping+= n_f_i ? defparams.t2 : 0; hopping+= n_f_i_1 ? defparams.t2 : 0; hopping+= n_f_i && n_f_i_1 ? defparams.t3 : 0; hopping*=base_hopping; sum+=hopping; } return -sum; }
Профілюємо:
% cumulative self self total time seconds seconds calls ms/call ms/call name 50.24 9.38 9.38 7650000 0.00 0.00 eoBitMutation>::operator()(eoBit &) ==>33.58 15.65 6.27 6859029 0.00 0.00 hamiltonian(eoBit const&) 6.91 16.94 1.29 3060969 0.00 0.00 eo1PtBitXover >::operator()(eoBit &, eoBit &) 2.79 17.46 0.52 _mcount_private 1.55 17.75 0.29 7650000 0.00 0.00 eoDetTournamentSelect >::operator()(eoPop > const&) 1.50 18.03 0.28 22512369 0.00 0.00 eoRng::rand() 1.34 18.28 0.25 51 4.90 350.41 eoSGA >::operator()(eoPop >&) 1.29 18.52 0.24 __fentry__ 0.54 18.62 0.10 153000 0.00 0.00 eoSelectPerc >::operator()(eoPop > const&, eoPop >&) 0.11 18.64 0.02 7650000 0.00 0.00 eoEvalFuncPtr , double, eoBit const&>::operator()(eoBit &) 0.05 18.65 0.01 non-virtual thunk to eo1PtBitXover >::operator()(eoBit &, eoBit &) 0.05 18.66 0.01 non-virtual thunk to eoBitMutation >::operator()(eoBit &) 0.05 18.67 0.01 __fu227__ZSt4cout 0.00 18.67 0.00 153000 0.00 0.00 eoSelectOne , double>::setup(eoPop > const&) 0.00 18.67 0.00 153000 0.00 0.00 eoGenContinue >::operator()(eoPop > const&) 0.00 18.67 0.00 8313 0.00 0.00 eoBit ::~eoBit()
Стало помітно швидше, ніж в початковому варіанті: 33.58% часу, або 6.27 секунд. Однак, не все так просто. Тепер кількість викликів: 6859029. Явно змінилася, хоча й лише на 0.02%, тобто, змінилися обчислення. Як так могло відбутися, в детерміністичній машині? (Нагадаю, seed генератора випадкових чисел не змінився).
<ВІДСТУП>
Спочатку дивимося на результати роботи:
Не так важливо, що це за конкретні числа (середні значення концентрацій f- i d-частинок за різних значень параметрів), але це і є продукт розрахунків. Ліворуч -- попередній варіант, праворуч -- останній. І якщо відхилення, обведені зеленим, цілком терпимі, обведені рожевим -- туди-сюди, то обведені червоним -- зовсім зле.
Однак, давайте побудуємо графіки в обох випадках:
 |
| Світліші кольори -- \(n_f\), (ті криві, що ростуть зліва направо), темніші -- \(n_d\) (ті, що падуть десь від -1 і далі праворуч). Зелені -- попередній результат, сині -- поточний, із використанням bool. |
Видно, що вони практично ідентичні. Більше того, якщо згадати, що сам метод, яким отримано ці графіки, генетичні алгоритми -- стохастичний, і запустити декілька раз із різними seed-ами, отримаємо такі самі, дещо різні "паркани". (На жаль, то його фундаментальний недолік -- точних результатів він не дає, дає лише достатньо пристойну, зате -- дуже швидко, оцінку.)
Тобто, хоча конкретні числа змінилися, на результат це суттєво не вплинуло. Однак, все ж, чому змінилися конкретні числа?
Давайте подивимося на початкові дані, (особини), згенеровані випадковим чином, для обох випадків, що розглядаються. Дані на зображенні нижче посортовані по спаданню енергії --- чим нижче, тим більший результат повернула функція, над якою знущаємося.
Варіант коду номер два (чи й один -- вони однакові):
-2.7944: _d|__|_d|_d|fd|_d|__|f_|f_|__|_d|_d|_d|fd|_d|f_|__|fd|fd|_d|f_|_d|fd|fd|f_|_d|fd|__|f_|f_|_d|fd|__|f_|fd|fd|f_|fd|__|f_|_d|__|f_|f_|__|__|fd|f_|_d|f_|__|f_|f_|_d|_d|_d|f_|_d|_d|__|__|__|fd|fd|
-2.6696: __|_d|f_|__|fd|fd|__|_d|__|_d|f_|f_|fd|_d|__|fd|__|_d|__|_d|fd|fd|f_|__|f_|fd|_d|fd|__|__|__|__|f_|fd|f_|__|f_|__|_d|fd|__|__|_d|_d|_d|f_|_d|f_|__|f_|f_|_d|f_|fd|_d|__|fd|f_|fd|f_|_d|__|__|f_|
-2.6672: fd|fd|f_|_d|_d|fd|fd|_d|_d|_d|fd|_d|_d|__|fd|f_|_d|f_|__|__|_d|_d|_d|f_|_d|fd|f_|f_|f_|_d|_d|fd|f_|_d|__|__|__|_d|_d|_d|__|__|f_|__|_d|f_|_d|_d|_d|fd|f_|_d|__|_d|__|f_|f_|fd|fd|f_|f_|f_|f_|__|
1==> -2.5592: f_|fd|fd|__|__|f_|__|fd|__|f_|_d|f_|__|__|__|fd|f_|_d|fd|fd|_d|__|_d|f_|f_|f_|f_|f_|_d|_d|f_|__|_d|__|fd|fd|__|f_|_d|fd|__|_d|fd|fd|_d|fd|f_|_d|_d|f_|_d|__|__|_d|_d|fd|f_|__|fd|f_|f_|__|fd|fd|
2==> -2.5592: _d|_d|f_|fd|_d|f_|f_|f_|_d|f_|f_|f_|f_|_d|f_|__|__|f_|__|fd|__|_d|fd|_d|fd|__|__|__|fd|__|_d|fd|f_|_d|fd|__|f_|f_|__|_d|f_|__|fd|fd|fd|fd|f_|fd|__|__|_d|f_|__|fd|__|__|fd|__|__|_d|f_|_d|fd|fd|
-2.5496: fd|fd|fd|__|__|fd|__|f_|f_|__|_d|fd|__|_d|f_|_d|_d|__|fd|_d|f_|_d|_d|fd|f_|f_|f_|__|f_|__|_d|f_|fd|__|f_|f_|_d|fd|__|__|_d|fd|__|_d|f_|_d|_d|_d|fd|_d|f_|__|_d|_d|__|f_|f_|_d|fd|__|f_|f_|_d|__|
-2.5144: __|__|f_|fd|f_|fd|fd|__|__|f_|__|f_|fd|_d|fd|_d|__|__|f_|_d|fd|fd|f_|fd|f_|f_|fd|_d|f_|__|fd|fd|_d|__|_d|f_|_d|__|fd|f_|fd|_d|_d|_d|fd|__|fd|f_|_d|f_|_d|_d|f_|__|fd|fd|__|_d|__|__|_d|__|__|_d|
-2.4864: fd|f_|fd|__|__|_d|__|f_|f_|fd|_d|fd|__|f_|__|fd|__|__|fd|_d|__|fd|__|fd|__|fd|__|f_|f_|fd|_d|_d|fd|__|fd|_d|fd|f_|f_|fd|_d|fd|fd|__|fd|f_|f_|_d|__|f_|fd|f_|__|_d|f_|_d|__|__|fd|f_|fd|fd|fd|_d|
Варіант коду номер три:
-2.7944: _d|__|_d|_d|fd|_d|__|f_|f_|__|_d|_d|_d|fd|_d|f_|__|fd|fd|_d|f_|_d|fd|fd|f_|_d|fd|__|f_|f_|_d|fd|__|f_|fd|fd|f_|fd|__|f_|_d|__|f_|f_|__|__|fd|f_|_d|f_|__|f_|f_|_d|_d|_d|f_|_d|_d|__|__|__|fd|fd|
-2.6696: __|_d|f_|__|fd|fd|__|_d|__|_d|f_|f_|fd|_d|__|fd|__|_d|__|_d|fd|fd|f_|__|f_|fd|_d|fd|__|__|__|__|f_|fd|f_|__|f_|__|_d|fd|__|__|_d|_d|_d|f_|_d|f_|__|f_|f_|_d|f_|fd|_d|__|fd|f_|fd|f_|_d|__|__|f_|
-2.6672: fd|fd|f_|_d|_d|fd|fd|_d|_d|_d|fd|_d|_d|__|fd|f_|_d|f_|__|__|_d|_d|_d|f_|_d|fd|f_|f_|f_|_d|_d|fd|f_|_d|__|__|__|_d|_d|_d|__|__|f_|__|_d|f_|_d|_d|_d|fd|f_|_d|__|_d|__|f_|f_|fd|fd|f_|f_|f_|f_|__|
2==> -2.5592: _d|_d|f_|fd|_d|f_|f_|f_|_d|f_|f_|f_|f_|_d|f_|__|__|f_|__|fd|__|_d|fd|_d|fd|__|__|__|fd|__|_d|fd|f_|_d|fd|__|f_|f_|__|_d|f_|__|fd|fd|fd|fd|f_|fd|__|__|_d|f_|__|fd|__|__|fd|__|__|_d|f_|_d|fd|fd|
1==> -2.5592: f_|fd|fd|__|__|f_|__|fd|__|f_|_d|f_|__|__|__|fd|f_|_d|fd|fd|_d|__|_d|f_|f_|f_|f_|f_|_d|_d|f_|__|_d|__|fd|fd|__|f_|_d|fd|__|_d|fd|fd|_d|fd|f_|_d|_d|f_|_d|__|__|_d|_d|fd|f_|__|fd|f_|f_|__|fd|fd|
-2.5496: fd|fd|fd|__|__|fd|__|f_|f_|__|_d|fd|__|_d|f_|_d|_d|__|fd|_d|f_|_d|_d|fd|f_|f_|f_|__|f_|__|_d|f_|fd|__|f_|f_|_d|fd|__|__|_d|fd|__|_d|f_|_d|_d|_d|fd|_d|f_|__|_d|_d|__|f_|f_|_d|fd|__|f_|f_|_d|__|
-2.5144: __|__|f_|fd|f_|fd|fd|__|__|f_|__|f_|fd|_d|fd|_d|__|__|f_|_d|fd|fd|f_|fd|f_|f_|fd|_d|f_|__|fd|fd|_d|__|_d|f_|_d|__|fd|f_|fd|_d|_d|_d|fd|__|fd|f_|_d|f_|_d|_d|f_|__|fd|fd|__|_d|__|__|_d|__|__|_d|
-2.4864: fd|f_|fd|__|__|_d|__|f_|f_|fd|_d|fd|__|f_|__|fd|__|__|fd|_d|__|fd|__|fd|__|fd|__|f_|f_|fd|_d|_d|fd|__|fd|_d|fd|f_|f_|fd|_d|fd|fd|__|fd|f_|f_|_d|__|f_|fd|f_|__|_d|f_|_d|__|__|fd|f_|fd|fd|fd|_d|
Рядки, із номером 1 (2) в обох випадках однакові, значення функції для них теж однакові (з точністю до 4-ї цифри), однак, вони переставлені між собою. А причина проста. Дискретна природа double в комп'ютерному представленні. Порядок скомпільованого коду обчислень у варіанті три трішки змінився, за рахунок похибки заокруглення, та інших схожих капостей, результати почали відрізнятися в останньому-передостанньому знаку. В результаті порядок рядків змінився, аж у \(8/255 \approx 0.03\) --- 3% випадків. Але генетичні алгоритми, вибираючи (за одного і того ж seed!), покладаються саме на цей порядок. Вибрали для спарювання не ту особину, і понеслася -- як у відомій пісні про цвях, підкову і коня.
Крім того, слід сказати, що без використання ключа оптимізації, fast-math, результати всі 5 запусків будуть однаковими, але без нього помітно паде загальна швидкодія. Можливо, варто повторити ці ж дослідження без даного ключа.
</ВІДСТУП>
Отож, завершуючи відступ, результати все ще релевантні. В перерахунку на одне використання функції: \( 4.89\cdot 10^{-6} \)%, \(9.14\cdot 10^{-7}\) с. Це краще, ніж на початку, хоч і не сильно. Рухаємося далі.
Якщо придивитися до коду, копії bool-івських змінних, тих що n_f_i, n_d_i, і т. д., нам не особливо потрібні. Можна обійтися константними посиланнями:
Код, варіант 4:
Код, варіант 4:
double hamiltonian(const FK_GA_c::Individual & _indi) { double sum = 0; for (unsigned i = 0; i < _indi.size(); i=i+2) { //i -- n_f, //i+1 -- n_d const bool& n_f_i{_indi[i]}; const bool& n_d_i{_indi[i+1]}; sum-= n_f_i ? defparams.mu_f : 0; sum-= n_d_i ? defparams.mu_d : 0 ; sum+= n_f_i && n_d_i ? defparams.U : 0 ; // hopping auto i_plus_1 = i+2; //i+1 в математичному сенсі --- наступний вузол // Циклічні граничні умови if(i_plus_1>=_indi.size()-1) i_plus_1=0; const bool& n_f_i_1{_indi[i_plus_1]}; const bool& n_d_i_1{_indi[i_plus_1+1]}; auto base_hopping = !n_d_i && n_d_i_1; double hopping=defparams.t1; hopping+= n_f_i ? defparams.t2 : 0; hopping+= n_f_i_1 ? defparams.t2 : 0; hopping+= n_f_i && n_f_i_1 ? defparams.t3 : 0; hopping*=base_hopping; sum+=hopping; } return -sum; }
Запускаємо:
% cumulative self self total time seconds seconds calls us/call us/call name 48.75 9.34 9.34 7650000 1.22 1.22 eoBitMutation>::operator()(eoBit &) ==>29.07 14.91 5.57 6856343 0.81 0.81 hamiltonian(eoBit const&) 6.99 16.25 1.34 3060969 0.44 0.45 eo1PtBitXover >::operator()(eoBit &, eoBit &) 3.44 16.91 0.66 _mcount_private 2.14 17.32 0.41 __fentry__ 1.62 17.63 0.31 7650000 0.04 0.05 eoDetTournamentSelect >::operator()(eoPop > const&) 1.46 17.91 0.28 7200787 0.04 0.04 void std::__unguarded_linear_insert<__gnu_cxx::__normal_iterator data-blogger-escaped-double="" data-blogger-escaped-eobit="">*, std::vector , std::allocator > > >, eoPop >::Cmp2>(__gnu_cxx::__normal_iterator *, std::vector , std::allocator > > >, eoPop >::Cmp2) 1.36 18.17 0.26 153255 1.70 1.70 operator<<(std::ostream&, FK_GA_c const&) 1.15 18.39 0.22 22512369 0.01 0.01 eoRng::rand() 0.94 18.57 0.18 153000 1.18 112.83 eoSGA >::operator()(eoPop >&) 0.84 18.73 0.16 153000 1.05 3.95 eoSelectPerc >::operator()(eoPop > const&, eoPop >&) 0.52 18.83 0.10 153204 0.65 0.65 average_nf_nd(eoBit , FK_params const&, unsigned int, unsigned int) 0.31 18.89 0.06 153000 0.39 0.39 void std::__uninitialized_default_n_1 ::__uninit_default_n *, unsigned long long>(eoBit *, unsigned long long) 0.16 18.92 0.03 7655763 0.00 0.00 eoBit ::~eoBit()
29.07% часу, або 5.57 секунд, 6856343
викликів, на одне
використання функції: \( 4.23\cdot 10^{-6} \)%, \(8.12\cdot 10^{-7}\)
с. Результат помітно покращився, продовжуємо.
Відомо, що сучасні процесори дуже не люблять розгалужень. if-ів всіляких. Точніше, навіть не стільки розгалужень, скільки розгалужень, яких вони не змогли передбачити -- конвеєр довгий, кожне не вгадане розгалуження його мусить очищати. Спробуємо в коді цих розгалужень позбутися:
Код, варіант 5:
double hamiltonian(const FK_GA_c::Individual & _indi) { double sum = 0; for (unsigned i = 0; i < _indi.size(); i=i+2) { //i -- n_f, //i+1 -- n_d const bool& n_f_i{_indi[i]}; const bool& n_d_i{_indi[i+1]}; n_f_i ? sum-= defparams.mu_f : 0; n_d_i ? sum-= defparams.mu_d : 0 ; n_f_i && n_d_i ? sum+= defparams.U : 0 ; // Hopping auto i_plus_1 = i+2; //i+1 в математичному сенсі --- наступний вузол // Циклічні граничні умови //i+1 в математичному сенсі --- наступний вузол i_plus_1 = i+2 >= _indi.size()-1 ? 0 : i+2; const bool& n_f_i_1{_indi[i_plus_1]}; const bool& n_d_i_1{_indi[i_plus_1+1]}; auto base_hopping = !n_d_i && n_d_i_1; double hopping=defparams.t1; n_f_i ? hopping+= defparams.t2 : 0; n_f_i_1 ? hopping+= defparams.t2 : 0; n_f_i && n_f_i_1 ? hopping+= defparams.t3 : 0; hopping*=base_hopping; sum+=hopping; } return -sum; }
Цього разу результати більш неоднозначні -- час роботи програми (відтворювано) зріс, але час виконання нашої функції (відтворювано) зменшився:
Each sample counts as 0.01 seconds.
% cumulative self self total
time seconds seconds calls us/call us/call name
49.66 9.58 9.58 7650000 1.25 1.25 eoBitMutation >::operator()(eoBit&)
==>27.99 14.98 5.40 6856343 0.79 0.79 hamiltonian(eoBit const&)
8.24 16.57 1.59 3060969 0.52 0.53 eo1PtBitXover >::operator()(eoBit&, eoBit&)
3.16 17.18 0.61 _mcount_private
1.97 17.56 0.38 __fentry__
1.61 17.87 0.31 7200787 0.04 0.04 void std::__unguarded_linear_insert<__gnu_cxx::__normal_iterator data-blogger-escaped-double="" data-blogger-escaped-eobit="">*, std::vector, std::allocator > > >, eoPop >::Cmp2>(__gnu_cxx::__normal_iterator*, std::vector, std::allocator > > >, eoPop >::Cmp2)
1.56 18.17 0.30 7650000 0.04 0.05 eoDetTournamentSelect >::operator()(eoPop > const&)
1.24 18.41 0.24 22512369 0.01 0.01 eoRng::rand()
1.24 18.65 0.24 153000 1.57 115.24 eoSGA >::operator()(eoPop >&)
0.52 18.75 0.10 153000 0.65 3.74 eoSelectPerc >::operator()(eoPop > const&, eoPop >&)
0.36 18.82 0.07 153204 0.46 0.46 average_nf_nd(eoBit, FK_params const&, unsigned int, unsigned int)
0.31 18.88 0.06 153000 0.39 0.39 void std::__uninitialized_default_n_1::__uninit_default_n*, unsigned long long>(eoBit*, unsigned long long)
0.31 18.94 0.06 eoLogger::outbuf::overflow(int)
0.26 18.99 0.05 153255 0.33 0.33 operator<<(std::ostream&, FK_GA_c const&)
0.26 19.04 0.05 153051 0.33 0.89 void std::__insertion_sort<__gnu_cxx::__normal_iterator data-blogger-escaped-double="" data-blogger-escaped-eobit="">*, std::vector, std::allocator > > >, eoPop >::Cmp2>(__gnu_cxx::__normal_iterator*, std::vector, std::allocator > > >, __gnu_cxx::__normal_iterator*, std::vector, std::allocator > > >, eoPop >::Cmp2)
0.21 19.08 0.04 7655763 0.01 0.01 eoBit::~eoBit()
Чому так, для мене поки залишається загадкою, але, як би там не було: 27.99% часу, або 5.40 секунд, 6856343 викликів -- кількість, із попереднього разу не змінилася, на одне використання функції: \( 4.08\cdot 10^{-6} \)%, \(7.87\cdot 10^{-7}\) с.
Висновки
Отож, підсумовуючи (на один виклик):
| Частка часу виконання,% | Час виконання функції, с | % часу від коду 1 | Коментарі |
|---|---|---|---|
| \( 5.12\cdot 10^{-6} \) | \(9.75\cdot 10^{-7}\) | 100% | Вихідний, до нудоти прямолінійний, код. |
| \( 5.45\cdot 10^{-6} \) | \(1.05\cdot 10^{-6}\) | 108% | Замість збереження вхідних 1 і 0 в double, використовуємо булівські значення. Стало гірше. |
| \( 4.89\cdot 10^{-6} \) | \(9.14\cdot 10^{-7}\) | 94% | Замість множити доданок на 1 або 0, використовуємо конструкції типу: sum-=defparams.mu_f*n_f_i; |
| \( 4.23\cdot 10^{-6} \) | \(8.12\cdot 10^{-7}\) | 83% | Тепер нам і копія булівського значення не потрібна -- скористаємося посиланням. |
| \( 4.08\cdot 10^{-6} \) | \(7.87\cdot 10^{-7}\) | 81% | Пробуємо перетасувати умови, щоб процесору було зручніше. Результат неоднозначний, але функція швидше працює. |
Тобто, на простому перетворенні, на зразок з:
double n_f_i = _indi[i]; double n_d_i = _indi[i+1]; sum-=defparams.mu_f*n_f_i; sum-=defparams.mu_d*n_d_i; sum+=defparams.U*n_f_i*n_d_i;в:
const bool& n_f_i{_indi[i]}; const bool& n_d_i{_indi[i+1]}; n_f_i ? sum-= defparams.mu_f : 0; n_d_i ? sum-= defparams.mu_d : 0 ; n_f_i && n_d_i ? sum+= defparams.U : 0 ;
вдалося виграти 20% продуктивності. Сказати чи це мало, чи багато, або мораль якусь вивести тут складно. Модель специфічна, методика вимірів місцями вразлива до критики, виграш не аж такий великий (хоча, від тривіального перетворення, а при багатотижневих розрахунках...), чи не постраждала в процесі читабельність коду, вимагає окремого дослідження (для фізиків, підозрюю, постраждала).
Однак, видно, що проста увага до дрібниць -- не копіювати зайвого, контролювати перетворення одних типів в інші, трішки уваги до потоку виконання, дозволяють із мінімальними зусиллями досягнути хороших результатів.
Хоча, слід надавати перевагу не мікро-оптимізаціям, а покращенню алгоритмів, але такі конструкції мали б "стікати з пальців" як славнозвісні "const Type&".
Зауваження щодо методики
- Компілятор --- GCC-4.8.2, MinGW64, 64-бітний.
- Код компілювався в режимі -O2, з додатковим ключем -ffast-math.
- Для цілей цього дослідження, seed для генератора випадкових чисел взято фіксованим.
- Перевірено, що результати розрахунків в режимі профілювання не відрізняються від результатів із ним. (Хіба що час роботи суттєво зростає).
- Так як сучасні OS багатозадачні, профілювання --- справа невдячна, процесор постійно і непередбачувано відволікається від задачі. Пом'якшувався вплив цього кількома повторними запусками, із вибором запуску, який зайняв найменше часу. (Відбір відбувався по сумарному часу виконання).
Немає коментарів:
Дописати коментар