| Zobrazit předchozí téma :: Zobrazit následující téma |
| Autor |
Zpráva |
mar
Založen: 16. 06. 2012
Příspěvky: 602
|
 Zaslal: 6. březen 2014, 23:42:04 Předmět: std::vector a rekurze |
 |
|
Čau,
řešil jsem před chvílí vtipný problém s std::vectorem (samozřejmě v debug buildu bez optimalizací problém nenastával 
měl jsem následující kód v rekurzivně volané fuknci
| kód: |
void func(...)
{
...
size_t pos = v.size();
...
v.push_back( ... );
if ( ... )
v[pos].a = func(...);
if ( ... )
v[pos].b = func(...);
}
|
problém je ten, že volání rekurzivní funkce může realokovat vektor, překladač ale udělal to, že si načetl pointer na data před voláním a až pak jej použil.
Řešení bylo uložit výsledek volání do pomocné proměnné a tu pak přiřadit (tj. uměle vytvořit sequence point)
| kód: |
if ( ... )
{
size_t tmp = func(...); // sequence point
v[pos].a = tmp;
}
|
samozřejmě chyba byla na mé straně (undefined behavior), nicméně nevíte někdo, jestli toto řešení (hack)
je v pořádku a nerozbije mi to v budoucnu chytřejší překladač?
Čistší řešení by bylo přidávat vyplněnou strukturu až po rekurzi, ale chci mít zachované toto pořadí (tj. aby root uzel byl uložen jako první). |
|
| Návrat nahoru |
|
 |
quas4
Založen: 18. 10. 2007
Příspěvky: 199
|
| Zaslal: 7. březen 2014, 00:31:39 Předmět: |
|
|
| Muzes vysvetlit co myslis tim "sequence point"? z kodu ktery jsi napsal nejsem moc moudry. func je void ale jeji vysledek nekam prirazujes. jsi schopen napsat kratky zkompilovatelny kod ktery by demonstroval toto rozdilne chovani mezi debug a optimalizovanou verzi o kterem pises? mam podezreni ze ti unika neco podstatneho. |
|
| Návrat nahoru |
|
|
micky
Založen: 28. 02. 2008
Příspěvky: 348
Bydliště: Plzeň, Praha
|
| Zaslal: 7. březen 2014, 00:43:55 Předmět: |
|
|
Co to bylo za překladač...?
Navíc - moje interpretace:
| kód: |
TYP func(...)
{
...
v.push_back( ... );
if ( ... )
temp = func(...);
v[v.size()-1].a = temp; ///??? push_back?
if ( ... )
temp = func(...);
v[v.size()-1].b = temp; ///??? push_back?
}
|
...nicméně se mi to celé nějak nezdá, podle toho segmentu, co jsi původně napsal, tak nejdřív vložím prvek do pole (odpovídá indexu pos), následně se v rekurzi vkládá vesele dál, pak se vrátím zpátky a na to samé pole (pos) si zapíšu výsledek. Pokud to chceš přepisovat, tak OK... Ani to nesouvisí s tím, jestli se teda vyhodnotí dříve pravá nebo levá strana přiřazení...
_________________
https://www.bluepulsar.cz/
https://twitter.com/11thDream_Game/ |
|
| Návrat nahoru |
|
|
mar
Založen: 16. 06. 2012
Příspěvky: 602
|
| Zaslal: 7. březen 2014, 09:17:52 Předmět: |
|
|
Ok zapomněl jsem pár věcí, takže tady mám funkční kód:
| kód: |
#include <cstdlib>
#include <vector>
struct Struct
{
size_t indices[2];
};
size_t func( std::vector< Struct > &v, int depth = 1 )
{
if ( depth >= 10 )
return -1;
// force allocation
std::vector< int > iv;
iv.push_back( depth );
size_t res = v.size();
v.push_back( Struct() );
v[res].indices[0] = func( v, depth+1 );
v[res].indices[1] = func( v, depth+1 );
return res;
}
int main()
{
std::vector< Struct > v;
func(v);
return 0;
}
|
Překladač je Microsoftí (VS2012).
Toto v release padá (protože si načtě pointer na data do registru před voláním func.
Se sequence pointem to funguje:
| kód: |
size_t tmp;
tmp = func( v, depth+1 );
v[res].indices[0] = tmp;
tmp = func( v, depth+1 );
v[res].indices[1] = tmp;
|
quas: sequence point je popsaný ve standardu, to není pojem, který bych já vymyslel
http://stackoverflow.com/questions/4176328/undefined-behavior-and-sequence-points |
|
| Návrat nahoru |
|
|
quas4
Založen: 18. 10. 2007
Příspěvky: 199
|
| Zaslal: 7. březen 2014, 10:30:11 Předmět: |
|
|
dik za link. Hezky to ilustruje co vsechno je potreba v c++ standardu specifikovat protoze samotny jazyk je tak neuveritelne komplikovany. Jenom specifikace gramatiky by byla urcite na mnoho stran. c++ je podle me spatny programovaci jazyk.
Neni lepsi si pred func() naalokovat vector (nebo Struct* v) uz s potrebnou velikosti? (mensi defragmentace pameti, optimalnejsi vuci L2 cache, jen jeden narocny malloc/new)
(1 << (max_recur - 1)) - 1
a neresit "sequence point"? Jeho existenci a nutnost v tomto pripade vnimam jako selhani jazyka nez jako chybu v uvaze programatora. |
|
| Návrat nahoru |
|
|
mar
Založen: 16. 06. 2012
Příspěvky: 602
|
| Zaslal: 7. březen 2014, 10:48:44 Předmět: |
|
|
| quas4 napsal: |
dik za link. Hezky to ilustruje co vsechno je potreba v c++ standardu specifikovat protoze samotny jazyk je tak neuveritelne komplikovany. Jenom specifikace gramatiky by byla urcite na mnoho stran. c++ je podle me spatny programovaci jazyk.
Neni lepsi si pred func() naalokovat vector (nebo Struct* v) uz s potrebnou velikosti? (mensi defragmentace pameti, optimalnejsi vuci L2 cache, jen jeden narocny malloc/new)
(1 << (max_recur - 1)) - 1
a neresit "sequence point"? Jeho existenci a nutnost v tomto pripade vnimam jako selhani jazyka nez jako chybu v uvaze programatora. |
No jak se na ten link koukám, tak volání funkce by měl být taky sequence point 
Ano předem si to naalokovat by řešení bylo, projít si strom, spočítat uzly a pak to jenom plnit. Je to kód, který dělám v preprocess kroku, takže nic kritického. Jenom bych se rád do budoucna vyhnul podobným překvapením.
Jinak souhlasím, nějakou dobu jsem pokukoval po D, ale nakonec z toho udělali podobný balast, jako z C++.
Je tam celkem dost dalších věcí, na které je třeba si dávat pozor, jako např. že přetečení signed integeru je undefined behavior, standard navíc neříká, že reprezentace celých čísel musí být ve two's complement formátu, že reprezentace nulového pointeru nemusí být nula apod., tohle jsou ale pozůstatky z dob minulých.
EDIT: tak to vypadá, že to nesouvisí se sequence points, ale s tím, že u přiřazovacího operátoru = standard nezaručuje, že pravá strana se vyhodnotí dřív, jediná záruka je, že přiřazení se provede až po vyhodnocení obou stran |
|
| Návrat nahoru |
|
|
perry
Založen: 28. 07. 2009
Příspěvky: 879
|
| Zaslal: 7. březen 2014, 11:19:22 Předmět: |
|
|
V tom postnutém "funkčním" kódu absolutně nepobírám tohle:
| kód: |
// force allocation
std::vector< int > iv;
iv.push_back( depth );
|
K čemu to tam je... to je naprosto k ničemu. Příklad jsem nezkoušel pustit, ale ani nechápu o jakém pointeru tam mluvíš.. žádný pointer nikde nevidím (pokud mluvíš o &, tak to není pointer ale reference).
Plus zkoušel jsem ten kód a nijak mi to nepadá
Ad C++... jazyk je to v pohodě a dá se v tom psát úplně normálně. Ano, jdou tam psát čuňárny.. ale to nevidím jako chybu jazyka, ale programátora
_________________
Perry.cz |
|
| Návrat nahoru |
|
|
quas4
Založen: 18. 10. 2007
Příspěvky: 199
|
| Zaslal: 7. březen 2014, 11:28:51 Předmět: |
|
|
mar> hehe. jasne. c++ umi cloveku vylozene explodovat pred ocima.
na programovani her kde je dulezita rychlost se mi jevi jako kandidati golang (velka komunita, pekne udelana prace s thready, nema operator overloading, atd..) nebo jeste lepe rust (generuje rychly kod, dobre navrhnuta prace s pointery, atd..)
na ostatni (napr. web server apod.) jsem zastancem lispu a scheme. expresivita a syntakticka jednoduchost lisp-like jazyku je uzasna. Z implementaci mam dobrou zkusenost s sbcl, clojure, guile, gambit, kazde je dobre podle typu ulohy. |
|
| Návrat nahoru |
|
|
mar
Založen: 16. 06. 2012
Příspěvky: 602
|
| Zaslal: 7. březen 2014, 11:43:15 Předmět: |
|
|
| perry napsal: |
V tom postnutém "funkčním" kódu absolutně nepobírám tohle:
| kód: |
// force allocation
std::vector< int > iv;
iv.push_back( depth );
|
K čemu to tam je... to je naprosto k ničemu. Příklad jsem nezkoušel pustit, ale ani nechápu o jakém pointeru tam mluvíš.. žádný pointer nikde nevidím (pokud mluvíš o &, tak to není pointer ale reference).
Plus zkoušel jsem ten kód a nijak mi to nepadá
|
Nekoukej na funkčnost toho kódu, demonstruje to čistě určitý případ, který může nastat.
Tohle tam je kvůli tomu, aby se vynutila alokace, která si vezme blok, který byl uvolněný realokací vektoru (tj. aby to poškodilo heap a tím pádem padalo).
Mně to tady padá, Microsoftí překladač (VS2012), release.
Jinak v tomhle případě to byla moje chyba a pro příště si dám větší pozor.
quas: díky, podívám se, většinu z toho neznám (kromě go a clojure, o kterých jsem už slyšel)
EDIT: perry tak máš pravdu, ta dummy alokace tam ani není potřeba, stačí si to zvýšit na ( depth >= 20 ) |
|
| Návrat nahoru |
|
|
perry
Založen: 28. 07. 2009
Příspěvky: 879
|
| Zaslal: 7. březen 2014, 12:25:07 Předmět: |
|
|
Jde o to, ze tu dummy alokaci stejne visualko pri prekladu vyhodi. Nikde se nepouziva, takze je tm k nicemu. Teda alespon myslim ze ji v release buildu vyhodi.
_________________
Perry.cz |
|
| Návrat nahoru |
|
|
]semo[
Založen: 29. 07. 2007
Příspěvky: 1525
Bydliště: Telč
|
| Zaslal: 7. březen 2014, 13:54:53 Předmět: |
|
|
| quas4 napsal: |
| ... c++ je podle me spatny programovaci jazyk. |
To mě vždycky tak rozesmutní. Je to napsat, že "moře je podle mě špatné, mělo by se jezdit jen na rybníku" Neni to tak nebezpečné, že...? :-)
_________________
Kdo jede na tygru, nesmí sesednout.
---
http://www.inventurakrajiny.cz/sipka/
Aquadelic GT, Mafia II, simulátory |
|
| Návrat nahoru |
|
|
quas4
Založen: 18. 10. 2007
Příspěvky: 199
|
| Zaslal: 7. březen 2014, 14:46:07 Předmět: |
|
|
| ]semo[ napsal: |
| quas4 napsal: |
| ... c++ je podle me spatny programovaci jazyk. |
To mě vždycky tak rozesmutní. Je to napsat, že "moře je podle mě špatné, mělo by se jezdit jen na rybníku" Neni to tak nebezpečné, že...? |
takoveto srovnani je velmi zjednodusujici a scestne. V cem srovnavas c++ s morem? V tom ze je na nem nebezpecne jezdit? O bezpecnosti prece nebyla vubec rec. A i kdyby tak jsem ani v nejmensim netvrdil ze ti co to umi by se na nej nemeli poustet. Minimalne v tomto je to zavadejici..
K cemu je c++ urceno a je v tom taky vyborne? Podle me velice komplikovanou syntaxi a neprehlednou semantikou prekladacu (napriklad zde: http://stackoverflow.com/questions/620137/do-the-parentheses-after-the-type-name-make-a-difference-with-new nebo vtipny dotaz zde: http://stackoverflow.com/questions/5347444/overload-resolution-and-arrays-which-function-should-be-called ). Pokud nevnimam programovaci jazyk jak nastroj pro psani poezie pak vyzaduji prakticke vlastnosti do kterych pro me spada i syntakticka jednoduchost. V pripade programovani "poezie" bych sahnul treba na Brainfuck nebo Piet. I v nich lze napsat velke veci. |
|
| Návrat nahoru |
|
|
VODA
Založen: 29. 07. 2007
Příspěvky: 1721
Bydliště: Plzeň
|
| Zaslal: 7. březen 2014, 15:14:04 Předmět: |
|
|
Mně se přirovnání, které Semo napsal líbí. Osobně C++ preferuji nad všemi dalšími jazyky.
A co se týče toho kódu, řeknu jen jednu věc... fuj rekurze! 
_________________
Opravdovost se pojí s trýzní... |
|
| Návrat nahoru |
|
|
]semo[
Založen: 29. 07. 2007
Příspěvky: 1525
Bydliště: Telč
|
| Zaslal: 7. březen 2014, 15:23:19 Předmět: |
|
|
Tak jiný přirovnání :-)- Máš letadlo - akrobatický speciál. Obyčejnej pilot se bude skoro bát do toho sednout, protože se to řídí špatně. A je to snad proto špatné letadlo? No neni. Prostě jen dává více volnosti za cenu náročnějšího řízení.
U těch příkladů, co si poslal, je samozřejmě jedno velké ALE: nikdo tě nenutí to psát takhle. A musel bys být fakt velké prase, abys to tak psal. U C++ zkrátka záleží na tom, jakým stylem budeš psát. U jiných jazyků ti ten styl většinou někdo vnutí.
Ještě že je pátek, aspoň se ten flame snad brzo utne (aspoň pro mě, až za chvíli vypnu komp :) ).
_________________
Kdo jede na tygru, nesmí sesednout.
---
http://www.inventurakrajiny.cz/sipka/
Aquadelic GT, Mafia II, simulátory |
|
| Návrat nahoru |
|
|
mar
Založen: 16. 06. 2012
Příspěvky: 602
|
| Zaslal: 7. březen 2014, 15:41:14 Předmět: |
|
|
| ]semo[ napsal: |
| To mě vždycky tak rozesmutní. Je to napsat, že "moře je podle mě špatné, mělo by se jezdit jen na rybníku" Neni to tak nebezpečné, že...? |
Kdyby mě pokaždé rozesmutnilo to, že má někdo jiný názor než já, tak bych byl asi smutný pořád
Co se týká rekurze, ten kód (původní) dumpuje bsp strom. Nevidím absolutně důvod to měnit a mít kvůli tomu složitější kód.
Btw. recursive descent je taky fuj?
Nicméně díky za flamewar, teď jsem konečně spokojený  |
|
| Návrat nahoru |
|
|
|
Hlavní strana
FAQ
Test
Hledat
Seznam uživatelů
Uživatelské skupiny
Registrace
Ke Stažení
Nastavení
Přihlášení
Calendar
