pytanie o wydajność CPU w kodzie c++

0

mam pytanie odnośnie krótkiego programu w C++ i sposobu użycia całego CPU.
Na przykład mamy krótki program który pobiera jako argument nazwę z pliku i program ten będzie zczytywał ilość unikalnych słów w tym pliku, np: "kot pies pies las" to wynik będzie 3 (bo są 3 unikalne słowa). Nie chodzi mi tutaj o sam algorytm i kod programu ale jak najlepiej napisać kod aby maksymalnie wykorzystać moc procesora gdyby plik miał np 10 Gb i był olbrzymi?

10

Jeśli plik będzie olbrzymi, niemal na sto procent wąskim gardłem będzie dysk, a nie procesor, więc nie ma czym się przejmować :-)

Zastosuj hashset/btreeset i będzie śmigać.

0
Patryk27 napisał(a):

Jeśli plik będzie olbrzymi, niemal na sto procent wąskim gardłem będzie dysk, a nie procesor, więc nie ma czym się przejmować :-)

Zastosuj hashset/btreeset i będzie śmigać.

ale mi chodzi jak wykorzystać CPU maksymalnie - tylko o to mi chodzi - i nie jest to jakieś realne zadanie ale bardziej takie własnie zeby się nauczyć

8

Nie da się wykorzystać CPU maksymalnie w sytuacji, gdy to nie ono jest wąskim gardłem.

Wyobraź sobie, że Ty jesteś CPU - masz przed sobą kartkę papieru (udającą RAM), a dysk twardy udaje Twój znajomy dyktujący Ci na głos słowa wśród których masz znaleźć duplikaty.

No i teraz tak: jeśli Twój znajomy dyktuje jedno słowo na minutę, w jaki sposób możesz maksymalnie wykorzystać swój czas? Chyba jedynie robiąc coś innego poza słuchaniem tego znajomego przez każde 59 sekund :-)

0

@Patryk27

No to pomiń wczytywanie pliku i nadal możesz napisać wiele różnych algorytmów na przeprocesowanie tego.

1

A gdyby to były liczby 100 GB pliku vs 8 GB RAM ... użyłbym jakiejś z szybkich baz key-value (berkeley, kyoto cabinet), czasem zwane mapami z backendem na dysk.

(Ale w tym wątku ta rada mało wnosi - jak koledzy pisali)

0

To jest kod programu:

#include <iostream>
#include <bits/stdc++.h>
int main(int argc, char** argv)
{
  std::unordered_map<std::string, unsigned> dict;
  std::fstream file;
  std::string word;
  file.open(std::string(argv[1]).c_str());
  while (file >> word) ++dict[word];
  for (auto x: dict)std::cout << x.first << " " << x.second << '\n';
}

program uruchamiamy:

./a.out data.txt

a plik data.txt to na przykład:

smok tata mama smok

pytanie brzmi jak wykorzystać dostępne zasoby CPU gdyby wyrazów były miliony a sam plik miał pare giga . Zakładamy, że mamy dość pamięci żeby pomieścić wszystkie wyrazy w wybranych strukturach danych w pamięci i się tym nie przejmujemy

6

Generalnie optymalizacje robi się tak, że piszesz program, który robi to co ma robić (benchmark). Taki program możesz analizować z innymi alternatywami albo różnymi profilerami np. https://perf.wiki.kernel.org/index.php/Tutorial#Source_level_analysis_with_perf_annotate.

Tak czy owak widzę tutaj dużo problemów, które mogą mocno wpływać na wydajność:

  • używasz flag kompilacji? -O2 lub -O3 na początek żeby były optymalizacje (bez tego nawet nie ma co analizować kodu), -march=native lub wybrana przez ciebie architektura żeby kompilator mógł użyć instrukcji z nowszych procesorów. Następnie LTO, dla hardkorów jest jeszcze PGO
  • można spróbować użyć innego alokatora jak np. jemalloc czy tcmalloc, jeśli na profilu wyjdzie duży narzut na alokację (w tym wypadku std::string i wewnętrzne mechanizmy std::unordered_map)
  • std::unordered_map jest zazwyczaj wolną kolekcją, bo jest stara i niereformowalna. Warto spróbować z alternatyw np. https://abseil.io/docs/cpp/guides/container (możliwe, że w tym wypadku std::unordered_map będzie się lepiej zachowywać w co wątpię)
  • mając taką hashmape warto użyć dict.reserve() jeśli wiemy ile tych słów będziemy mieli
  • całe iostream jest wolne, a w sposób jaki używasz (tj. file >> word) to już w ogóle. Generalnie im mniej wywołań funkcji IO tym lepiej, dlatego używa się buforów
  • std::cout jest raczej wolne, lepiej użyć czegoś innego jak printf albo fmt::print. A jak chcesz używać iostream to koniecznie wywołaj tą funkcję https://en.cppreference.com/w/cpp/io/ios_base/sync_with_stdio
  • zamiast polegać na iostreams żeby podzielić tekst na słowa lepiej załadować dużą porcję tekstu i samemu to zrobić. iostreams często używają (nie wiem jak jest w tym wypadku) std::locale do sprawdzenia np. czy coś jest spacją czynie a taki kod potrafi być bottleneckiem (widziałem to nie raz)
  • popularną metodą do bardzo wydajnego czytania plików jest mmap (nie wiem jak to działa na windowsie). W skrócie to mówimy kernelowi, że plik ma być załadowany do pamięci i tyle, w tle dzieją się czary, które ładują plik w zależności od tego którą część pliku czytasz
  • to już trochę czarna magia, ale gdzieś czytałem artykuł, że jest jakieś API do czytania z dysków SSD i podobno działa lepiej niż buforowanie + jest mniejsze zużycie pamięci

Jeszcze co do wykorzystania rdzeni: najlepiej podzielić plik na tyle części, ile masz rdzeni. Każdy plik miałby własny dict, jak już wszystkie rdzenie skończą swoją pracę to trzeba jeszcze zrobić wielkie łączenie wszystkich słowników tak, żeby ostatecznie mieć jeden

0
slsy napisał(a):

Jeszcze co do wykorzystania rdzeni: najlepiej podzielić plik na tyle części, ile masz rdzeni. Każdy plik miałby własny dict, jak już wszystkie rdzenie skończą swoją pracę to trzeba jeszcze zrobić wielkie łączenie wszystkich słowników tak, żeby ostatecznie mieć jeden

z tego wszystkiego chodzi mi tylko i wyłącznie o to , jak to najlepiej zaimplementować. Na przykład spróbować wydzielić wątek czytający plik. Drugi wątek obliczałby hashe stringow i updatował mapę. Klasyczne zastosowanie wzorca producent-konsument

2
dixieman napisał(a):

z tego wszystkiego chodzi mi tylko i wyłącznie o to , jak to najlepiej zaimplementować

Szukaj terminu data paralelism. Są dwie szkoły: albo klepiesz wszystko z palca, albo używasz biblioteki, których zadaniem jest wykorzystywanie wielu rdzeni w celu obliczeń np. TBB albo OpenMP.

W pierwszym przypadku wyglądałoby to tak:

  • sprawdzasz ile masz rdzeni do użycia np. https://en.cppreference.com/w/cpp/thread/thread/hardware_concurrency
  • otwierasz plik, sprawdzasz długość
  • odpalasz N wątków, każdy otwiera plik, za pomocą lseek i matematyki liczysz gdzie dany thread ma zacząć pracę i gdzie ma zakończyć
  • wynikiem operacji z wątku jest hash mapa, może to wyglądać tak
auto const N =  std::thread::hardware_concurrency();

using dict = std::unordered_map<std::string, unsigned>;
std::vector<dict> results(N);

std::vector<std::thread> threads;
for (int i = 0; i < N; ++i) {
  thread.emplace_back([i]{
    dict d;
    // tutaj algorytm
    results[i] = dict
  );
}

for (auto& t: threads) t.join()

dict result;
for (auto const& d: results) {
  for(auto const& [k, v]: d) {
    result[k]+=v;
  }
}
0
slsy napisał(a):
// tutaj algorytm

problem w tym jak podzielić czytanie z pliku - o ten algorytm właśnie chodzi

0
dixieman napisał(a):
slsy napisał(a):
// tutaj algorytm

problem w tym jak podzielić czytanie z pliku - o ten algorytm właśnie chodzi

Królu, w geometrii nie ma ścieżki specjalnej dla królów.

jest niemal pewne, ze nie ma magicznego algorytmu na skróty do czytania pliku tekstowego. Co byś nie wymyślił, albo nie otrzymasz zysku, albo wleziesz na kłopoty (czytanie blokami 1024 - a twój "pies" jest na granicy bloku).
Schody się robią bardziej strome, jak to są polskie słowa i np unikod.

Owszem, informatyka zna wiele rozwiązań dla plików binarnych POSIADAJĄCYH STRUKTURĘ, np taka drobna branża jak bazy danych, ale to zupełnie inna opowieść.

0
dixieman napisał(a):
slsy napisał(a):

Jeszcze co do wykorzystania rdzeni: najlepiej podzielić plik na tyle części, ile masz rdzeni. Każdy plik miałby własny dict, jak już wszystkie rdzenie skończą swoją pracę to trzeba jeszcze zrobić wielkie łączenie wszystkich słowników tak, żeby ostatecznie mieć jeden

z tego wszystkiego chodzi mi tylko i wyłącznie o to , jak to najlepiej zaimplementować. Na przykład spróbować wydzielić wątek czytający plik. Drugi wątek obliczałby hashe stringow i updatował mapę. Klasyczne zastosowanie wzorca producent-konsument

Ale jesteś uparty.
Cały czas wszyscy ci piszą, że to wąsewskie gardło decyduje co warto optymalizować. W tym wypadku optymalizować należy operacje IO.
CPU będzie czekać na dane do przetworzenia, więc nie ma tu nic do optymalizowania z punktu widzenia użycia CPU.
Wciskanie tu wątków tylko pogorszy sprawę, bo synchronizacja coś kosztuje, a tu nie ma nic do wykonywania równolegle.

Jako, że korzystasz ze standardowego wyjścia, to należy zrobić std::ios::sync_with_stdio(fasle);:

#include <iostream>
#include <unordered_map>
#include <unordered_map>

int main(int argc, char** argv)
{
  std::ios::sync_with_stdio(fasle);
  std::cin.tie(nullptr);
  
  std::unordered_map<std::string, unsigned> dict;
  std::fstream file;
  std::string word;
  file.open(argv[1]);
  
  while (file >> word) ++dict[word];
  
  for (auto x: dict) 
    std::cout << x.first << " " << x.second << '\n';
}

Jest jeszcze miejsce na optymalizowanie operacji IO, ale to już wymaga użycia API specyficznego dla danej platformy.

0
auto const N=thread::hardware_concurrency();
ifstream in(filename,ios::ate|ios::binary);
auto filesize=in.tellg(),prev=0;
for(int i=1;i<=N;++i)
{
  auto pos=i*filesize/N;
  in.clear();
  in.seekg(pos,ios::beg);
  while((in)&&(in.get()!=' ')) ++pos;
  // wypada sprawdzić czy przypadkiem pos nie jest mniejszy niż prev.
  cout<<i<<": "<<prev<<" - "<<pos<<endl;
  prev=pos;
}
cout<<N<<": "<<<<endl;
0
MarekR22 napisał(a):

Ale jesteś uparty.

ale jesteś uparty :) po raz kolejny piszę, że nie chodzi tu o optymalizację programu ale o poćwiczenie z wielowątkowości czy pracę na wielu procesach

3

W takm razie napisz sobie np. raytracer - nie dość, że da ciekawsze efekty, to jeszcze ślicznie się skaluje :-)

0

Możesz użyć memory file mapping (aczkolwiek ma ono ograniczenia co do rozmiaru pliku i nie zawsze będzie szybciej - tu musisz już przejrzeć dokumentację). Później korzystasz z tego, jak z normalnego wskaźnika i mozesz każdemu wątkowi przydzielić odpowiedni offset. Samą obróbkę danych można już bez problemu zrównoleglić i masz wtedy dobre obciążenie procesora.
Btw. Założyłem, że będziesz tylko czytać z pliku. Pisanie do niego wymaga już odpowiedniej synchronizacji.

1

Najlepiej nie wymyślać wyimaginowanych problemów tylko mierzyć się z istniejącymi

W moim przypadku gdy miałem 300 plików x 2GB (jedna porcja danych) i musiałem z tego wyliczyć "coś" w miarę szybko (poniżej 10minut) to trochę trwało dojście do optymalnego rozwiązania. Najwiecej pomogło dodanie zrobienie RAJD 0 z czterech dysków ( rezygnacja z mechanicznych dysków) , zablokowanie równoległego dostępu do dysku dla wielu watków.

1 użytkowników online, w tym zalogowanych: 0, gości: 1