Normalizovaná smyčka - Normalized loop
 | Tento článek má několik problémů. Prosím pomozte vylepši to nebo diskutovat o těchto otázkách na internetu diskusní stránka. (Zjistěte, jak a kdy tyto zprávy ze šablony odebrat) (Zjistěte, jak a kdy odstranit tuto zprávu šablony)
|
v počítačová věda, a normalizovaná smyčka (někdy nazývaná dobře vychovaná smyčka), je smyčka, ve které proměnná smyčky začíná na 0 (nebo jakékoli konstantě) a při každé iteraci se zvyšuje o jednu, dokud není splněna podmínka ukončení. Normalizované smyčky jsou velmi důležité pro teorie překladače, analýza závislosti smyčky protože zjednodušují datová závislost analýza.[Citace je zapotřebí ]
Dobře vychované smyčky
Dobře chovaná smyčka má obvykle tvar:
pro ( i = 0; i < MAX; i++ ) A[i] = b[i] + 5;Protože přírůstek je jednotný a konstantní, je velmi snadné to vidět, pokud jsou oba A a b jsou větší než MAX, tato smyčka nikdy nebude mít přístup k paměti mimo přidělený rozsah.
Nenormalizované smyčky
Nenormalizovaná smyčka může začínat u různých indexů, přírůstek o neunitární částky a definovat podmínky odchodu komplikovaně. Takové smyčky se obtížně optimalizují, vektorizují a dokonce i procházejí, zvláště pokud jsou funkce prováděny v jakékoli části podmínek smyčky.
Jednoduchý příklad, kdy nezačíná na začátku a zvyšuje se o více než jeden:
// Příklad 1pro ( i = 7; i < MAX; i+=3 ) A[i] = b[i] + 5;Složitější příklad s další podmínkou ukončení:
// Příklad 2pro ( i = 7; i < MAX || i > MIN; i+=3 ) A[i] = b[i] + 5;Smyčky mohou také mít nepředvídatelné chování během doby kompilace, kde podmínka ukončení závisí na obsahu upravovaných dat:
// Příklad 3pro ( i = 7; i < MAX && A[i]; i+=3 ) A[i] = b[i] + 5;Nebo dokonce dynamické výpočty pomocí volání funkcí:
// Příklad 4pro ( i = Start(); i < max(); i+=přírůstek() ) A[i] = b[i] + 5;Reverzní smyčky jsou také velmi jednoduché a lze je snadno normalizovat:
// Příklad 5pro ( i = MAX; i > 0; i-- ) A[i] = b[i] + 5;Převod na normalizovanou smyčku
Pokud nenormalizovaný nemá dynamické chování, je obvykle velmi snadné jej transformovat na normalizované. Například první příklad (příklad 1) výše lze snadno převést na:
// Příklad 1 -> normalizovánopro ( i = 0; i < (MAX-7)/3; i++ ) A[i*3+7] = b[i*3+7] + 5;Třetí příklad lze částečně normalizovat, aby umožnil určitou paralelizaci, ale stále mu chybí schopnost znát rozpětí smyček (kolik iterací bude existovat), což ztěžuje vektorizaci pomocí multimediálního hardwaru.
Začátek v 7 není tolik problém, pokud je přírůstek pravidelný, nejlépe jeden. Když více příkazů uvnitř smyčky používá index, mohou být vytvořeny některé soukromé dočasné proměnné, které zvládnou různé iterační kroky.
Reverzní smyčku (příklad 5) lze také snadno normalizovat:
// Příklad 5 -> normalizovánopro ( i = 0; i < MAX; i++ ) A[MAX-i] = b[MAX-i] + 5;Všimněte si, že přístup je stále zpět. V tomto případě nemá smysl ponechávat to zpět (protože tam není datová závislost ), ale tam, kde existují závislosti, je třeba postupovat opatrně, aby se také přístup vrátil, protože by to mohlo narušit pořadí přiřazení.
Nemožné převody
Příklad 4 výše znemožňuje předvídat cokoli z této smyčky. Pokud samotné funkce nejsou triviální (konstantní), neexistuje způsob, jak zjistit, kde bude smyčka začínat, zastavena a o kolik se zvýší každá iterace. Tyto smyčky se nejen těžko paralelizují, ale také fungují strašně.
Při každé iteraci smyčka vyhodnotí dvě funkce (max () a přírůstek()). I když jsou funkce podřízené, stav se stává příliš složitým, než aby bylo vhodné jej optimalizovat. Programátor by měl věnovat zvláštní pozornost tomu, aby tyto smyčky nevytvářel, pokud to není nezbytně nutné (pokud vůbec).
Další nebezpečí těchto smyček se objeví, pokud vyhodnocení závisí na změněných datech. Například běžnou chybou při použití iterátorů je odebrání položek ze seznamu při jeho úpravě nebo spoléhání se na velikosti (pro podmínku ukončení), které již nejsou pravdivé.