CODEWITHSUNDEEP
c++vectorallocatormemory-pool
Alireza Majidi
Alireza Majidi

Reputation: 115

Chunking a big vector to smaller ones without extra heap allocation

I need to replace 3 heap allocations for 3 instances of std::vector, with only one contiguous heap allocation and then share it between those 3 vectors. These vector sizes are not going to be changed, so I don't need to be worried about allocation of new contiguous storage in case of pushing or inserting elements to them. My experimental result shows I get up to 2X speed up for different sizes, when I replace these 3 vectors of size n, with one vector of size of *3*n*.

However, I don't know exactly how to achieve the job of making smaller vectors out of the big one, without doing any extra heap allocation.

std::array<std::vector<double>, 3>
chunck_vector(size_t size)
{
  std::vector<double> * underlying_vec = new std::vector<double>(3*size, 1.0);

  // how to avoid extra heap allocations in constructor of small vectors
  std::vector<double> vec0(underlying_vec->begin()         , underlying_vec->begin() + size);
  std::vector<double> vec1(underlying_vec->begin() + size  , underlying_vec->begin() + 2*size);
  std::vector<double> vec2(underlying_vec->begin() + 2*size, underlying_vec->end());

  return {vec0, vec1, vec2};
}

int main(int argc, char const *argv[])
{
  int size = 1000;

  auto&& chunked_vecs = chunck_vector(size);

  // passing each chunk to different functions
  // each chunk should be responsible for managing its resources
  foo0(std::get<0>(chunked_vecs));
  foo1(std::get<1>(chunked_vecs));
  foo2(std::get<2>(chunked_vecs));

  return 0;
}

I tried writing my own vector class, which its constructor accepts two iterators specifying begin and end of the portion of the underlying_vec storage belongs to this vector, but it doesn't sound a clean solution when it comes to the job of freeing resources when the underlying vector is not accessible any more and solving the memory leakage problem.

Apparently using a customized allocator which is shared between these three vectors and allocates a contiguous memory once and assign it to the corresponding vectors seems a better solution, however since I've never written one, any hint or suggestion to help me start coding will be appreciated.

Upvotes: 1

Views: 802

Answers (2)

anatolyg
anatolyg

Reputation: 28251

You can use std::shared_ptr, whose primary purpose is management of shared resources. First of all, create your buffer:

std::shared_ptr<double> underlying(new double[3 * size], std::default_delete<double[]>());

Here you have to use default_delete as an explicit deleter, so the correct operator delete[] is used for deallocation. BTW I heard that in C++17 you no longer need to use an explicit deleter, if you use shared_ptr<double[]>.

Then define your smaller containers, using the aliasing constructor:

std::shared_ptr<double> vec0(underlying, underlying.get());
std::shared_ptr<double> vec1(underlying, underlying.get() + size);
std::shared_ptr<double> vec2(underlying, underlying.get() + 2 * size);

Here you can use your "vectors" until the last of them goes out of scope, and when that happens, the buffer is deallocated. However, these are not vectors — e.g. they don't store their size, only the pointer to first element.

Upvotes: 1

Galik
Galik

Reputation: 48615

This is the kind of thing gsl::span is designed for.

You can find an implementation HERE. It is proposed for inclusion in the C++ standard libraries.

You can use it like this:

void double_data(gsl::span<int> sp)
{
    for(auto& i: sp)
        i *= 2;
}

void tripple_data(gsl::span<int> sp)
{
    for(auto& i: sp)
        i *= 3;
}

int main()
{
    std::vector<int> v = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};

    auto sp = gsl::make_span(v); // the whole vector

    auto sp1 = sp.subspan(0, 5); // first 5 elements
    auto sp2 = sp.subspan(5, 5); // last five elements

    double_data(sp1); // process it like you would a container

    tripple_data(sp2);

    for(auto i: v)
        std::cout << i << ' ';
    std::cout << '\n';
}

Output:

2 4 6 8 10 18 21 24 27 30

Upvotes: 2

Related Questions