Move semantics a rvalue

Motivace pro move semantics: chceme zabránit zbytečnému kopírování dat, když je stačí pouze přesunout (jako v následujícím příkladu). Tím můžeme z operace lineární vůči délce dat učinit operaci běžící v konstantním čase. V tomto případě využijeme rvalue reference.

void swapstrings(string s1, string s2) {
    string temp=s1;  // kopírování
    s1=s2;           // kopírování
    s2=temp;         // kopírování
};

Co je rvalue?

Všechny výrazy v C++ jsou buď rvalue nebo lvalue. Zjednodušeně lze říci, že lvalue je každý objekt, který má jméno a existuje tedy i mimo jediný výraz. Rvalue je naopak pouze dočasný objekt, na který existuje vždy jen jeden odkaz.

Rvalue reference

type-id && cast-expression

Rvalue reference nám umožňuje rozlišit lvalue a rvalue, takže můžeme “ukrást” data nějakého dočasného objektu, na nějž máme rvalue referenci – například pole prvků nějakého kontejneru. Tím se vyhneme zbytečnému kopírování.

Příklad: konkatenace řetězce

int main() {
    string s = string("h") + "e" + "ll" + "o";
    cout << s << endl;
};

V následujícím kódu by bez move semantics v string::operator+ bylo nutno vytvořit nový string, překopírovat do něj data z původního stringu a přidat, co má být přidáno. Nevíme totiž, zda se na původní string neodkazujeme někde jinde v programu. Pokud ale implementujeme move semantics, bude string předán jako rvalue reference a my jej můžeme bezstarostně modifikovat.

Příklad: přidávání prvků do vektoru

Mějme vektor, do kterého přidáváme prvky. Pokud je přesažena kapacita vektoru, musí tento realokovat pro prvky paměť a pak je všechny překopírovat na nové umístění, abychom měli prostor i pro vkládaný prvek. Při kopírování prvku vzniká nejdříve nový prvek, pak se zavolá jeho copy constructor na zkopírování dat z původního prvku, a nakonec je původní prvek odstraněn. Tomuto vpodstatě zbytečnému kopírování se dá zabránit právě pomocí move semantics.

Vlastnosti rvalue reference

  • Lze přetížit funkci, aby brala lvalue a rvalue reference. Smysl má brát jako parametr const lvalue referenci a rvalue referenci – tím jednoznačně rozlišíme, kdy dostáváme modifikovatelný a kdy nemodifikovatelný objekt.
  • Kompilátor bere pojmenovanou rvalue referenci jako lvalue (tedy např. v těle funkce, která přijímá rvalue referenci) – to protože na ni lze po pojmenování odkazovat na více místech programu.
  • Je možné přetypovat lvalue referenci na rvalue. Ideální je použití std::move(T&)

Move semantics

Potřebujeme implementovat především move constructor. Tento bude přijímat rvalue referenci na jinou instanci též třídy. V konstruktoru přiřadíme prvky zdrojového objektu do prvků konstruovaného objektu a nastavíme prvky ve zdrojovém objektu na výchozí hodnoty, abychom zabránili vícenásobnému uvolnění prostředků (např. skrze jeho destruktor).

operator= implementujeme analogicky.

Zdroje

Neprocedurální programování – domácí úkoly

Vše je naprosto bez záruk (ba dokonce vím, že se tam někde vyskytují chyby) a je určeno samozřejmě pouze jako studijní materiál… úlohy si řešte sami, jinak budete nejspíš mít vážný problém se zkouškou.

100301_dcv1, 100308_dcv2, 100315_dcv3, 100327_dcv5, 100404_dcv6, 100409_dcv7, 100425_dcv8, 100501_dcv9, 100505_dcv10, 100513_dcv11.

Programování v C#

NPRG035 Jazyk C# a platforma .NET

NPRG038 Pokročilé programování pro .NET

Programování v C++

NPRG041 – Programování v C++

NPRG051 – Pokročilé programování v C++ a C

  • Stránky předmětu
  • Upozorňuji, že domácí úkoly jsou poměrně pekelné, pokud ještě s požadovanými programovacími technikami nemáte žádnou zkušenost. Opravdu se nevyplatí nechávat vše na poslední den. Vím, o čem mluvím. ;-)
  • Dost materiálů má na svých stránkách Keddie.
  • Text o nové normě C++0x

Bude-li zájem, zvážím vystavení svých zdrojových kódů zde na web.

DU1 – Asynchronní čtení souboru

  • Keddieho stránka o asynchronním I/O

8 bodů

DU2 – Commandline parser

7 bodů

DU3 – Hash map

  • Něco málo o hashmapě, iterátorech od Keddieho.
  • Já pro změnu vytvořil stručný úvod do Move semantics a rvalue.

5 bodů

DU4 – TORRENTY

Tento úkol jsem nestihl dokončit (a pochopitelně nemám energii, čas ani motivaci pokračovat po deadline) – proto jsou následující odkazy prostě to, co se tak nějak nasbíralo v průběhu – nesetříděné, s nadějí, že to někomu k něčemu bude.

nedoděláno, neodevzdáno

Funkce trackeru a node

Tracker

Inicializace

  • Načtení dat z .torrentu
  • Navázáná session se seedery (přidělení session_id)
  • Otevření portu pro leechery

Připojení nového leechera

  • Navázání session, získání informací IHAVE, zaslání adresy jednoho seedera

Příjem zpráv

  • IHAVE: uložení získaných informací k příslušní session (bitová mapa stažených chunks?)
  • INEED: vrátit nějakou adresu leechera/seedera
    • U záznamu žádajícího uzlu si pamatovat, které adresy ostatních uzlů mu již byly zaslány (příp. ukládat i informaci o tom, které uzly mají jeho adresu)
    • Preferovat málo vytížení leechery. Seedeři mají ještě nižší prioritu.
  • TOOFAR – uložit a při vyhledávání zdroje pro nějaký uzel tento vynechat
  • NOOP – odpovědět taktéž NOOP a resetovat počítadlo timeoutu session

Spojení TCP

  • Zapouzdřující třída.
  • Výpadky neřešit a spojení obnovovat, až když chceme něco poslat, nebo umožnit navázání na příslušnou session.

Session timeout nebo BYEBYE

  • Ukončení TCP spojení
  • Odebrat uzel ze seznamu
  • Upravit informaci o referencích na ostatní uzly

Node

Inicializace

  • Načtení souboru .torrent
  • Načtení stavu souboru
  • Kontrola staženého souboru?
  • Navázání session s trackerem, odeslání INEED

Hledání dalších zdrojů chunku

  • Může běžet několik hledání paralelně (ovšem jen určitý počet chunks dopředu, abychom zbytečně nezískávali infromace, které pak už nebudou aktuální). Požadavky na hledání se budou zařazovat do FIFO fronty
  • Dotazy okolním uzlům INEED (u kterých ještě nevíme, že by chunk měli). Pokud v žádné odpovědi IHAVE hledaný chunk nebude, zkusíme se obrátit na tracker pro další adresy uzlů (těm už speciální INEED posílat nemusíme).

Stahování chunku

  • Může běžet nekolik paralelně (nezávisle na hledání)
  • Udržujeme seznam chunků setříděný podle dostupnosti a zkoušíme stahovat od nejnedostupnějších (ale dostupných). Žádáme postupně od uzlů, od kterých zatím nic nestahujeme (a seeder má nejnižší prioritu).
  • U uzlu každá další odpověď NOTNOW ==> zdvojnásobení prodlevy, než umožníme další dotaz jeho směrem.

Session timeout

  • Udržujeme seznam IP a počet timeoutů/doba spojení. Pokud je někde překročen threshold, nahlásíme TOOFAR trackeru a odebereme ze seznamu.

Dotažené chunks

  • Jednou za čas budeme posílat nové IHAVE trackeru a některým uzlům.

Požadavek na chunk

  • GET – vyhovět bez váhání, pokud nejsme přetížení (poslat PUT a dekrementovat prioritu žádajícího uzlu na nulu).
  • Pokud je víc požadavků než volných slotů, udržujeme prioritní frontu. Tomu, kdo je ve frontě první, posíláme vždy WAIT, ostatním NOTNOW. V obou případech inkrementujeme prioritu žádajícího uzlu.

Stažený celý soubor

  • Budeme si udržovat počet chybějících chunks, abychom měli snadný přehled
  • Vyplivneme soubor do cílového umístění
  • Odešleme trackeru IHAVE ALL
  • Ukončíme session se seedy