Saya memiliki program sederhana tempat saya menggabungkan dua vektor objek 100byte (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";

Saya telah mencoba membandingkannya dengan gabungan sederhana dari dua vektor ini dan secara mengejutkan kecepatannya hampir sama.

// 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";

Saya telah mencobanya di MSVC 2017, dan juga di gccdan dengan hasil yang sangat mirip. Ketika saya mencoba mengganti SortRecord dengan float atau int kemudian tiba-tiba saya mendapatkan banyak hasil yang lebih baik untuk penggabungan.

Apa masalahnya dengan varian SortRecord?

1
Radim Bača 29 Maret 2019, 16:52

1 menjawab

Jawaban Terbaik

Anda pada dasarnya memiliki dua efek yang keduanya berskala linier dengan jumlah elemen untuk digabungkan:

  • elemen harus dibaca dan ditulis
  • selain itu merge harus membandingkan elemen

Kedua skala kontribusi linier dengan jumlah elemen, tetapi ketergantungan mereka pada ukuran elemen tampaknya berbeda.

int menyisipkan vs menggabungkan

Untuk int kecil overhead karena membandingkan elemen menang dan Anda melihat insert mengungguli merge.

SortRecord menyisipkan vs menggabungkan

SortRecord Anda agak besar. Dalam hal ini terlihat bahwa kontribusi utama adalah dari membaca dan menulis unsur-unsur dan membandingkannya hanya merupakan kontribusi kecil. (Saya agak bingung mengapa di benchmark Anda merge sebenarnya 10% lebih cepat dari insert, tapi sebut saja itu tidak signifikan ;).

Orang bisa berspekulasi bahwa itu ada hubungannya dengan cache dan fakta bahwa akses memori sebenarnya tidak berskala linier. Bagaimanapun, jika Anda hanya membuat SortRecord lebih kecil, tetapi mempertahankan jumlah elemen untuk digabungkan, Anda lihat perbedaan yang sama seperti untuk bilangan bulat.

1
largest_prime_is_463035818 29 Maret 2019, 18:39