Ano ang nakakaapekto sa bilis ng mga programang C++ at kung paano ito makakamit sa isang mataas na antas ng code? Sinagot ng nangungunang developer ng library ng CatBoost na si Evgeniy Petrov ang mga tanong na ito gamit ang mga halimbawa at ilustrasyon mula sa kanyang karanasan sa pagtatrabaho sa CatBoost para sa x86_64.
Ulat sa video
- Kamusta kayong lahat. Ino-optimize ko ang CatBoost machine learning library para sa CPU. Ang pangunahing bahagi ng aming aklatan ay nakasulat sa C++. Ngayon sasabihin ko sa iyo kung anong mga simpleng paraan ang nakakamit natin ng bilis.
Ang bilis ng mga kalkulasyon ay binubuo ng dalawang bahagi. Ang unang bahagi ay ang algorithm. Kung magkakamali kami sa pagpili ng algorithm, hindi namin ito magagawang mabilis. Ang ikalawang bahagi ay kung gaano ka-optimize ang aming algorithm para sa computing system na mayroon kami, kasama ang performance at throughput nito.
Ang palitan ng data at mga kalkulasyon ay kailangang isaalang-alang nang hiwalay dahil sa malaking pagkakaiba sa kanilang bilis. Kung isasaalang-alang natin ang bilis ng memorya bilang bilis ng isang pedestrian, kung gayon ang bilis ng pag-compute ay humigit-kumulang sa bilis ng cruising ng isang pampasaherong eroplano.
Upang maayos ang pagkakaibang ito, ang arkitektura ay may ilang mga antas ng pag-cache. Ang pinakamabilis at pinakamaliit ay L1 cache. Pagkatapos ay mayroong mas malaki at mas mabagal na pangalawang antas na cache. At mayroong isang napakalaking cache, na maaaring sampu-sampung megabytes, isang third-level na cache, ngunit ito ang pinakamabagal.
Dahil sa iba't ibang bilis ng pagpapalitan ng data ng mga pagkalkula, ang computational code ay nahahati sa dalawang klase. Ang isang klase ay limitado ng bandwidth, iyon ay, ang bilis ng pagpapalitan ng data. Ang pangalawang klase ay limitado sa bilis ng processor. Ang hangganan sa pagitan ng mga ito ay itinakda depende sa bilang ng mga operasyon na isinagawa gamit ang isang byte ng data. Ito ay karaniwang isang code-specific constant.
Karamihan sa mabigat na computational code ay naisulat sa mahabang panahon, napakahusay na na-optimize, at mayroong isang malaking bilang ng mga aklatan, kaya makatuwiran, kung makakita ka ng mabigat na pagkalkula sa iyong code, upang maghanap ng isang aklatan na magagawa para sa iyo ito.
Sa natitira, hindi magagawa ng mga compiler ang lahat, dahil ang isang limitadong porsyento ng mga mapagkukunan ay ginugol sa kanilang pag-unlad. Alin sa kanila ang umuunlad nang higit o hindi gaanong aktibo ngayon, ibig sabihin, sinusuportahan nila ang mga pamantayan at sinusubukang subaybayan ang mga ito? Ito ay isang frontend EDG na ginagamit sa iba't ibang derivatives, tulad ng Intel compiler; LLVM; GNU at frontend na Microsoft.
Dahil kakaunti ang mga ito, sinusuportahan lamang ng mga compiler ang mga pattern ng kontrol sa dalas at mga dependency ng data. Kung titingnan natin ang kontrol, ito ay mga linear na seksyon at simpleng mga siklo, iyon ay, isang pagkakasunud-sunod ng mga tagubilin at pag-uulit. Natututo sila ng mga dependency ng dalas mula sa data mula sa pagbabawas, kapag, sabihin nating, magsama tayo ng maraming elemento sa isa, mag-collapse at magsagawa ng mga pagpapatakbo ng elemento-by-element sa isa o higit pang mga array.
Ano ang natitira para sa mga developer? Ito ay halos nahahati sa apat na bahagi. Ang una ay ang arkitektura ng application ay hindi maaaring makabuo nito para sa amin.
Ang parallelization ay isa ring mahirap na bagay para sa mga compiler. Paggawa gamit ang memorya - dahil ito ay talagang mahirap: kailangan mong isaalang-alang ang arkitektura, at parallelization, at lahat ng magkasama. Bilang karagdagan, ang mga compiler ay hindi alam kung paano maayos na suriin ang kalidad ng pag-optimize, kung gaano kabilis ang code. Kami, ang mga developer, ay kailangan ding gawin ito, gumawa ng desisyon - upang mag-optimize pa o huminto.
Sa panig ng arkitektura, titingnan natin ang amortisasyon ng overhead, ang mga virtual na tawag, na pinagbatayan ng maraming arkitektura.
Iwanan natin ang parallelization sa labas ng equation. Tungkol sa paggamit ng memorya: ito rin, sa isang kahulugan, ang pamumura at tamang trabaho sa data, ang kanilang tamang pagkakalagay sa memorya. Sa mga tuntunin ng pagsusuri ng kahusayan, pag-uusapan natin ang tungkol sa pag-profile at kung paano maghanap ng mga bottleneck sa code.
Ang paggamit ng mga interface at abstract na uri ng data ay isa sa mga pangunahing diskarte sa disenyo. Tingnan natin ang katulad na computational code mula sa machine learning. Isa itong conditional code na nag-a-update ng forecast gamit ang isang gradient na paraan.
Kung titingin tayo ng kaunti sa loob at susubukang unawain kung ano ang nangyayari sa loob, mayroon tayong interface ng IDerCalcer para sa pagkalkula ng mga derivatives ng function ng pagkawala, at isang function na nagbabago sa forecast (aming hula) alinsunod sa gradient ng loss function.
Sa kanang bahagi ng slide makikita mo kung ano ang ibig sabihin nito para sa two-dimensional na case. At sa machine learning, ang sukat ng forecast ay hindi dalawa o tatlo, ngunit milyon-milyong, sampu-sampung milyong elemento. Tingnan natin kung gaano kahusay ang code na ito para sa isang vector na humigit-kumulang 10 milyong elemento.
Kunin natin ang standard deviation bilang target na function at sukatin kung paano ito gumagana, gaano katagal bago ilipat ang forecast na ito. Ang derivative ng layuning function na ito ay ipinapakita sa slide. Ang oras ng pagpapatakbo sa isang conditional machine, na pagkatapos ay nananatiling maayos, ay 40 ms.
Subukan nating maunawaan kung ano ang mali dito. Ang unang bagay na nakakaakit ng pansin ay ang mga virtual na tawag. Kung titingnan mo ang profiler, makikita mo na depende sa bilang ng mga parameter, ito ay mga lima hanggang sampung mga tagubilin. At kung, tulad ng sa aming kaso, ang pagkalkula ng derivative mismo ay dalawang operasyon ng aritmetika, kung gayon madali itong maging isang makabuluhang overhead. Para sa isang malaking katawan kapag kinakalkula ang mga derivatives ito ay tinatayang. Para sa isang maikling katawan na kinakalkula ang derivative - sabihin, hindi kahit 500 mga tagubilin, ngunit 20, 50 o mas kaunti pa - ito ay magiging isang makabuluhang porsyento sa oras. Anong gagawin? Subukan nating i-amortize ang virtual function na tawag sa pamamagitan ng pagpapalit ng interface.
Sa una, kinakalkula namin ang mga derivatives, para sa bawat elemento ng vector nang hiwalay. Lumipat tayo mula sa pagpoproseso ng bawat elemento patungo sa pagproseso ng vector. Kumuha tayo ng isang karaniwang template ng C++ na nagbibigay-daan sa iyong magtrabaho kasama ang isang view sa isang vector. O, kung hindi sinusuportahan ng iyong compiler ang pinakabagong pamantayan, maaari kang gumamit ng simpleng homemade class na nag-iimbak ng pointer sa data at laki. Paano magbabago ang code? Maiiwan tayo ng isang tawag na nagkalkula ng mga derivative, at pagkatapos ay kailangan nating magdagdag ng loop na talagang mag-a-update ng forecast.
Bilang karagdagan sa pagdaragdag ng isang cycle, kakailanganin din nating tingnan ang data sa pangalawang pagkakataon, iyon ay, basahin ang forecast vector mismo at ang gradient vector na kinakalkula namin sa pangalawang pagkakataon.
Subukan natin itong muli sa parehong makina at makita na ito ay naging mas malala, may nangyaring mali. Alamin natin kung ano ang nangyari sa code.
Walang kwenta ang paghihinala sa cycle ng anuman, dahil ito ang eksaktong parehong frequency pattern na kinikilala at na-optimize ng mga compiler. Ang bilang ng mga operasyon sa bawat elemento ng data doon ay mas mababa kaysa sa halaga ng isang virtual na tawag.
Ngunit ang paglikha ng isang malaking vector at paulit-ulit na dumadaan dito - dito ka dapat maghinala ng isang problema. Upang maunawaan kung bakit ito masama at bumabagal, kailangan mong isipin kung ano ang nangyayari sa memorya kapag tumatakbo ang code na nakikita natin sa slide sa kanan.
Kapag ang vector ng mga derivative ay kinakalkula, ito ay darating sa isang loop na nagbabago sa forecast. Bago ang cycle na ito, isang napakaliit na bahagi lamang ng data ang mananatili sa mabilis na L1 cache, na tumatakbo sa bilis ng processor. Sa slide ito ay berde sa isang traffic light. Ang natitirang data ay itutulak palabas ng cache patungo sa memorya, at kapag ang cycle ay nagsimulang mag-update ng mga hula, ang data ay kailangang basahin mula sa memorya sa pangalawang pagkakataon. Ngunit para sa amin ito ay gumagana, sa pangkalahatan, napakabagal, sa bilis ng paglalakad.
Kapag nag-update kami ng forecast, hindi namin kailangang basahin ang lahat ng derivatives nang sabay-sabay. Ito ay sapat na upang bilangin ang mga ito sa malalaking pack upang makuha ang mga virtual na tawag. Samakatuwid, makatuwirang hatiin ang pagkalkula ng mga derivative at pag-update ng forecast sa maliliit na bloke at paghaluin ang dalawang pagkilos na ito. Ano ang hahantong dito kung titingnan natin kung saan babasahin ang data?
Ito ay hahantong sa katotohanan na kami ay kukuha ng data sa lahat ng oras, at sa katotohanan na ang data ay mananatili sa L1 cache at hindi magkakaroon ng oras upang pumunta sa mabagal na memorya. At pagkatapos ay kailangan nating maunawaan kung sino ang magsasabi sa amin ng laki ng bloke na ito.
Lohikal na ipagkatiwala ito sa derivative calculator mismo, dahil siya lang ang nakakaalam kung gaano karaming cache ang kailangan niya. Susunod na kailangan nating muling isulat ang loop na tumitingin sa array. Kailangan itong hatiin sa dalawa. Ang panlabas na loop ay dadaan sa mga bloke, at sa loob ay dadaan tayo sa mga elemento ng bloke nang dalawang beses.
Narito ito, panlabas sa mga bloke.
At narito ang panloob para sa mga elemento ng bloke.
Isinasaalang-alang namin na ang huling bloke ay maaaring hindi kumpleto.
Tingnan natin kung ano ang nanggagaling dito. Nakikita namin na nahulaan namin nang tama, naunawaan nang tama kung ano ang nangyayari, at sa halaga ng medyo maliit na pagbabago sa code, binawasan namin ang oras ng pagpapatakbo ng walong porsyento. Pero mas marami pa tayong magagawa. Kailangan nating suriin muli ang ating isinulat. Tingnan ang function na nagkalkula ng mga derivatives para sa amin. Ibinabalik nito sa amin ang isang vector ng mga derivatives na ang mga elemento ay mabagal na ma-access sa mga hindi kanais-nais na sitwasyon.
Mayroong dalawang dahilan dito. Una, paglalagay ng vector sa heap. Malaki ang posibilidad na malilikha at mawawasak ang vector na ito nang maraming beses. Ang pangalawang kawalan sa mga tuntunin ng bilis ay ang bawat oras na makakatanggap kami ng memorya, marahil sa isang bagong address. Ang memorya na ito ay magiging "malamig" mula sa isang punto ng view ng cache, ibig sabihin na bago sumulat dito, ang processor ay magsasagawa ng isang auxiliary read upang simulan ang data sa cache.
Upang ayusin ito, kailangan mong alisin ang paglalaan mula sa loop. Upang gawin ito, kailangan nating baguhin muli ang interface, ihinto ang pagbabalik ng mga vectors at simulan ang pagsusulat ng mga derivatives sa memorya na natatanggap natin mula sa calling code.
Ito ay isang karaniwang pamamaraan - inaalis ang lahat ng manipulasyon na may mga mapagkukunan mula sa mga bottleneck sa computing code. Magdagdag tayo ng isa pang parameter sa CalcDer method, view ng vector kung saan dapat pumunta ang mga derivatives.
Magbabago din ang code sa mga malinaw na paraan. Ang vector ng mga derivative ay magiging isa, sa labas ng lahat ng mga loop, at isang bagong parameter ay idadagdag lamang sa pamamaraan.
Tingnan natin. Lumalabas na nakakuha kami ng humigit-kumulang walong porsyento na higit pa kumpara sa nakaraang bersyon, at kumpara sa base na bersyon - na 15%.
Malinaw na ang mga pag-optimize ay hindi limitado sa amortisasyon ng mga gastos sa overhead, na may iba pang mga uri ng mga bottleneck.
Upang ilarawan kung paano maghanap ng mga bottleneck, kailangan namin ng isa pang simpleng test code. Halimbawa, kinuha ko ang matrix transpose. Mayroon kaming matrix approx at matrix approxByCol kung saan kailangan naming ilagay ang transposed data. At isang simpleng pugad ng dalawang mga loop. Walang mga virtual na tawag o paglikha ng vector dito. Naglilipat lang ng data. Ang loop ay medyo compiler-friendly.
Sukatin natin kung paano gumagana ang code na ito sa isang medyo malaking matrix at sa isang partikular na makina.
Halimbawa, kinuha ko ang bilang ng mga row na 1000, ang bilang ng mga column ay 100 Ang makina ay isang Intel server, isang core. Ang memorya ay eksakto tulad nito, ito ay mahalaga sa amin, dahil ang lahat ng gumagana na may memorya at bilis ay depende sa bilis ng memorya. Sinukat namin ito at nakakuha ng 000 s. Marami ba o kaunti? Ano ang magagawa natin sa panahong ito?
Pinamamahalaan naming basahin ang 800 megabytes, hindi ito isang transposed matrix, ngunit ang orihinal. At basahin at isulat din ang 1,6 GB, isa na itong transposed matrix. Ang processor ay nagsasagawa ng auxiliary read bago ang pagsulat upang masimulan ang data sa cache.
Kalkulahin natin kung gaano karaming bandwidth ang ginamit natin nang kapaki-pakinabang. Lumalabas na ang throughput ng aming code ay 1,7 GB/s.
Ito ay isang teoretikal na pagkalkula. Susunod, maaari kang gumamit ng isang profiler na maaaring masukat ang bilis ng pagtatrabaho sa memorya. Kinuha ko ang VTune. Tingnan natin kung ano ang kanyang ipinapakita. Nagpapakita ng katulad na figure - 1,8 GB. Sa prinsipyo, sumasang-ayon ito nang mabuti, dahil sa aming pagkalkula ay hindi namin isinasaalang-alang na kailangan naming basahin ang mga address ng hilera at mga address ng haligi. Dagdag pa, ang VTune ay nag-log ng background na aktibidad sa operating system. Samakatuwid, ang aming modelo ay naaayon sa katotohanan.
Upang maunawaan kung marami o kaunti ang 1,7 GB, kailangan nating malaman kung ano ang maximum na bandwidth na magagamit sa atin.
Upang gawin ito, kailangan mong basahin ang mga detalye ng processor. Mayroong isang espesyal na website na ark.intel.com, kung saan maaari mong malaman ang lahat tungkol sa anumang processor. Kung titingnan namin ang aming server, makikita namin na mayroon itong walong mga core at ang pinakamabilis na memorya ng DDR3 na sinusuportahan nito ay may kakayahang maglipat sa humigit-kumulang 60 GB/s isang paraan.
Ngunit dito dapat nating isaalang-alang na gumagamit lamang tayo ng isang core at ang ating memorya ay mas mabagal, iyon ay, kailangan nating sukatin ang mga 60 GB na ito sa ating mga kundisyon sa proporsyon sa bilang ng mga core at dalas ng memorya.
Lumalabas na ang aming code ay maaaring gumamit ng 5,3 GB sa isang paraan. At dahil maaari kang magbasa at sumulat nang magkatulad, sa isip, kung kumopya lang kami ng data mula sa isang lugar patungo sa lugar, makakamit namin ang 10,6. Dahil mayroon kaming dalawang reads at isang write, dapat itong humigit-kumulang 8 GB/s. Naaalala namin na nakakuha kami ng 1,7. Ibig sabihin, halos 20% ang ginamit namin.
Bakit ito nangyayari? Muli kailangan mong maunawaan ang arkitektura. Ang katotohanan ay ang data sa pagitan ng memorya at cache ay inilipat hindi sa mga di-makatwirang packet, ngunit sa eksaktong 64 bytes, hindi hihigit at hindi bababa. Ito ang unang pagsasaalang-alang.
Ang pangalawang pagsasaalang-alang ay ang pagsulat namin ng transposed data hindi sunud-sunod, ngunit random, dahil ang mga hilera ng matrix ay matatagpuan sa memorya sa isang hindi mahuhulaan na paraan.
Lumalabas na bago magsulat ng isang tunay na numero, kailangan nating magbasa ng 64 bytes ng data. Kung tinutukoy natin ang laki ng matrix bilang N, pagkatapos ay sa halip na ang pinakamainam na oras ng pagpapatakbo (N/5,3 + N/10,6), nakukuha natin (8*N/5,3 + N/10,6). Sa isang lugar apat hanggang limang beses na higit pa, na nagpapaliwanag ng 20% na kahusayan na ito.
Ano ang gagawin tungkol dito? Kailangan mong ihinto ang pagsusulat ng data nang paisa-isa at magsimulang magsulat ng pinakamaraming column na magkasya sa isang linya ng cache (64 bytes). Upang gawin ito, hahatiin namin ang loop sa mga column sa isang loop sa mga linya ng cache at isang nested loop sa mga elemento ng cache line.
Narito ang mga ito, mga pag-ulit sa mga linya ng cache.
At narito sila, mga pag-ulit sa loob ng linya ng cache. Dito, para sa pagiging simple, ipinapalagay namin na ang data ay nakahanay sa hangganan ng linya ng cache. Ngayon tingnan natin kung ano ang nangyayari gamit ang VTune.
Nakikita namin na ang resulta ay malapit sa kinakalkula na walong gigabytes bawat segundo - 7,6. Ngunit hindi katotohanan na ang lahat ng 7,6 na ito ay kapaki-pakinabang na gawain. Marahil ang ilan sa kanila ay nasa itaas.
Upang maunawaan kung gaano karaming benepisyo ang natanggap namin, sukatin natin ang oras ng pagpapatakbo pagkatapos ng pag-optimize. Ito ay lumalabas na 0,5 s sa parehong makina. Ang bandwidth dahil sa transposisyon mismo ay naging 4,8 GB/s. Makikita na may reserba pa rin na hindi natin napili, pero sa 20 percent efficiency ay nakakuha tayo ng 60 percent.
Gamit ang profiler malalaman natin kung bakit hindi tayo nakakuha ng 80% o 95%.
Ang katotohanan ay nag-iimbak kami ng mga matrice bilang isang vector ng mga vector, iyon ay, ginagamit namin ang pag-access sa memorya na may dobleng indireksiyon.
Gamit ang VTune, makikita mo kung aling mga tagubilin ang nabuo upang ma-access ang mga elemento ng array. Ang mga tagubilin na nagbabasa ng mga address ng mga column ng transposed matrix ay naka-highlight sa dilaw sa kaliwa. At ito ay, una, mga karagdagang tagubilin, at pangalawa, mga karagdagang paglilipat ng data. Ngunit hindi na tayo mag-o-optimize pa, huminto tayo at mag-summarize.
Ano ang sinabi ko sa iyo ngayon? Ang isang kapaki-pakinabang na tip para sa pagtatrabaho sa computational code ay ang pagproseso sa mga bloke, pag-amortize ng overhead na nauugnay sa mga virtual na tawag, halimbawa. Dagdag pa, dahil sa pagharang, bumubuti ang lokalidad ng data, at nakakakuha kami ng mas mataas na bilis ng pag-access.
Ang pag-alis ng mga alokasyon mula sa mga bottleneck ay ang kanilang amortization. At pinapataas din ang bilis ng pag-access sa pamamagitan ng pag-aayos ng mga pansamantalang buffer sa memorya.
Tungkol sa profiling. Una, ang pag-profile ay isang kapaki-pakinabang na pamamaraan para sa paghahanap ng mga bottleneck "sa pangkalahatan." Pangalawa, pinapayagan kaming suriin ang kahusayan ng code, magpasya kung nasiyahan kami sa bilis o nais na mag-optimize pa, at ipinapakita sa amin kung saan ang direksyon lilipat.
Para sa akin lang yan. Kung gumamit ka ng CatBoost o narinig mo ang tungkol dito sa unang pagkakataon at gusto mong malaman kung ano ito, basahin , bisitahin mo kami sa , sumulat sa . Maraming salamat sa iyong atensyon.
Pinagmulan: www.habr.com
