C/C++

Wymuszanie wysokiej wydajności iostream

  • 2016-02-11 16:09:22
  • 2016-02-11 16:26:02
  • 1 komentarz
  • 6210 odsłon

Spotyka się czasem z opiniami, że w języku C++ we/wy za pomocą <iostream> jest znacznie wolniejsze od we/wy za pomocą <cstdio>, do tego stopnia, że <iostream> jest nieodpowiednim wyborem, gdy wymagana jest wysoka wydajność, np. do zadań algorytmicznych.

Istnieją jednak sposoby na znaczące przyspieszenie działania <iostream>:

  • Wywołać std::ios_base::sync_with_stdio(false); przed jakąkolwiek operacją we/wy;
  • Używać '\n' zamiast std::endl;
  • Wywołać std::cin.tie(nullptr); przed przemieszanymi operacjami we/wy.

Uwaga1: Szczególnie interesujący jest ten ostatni punkt; dwa pierwsze są powtarzane dosyć często, ten ostatni wydaje się być raczej niezauważany a szkoda, bo różnica w czasie może być olbrzymia.

Uwaga2: Należy mieć świadomość, że każda z powyższych operacji ma swoje pułapki i należy się z nimi zapoznać zanim zacznie się ich używać.

std::ios_base::sync_with_stdio(false);

Cytując http://en.cppreference.com/w/cpp/io/ios_base/sync_with_stdio :

Sets whether the standard C++ streams are synchronized to the standard C streams after each input/output operation.

*By default, all eight standard C++ streams are synchronized with their respective C streams. *

*In practice, this means that the C++ and the C streams use the same buffer, and therefore, can be mixed freely. In addition, synchronized C++ streams are guaranteed to be thread-safe (individual characters output from multiple threads may interleave, but no data races occur) *

*If the synchronization is turned off, the C++ standard streams are allowed to buffer their I/O independently, which may be considerably faster in some cases. *

*It is implementation-defined if this function has any effect if called after some I/O occurred on the standard stream. *

Zatem należy pamiętać, że: (a) Po użyciu tej instrukcji nie należy mieszać strumieni z iostream i z cstdio, jeśli są one buforowane: a więc np. nie należy używać std::printf i std::cout w tym samym programie, chyba że się wyłączy buforowanie; (b) Podobnie, nie należy wywoływać operacji we/wy z iostream z kilku wątków na raz; (c) Należy użyć tej instrukcji przed jakąkolwiek operacją we/wy.

Benchmark:

Plik test1.cpp:

#include <iostream>
#include <vector>
using namespace std;

int main()
{
  vector<int> vec;
  vec.reserve(7077888);
  for(int i = 0; i < 7077888; ++i)
  {
    int n;
    cin >> n;
    vec.push_back(n);
  }
  for(int n : vec)
    cout << n << '\n';
}

Plik test2.cpp:

#include <iostream>
#include <vector>
using namespace std;

int main()
{
  
  ios_base::sync_with_stdio(false);
  
  vector<int> vec;
  vec.reserve(7077888);
  for(int i = 0; i < 7077888; ++i)
  {
    int n;
    cin >> n;
    vec.push_back(n);
  }
  for(int n : vec)
    cout << n << '\n';
}

Plik test3.cpp:

#include <cstdio>
#include <vector>
using namespace std;

int main()
{
  vector<int> vec;
  vec.reserve(7077888);
  for(int i = 0; i < 7077888; ++i)
  {
    int n;
    scanf("%d", &n);
    vec.push_back(n);
  }
  for(int n : vec)
    printf("%d\n", n);
}

Plik test.in składa się z 7077888 linii każda zawierająca tylko jedną cyfrę 5. Ma on 14,2 MB więc nie będę go tu zamieszczać.

Wszystkie powyższe pliki źródłowe kompilowane poleceniem g++ -O2 -std=c++11. Wersja kompilatora: g++ (Ubuntu 4.8.4-2ubuntu1~14.04) 4.8.4 (tak wiem, stary).

Wyniki benchmarku:

work@mg-K54C ~ $ time ./test1 < test.in > test1.out

real	0m2.582s
user	0m2.454s
sys	0m0.032s
work@mg-K54C ~ $ time ./test2 < test.in > test2.out

real	0m1.413s
user	0m1.302s
sys	0m0.032s
work@mg-K54C ~ $ time ./test3 < test.in > test3.out

real	0m1.656s
user	0m1.516s
sys	0m0.028s

Widać, że w tym przypadku bez synchronizacji strumienie z iostream są dwukrotnie szybsze, i nawet nieco szybsze niż cstdio.

'\n' zamiast std::endl

Cytując http://en.cppreference.com/w/cpp/io/manip/endl :

Inserts a newline character into the output sequence os and flushes it as if by calling os.put(os.widen('\n')) followed by os.flush().

Użycie '\n' zamiast std::endl nie powoduje wyczyszczenia bufora, co istotnie zwiększa szybkość. Należy pamiętać, że oznacza to, że wyjście może być opóźnione (buforowanie), zatem używanie '\n' może być nieodpowiednie w niektórych zastosowaniach.

Benchmark:

Plik test1.cpp:

#include <iostream>
using namespace std;

int main()
{
  ios_base::sync_with_stdio(false);

  for(int i = 0; i < 1179648; ++i)
    cout << i << endl;
}

Plik test2.cpp:

#include <iostream>
using namespace std;

int main()
{
  ios_base::sync_with_stdio(false);

  for(int i = 0; i < 1179648; ++i)
    cout << i << '\n';
  
  cout.flush();
}

Plik test3.cpp:

#include <cstdio>
using namespace std;

int main()
{
  for(int i = 0; i < 1179648; ++i)
    printf("%d\n", i);
}

Kompilacja jak wyżej.

Wyniki benchmarku:

work@mg-K54C ~ $ time ./test1 > test1.out

real	0m2.867s
user	0m0.409s
sys	0m2.454s
work@mg-K54C ~ $ time ./test2 > test2.out

real	0m0.160s
user	0m0.132s
sys	0m0.024s
work@mg-K54C ~ $ time ./test3 > test3.out

real	0m0.173s
user	0m0.154s
sys	0m0.015s

Jak widać, w tym przypadku użycie '\n' zamiast endl przyspieszyło działanie o rząd wielkości, do poziomu praktycznie nie różniącego się od cstdio.

Uwaga: Spróbowałem zastosować podobną optymalizację w przypadku printf, pisząc char buff[BUFSIZ]; setvbuf(stdout, buff, _IOFBF, BUFSIZ); przed wypisywaniem danych. Nie uzyskałem jednak żadnej różnicy w czasie wykonania. Być może bierze się to stąd, że, jak pisze man 3 stdout, „The stream stdout is line-buffered when it points to a terminal.” – a ja przecież przekierowuję strumień wyjścia do pliku, być może zatem ta optymalizacja dodaje się automatycznie.

std::cin.tie(nullptr)

Cytując http://en.cppreference.com/w/cpp/io/cin :

*Once std::cin is constructed, std::cin.tie() returns &std::cout, and likewise, std::wcin.tie() returns &std::wcout. This means that any formatted input operation on std::cin forces a call to std::cout.flush() if any characters are pending for output. *

Można uniknąć czyszczenia bufora, wyłączając to powiązanie poprzez std::cin.tie(nullptr). Przydatne, jeśli odwołania do std::cin i std::cout występują naprzemiennie. Należy pamiętać, że użycie tej instrukcji może spowodować, że wyjście będzie pojawiać się z opóźnieniem wobec wejścia, zatem użycie tej instrukcji jest nieodpowiednie do programów interaktywnych.

Benchmark:

Plik test1.cpp:

#include <iostream>
using namespace std;

int main()
{
  ios_base::sync_with_stdio(false);

  int i;
  while(cin >> i)
    cout << i << '\n';
}

Plik test2.cpp:

#include <iostream>
using namespace std;

int main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);

  int i;
  while(cin >> i)
    cout << i << '\n';

  cout.flush();
}

Plik test3.cpp:

#include <cstdio>
using namespace std;

int main()
{
  int i;
  while(scanf("%d", &i) != EOF)
    printf("%d\n", i);
}

Plik test.in jak wyżej, tyle że skrócony do 1179648 linii (2,4 MB).

Pliki źródłowe kompilowane jak wyżej.

Wyniki benchmarku:

work@mg-K54C ~ $ time ./test1 < test.in > test1.out

real	0m3.088s
user	0m0.692s
sys	0m2.397s
work@mg-K54C ~ $ time ./test2 < test.in > test2.out

real	0m0.236s
user	0m0.220s
sys	0m0.016s
work@mg-K54C ~ $ time ./test3 < test.in > test3.out

real	0m0.298s
user	0m0.286s
sys	0m0.008s

Widać, że w tym przypadku użycie tej optymalizacji przyspieszyło działanie iostream o cały rząd wielkości, do poziomu nawet nieco szybszego niż cstdio.

TODO: zwiększenie bufora, zabawy z locale? http://stackoverflow.com/questions/5166263/how-to-get-iostream-to-perform-better/35340653#35340653

TODO: Lepszy benchmark dla sync_with_stdio? Dziwi mnie tylko dwukrotna różnica w czasie, skoro wiele osób o tym trąbi i skoro zdarza się podobno, że sprawdzarki do zadań algorytmicznych odrzucają rozwiązania z iostream zamiast cstdio tylko dlatego, że nie ma sync_with_stdio(false).

C/C++

1 komentarz

hauleth

Mój skrypt testowy (stary i zużyty, ale zawsze):

#!/bin/sh

times=1000000 # count
main="int main(){"
loop=" for(int i = 0; i < $times; i++) "
end=" return 0;}"
CXX=g++
FLAGS=-O2

file=test.cpp # outfile
ofile=test.out # executable outfile

ifile=test.in # infile

if [ ! -e $ifile ]
then
  seq 0 $powt > $ifile
fi

echo "Output:"

echo -e "#include<iostream> \n$main $loop std::cout << i;$end" > $file
echo "std::cout bez sync_with_stdio(0)"
$CXX -o $ofile $file $FLAGS
time ./$ofile > /dev/null

echo -e "#include<iostream> \n$main std::ios_base::sync_with_stdio(0); $loop std::cout << i;$end" > $file
echo -e "\nstd::cout z sync_with_stdio(0)"
$CXX -o $ofile $file $FLAGS
time ./$ofile > /dev/null

echo -e "#include<cstdio> \n$main $loop printf(\"%d\", i);$end" > $file
echo -e "\nprintf()"
$CXX -o $ofile $file $FLAGS
time ./$ofile > /dev/null

echo -en "\nOutput:"

echo -e "#include<iostream> \n$main int test; $loop { std::cin >> test;}$end" > $file
echo -e "\nstd::cin bez sync_with_stdio(0)"
$CXX -o $ofile $file $FLAGS
time ./$ofile < $ifile

echo -e "#include<iostream> \n$main std::ios_base::sync_with_stdio(0); int test; $loop { std::cin >> test;}$end" > $file
echo -e "\nstd::cin z sync_with_stdio(0)"
$CXX -o $ofile $file $FLAGS
time ./$ofile < $ifile

echo -e "#include<cstdio> \n$main int test; $loop { scanf(\"%d\", &i);}$end" > $file
echo -e "\nscanf()"
g++ -o $ofile $file $FLAGS
time ./$ofile < $ifile

rm $ofile $ifile #file

Mówi, że tak nie zawsze jest:

Output:
std::cout bez sync_with_stdio(0)

real	0m0.179s
user	0m0.092s
sys	0m0.000s

std::cout z sync_with_stdio(0)

real	0m0.186s
user	0m0.092s
sys	0m0.000s

printf()

real	0m0.226s
user	0m0.116s
sys	0m0.000s

Output:
std::cin bez sync_with_stdio(0)

real	0m0.049s
user	0m0.024s
sys	0m0.000s

std::cin z sync_with_stdio(0)

real	0m0.015s
user	0m0.012s
sys	0m0.000s

scanf()
test.cpp: In function ‘int main()’:
test.cpp:2:75: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
 int main(){ int test;  for(int i = 0; i < 1000000; i++)  { scanf("%d", &i);} return 0;}
                                                                           ^

real	0m0.495s
user	0m0.100s
sys	0m0.160s