[VS2005, STL] Это недоработка STL, или так и задумано?

4223080

Полез тут в потроха STL (std::vector) на предмет быстродействия и увидел вот такой код:


	void resize(size_type _Newsize)

		{	// determine new length, padding with _Ty elements as needed

		resize(_Newsize, _Ty;

		}



	void resize(size_type _Newsize, _Ty _Val)

		{	// determine new length, padding with _Val elements as needed

		if (size < _Newsize)

			_Insert_n(end _Newsize - size _Val);

		else if (_Newsize < size

			erase(begin + _Newsize, end;

		}

Т.е. resize, вызванный с одним параметром вызывает дефолтный конструктор и получившийся объект передает в другой resize по значению :shocked: Соответственно потом это все будет копироваться еще раз.
Подумал, что меня глючит и решил провести тест
Время замерял командой rdtsc
В качестве элементов использовал вот такую структуру:


struct Sttttt

{

    Sttttt{};



    char u1[32];

    int  u2;

    double u3;

    void *u4;

};

Для теста выполнял 3 команды — создавал объект, делал reserve, потом resize
Получил следующие результаты:
10 элементов
Timer 0: Total time=6.71812e-006 sec (reserve)
Timer 1: Total time=7.7889e-007 sec (resize)
10000000 элементов
Timer 2: Total time=1.81819e-005 sec (reserve)
Timer 3: Total time= 0.826397 sec (resize)
Когда-то помницца копался в MFC... как щас помню там применялся placement new, а поскольку у меня дефолтный конструктор пустой, то и времени этот new отнимать не будет. Для проверки попробовал провести аналогичный тест для CAtlArray:
10 элементов
Timer 4: Total time=5.37589e-006 sec (reserve)
Timer 5: Total time=1.02289e-007 sec (resize)
10000000 элементов
Timer 6: Total time=1.94777e-005 sec (reserve)
Timer 7: Total time=4.19134e-008 sec (resize)
Как и предполагалось ресайз у CAtlArray реализован нормально, в то время как STL-вектор ресайзицца почти целую секунду. Как с этим бороцца?

4223080

В догонку....
В MSVS 6.0 передача параметра в двухаргументный ресайз идет по константной ссылке, что уже лучше. Так что это бага 2005-й студии. Щас проверил — в 2008 она осталась.
Однако неиспользование placement new это в данном случае ИМХО не есть гут :crazy:

4223080

еще в догонку
Это не баг 2005-й и 2008-й студии... Это баг 6-й студии :smirk:
В стандарте написано, что элемент передается по значению (но почему? :confused: )

ava3443

Это баг 6-й студии
а чего, кто-то пользуется в 6-ой студии микрософтовским STL?
если уж приходится сидеть на VS6, то только c STLPort, конечно
P.S. вот ещё про STL в VS6: http://support.microsoft.com/kb/813810

kokoc88

на предмет быстродействия
Кажется, что на предмет быстродействия приведённый код не влияет.

4223080

Вообще-то влияет, поскольку при таком интерфейсе невозможно реализовать такую же штуку, как в MFC/ATL а именно — создание объекта через placement new с вызовом дефолтного конструктора.
Кстати, судя по всему там в любом случае вызывается placement new, но используется copy-constructor. Так что, если в структуру добавить пустой copy-constructor, то время ресайза уменьшается на 7 порядков.

4223080

Вопчем, видимо вопрос закрыт
, спасибо за ссылку

karkar

> а чего, кто-то пользуется в 6-ой студии микрософтовским STL?
Я пользуюсь. Проблем не имел. Правда, std::string я не использую обычно.

Serab

что используешь?

kokoc88

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

4223080

Как это может влиять на порядок производительности?
Иногда бывают ситуации, когда например структура просто добавляется для группировки некоторых данных. Она не является настолько самостоятельной сущностью, что бы ее создание могло быть определено в конструкторе (собственно поэтому это не класс, а структура). Например программа работает с какими-то данными в которых в числе прочего имеется массив неких элементов... Ну например адресная книга — есть массив адресов домов, массив людей с указанием ФИО, паспортных данных, номеров адресов в таблице домов, номеров квартир, ну и кроме того есть некая шапка, типа даты обновления базы. разумно одного человека описать структурой. Теперь у нас есть задача считать такой файл с диска. Было бы удобно выделить память под один дополнительный элемент такой структуры, но НЕ ИНИЦИАЛИЗИРОВАТЬ его автоматом, а просто получить на него ссылку и заполнить его по ходу дела. В случае когда интерфейс ресайза имеет вид
 

    void resize(size_type _Newsize, _Ty _Val)

мы вынуждены делать минимум одно лишнее копирование на каждый объект — либо создавать пустой объект вызовом дефолтного конструктора (можно затраты на эту операцию сделать нулевыми) и затем копировать этот мусор в каждую из созданных ячеек массива. Либо создавать сразу нормальный заполненный объект и передавать уже его в ресайз (хотя в этом случае разумеецца стоит воспользовацца push_back — там по крайней мере передача объекта идет по ссылке). Как видим и там и там есть одно лишнее копирование.
Я уж не говорю про передачу объекта по значению — вапче не понимаю зачем это :confused: Но это можно и обойти выделяя массив сразу для всех элементов

4223080

ЗЫ:
У меня задача была немного другая и ее было возможно реализовать без потерь скорости и при такой реализации библиотеки (что я и сделал просто заинтересовала теоретическая подоплека ситуации. Зачем в STL сделали именно такой интерфейс контейнеров. Для общности, для простоты реализации, для предотвращения дублирования кода в самой библиотеке... ? :confused:

kokoc88

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

kokoc88

Было бы удобно выделить память под один дополнительный элемент такой структуры, но НЕ ИНИЦИАЛИЗИРОВАТЬ его автоматом, а просто получить на него ссылку и заполнить его по ходу дела.
Наверное, я плохо понимаю твои формулировки. Ссылка на память под класс без вызова какого-либо конструктора этого класса бесполезна и опасна. Поэтому структуры данных в Си++ не хранят несконструированных объектов.
Если тебя не устраивает скорость размещения памяти, можно воспользоваться аллокаторами или операторами new/delete. Если не устраивает скорость копирования, нужно хранить в векторе указатели вместо объектов. (Хотя в твоей конкретной задаче затраты на ввод-вывод перекроют затраты на работу процессора.)
вынуждены делать минимум одно лишнее копирование на каждый объект — либо создавать пустой объект вызовом дефолтного конструктора
Я не понимаю, почему одно копирование на каждый объект? Ты хочешь делать v.resize(v.size+1) для каждой новой структуры? Это вполне можно амортизировать, чем push_back и занимается. Или ты ведёшь речь о проблемах конструирования объектов с помощью конструктора копирования вместо конструкторов по умолчанию? Для твоей структуры производительность не падает до секунды.

kokoc88

10 элементов
Timer 0: Total time=6.71812e-006 sec (reserve)
Timer 1: Total time=7.7889e-007 sec (resize)
10000000 элементов
Timer 2: Total time=1.81819e-005 sec (reserve)
Timer 3: Total time= 0.826397 sec (resize)
Это, опять же, весьма странные цифры. Они наверняка получены в дебаге без включённой оптимизации inline. Когда работаешь с STL надо иметь ввиду, что debug и release билды могут различаться по производительности во много раз. Чтобы этого избежать, можно включить опцию /Ob2, хотя это может затруднить отладку, если ты любишь шаблонное программирование.

4223080

Ссылка на память под класс без вызова какого-либо конструктора этого класса бесполезна и опасна. Поэтому структуры данных в Си++ не хранят несконструированных объектов
Это ты сейчас говоришь не о структурах, а о классах. С точки зрения языка структура и класс — это почти одно и то же, однако с точки зрения "рекомендованного" использования они различаются очень сильно. Вот цитата из Страуструпа:
Я думаю о таких классах, как о "не совсем типах, являющихся просто структурами данных". Конструкторы и функции доступа могут быть весьма полезны даже для таких структур, но скорее для удобства, а не как гаранты свойств типа.

так что пустой конструктор по умолчанию для структуры очень даже возможен в реальной ситуации, а вот копирующий конструктор лучше бы вообще оставить предлагаемый компилятором по-умолчанию. И не придирайся к примеру с пустым копирующим конструктором — я же не говорю, что хотел использовать его в жизни. Это был только эксперимент(!) с целью быстро понять что используется внутри библиотеки — копирующий placement new или оператор присваивания. Все! Больше от этого эксперимента мне не нужно было ничего!
Я не понимаю, почему одно копирование на каждый объект? Ты хочешь делать v.resize(v.size+1) для каждой новой структуры? Это вполне можно амортизировать, чем push_back и занимается
1. Сперва создаем объект структуры (затраты по времени = 0)
2. Заполняем эту структуру (1-е копирование)
3. Вызываем push_back, который с помощью placement new помещает объект в вектор (2-е копирование)
Если использовать v.resize(v.size+1, NewObject) - это еще одно дополнительное копирование (2-е которое выполняется в момент передачи аргумента (как раз то, чего я совсем не понимаю, зачем нужно было так делать)
А если использовать
v.resize(v.size+1)
v.back = NewObject
то тут уже будет три (!) дополнительных (!) копирования: 1-е — передача объекта, созданного дефолтным конструктором в двухаргументный ресайз, 2-е — копирование того же объекта в конец вектора и 3-е — копирование правильного объекта в конец вектора.
Поэтому я и сказал, что при таком интерфейсе мы имеем как минимум одно лишнее копирование на каждый объект. А при неправильном испоьзовании количество лишних копирований может быть и 3 на каждый объект

4223080

Это, опять же, весьма странные цифры. Они наверняка получены в дебаге без включённой оптимизации inline
Все эти цифры были получены разумеется в релизе :)

kokoc88

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

В реальной ситуации конструктор по умолчанию возможен как для класса, так и для стуктуры. Я не вижу, почему конструктор копирования класса, созданного конструктором по умолчанию, должен работать намного медленнее конструктора по умолчанию.
А если использовать
     v.resize(v.size+1)
     v.back = NewObject
то тут уже будет три (!) дополнительных (!) копирования: 1-е — передача объекта, созданного дефолтным конструктором в двухаргументный ресайз, 2-е — копирование того же объекта в конец вектора и 3-е — копирование правильного объекта в конец вектора.
Поэтому я и сказал, что при таком интерфейсе мы имеем как минимум одно лишнее копирование на каждый объект. А при неправильном испоьзовании количество лишних копирований может быть и 3 на каждый объект
А если всё-таки не использовать ничего кривого? Вызов push_back - это одно копирование. Если объект пустой, то грамотное Си++ решение отработает с почти одинаковой скоростью как в случае конструктора копирования, так и в случае конструктора по умолчанию.
Все эти цифры были получены разумеется в релизе

У меня в релизе resize на 10кк без reserve работает 375 миллисекунд. У меня один камень на 2.5ГГц. Думаю, что тебе стоит пересмотреть твой тест.

4223080

В реальной ситуации конструктор по умолчанию возможен как для класса, так и для стуктуры. Я не вижу, почему конструктор копирования класса, созданного конструктором по умолчанию, должен работать намного медленнее конструктора по умолчанию.
Допустим есть такой код:


    void f(int Arg)

    {

        int a;

        int b = Arg;

        ..........

    }

Чему будет равно значение a и b? Вот именно... a — неопределено, b — равно Arg.
Структуры по сути являются такими же переменными. Они в отличие от классов не обязаны быть всегда и везде полностью корректно инициализированными. И если я напишу
    MyStruct ms;

То я могу ожидать, что ms пока что содержит мусор и ее еще надо определить. Именно про это и пишет Страуструп. И собственно именно так и происходит, если не писать самому конструктор по-умолчанию. А конструктор, предлагаемый компилятором в моем случае не делает вообще ничего, а значит и временнЫе затраты на его выполнение отсутствуют. С другой стороны копирующий конструктор должен создать копию объекта, и copy-constructor, предлагаемый компилятором (опять-таки в моем случае) просто делает банальное копирование бит-в-бит, так что он будет по-любому медленнее дефолтного конструктора
Если объект пустой, то грамотное Си++ решение отработает с почти одинаковой скоростью как в случае конструктора копирования, так и в случае конструктора по умолчанию
В C++ объект (структуры, типа моей) не может быть пустым — он либо содержит мусор, либо нормальные данные и компилятор не будет продираца через цепочу вызовов и пытацца определить, что там передается. Про возможные оптимизации, типа оборачивания структуры в smart_ptr и пр. я сейчас не говорю, я просто хотел сказать, что на мой взгляд можно было достаточно легким изменением интерфейса контейнеров позволить значительно увеличить эффективность в некоторых задачах без особых затрат со стороны программеров-пользователей библиотеки.
У меня в релизе resize на 10кк без reserve работает 375 миллисекунд
375 миллисекунд = 0.375 сек
у меня — 0.826 сек (проц — AMD Sempron 2ГГц)
Так что вопчем-то отличие не сильное. Просто однопараметрный ресайз при грамотной реализации должен тратить на порядки меньше времени. Например для реализации массивов в MFC/ATL мой тест показал значение в 40 наносекунд! А это уже просто на уровне шумов — точность таймера такие величины не позволяет измерять надежно.

kokoc88

я просто хотел сказать, что на мой взгляд можно было достаточно легким изменением интерфейса контейнеров позволить значительно увеличить эффективность в некоторых задачах без особых затрат со стороны программеров-пользователей библиотеки.
Эффективность достигается путём правильного использования всех механизмов языка программирования. И только тогда, когда это нужно. Я согласен, что многие моменты в stl/boost остаются спорными: производительность очень часто приносится в жертву универсальности (смотрим, например, на shared_ptr). В реализации ATL/MFC коллекций тоже не всё гладко, потому что у них линейная амортизация по размещению памяти.
375 миллисекунд = 0.375 сек
у меня — 0.826 сек (проц — AMD Sempron 2ГГц)
Так что вопчем-то отличие не сильное.
Ну да, не сильное, всего в три раза при 25% прибавке скорости работы ядра. Это меня, мягко говоря, смущает.

4223080

В реализации ATL/MFC коллекций тоже не всё гладко
У самого есть претензии :) Увы, нет в мире идеала
Ну да, не сильное, всего в три раза при 25% прибавке скорости работы ядра. Это меня, мягко говоря, смущает.

Ну, надо проверять скорость работы памяти на каждом конкретном компе, компиляторы, настройки и пр... на суть проблемы это все равно не влияет — 3 раза, это не несколько порядков

4223080

resize, вызванный с одним параметром вызывает дефолтный конструктор и получившийся объект передает в другой resize по значению :shocked:
Ну, и для истории....
нашел вот такую ссылку: http://www.open-std.org/jtc1/sc22/wg21/docs/lwg-defects.html...
Этa фича была добавлена в стандарт умышленно, с объяснением типа "для безопасной передачи в функцию элементов, уже записанных в массиве, типа такого:"
v.resize(v.size + 1, v[0]);

Как я понял добавление этого правила явилось прямым следствием пункта 5 параграфа 23.2.4.2 стандарта:
Notes: Reallocation invalidates all the references, pointers, and iterators referring to the elements in the sequence. It is guaranteed that no reallocation takes place during insertions that happen after a call to reserve until the time when an insertion would make the size of the vector greater than the size specified in the most recent call to reserve.

Однако непосредственно в момент ресайза старый блок данных еще существует, а значит и передача по ссылке вполне возможна.
В настоящее время проблема с передачей аргумента по значению в resize признана багом. Она занесена в список известных багов под номером 679 и имеет статус CD1:
CD1 - (Committee Draft 2008) - The full WG21 committee has voted to accept the Defect Report's Proposed Resolution into the Fall 2008 Committee Draft.
Заглянул в драфт стандарта C++ от мая 2007 года. Вот какие изменения там приняты в отношении ресайза:
1. Добавилось объявление ресайза с одним аргументом.
2. Двухаргументный ресайз по-прежнему принимает второй аргумент по-значению.
3. Для одноаргументного ресайза явно указано, что будет вызываться конструктор по-умолчанию (что вопчем-то и сейчас происходит но при этом ничего не сказано про наличие/отсутствие копирующего конструктора, в то время как для двухаргументного ресайза явно написано, что копи-конструктор не должен бросать исключения. Это дает повод надеяться, что реализация одноаргументного ресайза будет пользовать только конструктор по-умолчанию, а значит в приведенном выше случае затраты на ее вызов будут составлять O(1).
Вот текст из драфта стандарта:
void resize(size_type sz);
9 Effects: If sz < size equivalent to erase(begin + sz, end;. If size < sz, appends sz - size
default constructed elements to the sequence.
10 Requires: T shall be DefaultConstructible.
void resize(size_type sz, T c = T;
11 Effects:
if (sz > size
insert(end sz-size c);
else if (sz < size
erase(begin+sz, end;
else
; // do nothing
12 Requires: If value_type has a move constructor, that constructor shall not throw any exceptions.

Что ж.. подождем :)
Оставить комментарий
Имя или ник:
Комментарий: