Наскільки повільні iostreams?

Потоки введення-виведення в стандартної бібліотеки C++ прості у використанні, типобезопасны, стійкі до відпливу ресурсів, і дозволяють просту обробку помилок. Однак, за ними закріпилася репутація «повільних». Цьому є кілька причин, таких як широке використання динамічної алокації та віртуальних функцій. Взагалі, потоки — одна з найдавніших частин STL (вони почали використовуватися приблизно в 1988 році), і багато рішень у них зараз сприймаються як «спірні». Тим не менш, вони широко використовуються, особливо коли треба написати якусь просту програму, яка працює з текстовими даними.

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

Сьогодні у коментарях у посаді виникло обговорення про повільність iostreams. Зокрема, freopen пише:
Забавно дивитися на ваші оптимізації, розташовані по сусідству зі зчитуванням через cin :)
aesamson дає таку рекомендацію
Можна замінити на getchar_unlocked() для *nix або getchar() для всіх інших.
getchar_unlocked > getchar > scanf > cin, де ">" означає швидше.


У цьому пості я розвію і підтверджу деякі міфи і дам декілька рекомендацій.


Всі вимірювання в цьому пості наведені для системи Ubuntu 14.10 з компілятором GCC 4.9.1, компилировалось з ключами
g++ -Wall-Wextra-std=c++11-O3

Запуск проводився на ноутбуці з процесором Intel Core2 Duo P8600 (2.4 ГГц).

Постановка завдання

У спортивному програмуванні, як і в UNIX-way, зазвичай вхідні дані подаються на вхідний потік. Отже, завдання:

На вхідний потік (stdin) надходить багато невід'ємних цілих чисел по одному рядку. Програма повинна вивести максимальну вхідних чисел.

Сформуємо вхідні дані
seq 10000000 > data

Файл data ми записали 10 мільйонів послідовних цілих чисел, загальним обсягом 76 мегабайт.
Запускати програму ми будемо так
time ./a.out < data

Отже, приступаємо.

1.
scanf

Розв'яжемо задачу з використанням старого доброго scanf.
int max_scanf()
{
int x;
int max = -1;
while (scanf("%d", &x) == 1)
{
max = std::max(x, max);
}
return max;
}

При використанні scanf важливо не забути завжди перевіряти значення, що повертається — це кількість реально прочитаних і заповнених аргументів (GCC з-Wall нагадає про це). В нашому випадку при успішному читанні значення, що повертається, повинно дорівнювати 1.
Функція main
int main()
{
std::cout << max_scanf() << std::endl;
return 0;
}

Час роботи: 1.41 c

2. Наївний
std::cin

Тепер вирішимо завдання найпростішим способом за допомогою iostreams:
int max_iostream(std::istream & f)
{
int x;
int max = -1;
while(f >> x)
max = std::max(x, max);
return max;
}

Час роботи: 4.41 c
Ого! Потоки виявилися повільніше ніж scanf в 3 рази! Тобто виходить, що iostream виявляються дійсно нікуди не годиться по швидкості?

3. Швидкий
std::cin

Насправді, щоб виправити ситуацію, досить додати в програму одну сходинку. На самому початку функції main вставимо:
std::ios::sync_with_stdio(false);

Що це означає?
Для того, щоб в програмі можна було змішувати iostreams і stdio, була введена ця синхронізація. За замовчуванням, при роботі зі стандартними потоками (
std::cin, std::cout, std::cerr
...) буфер скидається після кожної операції вводу-виводу, щоб дані не перемішувалися. Якщо ж ми припускаємо користуватися тільки iostream, то ми можемо відключити цю синхронізацію. Детальніше можна почитати на cppreference.
Час роботи: 1.33 c
Зовсім інша справа! Більш того, це швидше, ніж scanf! Тобто, не все так погано. До плюсів iostreams можна віднести простоту використання, типобезопасность і більш легку обробку помилок.

4. Наївний
std::istringstream

Крім введення з файлу, стандартна бібліотека надає класи для введення тексту з таким же інтерфейсом. Подивимося, наскільки це повільно. Будемо читати з вхідного потоку по одному рядку, а потім парсити її за допомогою
std::istringstream
:
int max_iostream_iss(std::istream & f)
{
int x;
int max = -1;
std::string line;
while (std::getline(f, line))
{
std::istringstream iss(line);
if(! (iss >> x))
break;
max = std::max(x, max);
}
return max;
}

Час роботи: 7.21 c
Дуже повільно!

5. Переиспользование
std::istringstream

Виявляється, саме повільне
istringstream
— це його створення. А ми створюємо для кожної вхідний рядки заново. Спробуємо переиспользовать один і той же об'єкт:
int max_iostream_iss_2(std::istream & f)
int max_iostream_iss_2(std::istream & f)
{
int x;
int max = -1;
std::string line;
std::istringstream iss(line);

while (std::getline(f, line))
{
iss.clear(); // Скидаємо прапори помилок
iss.str(line); // Задаємо новий буфер
if(! (iss >> x))
break;
max = std::max(x, max);
}
return max;
}

Зверніть увагу, що потрібні 2 виклику — clear, щоб скинути прапори стану, і str, щоб задати новий буфер, з якого буде відбуватися читання.

Час роботи: 2.16 c
Це інша справа. Це очікувано повільніше, ніж читання безпосередньо з
std::cin
(дані проходять 2 рази через класи потоків), але не катастрофічно.

6. Хочемо ще швидше! (getchar/getchar_unlocked)

Що робити, якщо продуктивності все одно не вистачає? Використовувати більш низькорівневі засоби введення-виведення і кастомный парсер. У коментарях до згаданого топіку aesamson навів приклад коду, що реалізує простий парсер цілих чисел (ймовірно, взятий з StackOverflow). Для читання з вхідного потоку використовується
getchar_unlocked
— потоконебепасная версія
getchar
. Я додав пропуск зайвих символів і найпростішу обробку кінця файлу:
bool read_int_unlocked(int & out)
{
int c = getchar_unlocked();
int x = 0;
int neg = 0;

for (; !('0'<=c && c<='9') && c != '-'; c = getchar_unlocked())
{
if (c == EOF)
return false;
}
if (c == '-')
{
neg = 1;
c = getchar_unlocked();
}
if (c == EOF)
return false;
for (; '0' <= c && c <= '9' ; c = getchar_unlocked())
{
x = x*10 + c - '0';
}
out = neg ? -x : x;
return true;
}

int max_getchar_unlocked()
{
int x;
int max = -1;
while(read_int_unlocked(x))
max = std::max(x, max);
return max;
}

Час роботи:
getchar
0.82,
getchar_unlocked
0.28!
Дуже хороший результат! І видно, наскільки велике уповільнення через блокувань заради потокобезопасности.
Але у такого підходу є мінуси — потрібно писати парсери для всіх використовуваних типів даних (а це вже не так просто навіть для чисел з плаваючою комою), складність обробки помилок, потоконебезопасность у разі
getchar_unlocked
. Алтернативно — можна спробувати скористатися генератором парсерів, наприклад
re2c
,
boost::Spirit::Qi
, і т. д. (багато їх).

Результати та поради

Час роботи:
No Опис Час роботи
1 scanf 1.41
2 std::cin 4.41
3 std::cin і std::ios::sync_with_stdio(false) 1.33
4 std::istringstream 7.21
5 std::istringstream з переиспользованием 2.16
6a getchar 0.82
6b getchar_unlocked 0.28
Рекомендації:
  • Для того, щоб докорити
    std::cin/std::cout
    ,
    std::ios::sync_with_stdio(false);
    При цьому швидкість стане порівнянної або краще ніж scanf. (Тільки переконайтеся, що ви не змішуєте потокові та stdio операції на одному і тому ж потоці)
  • istringstream дуже повільний конструктор. Тому продуктивність можна серйозно підняти якщо переиспользовать об'єкт потоку.
  • Більшій продуктивності можна досягти, використовуючи
    getchar_unlocked
    (або
    getchar
    , якщо потрібна потокобезопасность) і кастомный парсер.
  • Ще більшої продуктивності ймовірно можна досягти, якщо читати дані великими шматками і потім працювати виключно в пам'яті.
Увага! Результати справедливі тільки на конкретній системі і можуть сильно відрізнятися на інших системах! Зокрема, я швиденько спробував clang + libc++ і отримав набагато гіршу продуктивність потоків (тоді як при використанні libstdc++ і clang і gcc дали майже ідентичні результати). Обов'язково тестуйте продуктивність при застосуванні рад! (І, в ідеалі, повідомляйте про результати на вашій системі в коментарях, щоб інші могли воспользвоваться). Повний код доступний тут.

Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.