Каковы некоторые поведенческие аномалии со структурами данных, которые используют подсчет ссылок в STL?

Скотт Мейер в «Эффективном STL» говорит, что при принятии решения о том, какую структуру данных использовать, нужно подумать о том, использует ли контейнер подсчет ссылок или нет. Он говорит, что при таком подходе есть некоторые поведенческие аномалии.

Какие из них? Почему контейнеры типа 'string' и 'веревка' имеют аномальное поведение?

7 голосов | спросил unj2 30 PM00000050000005931 2012, 17:08:59

4 ответа


0

Как уже говорили другие, типичным примером является std::string. Помимо проблем производительности с блокировкой в ​​многопоточных программах, существуют проблемы с потоком без учета строк со счетчиком ссылок. Вообразите это:

string s = "hello";
string t = s;                   // s and t share data
char &c = t[0];                 // copy made here, since t is non-const

Проблема в том, что неконстантный operator[] должен сделать копию строки, если она является общей, поскольку возвращаемая ссылка может быть позже используется для изменения строки (вы можете назначить ее не ссылочной char, но operator[] не знает, что он должен вести себя иначе). С другой стороны, const operator[] следует избегать создания копии, поскольку это исключит все преимущества подсчета ссылок (это будет означать, что вы всегда делаете копию на практике).

const char &get_first(const string &s) {
    return s[0];                // no copy, s is const
}

string s = "hello";
string t = s;                   // s and t share data
const char &c1 = get_first(t);  // no copy made here
const char &c2 = t[0];          // copy made, since t is non-const
// c1 just got invalidated (in fact, it's pointing at s[0], not t[0]).
s[0] = 'X';
printf("%c, %c\n", c1, c2);     // outputs "X, h"

Как видите, это различие сбивает с толку и может привести к действительно неожиданному поведению.

Вот старая статья о семантике копирования при записи и ее влиянии на производительность: http: //www.gotw.ca/gotw/045.htm .

Вот предложение с мотивацией изменить std::string, чтобы он не учитывался в стандарте C ++ 11: http://www.open-std.org/jtc1/sc22/wg21 /документы /документы /2008 /n2534.html . Это то, на чем основан приведенный выше пример.

ответил DS. 27 thEurope/Moscowp30Europe/Moscow09bEurope/MoscowThu, 27 Sep 2012 13:00:47 +0400 2012, 13:00:47
0

В качестве примера одной аномалией, которая может произойти со строками с подсчетом ссылок, в частности строками с обработкой "subpart" (с начальным /конечным срезом), является " неудачная блокировка ".

Представим, что вы выделяете память для всего текста файла. Затем вы анализируете свой файл и используете какой-то метод "slice ()", "left ()", "mid ()" или эквивалентный метод. Вы можете прекратить блокировку всей строки для файла, тогда как, возможно, только очень небольшая его часть содержит фактически текстовые данные (оставшиеся уже проанализированные числа, знаки препинания или что-то еще). Таким образом, вы могли бы использовать больше памяти , чем это необходимо, в конце концов, в то же время легче контролируя пиковое использование. В этом случае может возникнуть вторая проблема, если вы используете многопоточность и интенсивно используете некоторые строки в различных потоках: ненужный конфликт памяти , счетчик ссылок строк может увеличиваться /уменьшаться все раз и атомарность может быть решена, замедляя все потоки.

Однако нет ничего против подсчета ссылок, если вы знаете потенциальные проблемы в вашем приложении и предотвращаете их (в этом случае просто сделайте строки "одними", скопировав их).

ответил armel 30 PM00000060000001231 2012, 18:32:12
0

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

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

Здесь обсуждается вопрос о различных случаях барокко, связанных с умными указателями: http://www.velocityreviews.com/forums/t689414-c-primer-4th-edition-reference-counting-smart-pointers.html р>

ответил emperorz 22 ndEurope/Moscowp30Europe/Moscow09bEurope/MoscowSat, 22 Sep 2012 12:03:56 +0400 2012, 12:03:56
0

В пункте 13 Мейерс подробно описывает проблемы с многопоточностью и пересчетом строк.

Это сильно зависит от точной реализации std::string, блокировки и схемы использования.
может быть проблемой, если явно неопасное использование std::string в многопоточной среде вызывает задержки, поскольку скрытых замков. Наказание таких блокировок и переключений контекста в цикле может быть огромным. Но это никогда не должно вызывать тупиков.
Это не должно быть проблемой. Книге> 10 лет. Тем временем реализации потоков улучшились. Linux-Futexes, например в большинстве случаев вести себя гораздо более плавно.

Еще один момент: (я не знаю, если Мейерс тоже это обсуждал ...)
Пересчитанный std::string означает, что он имеет семантику копирования при записи. Как правило, это хорошо. Фактическая копия откладывается до тех пор, пока она действительно не понадобится. Но это также означает, что цена за копию должна быть заплачена в момент, который, возможно, трудно предсказать.

ответил rtlgrmpf 25 thEurope/Moscowp30Europe/Moscow09bEurope/MoscowTue, 25 Sep 2012 12:56:42 +0400 2012, 12:56:42

Похожие вопросы

Популярные теги

security × 330linux × 316macos × 2827 × 268performance × 244command-line × 241sql-server × 235joomla-3.x × 222java × 189c++ × 186windows × 180cisco × 168bash × 158c# × 142gmail × 139arduino-uno × 139javascript × 134ssh × 133seo × 132mysql × 132