[с++] контейнеры, итераторы и copy-on-write

мдяяя

    QList<int> a; 
    a.append(56); 
    a.append(746); 
    a.append(4566); 
    QList<int>::iterator it = a.begin(); 
    qDebug() << a.first(); 
    qDebug() << *it; 
    qDebug() << "-----------"; 
 
    QList<int> b(a); 
    *it = 9999; 
    qDebug() << a.first(); 
    qDebug() << b.first(); 
    qDebug() << *it; 
    qDebug() << "-----------"; 

 
56  
56  
-----------  
9999  
9999  <------- мы будем смеяться над вами, жалкие пользователи Qt
9999  
-----------  

Причем тут qt я не понял, но если нужен copy-on-write, можно использовать mmap с MAP_PRIVATE.

Ты видел хоть одну полноценную реализацию cow на c++, без использования возможностей железа?

Есть подозрение, что если тебе это потребовалось, надо что-то менять в консерватории.

>Причем тут qt я не понял

дык я хотел узнать как у них, но обломался

можно использовать mmap с MAP_PRIVATE.

как оно дружит с вендой и прочимим ОС? просто код возможно проживет с десяток лет и куда его портировать захотят неизвестно

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

мне почему-то кажется, что полноценный cow на c++ нереализуем без использования фич железа.

На винде аналог mmap есть, как насчет аналога MAP_PRIVATE - хз. Должен быть я думаю.

Вынеси функции выделяющие память с cow в отдельный модуль - если что - перепишешь.

Не то чтобы ненормального. Ты хочешь ненормального от c++.

Хотеть этого от ОС - нормально

>На винде аналог mmap есть, как насчет аналога MAP_PRIVATE - хз. Должен быть я думаю.

Вынеси функции выделяющие память с cow в отдельный модуль - если что - перепишешь.

угу, придется напрячься, спасиб

Не то чтобы ненормального. Ты хочешь ненормального от c++.

ясно :)

а как насчёт того чтобы сделать обёртку для lazy pointer и уже пихать в контейнер обёрнутые item'ы?

типа так:

std::vector< der_lazy_kontainer< int > > lazy_vector;

вроде логично выглядит и реализуется просто

ЗЫ я правильно понял задачу?

>пихать в контейнер обёрнутые item'ы?

такое уже реализовано :)

теперь бы избежать копирования списков и прочей хрени внутри моего контейнера

мдя

Читаем документацию по QList::iterator:

Multiple iterators can be used on the same list. However, be aware that any non-const function call performed on the QList will render all existing iterators undefined.

Теперь читаем документацию по QListIterator:

Multiple iterators can be used on the same list. If the list is modified while a QListIterator is active, the QListIterator will continue iterating over the original list, ignoring the modified copy.

Другими словами, за живой реализацией COW + итераторов читайте исходники QListIterator.

теперь бы избежать копирования списков и прочей хрени внутри моего контейнера

эм, вопрос: зачем??? в смысле покажите use case

и да, такой подход - это прямой путь к невалидным итераторам, тормозам и неуловимым багам, короче отлаживать замучитесь, ещё раз: зачем?

успел раньше меня.

Хотя конечно поведение не очевидное - но предсказуемое, если знать реализацию.

Вообще хранение итератора долго - это плохой стиль

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

Почему? Если ты делаешь копирование правильно, итератор должен продолжать ссылаться на данные первого объекта.

> Тут кто-то берет и изменяет первый объект, он делает свою копию и продолжает спокойно жить, но косяк в том, что итератор продолжает ссылаться на данные, которые теперь принадлежат второму объекту. как-бы это разрулить?

Для STL это типичная ситуация. Например, вставка элемента в середину вектора всегда инвалидирует все итераторы, ссылавшиеся на вектор. И представляете, разруливать ничего не надо. Все спокойно с этим живут.

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

> Если ты делаешь копирование правильно, итератор должен продолжать ссылаться на данные первого объекта.

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

>> теперь бы избежать копирования списков и прочей хрени внутри моего контейнера

эм, вопрос: зачем??? в смысле покажите use case

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

теперь бы избежать копирования списков и прочей хрени внутри моего контейнера

эм, вопрос: зачем??? в смысле покажите use case

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

Эм, а зачем там CoW? (для тренировки?) Лучше реализуйте move constructor (c++0x) - вот будет реальный профит по скорости и по ресурсам.

И да, CoW нужен только в весьма специфичных случаях, ИМХО.

и ещё, не забывайте про YAGNI и KISS ;)

>эм, вопрос: зачем??? в смысле покажите use case

около 5000 вставок в секунду, накладные расходы на new просто зашкаливают

и да, такой подход - это прямой путь к невалидным итераторам, тормозам и неуловимым багам, короче отлаживать замучитесь, ещё раз: зачем?

ну в qt как раз так и сделано )) так что я видимо повторю их подход

>Для STL это типичная ситуация. Например, вставка элемента в середину вектора всегда инвалидирует все итераторы, ссылавшиеся на вектор. И представляете, разруливать ничего не надо. Все спокойно с этим живут.

нууу... сложно не согласиться, тогда так и оставлю, спасиб

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

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

эм, вопрос: зачем??? в смысле покажите use case

около 5000 вставок в секунду, накладные расходы на new просто зашкаливают

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

напишите свой аллокатор лучше и/или фабрику которая память выдаёт один раз выделенную

>и да, такой подход - это прямой путь к невалидным итераторам, тормозам и неуловимым багам, короче отлаживать замучитесь, ещё раз: зачем?

ну в qt как раз так и сделано )) так что я видимо повторю их подход

отличная аргументация, сэр :)

>CoW за экономию памяти путём потери производительности :)

небольшие внутренние эксперименты показали, что в моем случае многкратные маленькие выделения памяти убивают производительность гораздо сильнее. в моем случае выгода проистекает не от экономии памяти, а от сокращения кол-ва mallocов/reallocов.

>отличная аргументация, сэр :)

ну на самом деле я еще ориентируюсь на тот код, который уже написан, замена куска должна пройти максимально безболезненно )

>напишите свой аллокатор

уже есть, не свой правда

фабрику которая память выдаёт один раз выделенную

частично эту проблему решит внутренее устройство контейнера

CoW за экономию памяти путём потери производительности :)

небольшие внутренние эксперименты показали, что в моем случае многкратные маленькие выделения памяти убивают производительность гораздо сильнее. в моем случае выгода проистекает не от экономии памяти, а от сокращения кол-ва mallocов/reallocов.

может я не вижу всего проекта и конкретной ситуации, но, в общем случае, CoW увеличивает их malloc'ов, это by design так сказать :)

в моем случае выгода проистекает не от экономии памяти, а от сокращения кол-ва mallocов/reallocов.

и да, это решается как раз написание custom allocator'а, CoW используется для экономии памяти

мммм, что-то я тебя не пониммаю, пояснишь?

мммм, что-то я тебя не пониммаю, пояснишь?

оке, у меня тоже сложилось впечатление что мы про разные вещи говорим :)

CoW что делает? (упрощённо) Производит аллокацию памяти только при обращении к контейнеру (будем называть так) на запись, правильно? Можно назвать это lazy memory allocation.

Как это поможет разрулить 1k вставок в секунду? Да никак. Точно так же будет выделяться память при каждой вставке, только появится ещё 1 промежуточный слой, который будет разруливать целостность данных. Причём (!) отслеживаться будет только целостность контейнера целиком, если хоть 1 элемент изменяется - создаётся честная копия. Задача CoW - экономия памяти, если есть 2 одинаковых контейнера - оке, пусть они лежат в памяти в одном месте (экономия же), если хоть один из них изменился - разделяем их, ибо это уже разные контейнеры.

Хоть убей не пойму как в такой ситуации CoW поможет избежать накладных на alloc/realloc.

> С чего бы?

С того, что,

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

Что тут не ясного?

>Как это поможет разрулить 1k вставок в секунду? Да никак.

Я забыл рассказать еще про ~10 потоков + гуй, и все они используют эти данные ))

> он наверное имел ввиду, что надо сначала было создать второй объект, а потом уже итератор

Что за бред?

Создаём объект, создаём указывающие на него итераторы. При изменении, создаём новый объект. Существующие итераторы указывают на старый. Если копию делать правильно, проблемы вообще нет.

>Что за бред?

я про пример в первом посте

Если копию делать правильно, проблемы вообще нет.

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

т.е. cow в данном случае позволяет избежать ненужного копирования

Как это поможет разрулить 1k вставок в секунду? Да никак.

Я забыл рассказать еще про ~10 потоков

ога, это всенепременно добавит гемора в огонь, так как при изменении придётся проверять ещё и локи

+ гуй, и все они используют эти данные ))

это ведь не относится к alloc/realloc, да? :)

ЗЫ может Вы про что-то другое забыли/не можете рассказать? :)

>ога, это всенепременно добавит гемора в огонь, так как при изменении придётся проверять ещё и локи

дык уже добавляет, хехе ))

это ведь не относится к alloc/realloc, да? :)

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

>это ведь не относится к alloc/realloc, да? :)

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

поздравлю, Вы только что порвали мне «моск» :)

1. зачем каждый будет копировать себе контейнер? взял указатель и пользуй

2. как от «копирования» в данном случае спасает CoW (-on-Write, заметьте)? если данные не пишутся тогда пофик что там и сколько контейнеров, если пишутся, то единственная и могучая роль CoW в данном случае, потупить при первой записи дёргая new/malloc, не?

>1. зачем каждый будет копировать себе контейнер?

1. за ~50 человек сложно отвечать, и хотя по мере сил все исправляется, косяки есть и будут

2. а если надо чето поменять, причем не сразу?

2. как от «копирования» в данном случае спасает CoW (-on-Write, заметьте)? если данные не пишутся тогда пофик что там и сколько контейнеров, если пишутся, то единственная и могучая роль CoW в данном случае, потупить при первой записи дёргая new/malloc, не?

это позволяет отсрочить этот момент

Надеюсь не стоит напоминать, что при CoW изменять контейнер может только один поток, потому как если это делают два одновременно, то в результате изменения одного из них потеряются. Из чего я могу сделать вывод, что из 10 потоков пишущий у вас 1, а остальные 9 только читают. Причём именно эти 9 более критичны к скорости доступа к данным. Если так, то стоит обратить внимание на Read Only Mutex, который можно произвольное количество раз блокировать для чтения из разных потоков, после чего все они могут читать данные одновременно. В Qt такой тип мутекса реализован в классе QReadWriteLock.

> единственная и могучая роль CoW в данном случае, потупить при первой записи дёргая new/malloc

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

это мог не рассказывать, это уже все есть, алсо все немного сложнее устроено на самом деле((

они уже завернуты в cow-контейнеры