Std::string реализация в GCC и накладные расходы на память для коротких строк

В настоящее время я работаю над приложением для платформы с низкой памятью, для которой требуется std:: set из множества коротких строк ( > 100 000 строк по 4-16 символов). Я недавно перевел этот набор из std::string в const char *, чтобы сохранить память, и мне было интересно, действительно ли я избегаю всех этих накладных расходов на строку.

Я попытался использовать следующее:

std::string sizeTest = "testString";
std::cout << sizeof(sizeTest) << " bytes";

Но он просто дал мне вывод из 4 байтов, указав, что строка содержит указатель. Мне хорошо известно, что строки хранят свои данные в char * внутренне, но я думал, что класс string будет иметь дополнительные накладные расходы.

Указывает ли реализация GCC std::string больше накладных расходов, чем sizeof (std::string)? Что еще более важно, важно ли это для этого размера набора данных?

Ниже приведены размеры соответствующих типов на моей платформе (32-разрядные и 8 бит на каждый байт):

char: 1 байт
void *: 4 байт
char *: 4 байт
std::string: 4 байта

Ответы

Ответ 1

Ну, по крайней мере, с GCC 4.4.5, и это то, что мне удобно в этом machine, std::string является typdef для std::basic_string<char>, и basic_string определяется в /usr/include/c++/4.4.5/bits/basic_string.h. Там много косвенность в этом файле, но к чему это сводится, это непустое std::string сохраните указатель на один из них:

  struct _Rep_base
  {
size_type       _M_length;
size_type       _M_capacity;
_Atomic_word        _M_refcount;
  };

Следование в памяти по фактическим строковым данным. Итак, std::string будет иметь по крайней мере три слова накладных расходов для каждой строки, плюс любые накладные расходы для более высокого capacity, чем `length (возможно не в зависимости от того, как вы строите свои строки - вы можете проверить задав метод capacity()).

Там также будут накладные расходы из вашего распределителя памяти для выполнения множество небольших ассигнований; Я не знаю, что GCC использует для С++, но предполагая, что он аналогичен распределителю dlmalloc, который он использует для C, что может составлять как минимум два слова на выделение, плюс некоторое пространство для выравнивания размер до кратного не менее 8 байтов.

Ответ 2

Я собираюсь угадать, что вы на 32-битной, 8-битной байт-платформе. Я также собираюсь догадаться, что, по крайней мере, на используемой версии gcc, они используют подсчитанную ссылку для std::string. Размер 4 байта, который вы видите, является указателем на структуру, содержащую счетчик ссылок и строковые данные (и любое состояние распределителя, если применимо).

В этом проекте gcc единственная "короткая" строка имеет размер == 0, и в этом случае она может совместно использовать представление с любой другой пустой строкой. В противном случае вы получите refcounted строку COW.

Чтобы выяснить это самостоятельно, введите код распределителя, который отслеживает, сколько памяти он выделяет и освобождает, и сколько раз. Используйте этот распределитель, чтобы исследовать реализацию интересующего контейнера.

Ответ 3

Если он гарантирует, что " > 100 000 строк по 4-16 символов каждый", то не используйте std::string. Вместо этого напишите свой собственный класс ShortString. Интересно, что "sizeof (std::string) == 4", как это возможно? Что такое sizeof (char) и sizeof (void *)?

Ответ 4

Я провел несколько сравнений с служебными данными std::string. В общем, это около 48 байт! Взгляните на статью в своем блоге: http://jovislab.com/blog/?p=76