Programowanie w języku C/C++ » Artykuły

Boost.Iostreams

  • 2010-03-12 16:09
  • 2 komentarze
  • 1969 odsłon
  • Oceń ten tekst jako pierwszy
Wstęp

Język C++ powstał, by połączyć siłę wyrazu, jaką dawały pojęcia Simuli67 służące strukturyzacji modelowanego w programie wycinka rzeczywistości z wydajnością okupioną zbliżeniem programisty do systemu komputerowego, jakie dawał język C.
     Zrezygnowano w nim z wielu udogodnień takich jak garbage collection, jednak dzięki założeniu, że wszelkie dodatkowe funkcje będą realizowane poprzez wykorzystanie odpowiednich bibliotek otwarto język C++ na innowacyjne rozszerzenia ze strony użytkowników – w ten sposób powstaje wiele rozwiązań uwzględniających wciąż na nowo, wraz z rozwojem techniki wspomniane wyżej aspekty, a coraz lepiej wychodzących naprzeciw współczesnym potrzebom.
     W tym tekście przyglądając się kwestii usunięcia komentarzy, postaramy się znaleźć drogę do wyrażenia tego we współczesnych kategoriach pojęciowych C++, na koniec odkryjemy ciekawe narzędzie, jakim jest biblioteka boost::iostreams dająca nową siłę wyrazu obecnym w C++ od dawna strumieniowym operacjom I/O.

Patowa sytuacja

Prosty kod w jęz. C, przetwarzający wsadowo plik wejściowy z komentarzami na wyjściowy ich pozbawiony może mieć następującą postać:
void remove_cmts(FILE* out, FILE* in) 
{
 char c = getc(in);
 enum { non_cmt, cmt, pre_cmt, ending_cmt } _state = non_cmt; 
 
  while(c != -1) 
  { 
    switch(_state) 
    { 
    case cmt : if(c=='*') _state = ending_cmt; break;
 
    case non_cmt : if(c=='/') _state = pre_cmt; 
                   else putc(c,out); // state still non_cmt 
                   break;
 
    case pre_cmt : if (c == '*') _state = cmt; 
                   else { 
                         putc('/',out); 
                          (c == '/') ? 
                               _state = pre_cmt : _state = non_cmt; 
                        } break;
 
    case ending_cmt: if (c=='/') _state = non_cmt; break; 
 
    } 
  c = getc(in); 
  } 
 
} 

Spróbujmy poszukać rozwiązania w C++, trzymającego się ściśle paradygmatu funkcyjnego. Wprawdzie biblioteka standardowa oferuje dość szerokie spektrum możliwości przetwarzania ciągu znaków, to jednak, chciałbym tu  wyjść od strumienia wejściowego i tak go przetworzyć, aby w wyjściowym otrzymać żądany wynik. W szczególności chciałbym uniknąć kopiowania czegokolwiek z tego pliku do kontenera znakowego.

Wychodząc od końca, czyli podsumowania funkcją main, zanotowanych wyżej postulatów przedstawiam wymarzony fragment kodu:
int main(int argc, char ** argv) 
{ 
if (argc < 3) return 1;
 
ifstream strIN  (argc[2]); 
ofstream strOUT (argc[1]); 
 
remove_copy_if(istream_iterator<char>(strIN), istream_iterator<char>(), 
               ostream_iterator<char>(strOUT), Predykat<char>()); 
return 0; 
} 


Algorytm std::remove_copy_if(…), przekopiuje znaki ze strumienia wejściowego do wyjściowego, przy okazji usuwając te, dla których predykat przybierze wartość true. Problem pojawia się przy sformułowaniu logiki, jaką taki predykat miałby się posłużyć…

Łatwo zauważyć, że powinien on posiadać stan uświadamiający go czy dany znak znajduje się wewnątrz komentarza czy poza nim. Co to treści komentarza nie ma większych problemów, jednak samo oznaczenie komentarza również wchodzi w jego skład, a jest ono dwuznakowe. W momencie, gdy predykat ma orzec, czy na przykład znak ‘/’ powinien zostać usunięty czy nie, musi wiedzieć czy po nim następuje ‘*’ czy też nie.

Dwa dodatkowe stany w kodzie C: pre_cmt, i ending_cmt dają programowi ma świadomość czy wcześniej był / lub *, jednak musi on wstawić / gdy przy następnym znaku okaże się że znak / nie zaczynał komentarza.
Problem polega na tym iż predykat posługując się iteratorami wejściowymi nie ma możliwości wstawienia znaku '/'.

Można próbować zwrócić się w stronę poglądania kolejnego znaku (czy po / nie ma *, czy też czy po * nie ma /) zamiast zamykania rozwiązania w sztywnej logice maszyny stanów jednak predykat nie ma również możliwości ani obejrzenia kolejnego znaku ani cofnięcia się do poprzedniego.

Algorytm dokonuje przetwarzania znak po znaku, a jedyną kontrolę, jaką ma nad nim programista jest orzeczenie za pomocą predykatu, jakie działanie ma algorytm podjąć w związku z przetwarzanym w danej chwili obiektem.

Jak więc widać, schemat przetwarzania zarysowany w kodzie na początku dałby się zastosować do komentarzy w rodzaju # … \n. Natomiast logika zawarta w przytoczonym na wstępie fragmencie programu w C, jest niemożliwa do zawarcia w tego rodzaju obiekcie funkcyjnym. Jeśliby jednak takie rozwiązanie było możliwe do napisania, nie byłoby najlepszym pomysłem, przez wzgląd na wydajność, ale po kolei…

Po 1. Co z tą logiką?

Tak czy inaczej, predykat, który orzeka o usunięciu bądź pozostawieniu znaku w strumieniu musiałby wiedzieć czy zaczyna on lub kończy komentarz. Rozważmy krótko rozwiązanie związane z pozyskaniem wiedzy na ten temat na niższym poziomie niż obiekt funkcyjny parametryzujący algorytm, gdy ten ostatni bezlitośnie biegnie do przodu.

Sam algorytm, do przechodzenia po elementach kontenera, posługuje się iteratorami (w artykule pt. Wyrażenia regularne jako black box w STL przedstawiłem relacje miedzy głównymi elementami tej biblioteki) można, więc za ich pomocą wczytywać po dwa znaki a nie po jednym i dać w ten sposób predykatowi możliwość określenia czy mamy do czynienia z komentarzem czy nie.

Jednak nim popełnimy tę zbrodnię, warto się chwilę zastanowić, jakie problemy mogą się pojawić na tej drodze.
Po pierwsze należy rozważyć, jaki będzie efekt użycia iteratora następującego typu: istream_iterator<char[2]>.

Wyjść w tym celu trzeba od standardu C++, który o wspomnianym iteratorze mówi, co następuje:

“istream_iterator reads (using operator>>) successive elements from the input stream for which it was constructed.”

Ważne, ze względu na sposób działania operatora>>. Spójrzmy na poniższe instrukcje:
char tmp_buf[2]; 
input_stream >> tmp_buf; // not an option... 

To właśnie zrobi strumieniowy iterator wejściowy, innymi słowy, czytając plik (przez sukcesywne użycie inkrementacji i pierwszy raz w konstruktorze), jeżeli natrafi na fragment tekstu większy niż dwuliterowe słowo dokona dzieła zniszczenia (przynajmniej stosu). Słowo jest tu rozumiane jako ciąg znaków ograniczony białymi znakami. Oczywista ta oczywistość związana jest ze standardowym działaniem extractora dla typu char*.

Nie jest to działanie zadowalające, w kontekście tego, co chcemy otrzymać wewnątrz predykatu. Można odwołać się, zatem do ingerencji na poziomie wczytywania strumienia tworząc osobny ekstraktor dla wczytania dwuznakowych elementów, niepozwalający na przekroczenie wielkości bufora.

Problemy, jakie się pojawią już nawet nie przy jego tworzeniu takie jak parzysta bądź nieparzysta liczba znaków w pliku, ale przy samej implementacji zdają się od tego odwodzić. Wystarczy wyobrazić sobie dwa możliwe dwuznakowe elementy pobrane przez kolejne przesunięcia iteratora: „a/” oraz „*b”, żeby ulec kompletnemu zniechęceniu do takiego rozwiązania.

Tworzenie bardziej skomplikowanych extractor'ów, wczytujących raz jeden raz dwa znaki oraz inserterów symentrycznie działającyh, by móc umożliwić algorytmowi remove... włąściwe działanie również nie napawa zbytnim optymizmem.

Technologia w służbie wydajności pracy (i nie tylko)
 
W jaki więc sposób włączyć logikę maszyny stanów, przedstawionej w kodzie C na początku, w ramy pracy ze strumieniami, w jakich język C++ każe nam umieszczać przetwarzanie plików?
Zbyt oczywistym problemem jest usunięcie komentarzy, żeby nie było do tego właściwszego narzędzia, w tak mocarnym języku.

Cóż natura nie znosi próżni, jak mówią, tak i społeczność użytkowników C++ nie pozostaje bierna wobec wyzwań, jakie stawia przed nimi rozwój języka.

Atrakcyjną infrastrukturę przetwarzania strumieni oferuje biblioteka boost::iostreams nadając nowy wyraz koncepcjom strumieni w kontekście współpracy z biblioteką standardową oraz dokonuje przeniesienia w świat współczesnych pojęć C++ dotychczasowego modus operandi na strumieniowym I/O, szczególnie w zakresie posługiwania się nieformatowanym wejściem - wyjściem.

Nie chcę tu wszystkiego opisywać, zachęcam do zapoznania się ze stroną domową biblioteki, tym niemniej wystarczy wspomnieć o kilku podstawowych problemach, których wystąpienie powinno skierować w stronę jej użycia.

Wszelkie przekierowania, z różnych źródeł do różnych ujść stają się dzięki pojęciowemu rusztowaniu biblioteki iostreams, możliwe wcześniej, staje się teraz przyjemne, proste i pełne wyrazu (pisząc źródło czy ujście mam na myśli na przykład kontenery STL, elementy GUI, tablice, dysk, cokolwiek).

Kapsułkowanie kodu rodem z C, używającego nieformatowanych funkcji I/O, który lepiej niż karzące za abstrakcję iteratory pozwoli przetworzyć dane płynące strumieniem w sytuacjach takich jak chociażby zamiana ciągów znaków/bajtów w strumieniu, czy też przetwarzanie wielu znaków naraz znajdują w iostreams swoje właściwe miejsce, oszczędza nam, bowiem ta biblioteka tworzenia nowych strumieni od podstaw, tworząc elastyczne struktury, do których nasza logika przetwarzania pasuje jak ulał.

Problem usunięcia komentarzy przedstawiony na początku z powodzeniem można rozwiązać stosując filtry zawarte w omawianej bibliotece, a w szczególności filtr, który można wygenerować na podstawie automatu skończonego, wyrażonego za pomocą biblioteki MPL.

Funkcja main zyskuje wówczas prostą, ale jakże wyrazistą formę:
i
nt main (void) 
{ 
// uncommenting_fsm <<< MPL state machine 
 
  typedef io::finite_state_filter<uncommenting_fsm> filter; 
 
  io::filtering_istream in; 
  in.push(filter()); 
  in.push(io::file_source("wejscie.txt")); 
 
  ofstream out("wyjscie.txt"); 
 
  in >> noskipws; 
 
  copy(istream_iterator<char>(in),istream_iterator<char>(), 
       ostream_iterator<char>(out)); 
 
  return 0; 
} 

Czy trzeba tu coś omawiać? Sam automat uncommentng_fsm podany jest jako przykład na stronie domowej projektu.
W swoim kodzie zmieniłem kilka jego linijek tak, aby usuwał również komentarze typu // … \n, co pozostawiam do wypróbowania zaciekawionym użytkownikom.
Dodam tylko, że nie wymaga to nawet znajomości biblioteki MPL, do zaznajomienia się, z którą jednak gorąco zachęcam!

Zły iterator, dobre iostreams ?

Na koniec, by nie być gołosłownym w chwaleniu biblioteki iostreams, małe porównanie. Zajmiemy się usunięciem komentarzy typu # … \n, co jest możliwe również za pomocą odpowiedniego predykatu i algorytmu STL, by zobaczyć czy coś tracimy stosując iostreams oraz, kolejno iostreams z MPL.

Pierwszy sposób z wykorzystaniem std::remove_copy_if oraz odpowiedniego predykatu:

Predykat:
struct rm_shell_cmts 
{ 
enum state {out_of_cmt, cmt}; 
static state _state ; 
 
 rm_shell_cmts() 
 { 
  _state = out_of_cmt;
 } 
 
 bool operator()(char c) 
 { 
  if (c == '#') _state = cmt;
  if(c == '\n') _state = out_of_cmt; 
  return (_state == cmt ) ? true : false;
 }
}; 
rm_shell_cmts::state rm_shell_cmts::_state;

Funkcja main:

int main (int argc, char ** argv) 
{ 
 
   if (argc < 3) return 1; 
 
   ofstream strOUT (argv[1]); 
   ifstream strIN (argv[2]); 
 
   strIN >> noskipws; 
 
   remove_copy_if(istream_iterator<char>(strIN), istream_iterator<char>(),   
                  ostream_iterator<char>(strOUT), rm_shell_cmts() ); 
 
   return 0; 
}

Drugi sposób ma wykorzystywać filtr wyjściowy biblioteki iostreams, któego implementacja znajduje się na stronie projektu.
int main(int argc, char** argv) 
{ 
   std::ifstream in ("wejscie.txt"); 
 
   filtering_ostream out;   
   out.push(shell_comments_output_filter()); 
   out.push(file_sink("wyjscie.txt")); 
 
   in >> noskipws; 
 
   out << in.rdbuf(); 
 
   return 0; 
} 

W trzeciej wersji generujemy filtr z automatu zapisanego przy pomocy MPL. Podaję implementację FSM:

struct shell_fsm : public finite_state_machine<shell_fsm> 
{ 
BOOST_IOSTREAMS_FSM(shell_fsm) 
typedef shell_fsm self; 
 
static const int no_comment = initial_state; 
static const int comment = no_comment + 1; 
 
typedef boost::mpl::vector< 
 
              row<no_comment, is<'#'>,  comment,    &self::skip>, 
              row<no_comment, is_any,   no_comment, &self::push>, 
              row<comment,    is<'\n'>, no_comment, &self::push>, 
              row<comment,    is_any,   comment,    &self::skip> 
 
              > transition_table; 
}; 


Użycie programu analizującego wydajność kodu daje do myślenia. W pierwszym z rozwiązań największym obciążeniem są iteratory, które, jak się wcześniej wyraziłem, karzą za abstrakcję (wywołanie funkcji) i to bardzo drogo.

Pierwsza wersja działając na dużym pliku, u mnie wykonuje się w średnio 78 sek., druga, w 18 sek. Obie wykorzystują procesor w ok. 50% przez cały czas przetwarzania (maksymalne jego wykorzystanie ograniczają oczywiście przeprowadzane przez program operacje I/O).

Mogłoby to nasunąć fałszywy wniosek, że wystarczy zrezygnować z iteratorów na rzecz rdbuf(), aby otrzymać wysokowydajne rozwiązanie. Otóż niestety nie można pominąć tu konstrukcji samego filtra. Wersja z filtrem wygenerowanym na bazie automatu MPL wykonuje się średnio w 165 sek!

Dodać jednak należy, że finie_state_filters, nie wchodzą jeszcze oficjalnie w skład biblioteki. Być może powstanie wydajniejsze rozwiązanie niż obecny, prowizoryczny plik finie_state_filter.hpp, pozwalający na generowanie filtrów, który nie jest, powtórzmy oficjalną częścią iostreams.

Niestety na dokładniejsze analizy związane z wydajnością poszczególnych rozwiązań, a zatem i wyciągnięcie poważniejszych wniosków nie ma już miejsca w tym tekście.

Nie można jednak pozostawić powyższych kilku zdań bez komentarza, że ze względu na fakt różnego charakteru poszczególnych rozwiązań należałoby przeprowadzić badanie wydajności czasowej w wielu aspektach zmieniając w każdej z opcji różne jej fragmenty jak i odnieść się do ich konkretnej architektury biorąc pod lupę określony ciąg instrukcji związanych z przetwarzaniem pojedynczego znaku.


Warto na koniec wspomnieć, że w bibliotece strumieniowej istnieje szkielet dla podobnych rozwiązań do tych, które przedstawiono w tekście (używających nieformatujących funkcji I/O), jednak nie ma on tak przyjaznego zestawu pojęć, jaki daje iostreams.

To pozwala wysnuć ogólną konkluzję, że wspomniana biblioteka tworzy atrakcyjną semantykę pracy ze strumieniami, oferując dobry poziom abstrakcji bez uciekania się do kosztownych koncepcji, a rozszerzając tym samym standardową bibliotekę strumieni, daje programistom C++ do ręki kolejną potężną broń w zmaganiach z ich problemami.


Zapraszam do popularyzacji nowoczesnych metod programowania w C++ >>> pierwotna wersja artykułu pojawiłą sie na mojej stronie: www.turek3j.aspnet.pl

2 komentarze

turek3j 2010-03-12 16:02

i giytara - jest w kategorii z "normalnym" tytułem - jak sie komuś chce może przebadać sprawę wydajności filtra generowanego z automatu MPL

nav 2010-03-12 15:37

Przydałby się jakiś normalny tytuł i umieszczenie w odpowiedniej kategorii, nie jak teraz na pałę.