Programowanie w języku C/C++

Wymuszanie wysokiej wydajności iostream

  • 2016-02-11 16:26
  • 1 komentarz
  • 876 odsłon
  • 2,5/6
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:

[email protected] ~ $ time ./test1 < test.in > test1.out
 
real    0m2.582s
user    0m2.454s
sys    0m0.032s
[email protected] ~ $ time ./test2 < test.in > test2.out
 
real    0m1.413s
user    0m1.302s
sys    0m0.032s
[email protected] ~ $ 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:
[email protected] ~ $ time ./test1 > test1.out
 
real    0m2.867s
user    0m0.409s
sys    0m2.454s
[email protected] ~ $ time ./test2 > test2.out
 
real    0m0.160s
user    0m0.132s
sys    0m0.024s
[email protected] ~ $ 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:
[email protected] ~ $ time ./test1 < test.in > test1.out
 
real    0m3.088s
user    0m0.692s
sys    0m2.397s
[email protected] ~ $ time ./test2 < test.in > test2.out
 
real    0m0.236s
user    0m0.220s
sys    0m0.016s
[email protected] ~ $ 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/quest[...]rform-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).

1 komentarz

winerfresh 2016-02-11 23:18

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