Вектор объединения и объединения объектов среднего размера

Question

У меня есть очень простая программа , где я объединяю два вектора 100-байтовых объектов (SortRecord).

#include <numeric>
#include <iostream>
#include <sstream>
#include <array>
#include <chrono>

constexpr size_t TUPLE_SIZE = 90;
constexpr size_t KEY_SIZE = 10;
constexpr size_t TUPLE_COUNT = 1024 * 1024 * 20;
constexpr size_t ARRAY_COUNT = 2;

using Record = std::array<uint8_t, TUPLE_SIZE>;
using Header = std::array<uint8_t, KEY_SIZE>;
using TimerClock = std::chrono::system_clock;

struct SortRecord {
    Header header;
    Record record;

    bool operator<(const SortRecord& record)
    {
        const uint64_t a = *reinterpret_cast<const uint64_t*>(&header[0]);
        const uint64_t b = *reinterpret_cast<const uint64_t*>(&record.header[0]);

        if (a == b)
        {
            const uint16_t c = *reinterpret_cast<const uint16_t*>(&header[8]);
            const uint16_t d = *reinterpret_cast<const uint16_t*>(&record.header[8]);
            return c < d;
        }
        return a < b;
    }
};

template<size_t tuplecount>
static auto CreateArray()
{
    std::array<std::vector<SortRecord>, ARRAY_COUNT> data_array;
    uint64_t hvalue = 0;
    srand(100);

    for (auto& data : data_array)
    {
        data.resize(tuplecount);
        hvalue = 0;
        std::for_each(data.begin(), data.end(), [&hvalue](auto& it)
        {
            *reinterpret_cast<uint64_t*>(&it.header[0]) = hvalue = hvalue + (rand() % 100);
        });
    }

    return data_array;
}

auto data_array = CreateArray<TUPLE_COUNT>();

// merge
std::vector<SortRecord> result1;
result1.reserve(TUPLE_COUNT * 2);
auto start = TimerClock::now();
std::merge(data_array[0].begin(), data_array[0].end(),
    data_array[1].begin(), data_array[1].end(),
    std::back_inserter(result1));
auto end = TimerClock::now();
std::cout << std::to_string(std::chrono::duration_cast<std::chrono::milliseconds>(end - start).count()) << " [ms]\n";

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

// concatenation
std::vector<SortRecord> result2;
result2.reserve(TUPLE_COUNT * 2);
auto start2 = TimerClock::now();
result2.insert(result2.end(), data_array[0].begin(), data_array[0].end());
result2.insert(result2.end(), data_array[1].begin(), data_array[1].end());  
auto end2 = TimerClock::now();
std::cout << std::to_string(std::chrono::duration_cast<std::chrono::milliseconds>(end2 - start2).count()) << " [ms]\n";

Я пробовал его на MSVC 2017, а также на gcc и с очень похожими результатами. Когда я пытался заменить SortRecord на float или int, то внезапно я получаю лучшие результаты для объединения.

В чем проблема с вариантом SortRecord?

Answer 1

У вас есть в основном два эффекта, которые масштабируются линейно с количеством элементов для объединения:

• элементы должны быть прочитаны и записаны
• в дополнение merge необходимо сравнитьelements

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

int insert vs merge

Для небольших int s выигрывают накладные расходы из-за сравнения элементов, и вы видите insert, превосходящий merge.

SortRecord вставка против слияния

Ваши SortRecord довольно массивные.В этом случае кажется, что основной вклад вносят чтение и запись элементов, а сравнение их является лишь незначительным вкладом.(Я немного озадачен, почему в вашем тесте merge на 10% быстрее, чем insert, но давайте назовем это незначительным;).

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