Kuris yra greitesnis: stekų paskirstymas ar paskirstymas

Šis klausimas gali atrodyti gana paprastas, tačiau tai yra diskusija, su kuria dirbau su kitu kūrėju, su kuriuo dirbau.

Bandžiau sukrauti daiktus, kur galėčiau vietoj krūvos paryškinti juos. Jis kalbėjo su manimi ir stebėjo mano pečių ir komentavo, kad tai nėra būtina, nes jie yra tokie patys.

Visada turėjau įspūdį, kad kamino augimas buvo pastovus, o krūvelių pasiskirstymas priklausė nuo dabartinio krūvos sudėtingumo tiek paskirstymo (tinkamo dydžio skylės suradimo), tiek atrankos (skylių sulankstymo sumažinimui, nes daugelis standartinių bibliotekų diegimų reikalauja) laikas, kai tai daroma ištrynimo metu, jei neklystu).

Man atrodo, kad tai yra labai priklausoma nuo kompiliatoriaus. Šiam projektui, ypač, naudoju „ Metrowerks“ kompiliatorių PPC . Šis derinys būtų naudingiausias, bet apskritai GCC ir MSVC ++ atveju, kas tai yra? Ar krūvos pasiskirstymas nėra toks didelis, kaip kamino paskirstymas? Ar nėra skirtumo? Arba tai yra skirtumas, todėl minutė tampa beprasmis mikroprocesoriais.

426
02 окт. Adomas yra nustatytas 02 okt. 2008-10-02 09:06 '08 at 9:06 AM 2008-10-02 09:06
@ 23 atsakymai

Kamino paskirstymas yra daug greitesnis, nes viskas, ką jis iš tikrųjų daro, yra perkelti stekų žymeklį. Naudojant atminties baseinus, galite gauti palyginamą našumą iš krūvos paskirstymo, tačiau tai yra dėl mažo sudėtingumo ir galvos skausmo.

Be to, krūva prieš krūvą ne tik atsižvelgia į našumą; jis taip pat daug sako apie numatomą daiktų gyvenimą.

426
02 окт. atsakymas duotas Torbjörn Gyllebring 02 okt. 2008-10-02 09:09 '08 at 9:09 2008-10-02 09:09

Srautas yra daug greičiau. Daugelyje architektūrų jis tiesiog naudoja tik vieną nurodymą, daugeliu atvejų, pavyzdžiui. x86:

 sub esp, 0x10 

(Tai perkelia kamino rodyklę 0x10 baitų ir tokiu būdu "paskirsto" šiuos baitus naudoti kintamąjį.)

border=0

Žinoma, kamino dydis yra labai, labai ribotas, nes jūs greitai sužinosite, ar netinkamai naudojate kamino paskirstymą arba bandote atlikti rekursą: -)

Be to, yra nedidelė priežastis optimizuoti kodo našumą, kurio nereikia patikrinti, pvz., Naudojant profiliavimą. „Išankstinis optimizavimas“ dažnai sukelia daugiau problemų nei kainuoja.

Mano nykščio taisyklė yra: jei žinau, kad kompiliavimo metu reikės tam tikrų duomenų, ir tai yra kelis šimtus baitų dydžio, aš jį įdėsiu į kamino. Priešingu atveju, aš jį pakirsiu.

145
02 окт. atsakymas, kurį pateikė Dan Lenski 02 spalis 2008-10-02 09:16 '08 at 9:16 AM 2008-10-02 09:16

Sąžiningai, yra nereikšminga parašyti programą, skirtą lyginti našumą:

 #include <ctime> #include <iostream> namespace { class empty { }; // even empty classes take up 1 byte of space, minimum } int main() { std::clock_t start = std::clock(); for (int i = 0; i < 100000; ++i) empty e; std::clock_t duration = std::clock() - start; std::cout << "stack allocation took " << duration << " clock ticks\n"; start = std::clock(); for (int i = 0; i < 100000; ++i) { empty* e = new empty; delete e; }; duration = std::clock() - start; std::cout << "heap allocation took " << duration << " clock ticks\n"; } 

Jis sakė, kad kvailas nuoseklumas yra mažų protų hobgoblinas . Matyt, kompiliatoriaus optimizavimas yra daugelio programuotojų sąmoningas protas. Ši diskusija buvo atsakymo centre, tačiau žmonės, atrodo, negali dirbti, kad jį perskaitytų, todėl aš čia noriu išvengti klausimų, kuriuos jau atsakiau.

Optimalus kompiliatorius gali pastebėti, kad šis kodas nieko nedaro ir gali jį optimizuoti. Tai yra optimizatoriaus užduotis atlikti tokius dalykus, o kova su optimizatoriumi yra beprotiška komisija.

Norėčiau rekomenduoti šį kodą sujungti su optimizavimu, nes nėra jokio gero būdo apgauti kiekvieną optimizatorių, kuris šiuo metu naudojamas ar bus naudojamas ateityje.

Kiekvienas, kuris įjungia optimizavimo priemonę ir skundžiasi dėl kovos su juo, turėtų būti veikiamas viešo gėdos.

Jei man būtų rūpi nanosekundės tikslumas, nenorėčiau naudoti std::clock() . Jei norėjau skelbti rezultatus kaip doktorantūros disertaciją, apie tai norėčiau labai daug nuveikti, o tikriausiai palyginčiau GCC, Tendra / Ten15, LLVM, Watcom, Borland, Visual C ++, Digital Mars, ICC ir kt. kompiliatoriai Bet kokiu atveju, krūvos paskirstymas trunka šimtus kartų ilgiau nei kamino paskirstymas, ir nematau nieko naudingo toliau tiriant šią problemą.

Optimizatoriaus užduotis - atsikratyti kodo, kurį bandau. Nematau jokios priežasties pasakyti, kad optimizatorius pradeda veikti, ir tada bandykite apgauti optimizatorių be optimizavimo. Bet jei tai padariau, norėčiau padaryti vieną ar daugiau iš šių veiksmų:

  • Pridėti duomenų elementą, kurį norite empty ir prieiti prie šio duomenų elemento kilpoje; bet jei aš visuomet perskaitysiu iš duomenų elemento, optimizatorius gali atlikti nuolatinę sulankstymą ir pašalinti kilpą; jei kada nors rašau duomenų nariui, optimizatorius gali praleisti viską, išskyrus naujausią ciklo iteraciją. Be to, klausimas nebuvo „stekų paskirstymas ir prieiga prie duomenų, palyginti su krūvos paskirstymu ir prieiga prie duomenų“.

  • Pripažinkite, kad volatile , bet volatile dažnai volatile neteisingai surenkamas (PDF).

  • Paimkite e Pašto kilpą (ir galbūt priskirkite jį kintamajam, kuris deklaruotas extern ir apibrėžtas kitame faile). Bet net ir tokiu atveju kompiliatorius gali pastebėti, kad - bent jau - ant kamino, e visada bus priskirtas tam pačiam atminties adresui, o tada atliks nuolatinį sulankstymą, kaip nurodyta aukščiau (1). Aš gausiu visas ciklo iteracijas, bet objektas niekada nesiskiria.

Be to, akivaizdu, kad šis testas yra klaidingas, nes matuoja tiek platinimą, tiek išleidimą, o pirminis klausimas nereikalauja išleisti. Žinoma, kintamieji, priskirti kaminai, automatiškai išleidžiami jų teritorijos pabaigoje, todėl nesukeliant delete (1), bus nubrėžti skaičiai (kamino išsiskyrimas įtraukiamas į numerius, kuriuose yra sklypo pasiskirstymas, todėl teisinga vertinti krūvos išleidimą) ir (2) sukelia gana blogą atminties nutekėjimą jei nenorime išsaugoti nuorodos į naują rodyklę ir neskambinti delete po laiko matmenų.

Mano kompiuteryje, naudojant „g ++ 3.4.4“ sistemoje „Windows“, gaunu „0 laikrodžius“, skirtus kamino ir krūvų paskirstymui už mažiau nei 100 000 paskirstymų, ir net tada aš gavau „0 laikrodžių“, kad būtų galima platinti kamino ir „15 laikrodžių“. krūvos paskirstymas. Kai išmatuoju 10.000.000 pasiskirstymą, kamino paskirstymas trunka 31 erkę, o krūvos paskirstymas užima 1562 erkes.


Taip, optimizavimo kompiliatorius gali pagreitinti tuščių objektų kūrimą. Jei suprantu teisingai, jis gali net viršyti visą pirmąjį ciklą. Kai išbėgau iki 10 000 000 stekų paskirstymo iteracijos, užtruko 31 laikrodis, o krūvos paskirstymas užtruko 1562 laikrodžius. Galiu pasakyti, kad, nenurodydama g ++, kad optimizuotų vykdomąjį failą, g ++ neatmetė konstruktorių.


Per pastaruosius metus, kai parašiau, „ngn-wiki.ru“ pirmenybė buvo teikiama našumo optimizavimui. Apskritai manau, kad tai teisinga. Vis dėlto vis dar atrodo kvaila paprašyti kompiliatoriaus optimizuoti kodą, kai tikrai nenorite, kad šis kodas būtų optimizuotas. Man atrodo, kad esu labai panašus į mokėjimą už papildomą automobilių stovėjimo aikštelę, bet atsisakau perduoti raktus. Šiuo konkrečiu atveju nenoriu, kad optimizatorius veiktų.

Naudojant šiek tiek pakeistą standarto versiją (norint kreiptis į galiojantį tašką, kuriame šaltinio programa nieko nepadarė kaskart per ciklą) ir kompiliuojant be optimizavimo, bet susiejant su išleidimo bibliotekomis (norint pasiekti faktinį tašką, kuriuo nenorime įtraukti sulėtėjimą, kurį sukelia privalomosios klaidos bibliotekos):

 #include <cstdio> #include <chrono> namespace { void on_stack() { int i; } void on_heap() { int* i = new int; delete i; } } int main() { auto begin = std::chrono::system_clock::now(); for (int i = 0; i < 1000000000; ++i) on_stack(); auto end = std::chrono::system_clock::now(); std::printf("on_stack took %f seconds\n", std::chrono::duration<double>(end - begin).count()); begin = std::chrono::system_clock::now(); for (int i = 0; i < 1000000000; ++i) on_heap(); end = std::chrono::system_clock::now(); std::printf("on_heap took %f seconds\n", std::chrono::duration<double>(end - begin).count()); return 0; } 

rodomas:

 on_stack took 2.070003 seconds on_heap took 57.980081 seconds 

mano sistemoje rengiant komandinę eilutę cl foo.cc /Od /MT /EHsc .

Jūs negalite sutikti su mano požiūriu, kaip gauti neoptimalų surinkimą. Tai puiku: nedvejodami galite keisti etaloną tiek, kiek norite. Kai įgalinu optimizavimą, gaunu:

 on_stack took 0.000000 seconds on_heap took 51.608723 seconds 

Ne todėl, kad kamino platinimas iš esmės yra akimirksniu, bet todėl, kad bet kuris pusiau patvarus kompiliatorius gali pastebėti, kad on_stack neturi nieko naudingo ir gali būti optimizuotas. Be to, GCC mano „Linux“ nešiojamuoju kompiuteriu pažymi, kad „ on_heap “ nieko nedaro ir optimizuoja:

 on_stack took 0.000003 seconds on_heap took 0.000002 seconds 
 on_stack took 0.000003 seconds on_heap took 0.000002 seconds 
104
02 окт. atsakymą pateikė Max Lybbert 02 okt. 2008-10-02 21:11 '08 at 9:11 pm 2008-10-02 21:11

Įdomu, ką sužinojau apie „Stack“ „Xbox 360“ ksenono procesoriaus krūvos paskirstymas, kuris taip pat gali būti pritaikytas kitoms daugiašalėms sistemoms, yra tai, kad perkrovimas sukelia kritinį skyrių sustabdyti visas kitas šerdis, todėl tai neprieštarauja. Taigi, uždaroje linijoje „Stack“ paskirstymas buvo būdas eiti į fiksuoto dydžio matricas, nes tai neleido stendams.

Tai gali būti dar vienas pagreitis, kad apsvarstytumėte, ar koduojate daugiasmenį / daugiaprocesą, nes kamino paskirstymas bus prieinamas tik branduoliui, naudojant ribotą funkciją, ir tai neturės įtakos kitiems branduoliams / procesoriams.

26
02 марта '09 в 4:55 2009-03-02 04:55 atsakymą pateikė „ Furious Coder“ kovo 02'09 val. 4:55 2009-03-02 04:55

Konkretiems objektų dydžiams, kurie yra labai efektyvūs, galite parašyti specialų krūvos dozatorių. Tačiau bendrasis krūvelių platintojas nėra itin veiksmingas.

Taip pat sutinku su Torbjörn Gyllebring dėl numatomo objektų gyvenimo. Geras taškas!

16
02 окт. Atsakymas, kurį pateikė Chris Jester-Young 02 Oct 2008-10-02 09:08 '08 at 9:08 am 2008-10-02 09:08

Be eksploatacinių pranašumų pagal dydį, palyginti su krūvos paskirstymu, ilgesnės serverio programos yra tinkamesnės kamino paskirstymui. Netgi geriausi valdomi krūvos yra tokie fragmentiški, kad programos našumas blogėja.

6
26 окт. Atsakymas Jay Oct 26 2009-10-26 20:36 '09 ne 20:36 2009-10-26 20:36

Paprastai kamino paskirstymas susideda tik iš kamino žymeklio iš registro. Tai daug daugiau nei krūvos paieška.

Kartais kamino paskirstymui reikia pridėti virtualiosios atminties puslapių. Naujo puslapio pridėjimas prie nulinės atminties nereikalauja skaityti puslapį iš disko, todėl paprastai tai bus kelios tonos greičiau nei ieškant krūvos (ypač jei dalis krūvos taip pat buvo iškrauta). Retoje situacijoje, ir jūs galėtumėte sukurti tokį pavyzdį, pakankamai laisvos vietos tik pasirodo, kad jau yra RAM atmintyje esančios dalies krūva, tačiau naujo puslapio išdavimas kaminai turi palaukti, kol kitas puslapis bus įrašytas į diską. Šioje retoje situacijoje daug greičiau.

5
02 окт. atsakymą pateikia „ Windows“ programuotojas 02 okt. 2008-10-02 09:18 '08 at 9:18 2008-10-02 09:18

Nemanau, kad kamino paskirstymas ir krūvos paskirstymas paprastai yra keičiami. Taip pat tikiuosi, kad abiejų jų atlikimas yra pakankamas bendram naudojimui.

Labai rekomenduoju mažus daiktus, priklausomai nuo to, kuris iš jų yra tinkamesnis platinimo sričiai. Dideliems daiktams tikriausiai reikalingas krūva.

32 bitų operacinėse sistemose, turinčiose keletą sriegių, kasetės dažnai yra gana ribotos (nors dažniausiai mažiausiai kelios MB), nes adresų erdvė turi būti supjaustyta, o anksčiau ar vėliau vienas įkrovos sriegis bus pradėtas kitoje, ant vienos srieginės sistemos („Linux glibc“ vienas sriegis) apribojimas yra daug mažesnis, nes kaminai gali tiesiog augti ir augti.

64 bitų operacinėse sistemose adresų erdvė yra pakankama, kad siūlų kaminai būtų gana dideli.

5
02 окт. atsakymą pateikė MarkR 02 okt. 2008-10-02 09:12 '08 at 9:12 2008-10-02 09:12

Tai nėra greitesnis kamino paskirstymas. Jūs taip pat naudosite iš kamino kintamųjų. Jie turi geriausias nuorodas. Ir galiausiai, išleidimas yra daug pigesnis.

3
03 окт. atsakymas, kurį pateikė MSalters 03 d 2008-10-03 18:35 '08, 18:35, 2008-10-03 18:35

Sraigtas turi ribotą pajėgumą, bet ne krūva. Tipiškas proceso ar siūlų kaminas yra apie 8K. Pasirinkę, negalite keisti dydžio.

Stekų kintamoji seka aprėpties taisykles, bet ne krūvos. Jei nurodymų rodyklė užeina už funkcijos, visi nauji su šiuo funkcija susiję kintamieji išnyksta.

Svarbiausia, kad negalite iš anksto numatyti bendrų funkcijų skambučių grandinės. Taigi, tik 200 baitų priskyrimas jūsų daliai gali lemti kamino perpildymą. Tai ypač svarbu, jei rašote biblioteką, o ne programą.

3
02 окт. atsakymą pateikė jogas 02 okt. 2008-10-02 19:57 '08 at 7:57 pm 2008-10-02 19:57

Stekų paskirstymas yra pora instrukcijų, o greičiausias krūvos platintojas rtos (TLSF) žinau, kad naudoja vidutiniškai apie 150 instrukcijų. Be to, blokuoti nereikia kamino paskirstymui, nes jie naudoja vietinį sričių saugojimą, kuris yra dar vienas didžiulis našumo padidėjimas. Taigi, stekų pasiskirstymas gali būti 2-3 laipsnių greičiau, priklausomai nuo to, kiek stipri yra daugiasukioji aplinka.

Apskritai, krūvos paskirstymas yra jūsų paskutinė išeitis, jei jums rūpi našumas. Perspektyvus tarpinis variantas gali būti fiksuoto fondo paskirstytojas, kuris taip pat yra pora instrukcija ir turi labai mažai paskirstymo išteklių, todėl tai tinka mažiems fiksuoto dydžio objektams. Kita vertus, jis veikia tik su fiksuoto dydžio objektais, iš esmės nėra saugus nuo sriegio ir turi blokų susiskaidymo problemas.

3
17 авг. Andrei Pokrovsky atsakymas rugpjūčio 17 d. 2010-08-17 23:22 '10, 11:22 PM 2010-08-17 23:22

Stekų paskirstymas beveik visada bus toks greitas arba greitas, kaip krūvos pasiskirstymas, nors krūvos paskirstytojui, žinoma, galima tiesiog naudoti kamino pagrindu paskirstymo metodą.

Vis dėlto dirbant su bendruoju krūvos ir krūvos rezultatu (arba kai kuriose geresnėse sąlygose, vietiniame ir išoriniame paskirstyme) kyla didelių problemų. Paprastai krūvos (išorės) pasiskirstymas yra lėtas, nes jis susijęs su daugeliu skirtingų platinimo ir paskirstymo tipų. Sumažinus naudojamo skirstytuvo tūrį (kuris daro jį vietos algoritmu / kodu), pagerės našumas be jokių esminių pakeitimų. Geresnės struktūros priskyrimas jūsų paskirstymo modeliams, pavyzdžiui, LIFO vykdymas platinimo ir išleidimo porose, taip pat gali pagerinti platintojo našumą naudojant platintoją paprastesniu ir struktūrizuotu būdu. Arba galite naudoti arba rašyti dozatorių, pritaikytą jūsų konkrečiam paskirstymo modeliui; Dauguma programų dažnai skiria kelis diskretiškus dydžius, todėl daugelio fiksuotų (pageidautinų) dydžių buferio krūva veiks labai gerai. Dėl šios priežasties „Windows“ naudoja savo mažai destruktyvią krūvą.

Kita vertus, 32 bitų atminties juostoje sukauptos dėmės taip pat yra pavojingos, jei turite per daug gijų. Rinkmenoms reikalingas nuolatinis atminties diapazonas, taigi kuo daugiau sriegių turite, tuo daugiau virtualios adresų vietos, kurią turėsite paleisti be. Tai nebus problema (dabar) su 64 bitų versija, tačiau ji gali sukelti chaosą ilgose programose su dideliu gijų skaičiumi. Virtualios adresų erdvės paleidimas dėl susiskaidymo visada yra skausmas.

3
10 авг. atsakymas pateiktas MSN 10 rug. 2010-08-10 19:27 '10, 07:27 PM 2010-08-10 19:27

Tikriausiai didžiausia problema, susijusi su krūvos paskirstymu, palyginti su kamino paskirstymu, yra ta, kad krūvos paskirstymas paprastai yra neribotas veikimas, todėl jūs negalite jo naudoti, jei laikas yra problema.

Kitoms programoms, kuriose laikas nėra problema, tai gali būti ne tokia svarbi, tačiau jei skiriate daug, tai turės įtakos vykdymo greičiui. Visada stenkitės naudoti steką trumpam gyvenimui ir dažnai priskirtą atmintį (pvz., Ciklų metu) ir, kiek įmanoma, platinti krūvą programos paleidimo metu.

3
02 окт. atsakymas pateikiamas larsivi 02 okt. 2008-10-02 11:34 '08 at 11:34 2008-10-02 11:34

Manau, kad gyvenimo laikas yra labai svarbus ir ar jums reikia sukurti sudėtingą dalyką. Pavyzdžiui, sandoriais pagrįstame modeliavime paprastai reikia užpildyti ir perkelti sandorio struktūrą su daugeliu laukų, skirtų darbo funkcijoms. Pavyzdžiui, žiūrėkite OSCI SystemC TLM-2.0 standartą.

Skirstant juos į operacijos užduotį, susidaro didžiulė pridėtinė vertė, nes statyba yra brangi. Geras būdas yra paskirstyti krūvą ir pakartotinai panaudoti sandorių objektus derinant arba paprasta politika, pavyzdžiui, „šis modulis reikalauja tik vieno sandorio objekto“.

Tai daug kartų greičiau nei objekto pasirinkimas su kiekvienu operacijos iškvietimu.

Taip yra todėl, kad objektas turi brangią konstrukciją ir gana ilgą naudingo tarnavimo laiką.

Sakyčiau: pabandykite abu ir pažiūrėkite, kas geriausiai tinka jūsų atveju, nes ji tikrai gali priklausyti nuo jūsų elgesio.

3
02 окт. atsakymas duotas jakobengblom2 02 okt. 2008-10-02 09:43 '08 at 9:43 2008-10-02 09:43

Yra bendras požiūris į tokius optimizavimus.

Оптимизация, которую вы получаете, пропорциональна количеству времени, в течение которого счетчик программ фактически находится в этом коде.