Vznikající kuchařka C++ na GitHubu.
Štítek: c
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
Programování v C#
NPRG035 Jazyk C# a platforma .NET
- přednáší Ježek, cvičí Klímek
- vše o vláknech: http://www.albahari.com/threading/
NPRG038 Pokročilé programování pro .NET
- Web přednášejícího
- Učivo ke zkoušce:
Programování v C++
- http://www.cplusplus.com užitečné stránky
NPRG041 – Programování v C++
- Stránky předmětu – zde naleznete především slajdy.
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.
- Keddieho stránka o tomto úkolu
- Specifikace mého protokolu
- Funkce trackeru a node
- Třídy pro socketovou komunikaci: Practical C++ Socket (a informace o jejím použití)
- Specifikace protokolu BitTorrent
- Knihovna pro thread pool první (stavící na boost::thread) a druhá (POSIX).
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
Specifikace torrentoidního protokolu
Budeme mít dva základní typy komunikace.
Node ↔ Tracker
- Spojení může začít kterákoliv strana. Tracker posílá „HELO NODE“ a node odpovídá „HELO TRACKER“ (nebo v opačném pořadí). Tím je session považována za započatou.
- Udržování session probíhá pomocí zprávy „NOOP“ (druhá strana odpoví stejně).
- Požadavky na chunks mohou přijít taktéž z obou směrů. K tomu slouží zpráva INEED v jedné z následujících variant:
- „INEED ALL“ je žádost na poslání celého seznamu dostupných chunks (v případě, že zasílá tracker) anebo maximálního přípustného seznamu ostatních uzlů (v případě, že zasílá node; co znamená „maximální přípustný“, to si určuje tracker).
- „INEED SOURCES number_of_sources“ zasílá node trackerovi a žádá number_of_sources adres dalších uzlů (které ještě nemá). Tracker může nebo nemusí vyhovět.
- „INEED chunks“ zasílá node trackerovi a žádá zdroje, které mají konkrétně chunks.
- chunks je seznam prvků oddělený mezerami, kde prvek je buď id jednoho chunku (celé kladné číslo) anebo „id_from–id_to“ celý interval chunks
- Na žádost INEED odpovídá uzel zprávou IHAVE, a to některou z variant:
- „IHAVE ALL„, tzn. daný uzel je seeder
- „IHAVE NONE„, tzn. uzel je právě začínající leecher
- „IHAVE chunks“ (seznam chunks viz. výše)
- Tracker na INEED odpovídá zprávou „NODES NONE„, pokud žádné dostupné uzly momentálně nevyhovují dotazu, anebo „NODES node_list„, kde node_list je seznam prvků ip:port oddělených mezerami.
- Node může trackerovi nahlásit, že je pro něj jiný node nedostupný, pomocí zprávy „TOOFAR node_ip„.
- Oznámení o ukončení session se provádí zprávou „BYEBYE„. Tu smí zaslat node komukoliv a tracker seederovi.
- V případě nerozpoznané, špatně formulované nebo nevhodné zprávy je session resetována zprávou „BLAHBLAHBLAH„
Node ↔ Node
- Session je zahájena výměnou zpráv „HELO NODE„, udržuje se zprávou „NOOP“ a ukončuje „BYEBYE„.
- Používají se zprávy INEED, IHAVE stejně jako u komunikace s trackerem.
- Požadavek na stažení konkrétního chunku je „GET chunk_id„, na což může druhá strana odpovědět následujícími způsoby:
- „PUT chunk_data“ – samotný přenos.
- „WAIT“ – počkat dvě minuty, pokud nepřijde PUT. Pak zkoušet znova.
- „NOTNOW“ – druhý node je příliš zaneprázdněn, zkusit později.
- Nesrozumitelnost komunikace je druhé straně oznámena zprávou „BLAHBLAHBLAH„.