Используйте контейнеры STL! …если вы не хотите ехать быстрее

Мы все знаем, что нужно использовать STL, когда это возможно, не изобретать велосипед и двигаться вперед как сообщество.
Тем не менее, некоторые его недостатки и задержки в процессе интеграции часто являются причинами для развертывания собственных контейнеров/алгоритмов (mozilla::vector, eastl::list, так далее). Мы собираемся увидеть реальный пример этого.

В этом случае у нас есть 2D изображение (матрица значений), которые нам нужно сериализовать в длинный 1D вектор (поставить ряды в линию).
Каждая строка является смежной, но они не обязательно являются смежными друг с другом.

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

Мы будем использовать следующую реализацию image:

const size_t width = 2000000, height = 5; // Small sizes for example sake
std::vector<std::vector<double>> image (height);
image[0].resize(width);
image[1].resize(width);
image[2].resize(width);
image[3].resize(width);
image[4].resize(width);
std::iota(image[0].begin(), image[0].end(), 1); // Giving non-trivial values
std::iota(image[1].begin(), image[1].end(), 1);
std::iota(image[2].begin(), image[2].end(), 1);
std::iota(image[3].begin(), image[3].end(), 1);
std::iota(image[4].begin(), image[4].end(), 1);

Мы используем непрерывный std::vector для изображения, но это просто для упрощения доступа к строкам (оператор нижнего индекса []) в этом примере.

Итак, мы хотим создать std::vector и заполните его значениями!
Но здесь мы застреваем: у каждого варианта есть обратная сторона…

std::vector<double> res1 (image.size()*width);
for (size_t i = 0; i < image.size(); ++i)
    std::copy(image[i].begin(), image[i].end(), res1.begin()+i*width);

Этот пример можно хорошо распараллелить, но создание вектора (res1(image.size()*width);) инициализирует его элементы, что является дорогостоящей операцией, когда изображение становится очень большим.

Переходим к известному решению «reserve & push_back»:

std::vector<double> res2;
res2.reserve(width*height);
for (size_t i = 0; i < height; ++i)
    for (size_t j = 0; j < width; ++j)
        res2.push_back(image[i][j]);

Здесь два минуса: push_back не распараллеливается, и каждый стоит проверка/увеличение размера на каждом шагу. То же самое касается assign решение.
Мы ограничены тем, что для большей безопасности size член std::vector не имеет общедоступного сеттера, поэтому мы не можем «зарезервировать, установить размер и скопировать данные»что, по сути, мы и хотим сделать.

Итак, вот идея иметь быструю копию:

template <typename T>
class serializedImage
{
public:
    serializedImage(const std::vector<std::vector<T>>& vectors) :
        data   (nullptr),
        width  (vectors[0].size()),
        height (vectors.size()),
        size   (vectors[0].size()*vectors.size())
    {
        data = new T[size]; // 'new T[size]()' would initialize
#pragma omp parallel for
        for (size_t i = 0; i < height; ++i)
            std::copy(vectors[i].begin(), vectors[i].end(), data+i*width);
    }

    ~serializedImage() { delete[] data; data = nullptr; }

private:
    T* data; size_t width; size_t height; size_t size;
};

Для удобочитаемости код был сокращен до минимума без проверок безопасности (пустой ввод, операторы, пространство имен и т. д.).

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

serializedImage<double> res3 (image);

Источник: Гифи

Кстати, я попытался сделать ctor выражением Fold, которое использует переменное количество входных векторов (например, size = (vectors.size()+...);) но пока не удалось, если кто сможет, было бы интересно посмотреть.

Ссылки по теме: