Домівка > Перекладені > Прагнеш швидкості? Передавай за значенням.

Прагнеш швидкості? Передавай за значенням.

Тільки чесно: які почуття викликає в вас наступний код?

std::vector<std::string> get_names();
...
std::vector<std::string> const names = get_names();

Відверто, я б занервував. В принципі, по завершені get_names() ми маємо копіювати вектор рядків. Потім ми маємо копіювати його знов, коли ініціалізуємо names, і маємо знищити першу копію. Якщо в векторі N рядків, кожне копіювання може вимагати аж по N+1 виділень пам’яті і безліч недружнього щодо кешу доступу до даних, коли вміст рядка копіюється.

Радше ніж відчувати цю тривогу, я часто повертався до використання передачі за посиланням, щоб уникнути непотрібних копій:

get_names(std::vector<std::string>& out_param );
...
std::vector<std::string> names;
get_names( names );

На жаль, цей підхід далекий від досконалості.

  • Об’єм коду виріс на 150%
  • Нам довелось поступитись сталістю, бо ми змінюємо names.
  • Як функційні програмісти захочуть нам нагадати, зміна параметра ускладнює розуміння через підривання прозорості посилань і міркувань щодо рівнянь (equational reasoning.).
  • Ми більше не дотримуємось суворої семантики передачі за значенням для names.

Але, чи дійсно конче необхідно так плутати наш код для досягнення дієвості? На щастя, виявляється, що відповідь ні (особливо, якщо ви використовуєте C++0x). Ця стаття перша в серії, що досліджує п-значення (rvalues) та їх вплив на дієвість семантики значень (value semantics) в C++.

П-значення

П-значення – значення, що відповідають безіменним тимчасовим об’єктам. Назва п-значення посилається до факту, що вбудований тип може зустрічатись лише праворуч від символу надання значення. На відміну л-значень, які, у випадку несталості, можна використовувати ліворуч оператора надання значення, п-значення породжують об’єкт без будь-якої стійкої особистості, якій можна було б надати значення.

Важливим зауваженням щодо безіменних тимчасових об’єктів у нашому випадку є те, що їх можна лише один раз використати в виразі. Як би ви могли вдруге послатись на цей об’єкт. В нього немає ім’я (звідси “безіменний”); і після обчислення цілого виразу, об’єкт знищується (звідси “тимчасовий”)!

Якщо ви знаєте, що копіюєте п-значення, тоді, має існувати можливість “поцупити” дорогі для копіювання ресурси з вихідного об’єкта і використовувати їх в цільовому об’єктові, не зашкодивши цім нікому. В нашому випадку, це означаю передачу володіння динамічно розміщеного масиву рядків вихідного вектора цільовому вектору. Якщо б ми могли якось примусити компілятор виконати цей “переніс” для нас, ініціалізація з вектора повернутого за значенням була б майже безкоштовною.

Так ми б подбали про друге дороге копіювання, але що з першим? Коли get_names повертає керування, в принципі, вона має скопіювати значення, що повертається з середини функції назовні. Добре, зрозуміло, що значення до повертання мають однакові властивості з безіменними тимчасовими об’єктами: вони будуть знищені і не будуть використані повторно. Отже, ми можемо виключити перше дороге копіювання так само, передав ресурси від значення, що повертається до тимчасового об’єкта, якого побачить викликова функція.

Уникнення копіювання та RVO

Причина чому я вжив слова “в принципі” в попередньому розділі полягає в тому, що компілятор насправді дозволяє виконання деяких поліпшень базованих на тих самих принципах, що ми щойно обговорювали. Цей клас поліпшень зазвичай формально відомий як уникнення копіювання (copy elision). Наприклад, при поліпшенні повернення значення(Return Value Optimization, RVO), викликова (caller) функція виділяє простір для значення, яке буде повертатись у своєму стеці, і передає адресу цієї пам’яті викликуваній (callee) функції. Тепер викликувана функція може сконструювати значення прямо в цьому місці, такий підхід дозволяє уникнути одного копіювання зсередини назовні. Отже в коді на кшталт наступного копіювання не потрібні:

std::vector<std::string> names = get_names();

Також, хоча компілятор зазвичай має зробити копію коли параметр функції передається з значенням (отже зміни в параметрі в середині функції не відіб’ються на значені у зовнішній функції), йому дозволено уникнути копіювання, і просто використовувати поданий об’єкт, у разі якщо це п-значення.

std::vector<std::string> 
sorted(std::vector<std::string> names)
{
    std::sort(names);
    return names;
}
 
// names - це л-значення; копіювання обов'язково, щоб не змінити names
std::vector<std::string> sorted_names1 = sorted( names );
 
// get_names() - це п-значення; ми можемо опустити копіювання!
std::vector<std::string> sorted_names2 = sorted( get_names() );

Це досить дивовижно. В принципі, в останньому рядку компілятор може взагалі уникнути копіювань, зробив sorted_names2 тим самим об’єктом, який створила get_names(). Хоча на практиці, як я поясню пізніше, так далеко не заходить.

Наслідки

Хоча стандарт ніколи не вимагав уникати копіювання, останні версії всіх компіляторів, що я перевіряв, виконують таке поліпшення на сьогодні. Але навіть якщо ви на почуваєтесь зручно повертаючи важкі об’єкти за значенням, уникнення копіювання мало б змінити ваш код.

Уявімо таку братню до початкової sorted(…) функцію, яка приймає names як стале посилання і виконує явне копіювання:

std::vector<std::string> 
sorted2(std::vector<std::string> const& names) // names передається за посиланням
{
    std::vector<std::string> r(names);        // і явно копіюється
    std::sort(r);
    return r;
}

Незважаючи на те, що sorted і sorted2 спочатку здаються тотожними, тут може бути значна різниця в швидкодії якщо компілятор виконує уникнення копіювання. Навіть якщо дійсний аргумент (actual argument) sorted2 – це п-значення, джерело для копіювання, names, це л-значення, отже компілятор не може відоптимізувати копіювання. В деякому сенсі уникнення копіювання – це жертва моделі роздільної компіляції: в тілі sorted2 немає даних про те чи є дійсний аргумент п-значенням; назовні, в місці виклику, нічого не вказує на те, що копія буде зроблена.

Ця реалізація підводить нас прямо до такого:

Керівництво: Не копіюйте аргументи своїх функцій. Натомість, передавайте їх за значенням і нехай компілятор копіює.

В найгіршому випадку, якщо компілятор не уникне копіювання, швидкодія буде не гіршою. Як найкращий варінт, ви отримаєте значне покращення швидкодії.

Одне з місць, де ви можете застосувати це керівництво негайно, це оператор надавання значення. Канонічний, легкий до написання, завжди вірний, копіювання й обміну оператор надавання значення часто виглядає так:

T& T::operator=(T const& x) // x - це посилання на джерело
{ 
    T tmp(x);          // конструктор копіювання tmp зробить важку роботу
    swap(*this, tmp);  // обмінюємось ресурсами з tmp
    return *this;      // наші (старі) ресурси знищені з tmp 
}

але в світлі уникнення копіювання, це формулювання кричуще недієве! Зараз явно видно, що вірний спосіб написання оператора копіюванням і присвоєнням такий:

T& operator=(T x)    // x - це посилання на джерело; важку роботу вже зроблено
{
    swap(*this, x);  // обмінюємо наші ресурси з x
    return *this;    // наші (старі) ресурси знищуються з x
}

Сувора дійсність

Звісно, сир ніколи не буває безкоштовним, отже я маю пару застережень.

По-перше, коли ви передаєте параметри за посиланням і копіювання відбувається в тілі функції, конструктор копіювання викликається з одного місця, централізовано. Однак, коли ви передаєте параметр за значенням, компілятор створює виклики до конструктора копіювання в місці кожного виклику, де передається аргумент л-значення. Якщо функція викликається з багатьох місць і розмір коду має серйозне значення для вашого застосунку, це може мати помітний ефект.

З іншого боку, легко написати функцію-обгортку яка локалізує копіювання:

std::vector<std::string> 
sorted3(std::vector<std::string> const& names)
{
    // копіювання генерується один раз, в місці цього виклику
    return sorted(names);
}

З того, що зворотнє не вірно – ви не можете повернути втрачені через обгортку можливості з уникнення копіювання – я раджу вам почати з дотримання керівництва, і робити зміни лиш коли знайдете їх необхідними.

По-друге, я хотів би знайти компілятор, який зміг би уникнути копіювання, коли параметр функції повертається з неї, як в нашому втіленні sorted. Коли ви думаєте як ці уникнення робляться, це має сенс: без якоїсь з форм міжпроцедурної оптимізації, викликова функція (caller) не може знати, що аргумент (а не інший об’єкт) буде зрештою повернутий, отже компілятор має виділити окреме місце на стеці для аргументу і значення для повернення.

Якщо вам необхідно повернути параметр функції, ви все ще можете отримати майже найліпшу швидкодію через обмін з по замовчанню створеним значенням до повернення (за умови якщо конструювання за замовчанням й обмін дешеві, якими вони й мають бути):

std::vector<std::string> 
sorted(std::vector<std::string> names)
{
    std::sort(names);
    std::vector<std::string> ret;
    swap(ret, names);
    return ret;
}

Вихідна стаття

Advertisements
Категорії:Перекладені Позначки:,
  1. Коментарів ще немає.
  1. No trackbacks yet.

Залишити відповідь

Заповніть поля нижче або авторизуйтесь клікнувши по іконці

Лого WordPress.com

Ви коментуєте, використовуючи свій обліковий запис WordPress.com. Log Out / Змінити )

Twitter picture

Ви коментуєте, використовуючи свій обліковий запис Twitter. Log Out / Змінити )

Facebook photo

Ви коментуєте, використовуючи свій обліковий запис Facebook. Log Out / Змінити )

Google+ photo

Ви коментуєте, використовуючи свій обліковий запис Google+. Log Out / Змінити )

З’єднання з %s

%d блогерам подобається це: