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

117

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

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

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

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

ACM
источник
5
Ошибка GCC для их строки COW - gcc.gnu.org/bugzilla/show_bug.cgi?id=21334#c45 . Одна из ошибок, отслеживающих новую компилирующую реализацию C ++ 11 std :: string в libstdc ++, - это gcc.gnu.org/bugzilla/show_bug.cgi?id=53221
user7610

Ответы:

120

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

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

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

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

Дэйв С.
источник
4
Некоторое обоснование: N2534
MM
8
-1 Логика не выдерживает критики. Во время копирования COW нет ссылок или итераторов, которые могут быть признаны недействительными, весь смысл копирования заключается в том, что такие ссылки или итераторы теперь получены, поэтому копирование необходимо. Но все еще может быть, что C ++ 11 запрещает реализации COW.
Приветствия и hth. - Alf
11
@ Cheersandhth.-Alf: Логику можно увидеть в следующем, если COW была разрешена: std::string a("something"); char& c1 = a[0]; std::string b(a); char& c2 = a[1]; c1 - это ссылка на a. Затем вы «копируете» файл. Затем, когда вы пытаетесь взять ссылку во второй раз, он должен сделать копию, чтобы получить неконстантную ссылку, поскольку есть две строки, которые указывают на один и тот же буфер. Это должно сделать недействительной первую взятую ссылку и противоречит приведенному выше разделу.
Dave S
9
@ Cheersandhth.-Alf, согласно этому , по крайней мере, реализация COW GCC делает именно то, что говорит DaveS. По крайней мере, этот стиль КОРОВЫ запрещен стандартом.
Тавиан Барнс
4
@Alf: Этот ответ утверждает, что неконстантный operator[](1) должен делать копию и что (2) это незаконно. С каким из этих двух пунктов вы не согласны? Глядя на ваш первый комментарий, кажется, что реализация может совместно использовать строку, по крайней мере, в соответствии с этим требованием, до момента обращения к ней, но что при доступе как для чтения, так и для записи необходимо будет отменить ее. Это ваше рассуждение?
Бен Фойгт,
48

Ответы на Dave S и gbjbaanb являются правильными . (И Люк Дантон тоже прав, хотя это скорее побочный эффект запрета строк 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.

Используя старую std::stringреализацию GCC с подсчетом ссылок , этот код имеет неопределенное поведение, потому что 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 в libstdС ++, поэтому такая строка COW не разрешена в C ++ 11.

Джонатан Уэйкли
источник
3
Реализация, которая отменяет совместное использование при вызове .data()(и при каждом возврате указателя, ссылки или итератора), не страдает от этой проблемы. Т.е. (инвариантный) буфер в любой момент не используется совместно, либо используется совместно без внешних ссылок. Я думал, что вы задумали комментарий об этом примере как неформальный отчет об ошибке в виде комментария, очень извиняюсь за недопонимание! Но, как вы можете видеть, рассматривая описанную здесь реализацию, которая отлично работает в C ++ 11, когда noexceptтребования игнорируются, в примере ничего не говорится о формальном. Я могу предоставить код, если хотите.
Приветствия и hth. - Alf
7
Если вы закрываете доступ почти при каждом доступе к строке, вы теряете все преимущества совместного использования. Реализация COW должна быть практичной, чтобы стандартная библиотека беспокоилась об использовании этого as std::string, и я искренне сомневаюсь, что вы сможете продемонстрировать полезную, производительную строку COW, которая соответствует требованиям C ++ 11 к недействительности. Поэтому я утверждаю, что noexceptспецификации, которые были добавлены в последнюю минуту, являются следствием запрета строк COW, а не основной причиной. N2668 кажется совершенно ясным, почему вы продолжаете отрицать явные доказательства намерений комитета, изложенные там?
Джонатан Уэйкли,
Также помните, что data()это константная функция-член, поэтому ее следует безопасно вызывать одновременно с другими константными членами и, например, вызывать data()одновременно с другим потоком, создающим копию строки. Таким образом, вам понадобятся все накладные расходы на мьютекс для каждой строковой операции, даже константной, или сложность изменяемой структуры с подсчетом ссылок без блокировок, и, в конце концов, вы получите общий доступ только в том случае, если вы никогда не изменяете или не получаете доступа ваши строки, так много-много строк будут иметь счетчик ссылок, равный единице. Пожалуйста, предоставьте код, не стесняйтесь игнорировать noexceptгарантии.
Джонатан Уэйкли,
2
Теперь, просто собирая код, я обнаружил, что есть 129 basic_stringфункций-членов плюс бесплатные функции. Стоимость абстракции: этот нестандартный неоптимизированный свежий код нулевой версии на 50–100% медленнее как с g ++, так и с MSVC. Он не обеспечивает потокобезопасность ( shared_ptrя думаю, достаточно легко использовать ), и этого достаточно для поддержки сортировки словаря для целей синхронизации, но по модулю ошибок он доказывает, что подсчет ссылок basic_stringразрешен, за исключением noexceptтребований C ++ . github.com/alfps/In-principle-demo-of-ref-counted-basic_string
Ура и hth. - Alf
1
Давайте продолжим эту дискуссию в чате .
Джонатан Уэйкли,
20

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

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

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

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

В предложении говорится:

Предложение

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

Повышаем стабильность работы даже в последовательном коде.

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

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

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

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

gbjbaanb
источник
2
Проблема с оператором [] на самом деле не проблема. Вариант const предлагает защиту, а вариант неконстантный всегда имеет возможность выполнить CoW в это время (или быть действительно сумасшедшим и настроить отказ страницы для его запуска).
Кристофер Смит
+1 Переходит к вопросам.
Приветствия и hth. - Alf
5
просто глупо, что класс std :: cow_string не был включен, с lock_buffer () и т.д., я много раз знаю, что многопоточность не является проблемой. на самом деле чаще всего.
Эрик Аронести
Мне нравится предложение альтернативы, например, веревки. Интересно, есть ли какие-либо другие альтернативные типы и реализации.
Вольтер
5

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

basic_string(const basic_string<charT,traits,Allocator>& str);

[...]

2 Эффекты : Создает объект класса, basic_stringкак указано в Таблице 64. [...]

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

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

Аналогичные требования предъявляются и к другим аналогичным конструкторам.

Люк Дантон
источник
+1 Объясняет, как C ++ 11 (хотя бы частично) запрещает COW.
Приветствия и hth. - Alf
Извини, я устал. Это не объясняет ничего, кроме того, что вызов .data () должен запускать копирование COW, если буфер в настоящее время используется совместно. Тем не менее, это полезная информация, поэтому я оставлю голос за.
Приветствия и hth. - Alf
1

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

Дирк Холсоппл
источник
1
Я думаю, что строки в С ++ 11 гарантированно хранятся непрерывно.
mfontanini
4
Раньше вам приходилось делать копии во всех этих ситуациях, и это не было проблемой ...
Дэвид Родригес - dribeas
@mfontanini да, но раньше их не было
Дирк Холсопл
3
Хотя C ++ 11 действительно гарантирует, что строки являются смежными, это ортогонально запрету строк COW. Строка COW в GCC является непрерывной, поэтому ясно, что ваше утверждение о том, что «невозможно создать полезную реализацию COW», является подделкой.
Джонатан Уэйкли,
1
@supercat, запрос резервного хранилища (например, путем вызова c_str()) должен быть O (1) и не может отбрасывать, и не должен вводить гонки данных, поэтому очень сложно удовлетворить эти требования, если вы лениво объединяете. На практике единственный разумный вариант - всегда хранить непрерывные данные.
Джонатан Уэйкли,
1

basic_stringЗапрещена ли COW в 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 требует

С ++ 11 §21.4.5 / 4 :

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

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

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


Является ли COW также запрещенным правилами аннулирования C ++ 11?

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

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

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

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

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

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

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

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

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

Здесь обоснование объясняет, почему было решено удалить специальную поддержку COW в 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 for basic_stringможет быть технически осуществимым, но трудным для реализации.

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

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

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

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

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


Примечания:
¹ Средство constдоступа к элементам запускает копирование данных COW, потому что оно позволяет клиентскому коду получить ссылку или указатель на данные, которые не разрешается аннулировать путем последующего копирования данных, инициированного, например, средством constдоступа, не являющимся элементом.

Приветствия и hth. - Альф
источник
3
« Ваш пример - хороший пример неправильной реализации для C ++ 11. Возможно, он был правильным для C ++ 03». Да в этом суть примера . Он показывает строку COW, которая была разрешена в C ++ 03, потому что она не нарушает старые правила аннулирования итератора, и недопустима в C ++ 11, поскольку нарушает новые правила аннулирования итератора. И это также противоречит утверждению, которое я цитировал в комментарии выше.
Джонатан Уэйкли,
2
Если бы вы сказали, что общий доступ не используется изначально, я бы не стал спорить. Сказать, что кто-то изначально поделился, просто сбивает с толку. Поделился с самим собой? Это слово означает не это. Но я повторяю: ваша попытка доказать, что правила аннулирования итератора C ++ 11 не запрещают некоторую гипотетическую строку COW, которая никогда не использовалась на практике (и имела бы неприемлемую производительность), хотя они наверняка запрещают такую ​​строку COW то, что использовалось на практике, несколько академично и бессмысленно.
Джонатан Уэйкли,
5
Предлагаемая вами строка COW интересна, но я не уверен, насколько она будет полезна . Смысл строки COW состоит в том, чтобы копировать строковые данные только в том случае, если в них записываются две строки. Предлагаемая вами реализация требует копирования при выполнении любой пользовательской операции чтения. Даже если компилятор знает, что это только чтение, он все равно должен копировать. Кроме того, копирование уникальной строки приведет к копированию ее строковых данных (предположительно в состояние Sharable), что снова делает COW бессмысленным. Таким образом, без гарантий сложности вы могли бы написать ... действительно дрянную строку COW.
Никол Болас
2
Итак, хотя вы технически правы в том, что гарантии сложности - это то, что мешает вам писать любую форму COW, на самом деле [basic.string] / 5 мешает вам написать любую действительно полезную форму строки COW.
Никол Болас
4
@JonathanWakely: (1) Ваша цитата не вопрос. Вот вопрос: «Правильно ли я, что C ++ 11 не допускает реализации std :: string на основе COW? Если да, то указано ли это ограничение явно где-нибудь в новом стандарте (где)? » (2) Ваше мнение, что COW std::stringпри игнорировании требований O (1) будет неэффективным, - это ваше мнение. Я не знаю, каким может быть выступление, но я думаю, что это утверждение выдвигается скорее из-за ощущения его, из-за вибрации, которую оно передает, чем из-за какого-либо отношения к этому ответу.
Приветствия и hth. - Альф,
0

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

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