Return to Revisions

The functions cheat their benchmarks by allocating their auxiliary storage outside of the timing loop. That's not reasonable unless you can arrange for the "real life" versions to have their own (per-thread?) long-lived auxiliary storage.

I think there's a problem with the vector<bool> version that's masked by the test data (which always keeps the element values between 0 and test_data.max_possible_size. Perhaps that's how the real-life input data are naturally distributed, but the constraint needs to be clearly specified. For a more general case, we would need to arrange bool storage from the min to max values of all the inputs (and memory exhaustion becomes much more likely).

I did manage to improve the inplace-merge version by using a heap to identify the current lowest iterator among all inputs, for about 20% speedup:

#include <queue>

template<typename Container>
using QueueItem = std::pair<typename Container::const_iterator,
                            typename Container::const_iterator>;

static void merge_with_heap_merge(benchmark::State& state)
{
    const auto& test_data = get_test_data();

    for (auto _ : state) {

        auto compare = [](auto a, auto b) { return *(a.first) < *(b.first); };
        std::priority_queue<QueueItem<std::vector<int>>,
                            std::vector<QueueItem<std::vector<int>>>,
                            decltype(compare)>
            heap(compare);

        std::vector<int> result;
        result.reserve(test_data.max_possible_size);

        for (auto const& r: test_data.ranges) {
            heap.emplace(r.begin(), r.end());
        }

        while (!heap.empty()) {
            auto item = heap.top();
            heap.pop();
            if (!result.empty() && result.back() != *(item.first))
                result.push_back(*(item.first));
            if (++item.first != item.second) {
                heap.emplace(item);
            }
        }

        // return dump_results(result);

        benchmark::DoNotOptimize(result);
    }
}

The speedup comes primarily from avoiding repeated copying, and in particular, the final deduplication pass.