C++ error: terminate called after throwing an instance of 'std::bad_alloc' when running a function twice

user_4451521 0
Viewed 161

I have the following function

void ParticleFilter::resample() {
  /**
   * TODO: Resample particles with replacement with probability proportional 
   *   to their weight. 
   */
  // First put all the weights in a vector
  std::cout<<"Weights: ";
  for (auto const & p: particles){
    std::cout<<p.weight<<"  ";
    weights.push_back(p.weight);
  }
  std::cout<<std::endl;

  std::cout<<"Preparing distribution"<<std::endl;

  std::discrete_distribution<size_t> distr(weights.begin(), weights.end());
  std::random_device rd;

  std::cout<<"distribution prepared"<<std::endl;
  // From here we are going to get the index for the particles
  // as distr(rd)
     
  
  //std::cout<<"New Particles: ";   //<=====HERE it breaks!
  std::vector<Particle> new_particles; 
  for(int i=0;i<num_particles;i++){
    int indice = distr(rd);
    std::cout<< indice <<" ";
    new_particles.push_back(particles[indice]);
  }   
  std::cout<<std::endl;  

  particles = new_particles;
}

that is part of a bigger code. When I run the code and this function is executed it runs as expected, but when it is called a second time it throws the exception of the title.

The part where it fails is marked in the code, that means that "distribution prepared" is printed but strangely the next "New Particles" (when it was not commented) was not printed. (wonder why if they were just print statements)

After this the exception occurs. This I read is usually related to bad memory use so

I wonder if I am using the std::vector<Particle> new_particles wrong?

Annex

To understand the types used

 std::vector<double> weights;

and

struct Particle {
  int id;
  double x;
  double y;
  double theta;
  double weight;
  std::vector<int> associations;
  std::vector<double> sense_x;
  std::vector<double> sense_y;
};
std::vector<Particle> particles;
memory c++
1 Answers

You're likely running out of memory, and the bad_alloc exception is telling you as much. So I don't quite see what the confusion is about: a memory allocation has failed, an exception got thrown, your code doesn't seem to make much sense if the allocation fails and thus you don't catch the exception (since there are no reasonable recovery actions), the program terminates - all is good. Allocate less memory and you won't have that problem, or compile for 64 bits.

There are other inefficiencies as well, so let's address them all.

It's not a good idea to store sense_x and sense_y values separately: each vector allocates, so you have twice as many allocations per particle and they aren't necessarily close together in memory, so there's higher cache pressure and latency to access those. Keep them together in a single structure, e.g Point:

#include <iostream>
#include <random>
#include <type_traits>
#include <vector>

struct Point {
    double x, y;
};

struct Particle {
    int id;
    Point pos;
    double theta;
    double weight;
    std::vector<int> associations;
    std::vector<Point> sense;
};

Then, you don't need to copy the weights: they already exist, so you may as well provide an iterator that "views" them:

class const_weight_iterator : public std::vector<Particle>::const_iterator {
    using It = std::vector<Particle>::const_iterator;
    inline It &base() { return *this; }
    inline const It &base() const { return *this; }
public:
    using value_type = const double;
    using pointer = value_type*;
    using reference = value_type&;
    reference operator*() const { return base()->weight; }
    pointer operator&() const { return &(base()->weight); }
    const_weight_iterator(const_weight_iterator &) = default;
    const_weight_iterator(const It &iter) : It(iter) {}
};

We use that to create a view onto the weights in a vector of particles:

class as_const_weights {
    const const_weight_iterator m_begin, m_end;
public:
    as_const_weights(const std::vector<Particle> &v) :
        m_begin(v.begin()), m_end(v.end()) {}
    const_weight_iterator begin() const { return m_begin; }
    const_weight_iterator end() const { return m_end; }
};

Writing such code gets tedious, you'd probably want to use boost::make_transform_iterator instead - that way you don't need to write your own iterators:

class as_const_weights {
    static auto get_weight(const Particle &particle) { return particle.weight; }
    const std::vector<Particle>::const_iterator m_begin, m_end;
public:
    as_const_weights(const std::vector<Particle> &v) :
        m_begin(v.begin()), m_end(v.end()) {}
    auto begin() const { return boost::make_transform_iterator(m_begin, get_weight); }
    auto end() const { return boost::make_transform_iterator(m_end, get_weight); }
};

Another alternative may be to reuse member_access_iterator from the lug project.

And now there's no need to make a copy of weights:

void ParticleFilter::resample() {
    auto const_weights_view = as_const_weights(m_particles);

    std::cout << "Weights: ";
    for (auto weight : const_weights_view)
        std::cout << weight << "  ";
    std::cout << std::endl;

    std::discrete_distribution<size_t> distr(
        const_weights_view.begin(), const_weights_view.end()
    );
    std::random_device rd;

    auto const num_particles = m_particles.size();
    std::cout << "New Particles: ";
    std::vector<Particle> new_particles; 
    new_particles.reserve(num_particles);
    for (int i=0; i<num_particles; i++){
        int indice = distr(rd);
        std::cout << indice << " ";
        new_particles.push_back(m_particles[indice]); //*note
    }   
    std::cout << std::endl;  

    m_particles = std::move(new_particles);
}

We know exactly how many new_particles there will be, so sufficient storage can be reserved, avoiding repeated memory reallocations and both memory and copying overhead that would entail as the new_particles vector had to grow.

Since new_particles won't be used after the method returns, we move them into m_particles - this is a cheap operation, compared to the copy implied by m_particles = new_particles.

*note: I assume that the indices can repeat. Because of that, we can't move the particles into the new_particles vector, i.e. new_particles.push_back(std::move(m_particles[indice])); would be wrong. But if the indices are unique (don't repeat) then the move would be appropriate - but you'd really want to assert that fact then:

    auto const num_particles = m_particles.size();

    std::vector<Particle> new_particles; 
    new_particles.reserve(num_particles);
    std::set<int> new_indices;

    for (int i=0; i<num_particles; i++){
        int indice = distr(rd);
        std::cout << indice << " ";
        assert(new_indices.find(indice) == new_indices.end());
        // the index is unique
        new_particles.push_back(std::move(m_particles[indice]));
        new_indices.insert(indice); 
    }

I'm not sure what your exact application is and how often do you need to access the m_particles array, but there's one further step we could potentially do. Note that all that resample does is create a mapping of indices. If this resampled particle array is not accessed very often, then we won't realize the gains from sequential access - they'll be obscured by the cost of copying the particles vector.

In that case, we'd just need to generate the vector of new indices (instead of particles), and have a view that uses that:

template <class Container, class Index> class indexed_view {
    Container &m_container;
    const Index &m_index;
    using value_iter = typename Container::iterator;
    using index_iter = typename Index::const_iterator;
    using index_value = typename Index::value_type;
public:
    using value_type = typename Container::value_type;
    using size_type = typename Container::size_type;

    class iterator {
        Container &m_container;
        index_iter m_it_index, m_end_index;
        index_value m_val_index;
        auto get_index() const { return m_it_index != m_end_index ? *m_it_index : index_value{}; }
    public:
        using value_type = typename value_iter::value_type;
        using reference = typename value_iter::reference;
        using pointer = typename value_iter::pointer;
        iterator(Container &container, index_iter iter, index_iter end) : 
            m_container(container),
            m_it_index(iter), m_end_index(end),
            m_val_index(get_index())
        {}
        iterator(const iterator &) = default;
        reference operator*() const { return m_container[m_val_index]; }
        pointer operator&() const { return &(m_container[m_val_index]); }
        auto &operator++() { ++m_it_index; m_val_index = get_index(); return *this; }
        auto &operator--() { --m_it_index; m_val_index = get_index(); return *this; }
        auto operator++(int) = delete;
        auto operator--(int) = delete;
        bool operator!=(const iterator &o) const { return m_it_index != o.m_it_index; }
    };

    indexed_view(Container &container, Index &index) :
        m_container(container), m_index(index)
    {}
    auto size() const { return m_index.size(); }
    iterator begin() { return iterator(m_container, m_index.begin(), m_index.end()); }
    iterator end() { return iterator(m_container, m_index.end(), m_index.end()); }
    auto &operator[](size_type index) { return m_container[m_index(index)]; }
};

template <class T1, class T2>
auto make_indexed_view(T1 &&container, T2 &&view) {
    return indexed_view<std::decay_t<T1>, std::decay_t<T2>>(
        std::forward<T1>(container), std::forward<T2>(view)
    );
}

I don't think that Boost offers something like it, certainly the Ranges library doesn't provide it.

The ParticleFilter class now looks as follows:

class ParticleFilter {
    using size_type = std::vector<Particle>::size_type;
    std::vector<Particle> m_particles;
    std::vector<size_type> m_sampledIndex;

public:
    void resample();
    void generateSampledIndex();
    void processSampledParticles();
};

The sampled index is generated using a loop very similar to the particle sampling loop, except that instead of storing particles we just store the new indices:

void ParticleFilter::generateSampledIndex() {
    auto const_weights_view = as_const_weights(m_particles);

    std::discrete_distribution<size_t> distr(
        const_weights_view.begin(), const_weights_view.end()
    );
    std::random_device rd;

    auto const num_particles = m_particles.size();
    m_sampledIndex.clear();
    m_sampledIndex.reserve(num_particles);
    for (int i=0; i<num_particles; i++) {
        int indice = distr(rd);
        m_sampledIndex.push_back(indice);
    }
}

And now the sampled view can be easily used - the original particle vector is not disturbed.

void ParticleFilter::processSampledParticles()
{
    for (auto &particle : make_indexed_view(m_particles, m_sampledIndex)) {
        // ...
    }
}

In C++20, the make_indexed_view is not necessary (thanks HTNW!):

auto ParticleFilter::sampled_view() {
  return
    m_sampledIndex
    | std::views::transform([&](auto i) -> auto& { return m_particles[i]; });
}

void ParticleFilter::processSampledParticles()
{
    for (auto &particle : make_indexed_view(m_particles, m_sampledIndex)) {
        // ...
    }
}

Of course, you'd have to perform benchmarks to ascertain whether the indexed view is advantageous or not. Such benchmarks must be done using real data and in a release build - benchmarking debug builds provides little to no insight on performance of release builds.

user_13296520
Related