Размер узла для сегментов unordered_map - PullRequest
Новая
       23

Размер узла для сегментов unordered_map

0 голосов
/ 08 января 2019

У меня есть программа, в которой я хочу хранить kmers (подстроки размера k) и сколько раз они появляются. Для этого конкретного приложения я читаю в файле с этими значениями, и если число их появления> 255, можно округлить до 255. Я подумал, что если я сохраню пары ключ-значение как (строка , unsigned char), что может сэкономить место по сравнению с сохранением пар ключ-значение в виде (string, int), но, похоже, это не тот случай, когда я проверял максимальный размер резидента, запустив / usr / bin / time.

Для подтверждения я также попытался запустить следующую тестовую программу, в которой я чередовал тип значения в unordered_map: 

#include <iostream>
#include <unordered_map>
#include <utility>
#include <string>
#include <fstream>

int main() {
    std::unordered_map<std::string, unsigned char> kmap;
    std::ifstream infile("kmers_from_reads");
    std::string kmer;
    int abun;

    while(infile >> kmer >> abun) {
        unsigned char abundance = (abun > 255) ? 255 : abun;
        kmap[kmer] = abundance;
    }

    std::cout << sizeof(*kmap.begin(0)) << std::endl; 
}

Похоже, это не повлияло на размер узлов в корзине (на моей машине было возвращено 40 для значений без знака и значения типа int).

Мне было интересно, как определяется размер узлов в каждом сегменте.

Мое понимание неупорядоченных карт состоит в том, что стандарт c ++ более или менее требует отдельной цепочки, и каждый узел в корзине должен иметь хотя бы один указатель, чтобы элементы могли быть повторяемыми и могли быть стерты (http://bannalia.blogspot.com/2013/10/implementation-of-c-unordered.html). Однако Я не понимаю, как определяется объем пространства для хранения значения, и кажется, что он также должен быть гибким для размещения больших значений. Я также попытался посмотреть на заголовок gcc libstc ++ unordered_map (https://github.com/gcc-mirror/gcc/blob/master/libstdc%2B%2B-v3/include/bits/unordered_map.h), но имел трудно понять, что происходит.

1 Ответ

0 голосов
/ 08 января 2019

Скомпилируйте и выполните этот код: 

#include <iostream>
#include <unordered_map>
#include <utility>
#include <string>
#include <fstream>

class foo
{
   std::string kmer;
   unsigned char abun;
};

class bar
{
    std::string kmer;
    int abun;
};

int main() {
    std::cout << sizeof(foo) << " " << sizeof(bar) << std::endl;
}

Я понимаю, и вы, вероятно, тоже, 40 40. Это из-за требований выравнивания. Если, например, std::string содержит хотя бы один указатель (что почти наверняка), он должен быть выровнен по крайней мере на 4-байтовой границе.

Представьте себе, если sizeof(foo) было 39, и у вас был код, который сделал foo foos[2]. Если указатель в foos[0].kmer был правильно выровнен, указатель в foos[1].kmer не был бы. Это было бы катастрофой.

...