Здравствуйте, e-Xecutor, Вы писали:

EX>Здравствуйте, Шахтер, Вы писали:


Ш>>Это каких, обычных? Если реализация string клонирует строку при копировании, это значит -- кривая реализация.


EX>Если реализация std::string сделана с подсчётом ссылок,
EX>то отрывать руки надо за такую реализацию.

EX>Жил был очень многопоточный проект.

Я извиняюсь, но никаких гарантий касающихся многопоточности стандарт относительно класса string не даёт, так что разработчики библиоткеки вольны делать любую реализацию. А руки надо отрывать людям, которые его бездумно использовали.

Копай Нео, копай -- летать научишься. © Matrix. Парадоксы

Здравствуйте, MaximE, Вы писали:

>> А вообще пора вернуться к теме. В оригинальном примере применение строк, основанных на использовании счётчика ссылок, -- это то что доктор прописал. Причем, как я понял, вполне достаточно немутирующих строк -- соответсвенно, никаких проблем с COW нет.

ME>Как раз про это и пишет Kevlin Henney в вышеупомянутой статье. Стандартный класс строк спроектирован неряшливо — перегруженный интерефейс, слишком много функционала, чтобы сделать этот класс эффективным. От того и проблема, что когда стандартную строку хотят оптимизировать при помощи COW, приходится запихивать в нее синхронизацию, так как многопоточный код пишется в расчете на то, что строка "тупая" — будет копироваться, когда ее передают по значению.

ME>--
ME>Maxim Yegorushkin

А зачем он так пишется? Ну в конце концов, можно сделать две реализации -- одна быстрая, а вторая -- специально для тупо написанного многопоточного кода. Может я слишком много хочу от программистов?

Копай Нео, копай -- летать научишься. © Matrix. Парадоксы

Здравствуйте, Шахтер, Вы писали:

Ш>Да здесь не нужен проект. Скорее -- ФАК, как писать строки, как впрочем и другие контейнеры. Я этого добра написал столько, что теперь всё что мне нужно пишу чуть ли не с закрытими глазами: берётся код из архива, скрещивается, мутируется, дорабатывем напильником -- и готово.

Делись!

Шахтер:

> ПК>Разве что, в большинстве случаев прикладного программирования это совершенно неэффективно с точки зрения соотношения производительность/стоимость разработки.

> Вы неправильно считаете деньги. Это делается один раз -- хорошо. Или много раз плохо. В рамках написания очередной "экспертной" реализации stl.

Это не хорошо/плохо. Это одним/другим способом. Все зависит от того, какое поведение принять по умолчанию.

> ПК> в большинстве приложений копирование строк и близко не появляется в первой сотне функций, выделенных профайлером.

> А вот я, например, не делаю это большинство. Мне регулярно приходится заниматься задачами, где производительность принципиальна.

Обрати внимание: "копирование строк и близко не появляется в первой сотне функций, выделенных профайлером" и "производительность принципиальна" не являются противопоставлениями.

Здравствуйте, adontz, Вы писали:

A>Здравствуйте, Шахтер, Вы писали:

Ш>>Да здесь не нужен проект. Скорее -- ФАК, как писать строки, как впрочем и другие контейнеры. Я этого добра написал столько, что теперь всё что мне нужно пишу чуть ли не с закрытими глазами: берётся код из архива, скрещивается, мутируется, дорабатывем напильником -- и готово.

A>Делись!

Знаешь, есть такое слово -- копирайт. Я вот, например, люблю использовать такой немудрящий класс:

class NoCopy
 {
   NoCopy(const NoCopy &) {} 
   void operator = (const NoCopy &) {}
 
  public:
  
   NoCopy() {}
 };

Я его написал 14 лет назад, и с тех пор он у меня по всем проектам кочует. А копирайты на этих проектах разные. Вот я и думаю, а не случится ли чего... Особенно, если я буду публично код свой показывать. А если код не такой тривиальный? Засудют ещё. За нарушение авторских прав в цифровую эпоху.

Копай Нео, копай -- летать научишься. © Matrix. Парадоксы

Здравствуйте, Шахтер, Вы писали:

A>>Делись!
Ш>Знаешь, есть такое слово -- копирайт.

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

c-smile:

> ПК>...Don't fix what isn't broken...

> А если дизайн broken изначально? Или не подходит к задачам реального мира в 70% случаев?

Мне кажется, с процентами ты немного преувеличил

> Пример: XML/HTML — аттрибуты и их значения повторяются примерно на 70-90% в одном документе. Слепая имплементация в стиле <...> Ведет к неоправданному перерасходу ресурсов и чудовищной неэффективности.

Так не надо слепо, смотреть нужно...

> Попытка имплементации "как должно" (интернирование строк например) средствами стандартной библиотеки приводит к неуклюжим, неэффективным и эмпирически недоказуемым конструкциям.

Во как, но ведь о 70% же доказал

Шахтер:

> в конце концов, можно сделать две реализации -- одна быстрая, а вторая -- специально для тупо написанного многопоточного кода. Может я слишком много хочу от программистов?

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

Здравствуйте, Шахтер, Вы писали:

Ш>Здравствуйте, e-Xecutor, Вы писали:

EX>>Здравствуйте, Шахтер, Вы писали:


Ш>>>Это каких, обычных? Если реализация string клонирует строку при копировании, это значит -- кривая реализация.


EX>>Если реализация std::string сделана с подсчётом ссылок,
EX>>то отрывать руки надо за такую реализацию.

EX>>Жил был очень многопоточный проект.

Ш>Я извиняюсь, но никаких гарантий касающихся многопоточности стандарт относительно класса string не даёт, так что разработчики библиоткеки вольны делать любую реализацию. А руки надо отрывать людям, которые его бездумно использовали.

Стандарт вообще штука скользкая...
Там много чего недоговорено.
Вот про std::list ничего не сказано про сложность функции size(), дык
некоторые имплементации делают её O(n). Сюрприз еще тот...
ИМХО _нормальная_ реализация stl должна содержать как можно меньше всяких side effect-ов.
то, что после
std::string a="hello";
std::string b=a;

a и b чем-то связаны, это не совсем ожидаемое поведение от строки...
учитывая, что в стандарте ничего про подсчёт ссылок нет,
и как следствие никаких гарантированных средств расклеивания тоже нет...
По крайней мере средств без накладняков...

Здравствуйте, Павел Кузнецов, Вы писали:

ПК>Шахтер:

>> в конце концов, можно сделать две реализации -- одна быстрая, а вторая -- специально для тупо написанного многопоточного кода. Может я слишком много хочу от программистов?

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

Ну на счет эффективности никогда нельзя быть субъективным
я например искренне верил что копирование миллиона строк должно
быть медленнее чем работа со счетчиком ссылок .
После небольшого эксперимента я был просто в шоке.
Теперь я понял в чем была аргументация авторов клонирующей реализации:
для недлинных строк разницу между копированием и чистым cow
обнаружить _НЕВОЗМОЖНО_. И этому есть простое объяснение.

Короткое резюме — менять строки изменяя storage policy это хорошо
необходимость в этом возникает только если все совсем плохо
те либо не хватает памяти либо нужно выжать _все_ что есть.

"Даешь полиси базед стандард лайбрэри!"

best regards

Здравствуйте, Шахтер, Вы писали:

Ш>Я видел реализации с подсчетом ссылок. Давно правда это было.

ИМХО, счастье, что давно. Целиком согласен с аргументами, что в большинстве реальных приложений reference counting для строк ничего кроме дополнительных тормозов, либо огромого потенциала для глюков в MT не дает.
И reference counting не уменьшает сложность копирования до O(1). Он просто переносит это копирование на этап записи.

A>>Максимум это то, что копирование скорее всего сделано не в цикле по элементам, а с помошью memmove. Но в любом случае никакого подсчёта ссылок там нет. Так что ты жестоко ошибался.

Ш>Повторю ещё раз. Я НЕ пользуюсь stl. Одна из причин, что не никаких гарантий, как реализован там тот или иной класс.

Интересно, насколько это реально оправдано в твоем случае?

Здравствуйте, Шахтер, Вы писали:

Ш>Я извиняюсь, но никаких гарантий касающихся многопоточности стандарт относительно класса string не даёт, так что разработчики библиоткеки вольны делать любую реализацию. А руки надо отрывать людям, которые его бездумно использовали.

Есть такая вещь, как нормальное ожидание поведения объекта. От operator= программист обычно ожидает, что будет создана копия объекта, поскольку именно так ведут себя все встроенные типы. Ты предлагаешь поменять нормальную семантику оператора = и заставить программиста думать на каждом шаге о синхронизации? Как тебе уже сказали, ни к чему кроме трудноуловимых и дорогостоящих глюков это не приведет.

Здравствуйте, Lexey, Вы писали:

L>Здравствуйте, Шахтер, Вы писали:

Ш>>Я извиняюсь, но никаких гарантий касающихся многопоточности стандарт относительно класса string не даёт, так что разработчики библиоткеки вольны делать любую реализацию. А руки надо отрывать людям, которые его бездумно использовали.

L>Есть такая вещь, как нормальное ожидание поведения объекта. От operator= программист обычно ожидает, что будет создана копия объекта, поскольку именно так ведут себя все встроенные типы. Ты предлагаешь поменять нормальную семантику оператора = и заставить программиста думать на каждом шаге о синхронизации? Как тебе уже сказали, ни к чему кроме трудноуловимых и дорогостоящих глюков это не приведет.

Уважаемые други, а все таки, о какой такой навороченной синхронизации вот уже не первый день идет речь — может не так страшен черт как его малюют?

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

Здравствуйте, Batiskaf, Вы писали:

B>Уважаемые други, а все таки, о какой такой навороченной синхронизации вот уже не первый день идет речь — может не так страшен черт как его малюют?

Да вроде как уже все расписали. Если реализовывать подсчет ссылок, то increment, decrement и (что самое фиговое) COW придется синхронизировать внутри самой реализации std:string. Это довольно сильно снизит эффективность.

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

Это да, только не так уж и часто это бывает реально нужно.

Здравствуйте, Lexey, Вы писали:

L>Здравствуйте, Batiskaf, Вы писали:

B>>Уважаемые други, а все таки, о какой такой навороченной синхронизации вот уже не первый день идет речь — может не так страшен черт как его малюют?

L>Да вроде как уже все расписали. Если реализовывать подсчет ссылок, то increment, decrement и (что самое фиговое) COW придется синхронизировать внутри самой реализации std:string. Это довольно сильно снизит эффективность.

Ок, инкремент/декремент это не так дорого, кажется на 86 процессорах есть команда блокирования прерываний, для атомарной операции с каунтерами этого достаточно, на других типах процессоров уверен есть аналоги. И все! Больше ничего синхронизировать не нужно, буфер то все равно ни один экземпляр строки не имеет права модифицировать, каждое модифицирование выливается в построение нового буфера, в этом то прикол COW.

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

L>Это да, только не так уж и часто это бывает реально нужно.
Ну если строки не модифицируются, значит они чаще всего передаются, использование стратегии COW тем более существенно улучшит перформенс, а хранение стринга одновременно в разных списках еще и приведет к экономичному использованию динамической памяти.

Здравствуйте, Batiskaf, Вы писали:

L>>Да вроде как уже все расписали. Если реализовывать подсчет ссылок, то increment, decrement и (что самое фиговое) COW придется синхронизировать внутри самой реализации std:string. Это довольно сильно снизит эффективность.

B>Ок, инкремент/декремент это не так дорого, кажется на 86 процессорах есть команда блокирования прерываний, для атомарной операции с каунтерами этого достаточно, на других типах процессоров уверен есть аналоги. И все! Больше ничего синхронизировать
B> не нужно, буфер то все равно ни один экземпляр строки не имеет права модифицировать, каждое модифицирование выливается в построение нового буфера, в этом то прикол COW.

Да, насчет COW ты прав. Но InterlockedIncrement/Decrement на самом деле тоже не такая уж и дешевая операция. По Рихтеру порядка 50 тактов.

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

L>>Это да, только не так уж и часто это бывает реально нужно.
B>Ну если строки не модифицируются, значит они чаще всего передаются, использование стратегии COW тем более существенно улучшит перформенс, а хранение стринга одновременно в разных списках еще и приведет к экономичному использованию динамической памяти.

Если они не модифицируются, то наиболее эффективно их передавать по константной ссылке.

Здравствуйте, e-Xecutor, Вы писали:

EX>>>Жил был очень многопоточный проект.

Ш>>Я извиняюсь, но никаких гарантий касающихся многопоточности стандарт относительно класса string не даёт, так что разработчики библиоткеки вольны делать любую реализацию. А руки надо отрывать людям, которые его бездумно использовали.

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

EX>Стандарт вообще штука скользкая...
EX>Там много чего недоговорено.
EX>Вот про std::list ничего не сказано про сложность функции size(), дык
EX>некоторые имплементации делают её O(n). Сюрприз еще тот...
EX>ИМХО _нормальная_ реализация stl должна содержать как можно меньше всяких side effect-ов.
EX>то, что после

EX>std::string a="hello";
EX>std::string b=a;

EX>a и b чем-то связаны, это не совсем ожидаемое поведение от строки...
EX>учитывая, что в стандарте ничего про подсчёт ссылок нет,
EX>и как следствие никаких гарантированных средств расклеивания тоже нет...
EX>По крайней мере средств без накладняков...

Накладняк состоит в том, что операции чтения и изменения счётчика ссылок (используемого для Copy-On-Write), во-первых, должны быть, а во-вторых, должны быть interlocked.
Каждое изменение объекта либо получение доступа с правом записи (например, operator[]) выполняет COW. Это, конечно, тягостно.

Поэтому, что действительно было бы полезно — так это явно управлять COW'ом. Например, сделать обёртку вида

template<class T>
class cowboy // парадокс: несколько ковбоев пасут одну корову :))
{
public:
    cowboy(); // разделяет общие дефолтные данные
    cowboy(const T& data); // клонирует
    cowboy(const cowboy& buddy); // разделяет данные с партнёром (если тот не монополист), либо клонирует
    
    cowboy& operator=(const T& data); // клонирует
    cowboy& operator=(const cowboy& buddy); // разделяет либо клонирует
    
    ~cowboy(); // отпускает (возможно, удаляет)
    
    const T& get() const; // ничего не меняет
    
    void take(); // отпочковывает, заявляет монопольные права
    T& unsafe(); // ничего не меняет при условии монопольного права (должен быть предварён вызовом take(), валиден до give())
    void give(); // снимает монопольные права
        // take/give должны быть реентерабельны, поэтому у буфера, помимо счётчика ссылок, есть счётчик монопольности
        // если счётчик монопольности == 0, то данные можно разделять
        // если счётчик монопольности > 0, то счётчик ссылок == 1 (кроме этого экземпляра, никто буфером не владеет)
        // в случае, если забыли снять монопольность, просто будут немедленные клонирования в копикторе и присваивании
        // если же забыли назначить монопольность, то при модификации через unsafe() возможно unspecified и даже undefined behavior
        
    // простенькая обёртка для вызова
    class taker
    {
        cowboy& domain;
    public:
        taker(cowboy& d) : domain(d) { domain.take(); }
        taker(const taker& src) : domain(d) { domain.take(); }
        T& get() const { return domain.unsafe(); }
        ~taker() { domain.give(); }
    };
    taker safe() { return taker(*this); }
    
private:
    // лень расписывать
};

.....
class Holder
{
    cowboy<string> str;
        
    с1() { cout << str.get() << endl; } // константный доступ
    с2() { const string& ref = str.get(); cout << ref << endl; } // не нуждается в какой-то рантаймовой защите
    
    m1() { str.take(); str.unsafe() = "a"; str.unsafe() += "b"; str.give(); } // а неконстантный - нуждается
    // причём в пределах защиты можно держать ссылки на данные
    m2() { str.take(); string& ref = str.unsafe(); ref += "c"; ref += "d"; str.give(); }
    // хороший стиль - использовать scope guard
    m3() { cowboy<string>::taker t(str); str.unsafe() += "e"; m2(); str.unsafe() += "f"; } // заодно - пример реентера
    m4() { str.safe().get() = "g"; } // для однократной защиты можно получить умную ссылку 
};

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

Здравствуйте, Павел Кузнецов, Вы писали:

ПК>c-smile:

>> ПК>...Don't fix what isn't broken...

>> А если дизайн broken изначально? Или не подходит к задачам реального мира в 70% случаев?

ПК>Мне кажется, с процентами ты немного преувеличил

Да нет, скорее дал оптимистичную оценку.

Из известных мне библиотек/аппликаций интенсивно работающих со строками ( домен: XML/HTML )
я не видел ни одной в которой используется std::string или какая другая имплементация string по принципу std::string.

например mozilla/string использует такие вот абстракции (типы строковых имплементаций):

527       enum
528         {
529           F_NONE         = 0,       // no flags
530 
531           // data flags are in the lower 16-bits
532           F_TERMINATED   = 1 << 0,  // IsTerminated returns true
533           F_VOIDED       = 1 << 1,  // IsVoid returns true
534           F_SHARED       = 1 << 2,  // mData points to a heap-allocated, shared buffer
535           F_OWNED        = 1 << 3,  // mData points to a heap-allocated, raw buffer
536           F_FIXED        = 1 << 4,  // mData points to a fixed-size writable, dependent buffer
537 
538           // class flags are in the upper 16-bits
539           F_CLASS_FIXED  = 1 << 16   // indicates that |this| is of type nsTFixedString
540         };
541 
542       //
543       // Some terminology:
544       //
545       //   "dependent buffer"    A dependent buffer is one that the string class
546       //                         does not own.  The string class relies on some
547       //                         external code to ensure the lifetime of the
548       //                         dependent buffer.
549       //
550       //   "shared buffer"       A shared buffer is one that the string class
551       //                         allocates.  When it allocates a shared string
552       //                         buffer, it allocates some additional space at
553       //                         the beginning of the buffer for additional 
554       //                         fields, including a reference count and a 
555       //                         buffer length.  See nsStringHeader.
556       //                         
557       //   "adopted buffer"      An adopted buffer is a raw string buffer
558       //                         allocated on the heap (using nsMemory::Alloc)
559       //                         of which the string class subsumes ownership.
560       //
561       // Some comments about the string flags:
562       //
563       //   F_SHARED, F_OWNED, and F_FIXED are all mutually exlusive.  They
564       //   indicate the allocation type of mData.  If none of these flags
565       //   are set, then the string buffer is dependent.
566       //
567       //   F_SHARED, F_OWNED, or F_FIXED imply F_TERMINATED.  This is because
568       //   the string classes always allocate null-terminated buffers, and
569       //   non-terminated substrings are always dependent.
570       //
571       //   F_VOIDED implies F_TERMINATED, and moreover it implies that mData
572       //   points to char_traits::sEmptyBuffer.  Therefore, F_VOIDED is
573       //   mutually exclusive with F_SHARED, F_OWNED, and F_FIXED.

Здравствуйте, Кодт, Вы писали:

К>Здравствуйте, e-Xecutor, Вы писали:

EX>>>>Жил был очень многопоточный проект.

Ш>>>Я извиняюсь, но никаких гарантий касающихся многопоточности стандарт относительно класса string не даёт, так что разработчики библиоткеки вольны делать любую реализацию. А руки надо отрывать людям, которые его бездумно использовали.

К>И вообще удивительно, как на однопроцессорном ящике это не падало. Или очень сильно везло, или все критические секции были сделаны на interlocked операциях без поддержки многопроцессорности. Так это уже вопросы не к STL.


Если я правильно понял, там интерлокеды без мембара были.
Но не уверен. В хидерах на тему атомисити чёрт ногу сломит — там
дефайн на дефайне и дефайном погоняет.

А всё, что делалось — из кучи потоков делался запрос, который возвращал _копию_
структуры, в которой были строки. Строка в структуру копировалась из некоего контейнера.
В определённый момент строка в контейнере оказывалась мёртвой.
Хотя она там в рантайме вообще не менялась, заполнялась на взлёте.

И, пардон, греть голову на тему detached copy каждый раз когда
_копия_ строки возвращается в разные потоки — спасибо, такой реализации строк мне не надо...

ИМХО таки если и делать cow строки, то
1) это должно быть опционально
2) по умолчанию отключено.

Я вот сейчас профилированием занимаюсь.
Строковые операции светились где-то более-менее вверху только
когда один нехороший человек делал очень много +=, без предварительного reserve().

Здравствуйте, e-Xecutor, Вы писали:

EX>А всё, что делалось — из кучи потоков делался запрос, который возвращал _копию_
EX>структуры, в которой были строки. Строка в структуру копировалась из некоего контейнера.
EX>В определённый момент строка в контейнере оказывалась мёртвой.
EX>Хотя она там в рантайме вообще не менялась, заполнялась на взлёте.

EX>И, пардон, греть голову на тему detached copy каждый раз когда
EX>_копия_ строки возвращается в разные потоки — спасибо, такой реализации строк мне не надо...

Не, разумеется, детачить нужно только в том месте, где ты собираешься модифицировать.
И, в принципе, грамотный интерлок спасает (как я уже говорил: нужно два счётчика — на количество владельцев и на количество сессий изменения).

EX>ИМХО таки если и делать cow строки, то
EX>1) это должно быть опционально
EX>2) по умолчанию отключено.

Cow должно работать в масштабе транзакций (сессий изменения), а не отдельных примитивных операций.
Если я поэлементно ковыряю строку (через итераторы или operator[]), то выполнять проверки — неразумная трата времени.

Это касается любых данных, не только векторов и строк.

EX>Я вот сейчас профилированием занимаюсь.
EX>Строковые операции светились где-то более-менее вверху только
EX>когда один нехороший человек делал очень много +=, без предварительного reserve().

Мы профилировали строки в жёстком режиме ("выжимали кисаньку") и выяснили, что большая часть времени и памяти тратится на выделение буфера. Поэтому разумно делать так: в составе объекта строки держать буфер размера 16-32 символа (оптимум определяется профилированием) и мелочёвку хранить в нём. Немного усложняется метод reserve() — нужно проверять, куда нацелен указатель на данные (в буфере или в куче), и если в буфере — то следить за габаритами.