Законность реализации COW std::string в C++11

Question

Законность реализации COW std::string в C++11

Насколько я понимаю, копирование при записи не является жизнеспособным способом реализации соответствующего std::string в C++11, но когда он недавно обсуждался, я не смог напрямую поддержать это утверждение.

Я прав, что C++ 11 не допускает реализации на основе COW std::string?

Если да, указано ли это ограничение явно где-то в новом стандарте (где)?

Или подразумевается это ограничение в том смысле, что оно представляет собой совокупное влияние новых требований на std::string что исключает основанную на COW реализацию std::string, В этом случае, я бы заинтересовался выводом стиля главы и стиха из C++11, эффективно запрещающего COW на основе std::string Реализации.

130

c++ string c++11 stdstring copy-on-write

Источник

user776473 30 авг '12 в 14:54

6 ответов

Решение

Ответы Дэйва С и Гбджаанба верны. (И Люк Дантон тоже прав, хотя это скорее побочный эффект запрета строк COW, чем оригинальное правило, которое запрещает это.)

Но чтобы устранить некоторую путаницу, я собираюсь добавить дальнейшее изложение. Различные комментарии ссылаются на мой комментарий на bugzilla GCC, который дает следующий пример:

std::string s("str");
const char* p = s.data();
{
    std::string s2(s);
    (void) s[0];
}
std::cout << *p << '\n';  // p is dangling

Цель этого примера - продемонстрировать, почему строка подсчета ссылок (COW) в GCC недопустима в C++11. Стандарт C++ 11 требует, чтобы этот код работал правильно. Ничто в коде не позволяет p быть признанным недействительным в C++11.

Использование GCC по старым ссылкам std::string реализация, этот код имеет неопределенное поведение, потому что p становится недействительным и становится висящим указателем. (Что происходит, когда s2 построен он делится данными с s, но получение неконстантной ссылки через s[0] требует, чтобы данные были недоступны, поэтому s делает "копировать при записи", потому что ссылка s[0] потенциально может быть использован для записи в s, затем s2 выходит из области видимости, уничтожая массив, на который указывает p).

Стандарт C++03 явно разрешает такое поведение в 21.3 [lib.basic.string] p5, где говорится, что после вызова data() первый звонок operator[]() может сделать недействительными указатели, ссылки и итераторы. Таким образом, строка COW в GCC была допустимой реализацией C++03.

Стандарт C++ 11 больше не допускает такого поведения, потому что нет вызова operator[]() может сделать недействительными указатели, ссылки или итераторы, независимо от того, следуют ли они за вызовом data(),

Таким образом, приведенный выше пример должен работать в C++11, но не работает со строкой COW в libstdC++, поэтому этот тип COW не разрешен в C++11.

57

Источник

user981959 22 мар '15 в 20:55

Это CoW - приемлемый механизм для создания более быстрых струн... но...

это замедляет многопоточность кода (все эти блокировки, чтобы проверить, что вы пишете только один, снижают производительность при использовании большого количества строк). Это было главной причиной того, что CoW был убит много лет назад.

Другие причины в том, что [] Оператор вернет вам строковые данные, без какой-либо защиты для вас, чтобы перезаписать строку, которую кто-то еще ожидает изменить. То же самое относится и к c_str() а также data(),

Быстрый Google говорит, что многопоточность - в основном причина, по которой это было фактически запрещено (не явно).

Предложение говорит:

Предложение
Мы предлагаем сделать все операции доступа к итераторам и элементам безопасными одновременно выполняемыми.
Мы повышаем стабильность операций даже в последовательном коде.
Это изменение фактически запрещает реализации копирования при записи.

с последующим

Наибольшая потенциальная потеря производительности из-за перехода от реализаций копирования при записи - это повышенное потребление памяти для приложений с очень большими строками, в основном для чтения. Тем не менее, мы считаем, что для этих применений канаты являются лучшим техническим решением, и рекомендуем рассмотреть предложение по канатам для включения в библиотеку TR2.

Канаты являются частью STLPort и SGIs STL.

21

Источник

user13744 30 авг '12 в 15:01

Из 21.4.2 конструкторы basic_string и операторы присваивания [string.cons]

basic_string(const basic_string<charT,traits,Allocator>& str);
[...]
2 Эффекта: Создает объект класса basic_string как указано в таблице 64. [...]

Таблица 64 содержит полезную информацию о том, что после построения объекта с помощью этого (копирования) конструктор, this->data() имеет в качестве значения:

указывает на первый элемент выделенной копии массива, на первый элемент которого указывает str.data()

Есть аналогичные требования для других подобных конструкторов.

5

Источник

user726300 30 авг '12 в 15:02

Корова `basic_string` запрещено в C++11 и позже?

относительно

Я прав, что C++11 не допускает реализации на COW std::string?

Да.

относительно

Если да, указано ли это ограничение явно где-то в новом стандарте (где)?

Почти напрямую, в соответствии с требованиями постоянной сложности для ряда операций, которые потребовали бы O (n) физического копирования строковых данных в реализации COW.

Например, для функций-членов

auto operator[](size_type pos) const -> const_reference;
auto operator[](size_type pos) -> reference;

… Который в реализации COW будет "запускать" копирование строковых данных для разглашения строкового значения, стандарт C++11 требует

C++11 §21.4.5 / 4:

Сложность: постоянное время.

... что исключает такое копирование данных и, следовательно, COW.

C++03 поддерживал реализации COW, не имея этих требований постоянной сложности, и, при определенных ограничивающих условиях, разрешал вызовы operator[](), at(), begin(), rbegin(), end(), или же rend() аннулировать ссылки, указатели и итераторы, ссылающиеся на строковые элементы, т. е. возможно копировать данные COW. Эта поддержка была удалена в C++11.

Также запрещены COW через правила аннулирования C++11?

В другом ответе, который на момент написания статьи был выбран в качестве решения, и который получил серьезное одобрение и поэтому, по-видимому, считается, утверждается, что

Для строки COW, вызывая constoperator[] потребует создания копии (и аннулирования ссылок), что запрещено [цитируемым] параграфом выше [C++11 §21.4.1/6]. Следовательно, больше не разрешено иметь строку COW в C++11.

Это утверждение неверно и вводит в заблуждение двумя основными способами:

Это неверно указывает на то, что только const Средства доступа к элементам должны запускать копирование данных COW.
Но также const Средства доступа к элементам должны инициировать копирование данных, потому что они позволяют клиентскому коду формировать ссылки или указатели, которые (в C++11) не разрешаются позднее для аннулирования посредством операций, которые могут инициировать копирование данных COW.
Это неправильно предполагает, что копирование данных COW может вызвать недействительность ссылки.
Но в правильной реализации копирование данных COW, не разделяя строковое значение, выполняется в момент, когда есть какие-либо ссылки, которые могут быть признаны недействительными.

Чтобы увидеть, как правильно C++11 COW реализация basic_string будет работать, когда требования O(1), которые делают этот недействительным, игнорируются, подумайте о реализации, где строка может переключаться между политиками владения. Экземпляр строки начинается с политики Sharable. Если эта политика активна, ссылки на внешние элементы не могут быть. Экземпляр может перейти к уникальной политике, и он должен сделать это, когда ссылка на элемент потенциально создается, например, с помощью вызова .c_str() (по крайней мере, если это производит указатель на внутренний буфер). В общем случае, когда несколько экземпляров совместно используют владельца значения, это влечет за собой копирование строковых данных. После этого перехода к уникальной политике экземпляр может вернуться обратно к Sharable только с помощью операции, которая делает недействительными все ссылки, такие как назначение.

Таким образом, хотя вывод этого ответа о том, что строки COW исключены, является верным, предлагаемые аргументы неверны и сильно вводят в заблуждение.

Я подозреваю, что причиной этого недоразумения является ненормативная заметка в приложении C к C++11:

C++11 §C.2.11 [diff.cpp03.strings], о §21.3:

Изменить: basic_string требования больше не позволяют строки с подсчетом ссылок
Обоснование: Invalidation несколько отличается от строк с подсчетом ссылок. Это изменение регулирует поведение (sic) для этого международного стандарта.
Эффект на оригинальную особенность: действительный код C ++ 2003 может выполняться по-разному в этом международном стандарте

Здесь обоснование объясняет основную причину, по которой решили удалить специальную поддержку CW для C++03. Это обоснование, почему, не в том, как стандарт эффективно запрещает внедрение COW. Стандарт запрещает COW через требования O(1).

Короче говоря, правила аннулирования C++11 не исключают реализацию COW std::basic_string, Но они исключают достаточно эффективную неограниченную реализацию COW в стиле C++03, такую как, по крайней мере, в одной из стандартных реализаций библиотеки g++. Специальная поддержка C++03 COW обеспечила практическую эффективность, в частности использование const средства доступа к элементам за счет тонких, сложных правил признания недействительными:

C++03 §21.3 / 5, который включает поддержку COW "первого вызова":

Ссылки, указатели и итераторы, ссылающиеся на элементы basic_string последовательность может быть признана недействительной из-за следующих basic_string объект:
- в качестве аргумента для функций, не являющихся членами swap() (21.3.7.8), operator>>() (21.3.7.9) и getline() (21.3.7.9).
- В качестве аргумента basic_string::swap(),
- звоню data() а также c_str() функции-члены.
- Вызов не const функции-члены, кроме operator[](), at(), begin(), rbegin(), end(), а также rend(),
- После любого из вышеуказанных видов использования, кроме форм insert() а также erase() которые возвращают итераторы, первый вызов const функции-члены operator[](), at(), begin(), rbegin(), end(), или же rend(),

Эти правила настолько сложны и тонки, что я сомневаюсь, что многие программисты, если таковые имеются, могли бы дать точное резюме. Я не мог.

Что если требования O(1) игнорируются?

Если C++11 постоянное время требования, например, operator[] игнорируются, то COW для basic_string может быть технически осуществимым, но трудно осуществимым.

Операции, которые могут получить доступ к содержимому строки без копирования COW-данных, включают в себя:

Конкатенация через +,
Выход через <<,
Используя basic_string в качестве аргумента для стандартных библиотечных функций.

Последнее потому, что стандартной библиотеке разрешено полагаться на специфические для реализации знания и конструкции.

Кроме того, реализация может предлагать различные нестандартные функции для доступа к содержимому строки без запуска копирования данных COW.

Основным усложняющим фактором является то, что в C++11 basic_string доступ к элементу должен инициировать копирование данных (не разделяя строковые данные), но требуется не выбрасывать, например, C++11 §21.4.5/3 " Броски: ничего". И поэтому он не может использовать обычное динамическое выделение для создания нового буфера для копирования данных COW. Одним из способов решения этой проблемы является использование специальной кучи, где память может быть зарезервирована без фактического выделения, а затем зарезервировать необходимое количество для каждой логической ссылки на строковое значение. Резервирование и отмена резервирования в такой куче может быть постоянным временем, O(1), и выделение суммы, которую уже зарезервировано, может быть noexcept, Чтобы соответствовать требованиям стандарта, при таком подходе, по-видимому, должна быть одна такая специальная куча на основе резервирования для каждого отдельного распределителя.

^{Заметки:} ^¹ const ^{средство доступа к элементу запускает копирование данных COW, поскольку оно позволяет клиентскому коду получить ссылку или указатель на данные, которые нельзя разрешить аннулировать при более позднем копировании данных, инициированном, например, не} const ^{элемент доступа.}

5

Источник

user464581 29 июл '16 в 05:53

Поскольку теперь гарантируется, что строки хранятся смежно, и теперь вы можете получить указатель на внутреннее хранилище строки (т.е. &str[0] работает так же, как и для массива), сделать полезную COW невозможно реализация. Вам придется сделать копию для слишком многих вещей. Даже просто используя operator[] или же begin() для неконстантной строки потребуется копия.

2

Источник

user1568792 30 авг '12 в 15:00

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

У меня было время попробовать это сегодня для простого сравнительного теста: карта размера N с ключом строка / корова, где каждый узел содержит набор всех строк на карте (у нас есть количество объектов NxN).

Со строками размером ~300 байт и N=2000 коровы работают немного быстрее и используют почти на порядок меньше памяти. См. Ниже, размеры указаны в килобайтах, пробег с коровами.

~/icow$ ./tst 2000
preparation a
run
done a: time-delta=6 mem-delta=1563276
preparation b
run
done a: time-delta=3 mem-delta=186384

-1

Источник

user194305 16 окт '19 в 04:06

Другие вопросы по тегам c++ string c++11 stdstring copy-on-write

user862231 30 авг '12 в 15:06 2012-08-30 15:06 · Accepted Answer · 2012-08-30 15:06

Это не разрешено, потому что согласно стандарту 21.4.1 p6, аннулирование итераторов / ссылок разрешено только для

- в качестве аргумента любой стандартной библиотечной функции, принимающей ссылку на неконстантную basic_string в качестве аргумента.
- Вызов неконстантных функций-членов, кроме оператора [], at, front, back, begin, rbegin, end и rend.

Для строки COW вызов неконстантного operator[] потребует создания копии (и аннулирования ссылок), что запрещено параграфом выше. Следовательно, больше не разрешено иметь строку COW в C++11.

Законность реализации COW std::string в C++11

6 ответов

Корова basic_string запрещено в C++11 и позже?

Также запрещены COW через правила аннулирования C++11?

Что если требования O(1) игнорируются?

Корова `basic_string` запрещено в C++11 и позже?