Подтвердить что ты не робот

Легальность реализации COW std::string в С++ 11

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

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

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

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

4b9b3361

ОТВЕТЫ

Ответ 1

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

- в качестве аргумента любой стандартной библиотечной функции, использующей ссылку to non-const basic_string в качестве аргумента.

- вызов неконстантного функции члена, за исключением оператора [], спереди, сзади, начала, rbegin, end и rend.

Для строки COW вызов non-const operator[] потребует создания копии (и недействительных ссылок), которая запрещена вышеприведенным абзацем. Следовательно, уже не законно иметь строку COW в С++ 11.

Ответ 2

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

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

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

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

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

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

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

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

Ответ 3

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

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

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

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

В заявлении говорится:

Предложение

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

Мы увеличиваем устойчивость операций даже в последовательном коде.

Это изменение эффективно запрещает реализацию копирования на запись.

за которым следует

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

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

Ответ 4

Из 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

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

Ответ 6

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

У меня было время попробовать его сегодня для простого сравнительного теста: карта размера 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

Ответ 7

Запрещен ли COW basic_string на С++ 11 и более поздних версиях?

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

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

Да.

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

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

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

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

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

& hellip; который в реализации COW не мог бы инициировать копирование строковых данных, чтобы разделить значение строки, для стандарта С++ 11 требуется

С++ 11 §21.4.5/4:

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

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

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

Также запрещена ли COW с помощью правил недействительности С++ 11?

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

" Для строки COW для вызова не const operator[] потребуется создать копию (и недействительные ссылки), которая запрещена [приведенным] абзацем выше [С++ 11 §21.4.1/6]. Следовательно, уже не законно иметь строку COW в С++ 11.

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

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

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

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

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

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

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

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

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

С++ 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(), которые возвращают итераторы, первый вызов функций-членов operator[]() operator[](), at(), begin(), rbegin() end() или rend().

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

Что делать, если требования O (1) не учитываются?

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

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

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

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

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

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

Примечания:
¹ Аксессор элемента const запускает копирование данных COW, поскольку он позволяет клиентскому коду получать ссылку или указатель на данные, которые ему не разрешено делать недействительными более поздним копированием данных, вызванным, например, элемент доступа <<29 > .