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?
0
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
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?
-O2lub-O3na początek żeby były optymalizacje (bez tego nawet nie ma co analizować kodu),-march=nativelub 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.
jemallocczytcmalloc, jeśli na profilu wyjdzie duży narzut na alokację (w tym wypadkustd::stringi wewnętrzne mechanizmystd::unordered_map) -
std::unordered_mapjest 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 wypadkustd::unordered_mapbę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
iostreamjest 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::coutjest raczej wolne, lepiej użyć czegoś innego jakprintfalbofmt::print. A jak chcesz używaćiostreamto 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ć.iostreamsczęsto używają (nie wiem jak jest w tym wypadku)std::localedo 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ą
lseeki 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;
}
}