0xDEADBEEF

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.