Iteration speed of unordered_set vs vector-CodePudding

I have an application where I need to store various subsets of different customers. The order of the customers in the container does not matter.

Since the order does not matter, I was hoping that storing and iterating through this set of customers would be faster on an std::unordered_set<int> as compared to std::vector<int>.

CPPREference, however, states:

unordered_set containers are faster than set containers to access individual elements by their key, although they are generally less efficient for range iteration through a subset of their elements.

To test this out, I evaluated the time it takes to iterate through std::unoredered_set and std::vector.

#include <vector>
#include <unordered_set>
#include <chrono>
#include <stdio.h>

static const int NoElements = 100000000;

int main()
{
    std::vector<int> VecofElems;
    VecofElems.reserve(NoElements);

    std::unordered_set<int> SetofElems;
    SetofElems.reserve(NoElements);

    for (int i = 0; i < NoElements; i  )
        VecofElems.push_back(i); 
    for (int i = 0; i < NoElements; i  )
        SetofElems.insert(i);

    auto VecIterStartTime = std::chrono::steady_clock::now();
    long vec_cumulative_sum = 0;
    for (std::vector<int>::const_iterator viter = VecofElems.begin(); viter != VecofElems.end();   viter)
        vec_cumulative_sum  = *viter;
    auto VecIterEndTime = std::chrono::steady_clock::now();
    std::chrono::duration<double, std::milli> VecTime = VecIterEndTime - VecIterStartTime;
    
    auto SetIterStartTime = std::chrono::steady_clock::now();
    long set_cumulative_sum = 0;
    for (std::unordered_set<int>::const_iterator uositer = SetofElems.begin(); uositer != SetofElems.end();   uositer) {
        set_cumulative_sum  = *uositer;
    }
    auto SetIterEndTime = std::chrono::steady_clock::now();
    std::chrono::duration<double, std::milli> SetTime = SetIterEndTime - SetIterStartTime;

    printf("Vector Sum %ld, Size %ld, Time Taken %f\n", vec_cumulative_sum, VecofElems.size(), VecTime);
    printf("Set Sum %ld, Size %ld, Time Taken %f\n", set_cumulative_sum, SetofElems.size(), SetTime);

    getchar();
}

The output on my machine, when the above is compiled in Release Mode of MSVC compiler is:

Vector Sum 887459712, Size 100000000, Time Taken 51.340000
Set Sum 887459712, Size 100000000, Time Taken 4772.139100

indicating that iterating through a vector is many orders of magnitude faster than an unordered_set.

In my application, since the order of the elements in a container do not matter, and since an std::vector preserves order (unnecessarily in this case), is there any other container that can be faster than even std::vector in iterating through various elements of the container?

CodePudding user response：

std::vector is the fastest STL container for linear iterations like in your scenario. This is simply because memory is contiguously allocated and therefore can benefit of caching mechanisms. A vector iterator just increments a pointer internally.

You might improve performance further by trying to use a smaller type than int when possible.

In your case I think parallelization/SIMD would give largest performance boost for reduction. This might be achieved by auto vectorization (check project compiler settings).

You could also try OMP to do this like this (not tested)

size_t end = VecofElems.size();
#pragma omp parallel for shared(vec_cumulative_sum ) reduction( : vec_cumulative_sum )
for (size_t i = 0; i < end;   i) {
    vec_cumulative_sum  = VecofElems[i];
}

This would run multiple threads in parallel. Therefore it's important to declare vec_cumulative_sum as being shared amongst the threads.

std::for_each provides some simple way to make use of parallelism including vectorization. This allows to simply use any STL container like std::vector (and any other container providing iterators) like this

std::for_each(std::execution::par, VecofElems.begin(), VecofElems.end(), 
    , []() {
        // have some fun using a lambda, or function
    }
}