Почему эта векторная реализация более производительна?

Question

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

Я на полпути к реализации этого класса (вставка и получение завершены), и я решил написать несколько тестов с удивительными результатами .

Мой компилятор - это то, что использует Visual Studio 2019. Я пробовал отладку и выпуск в x64 и x86.

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

Вот мои результаты (x64, отладка):

List: 13269ms
Vector: 78515ms

Релиз имеет гораздо меньшие потери c, но все еще очевиден , разница.

List: 65ms
Vector: 247ms

Вот мой код

dataset.hpp:

#ifndef DATASET_H
#define DATASET_H

#include <memory>
#include <stdexcept>
#include <algorithm>
#include <functional>
#include <chrono>

namespace Dataset {
    template <class T>
    class List {
    public:
        List();
        List(unsigned int);
        void push(T);
        T& get(int);
        void reserve(int);
        void shrink();
        int count();
        int capacity();
        ~List();
    private:
        void checkCapacity(int);
        void setCapacity(int);
        char* buffer;
        int mCount, mCapacity;
    };


    template <class T>
    List<T>::List() {
        mCount = 0;
        mCapacity = 0;
        buffer = 0;
        setCapacity(64);
    }
    template <class T>
    List<T>::List(unsigned int initcap) {
        mCount = 0;
        buffer = 0;
        setCapacity(initcap);
    }
    template <class T>
    void List<T>::push(T item) {
        checkCapacity(1);
        new(buffer + (sizeof(T) * mCount++)) T(item);
    }
    template <class T>
    T& List<T>::get(int index) {
        return *((T*)(buffer + (sizeof(T) * index)));
    }
    template <class T>
    void List<T>::reserve(int desired) {
        if (desired > mCapacity) {
            setCapacity(desired);
        }
    }
    template <class T>
    void List<T>::shrink() {
        if (mCapacity > mCount) {
            setCapacity(mCount);
        }
    }
    template <class T>
    int List<T>::count() {
        return mCount;
    }
    template <class T>
    int List<T>::capacity() {
        return mCapacity;
    }
    template <class T>
    void List<T>::checkCapacity(int cap) {
        // Can <cap> more items fit in the list? If not, expand!
        if (mCount + cap > mCapacity) {
            setCapacity((int)((float)mCapacity * 1.5));
        }
    }
    template <class T>
    void List<T>::setCapacity(int cap) {
        mCapacity = cap;
        // Does buffer exist yet?
        if (!buffer) {
            // Allocate a new buffer
            buffer = new char[sizeof(T) * cap];
        }
        else {
            // Reallocate the old buffer
            char* newBuffer = new char[sizeof(T) * cap];
            if (newBuffer) {
                std::copy(buffer, buffer + (sizeof(T) * mCount), newBuffer);
                delete[] buffer;
                buffer = newBuffer;
            }
            else {
                throw std::runtime_error("Allocation failed");
            }
        }
    }
    template <class T>
    List<T>::~List() {
        for (int i = 0; i < mCount; i++) {
            get(i).~T();
        }
        delete[] buffer;
    }

    long benchmark(std::function<void()>);
    long benchmark(std::function<void()>, long);

    long benchmark(std::function<void()> f) {
        return benchmark(f, 100000);
    }

    long benchmark(std::function<void()> f, long iters) {
        using std::chrono::high_resolution_clock;
        using std::chrono::duration_cast;
        auto start = high_resolution_clock::now();
        for (long i = 0; i < iters; i++) {
            f();
        }
        auto end = high_resolution_clock::now();
        auto time = duration_cast<std::chrono::milliseconds>(end - start);
        return (long)time.count();
    }

}


#endif

test. cpp:

#include "dataset.hpp"
#include <iostream>
#include <vector>


/*

    TEST CODE

*/


class SimpleClass {
public:
    SimpleClass();
    SimpleClass(int);
    SimpleClass(const SimpleClass&);
    void sayHello();
    ~SimpleClass();
private:
    int data;
};

SimpleClass::SimpleClass() {
    //std::cout << "Constructed " << this << std::endl;
    data = 0;
}

SimpleClass::SimpleClass(int data) {
    //std::cout << "Constructed " << this << std::endl;
    this->data = data;
}

SimpleClass::SimpleClass(const SimpleClass& other) {
    //std::cout << "Copied to " << this << std::endl;
    data = other.data;
}

SimpleClass::~SimpleClass() {
    //std::cout << "Deconstructed " << this << std::endl;
}

void SimpleClass::sayHello() {
    std::cout << "Hello! I am #" << data << std::endl;
}

int main() {

    long list = Dataset::benchmark([]() {
        Dataset::List<SimpleClass> list = Dataset::List<SimpleClass>(1000);
        for (int i = 0; i < 1000; i++) {
            list.push(SimpleClass(i));
        }
    });

    long vec = Dataset::benchmark([]() {
        std::vector<SimpleClass> list = std::vector<SimpleClass>(1000);
        for (int i = 0; i < 1000; i++) {
            list.emplace_back(SimpleClass(i));
        }
    });

    std::cout << "List: " << list << "ms" << std::endl;
    std::cout << "Vector: " << vec << "ms" << std::endl;

    return 0;
}

Answer 1

std::vector конструктор с одним параметром создает вектор с количеством элементов:

explicit vector( size_type count, const Allocator& alloc = Allocator() );

Чтобы получить что-то сопоставимое с вектором, вы должны сделать:

std::vector<SimpleClass> list;
list.reserve( 1000 );

также ваш «вектор» копирует объекты, которые он хранит, просто копируя память, что разрешено только для тривиально копируемых объектов, и SimpleClass не является одним из них, поскольку имеет определенные пользователем конструкторы.

Answer 2

Это действительно хорошее начало! Чистое и простое решение для упражнения. К сожалению, ваши инстинкты правы в том, что вы не тестировали достаточно случаев.

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

Одна ошибка, которая выскакивает из меня, это то, что вы вызываете new[], чтобы выделить буфер char - который не гарантируется соответствие требованиям выравнивания T. На некоторых процессорах, которые могут обработать sh программу.

Другое - вы используете std::copy с неинициализированной областью памяти в качестве места назначения в List::setCapacity. Это не работает, за исключением особых случаев: std::copy ожидает корректно инициализированный объект, который может быть назначен. Для любого типа, где присваивание является нетривиальной операцией, это завершится неудачно, когда программа попытается вызвать деструктор для данных мусора. Если это сработает, то перемещение будет неэффективно клонировать данные и уничтожить оригинал, а не использовать конструктор перемещения, если таковой существует. Алгоритм STL, который вам действительно нужен, это std::uninitialized_move. Возможно, вы также захотите использовать calloc / realloc, что позволяет изменять размеры блоков.

Ваши элементы емкости и размера должны быть size_t, а не int. Это не только ограничивает размер памяти меньшим, чем может реализовать большинство реализаций, но вычисление размера, превышающего INT_MAX (т. Е. 2 ​​ГБ или более в большинстве реализаций), приводит к неопределенному поведению.

Одна вещь List::push имеет для этого используется семантика std::vector::emplace_back (которую вы понимаете и используете для сравнения). Это, однако, может быть улучшено. Вы передаете item по значению, а не по константной ссылке. Это создает ненужную копию данных. К счастью, если T имеет конструктор перемещения, дополнительную копию можно переместить, и если item является значением xvalue, компилятор может оптимизировать ее удаление, но было бы лучше иметь List::push(const T&) и List::push(T&&). Это позволит классу pu sh xvalue вообще не делать копий.

List::get лучше и избегает делать копии, но у него нет версии const, поэтому const List<T> ничего не может сделать. Он также не проверяет границы.

Рассмотрите возможность помещения кода для поиска позиции индекса в буфере в частную встроенную функцию-член, что значительно сократит объем работы, которую вам нужно будет выполнить исправьте изменения в дизайне (например, те, которые вам понадобятся для исправления ошибки выравнивания данных).