# Paměť

## Objekty

### Připomenutí: objekt

│ • objekt je zobecnění paměti
│ • vzniká «deklarací proměnné»
│ • ukládá «hodnotu» (ne bajty!)
│ • může mít přidělenu adresu

(má-li objekt adresu, může na něj existovat ukazatel; existuje-li
ukazatel, objekt musí mít adresu)

### Paměť

│ • „pole bajtů“
│ • adresa ~ index
│   ◦ (± díry v adresním prostoru)
│ • bajt ~ ‹unsigned char›
│   ◦ hodnota 0–255

(paměť je efektivně pole bajtů, adresy hrají roli indexů; na úrovni
C odpovídá bajtu – nejmenší adresovatelné jednotce – typ ‹unsigned
char›)

### Překrývání (aliasing)

│ • objekty se stejnou adresou
│ • typicky není dovoleno
│ • výjimky:
│   ◦ reprezentace
│   ◦ kompatibilní typy


### Reprezentace objektu

│ • bajty objektu = reprezentace
│ • reprezentace je sama objektem
│ • kódování definováno implementací
│ • nemusí být jednoznačná


### Přetypování

│ • objekt a reprezentace sdílí adresu
│ • ukazatele mají různé typy
│ • přesto lze bezpečně přetypovat
│   ◦ reprezentace → ‹unsigned char *›
│ • jen pozor na ‹const›


### Vznik objektu

│ • paměť ~ ‹unsigned char[N]›
│ • zápisem reprezentace
│   ◦ kopie po bajtech
│   ◦ přiřazení


### Neplatné objekty

│ • objekt lze konstruovat z bajtů
│ • ne každá reprezentace je platná
│ • čtení z neplatného objektu → UB


### Ukazatel bez typu

│ • ‹void *› – neurčuje typ objektu
│ • není dovoleno dereferencovat
│ • povoluje implicitní přetypování
│ • nesmí porušit pravidla o překrývání


## Alokace

### Zadání úlohy

│ • nalézt nepoužitou paměť
│ • v nějaké větší oblasti
│   ◦ typicky od operačního systému
│   ◦ nemusí být souvislá
│ • zadané minimální velikosti


### Dynamická paměť

│ • nekonstantní velikost alokace
│ • živost určená za běhu
│   ◦ vedlejší efekt výrazu
│   ◦ detailněji příště


### Další požadavky

│ • co nejrychleji
│ • co nejméně nevyužitelné paměti
│   ◦ fragmentace adresního prostoru
│   ◦ metadata alokátoru


### Strategie

│ • rozdělit volný blok
│   ◦ musí být dostatečně velký
│   ◦ first-fit → první takový
│   ◦ best-fit → nejmenší takový
│ • sub-alokátory
│   ◦ kombince různých strategií


### Předalokace

│ • typicky pro malé velikosti
│ • paměť se chystá dávkově
│   ◦ třeba po 4KiB blocích
│   ◦ všechny objekty stejně velké


### Datové struktury

│ • zřetězený seznam volných bloků
│   ◦ uzel «uvnitř» volného bloku
│   ◦ zaužívaný název freelist
│ • tabulka indexovaná velikostí
│ • hashovací tabulky


## Realokace paměti

### Situace

│ • implementujeme dynamické pole
│ • potřebujeme pole zvětšit
│ • triviálně:
│   ◦ nová alokace + kopie dat
│   ◦ dealokace původního
│ • lze provést i lépe?

### Využití stávající alokace

│ • vyžaduje spolupráci alokátoru
│ • použít následující volný blok
│   ◦ optimální – není potřeba přesun
│   ◦ 
│ • použít předchozí blok

### Využití předchozího bloku

│ • vyžaduje přesun dat
│   ◦ překryv podle poměru velikostí
│   ◦ dvojnásobek → bez překryvu
│ • celková potřebná paměť ⟦m⟧
│   ◦ oproti ⟦m + n⟧ pro novou alokaci
│   ◦ dvojnásobek → ⟦2n⟧ vs ⟦3n⟧

### Přesun dat

│ • kopie ‹for› cyklem po bajtech
│ • co překrývající se oblasti
│   ◦ někdy je potřeba iterovat odzadu
│   ◦ mnohem méně efektivní
│ • alternativní metody dle platformy

### Situace v praxi

│ • knihovna jazyka C má ‹realloc›
│   ◦ umožňuje i zmenšení alokace
│   ◦ poněkud komplikované rozhraní
│ • Rust, D také nabízí ‹realloc›
│ • C++ od podpory upustilo