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;
  }
}

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