Asociativní pole v jazyce D
Nejenom poli je člověk živ i když to tak v systémových programovacích jazycích může vypadat. Někdy potřebuje hash-mapu. Nebo asociativní pole, jak se ji říká v žargonu jazyka D.
Dneska se opět zaměřím na D, konkrétně na otázku kolik paměti potřebují
asociativní pole. Jejich implementace je se nachází ve struct AA
a
zjednodušeně vypadá následovně.
struct AA { // ... Bucket[] buckets; } struct Bucket { ulong hash; Element* element; } struct Element(Key, Val) { Key key; Val val; }
Používá open addressing, žádné řetězy kolizí, jen jedno spojité pole. To je
dobré. Smazané prvky po sobě zachovají tombstone hash, který je odstraněn při
následném zvětšení tabulky. Klasika. Pole buckets
začíná na velikosti 8,
rozumně malé, a roste při naplnění z 4/5 na čtyřnásobek. V průměru tak zabere
2x víc místa, než je nezbytně nutné.
Struct Bucket
má velikost 16 bajtů: 8B hash a 8B pointer na element.
Element
je dynamicky alokovaný na haldě spravované GC. Pro key
a val
platí, že když jde
o statické pole nebo struct (tj. staticky známe jejich velikost), jsou ve
structu Element
přímo, ne jako pointery ven. To je taky dobré, zlepšuje to
paměťovou lokalitu dat. Alokace má velikost mocniny dvou a nejmenší zabírá 16
B místa.
Když to všechno dám dohromady, v případě uint[uint] map
bucket zabere 16B +
16B průměrné režie, Element
má 16B jako nejmenší velikost alokace (i když by
se dva inty vešly do prostoru pro pointer *element
). Dohromady to dělá 48B na
jeden pár klíč/hodnota. ulong[ulong] map
nebo mapy s pointery jsou na tom
stejně. V ostatních případech musím počítat v průměru s 32B extra na každý pár
klíč/hodnota a to není úplně málo.