std :: vector в VisualStudio2008 представляется неоптимально реализованным - слишком много вызовов конструктора копирования

Question

Я сравнивал реализацию STL популярной библиотеки XmlRpc с реализацией, которая в основном избегает STL. Реализация STL намного медленнее - я получил 47 с до 4,5 с. Я диагностировал некоторые из причин: это частично из-за неправильного использования std :: string (например, автор должен был использовать «const std :: string &» везде, где это возможно - не просто используйте std :: string, как будто они были строки Java), но это также потому, что конструкторы копирования постоянно вызывались каждый раз, когда вектор выходил за свои границы, что было очень часто. Конструкторы копирования были очень медленными, потому что они делали глубокие копии деревьев (значений XmlRpc).

Кто-то сказал мне в StackOverflow, что реализации std :: vector обычно удваивают размер буфера каждый раз, когда они перерастают. Это не похоже на случай VisualStudio 2008: для добавления 50 элементов в std :: vector потребовалось 177 вызовов конструктора копирования. Удвоение каждый раз должно вызывать конструктор копирования 64 раза. Если вы очень обеспокоены сохранением низкого уровня использования памяти, то при увеличении на 50% каждый раз следует вызывать конструктор копирования 121 раз. Так откуда взялись 177?

Мой вопрос: а) почему конструктор копирования вызывается так часто? (б) есть ли способ избежать использования конструктора копирования, если вы просто перемещаете объект из одного места в другое? (В этом случае и в большинстве случаев было бы достаточно использовать memcpy () - и это имеет БОЛЬШУЮ разницу).

(NB: я знаю о vector :: reserve (), я немного разочарован тем, что разработчикам приложений потребуется реализовать трюк удвоения, когда нечто подобное уже является частью любой хорошей реализации STL.)

Моя тестовая программа:

#include <string>
#include <iostream>
#include <vector>



using namespace std;


int constructorCalls;
int assignmentCalls;
int copyCalls;


class C {
    int n;

public:
    C(int _n) { n = _n; constructorCalls++; }
    C(const C& orig) { copyCalls++; n = orig.n; }
    void operator=(const C &orig) { assignmentCalls++; n = orig.n; }
};



int main(int argc, char* argv[])
{
    std::vector<C> A;

    //A.reserve(50);
    for (int i=0; i < 50; i++)
        A.push_back(i);
    cout << "constructor calls = " << constructorCalls << "\n";
    cout << "assignment calls = " << assignmentCalls << "\n";
    cout << "copy calls = " << copyCalls << "\n";
    return 0;
}

Answer 1

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

Если вы добавите больше печатного кода, то будет немного яснее, что происходит:

std::vector<C> A;
std::vector<C>::size_type prevCapacity = A.capacity();

for (int i=0; i < 50; i++) {
    A.push_back(i);
    if(prevCapacity != A.capacity()) {
       cout << "capacity " << prevCapacity << " -> " << A.capacity() << "\n";
    }
    prevCapacity = A.capacity();
}

Это имеет следующий вывод:

capacity 0 -> 1
capacity 1 -> 2
capacity 2 -> 3
capacity 3 -> 4
capacity 4 -> 6
capacity 6 -> 9
capacity 9 -> 13
capacity 13 -> 19
capacity 19 -> 28
capacity 28 -> 42
capacity 42 -> 63

Так что да, емкость увеличивается на 50% каждый раз, и это составляет 127 экземпляров:

1 + 2 + 3 + 4 + 6 + 9 + 13 + 19 + 28 + 42 = 127

Добавьте 50 дополнительных копий из 50 вызовов к push_back, и вы получите 177:

127 + 50 = 177

Answer 2

Мой вопрос:

(а) почему конструктор копирования вызывается так часто?

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

(b) есть ли способ избежать использования конструктора копирования, если вы просто двигаетесь объект из одного места в другое?

Нет, нет способа избежать использования конструктора копирования.
Это потому, что объект имеет несколько членов, которые должны быть правильно инициализированы.
Если вы использовали memcpy, как узнать, что объект был правильно инициализирован для объекта!

Например. ЕСЛИ объект содержал умный указатель. Вы не можете просто запоминать умный указатель. Нужно сделать дополнительную работу, чтобы отследить право собственности. В противном случае, когда оригинал выходит из области видимости, память удаляется, а новый объект имеет висячий указатель. Тот же принцип применим ко всем объектам, у которых есть конструктор (конструктор копирования), который конструктор действительно требует требуемой работы.

Способ остановить копирование содержимого слишком зарезервировать место.
Это заставляет вектор выделять достаточно места для всех объектов, которые он будет хранить. Таким образом, нет необходимости постоянно перераспределять основной буфер. Он просто копирует объекты в вектор.

Удвоение каждый раз должно вызывать конструктор копирования 64 раза. Если вы очень обеспокоены сохранением низкого уровня использования памяти, то увеличивайте на 50% каждый раз должны вызывать конструктор копирования 121 раз. Так откуда взялись 177?

Вектор выделенного размера = 1:
Добавить элемент 1: (без перераспределения) Но копирует элемент 1 в вектор.
Добавить элемент 2: перераспределить буфер (размер 2): скопировать элемент 1 поперек. Скопируйте элемент 2 в вектор.
Добавить элемент 3: перераспределить буфер (размер 4): скопировать элемент 1-2 поперек. Скопируйте элемент 3 в вектор.
Добавьте элемент 4: скопируйте элемент 4 в вектор
Добавить элемент 5: перераспределить буфер (размер 8): скопировать элемент 1-4 поперек. Скопируйте элемент 5 в вектор.
Добавить элемент 6: скопировать элемент 6 в вектор
Добавьте элемент 7: скопируйте элемент 7 в вектор
Добавить элемент 8: скопировать элемент 8 в вектор
Добавить элемент 9: перераспределить буфер (размер 16): скопировать элемент 1-8 поперек. Скопируйте элемент 9 в вектор.
Добавьте элемент 10: скопируйте элемент 10 в вектор
и т. д.

Первые 10 элементов заняли 25 копий конструкций.
Если бы вы сначала использовали резерв, то потребовалось бы всего 10 копий конструкций.

Answer 3

STL имеет тенденцию вызывать подобные вещи. Спецификация не позволяет использовать memcpy, потому что это работает не во всех случаях. Есть документ, описывающий EASTL , множество изменений, сделанных EA, чтобы сделать его более подходящим для их целей, в котором есть метод объявления, что тип безопасен для memcpy. К сожалению, это не AFAIK с открытым исходным кодом, поэтому мы не можем играть с ним.

IIRC Dinkumware STL (тот, что в VS) каждый раз увеличивает векторы на 50%.

Однако выполнение серии push_back для вектора является общей неэффективностью. Вы можете использовать резерв для его уменьшения (за счет возможной траты памяти, если вы значительно переоцениваете), или использовать другой контейнер - deque работает лучше для ряда подобных вставок, но немного медленнее при произвольном доступе, который может / может не будет хорошим компромиссом для вас.

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

Answer 4

Похоже, дополнения к C ++ 0x помогут здесь; см. Rvalue и STL .

Answer 5

Если я правильно помню, C ++ 0x может иметь семантику перемещения (в дополнение к семантике копирования), при этом вы можете реализовать более эффективный конструктор копирования, если действительно хотите.

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

Answer 6

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

1. Плохая локальность данных указателей в векторе делает версию без указателя с последовательными объектами, обведенными вокруг версии указателя, когда вектор фактически используется .
2. Распределение кучи медленнее, чем выделение стека.

Вы чаще используете вектор или добавляете материал к нему?

Answer 7

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

Другими словами, std::vector<C*> вместо std::vector<C>. Memcpy'ing указатели очень быстро.