Reducing memory usage of nested vectors

Question

I recently asked this question about performance of an unordered_map, but I realize my question is probably more about this piece of code here.

I create a 8 x 10 x 30 x 30 x 24000 nested vectors of floats. This structure is used to keep track of votes in this 5D space. Many of the bins are never actually incremented, though (0 votes). The structure takes up 7.2GB of memory.

I initially thought to switch to a hash map (hence, my other question), but there's memory overhead in storing the 5D keys, and it's actually slower.

How can I improve this solution? I'd like to reduce the memory used, without giving up much speed.

Things I've thought of:

• Switching to an unordered_map (was slower and used more memory)
• Dropping to half-precision floats (I only need about 3-4 digits of precision, and the votes accumulated in any of the bins are in approximately [-3,3]) - haven't tried this
• Replacing the inner vector<float> with map<float> - haven't tried this

I'd appreciate feedback about any of these ideas.

#include <random>
#include <vector>

int main(int argc, char** argv) {
  std::default_random_engine generator;
  std::uniform_int_distribution<int> random_z(1,24000);
  std::uniform_real_distribution<float> random_vote(0.0, 1.0);

  // This makes an 8 x 10 x 30 x 30 x 24000 vector of vectors... of vectors.
  std::vector<std::vector<std::vector<std::vector<std::vector<float> > > > > votes;
  for (size_t a = 0; a < 8; ++a) {
    std::vector<std::vector<std::vector<std::vector<float> > > > a_grid;
    for (size_t b = 0; b < 10; ++b) {
      std::vector<std::vector<std::vector<float> > > b_grid;
      for (size_t y = 0; y < 30; ++y) {
        std::vector<std::vector<float> > y_grid;
        for (size_t x = 0; x < 30; ++x) {
          y_grid.push_back(std::vector<float>(24000, 0));
        }
        b_grid.push_back(y_grid);
      }
      a_grid.push_back(b_grid);
    }
    votes.push_back(a_grid);
  }

  for (int i = 0; i < 200000; ++i) {
    int z = random_z(generator); // z in [1,24000]
    for (int a = 0; a < 8; ++a) {
      for (int b = 0; b < 10; ++b) {
        for (int x = 0; x < 30; ++x) {
          for (int y = 0; y < 30; ++y) {
            float this_vote = random_vote(generator);
            if (this_vote > 0.8) {
              votes[a][b][y][x][z] += this_vote;
            }
          }
        }
      }
    }
  }
  return 0;
}

Answer 1

Since your overall number of indices just fits into 31 bits, you could try a std::map:

uint32_t keyFrom5DIndex(uint32_t a, uint32_t b, 
                        uint32_t x, uint32_t y, uint32_t z)
{
    return z+24000*(x+30*(y+30*(b+10*a)));
}

std::map<uint32_t, float> votes;
// Compute indices
votes[keyFrom5DIndex(a,b,z,y,z)] += this_vote;

Answer 2

I'm not sure whether it'll reduce memory usage as much as you'd like, but one obvious possibility would be to use a single vector, and overload an operator to provide 5D addressing into that vector.

template <class T>
class vector5 { 
   std::vector<T> data;
   size_t a, b, c, d;
public:
    vector5(size_t a, size_t b, size_b c, size_t d, size_t e) 
        : data(a*b*c*d*e),
        a(a), b(b), c(c), d(d)
    {}

    T &operator()(size_t one, size_t two, size_t three, size_t four, size_t 5) {
        one*(a+b+c+d) + two*(a+b+c) + three * (a + b) + four * (a) + five;
    }
};

Although this should require less overall memory, it does have one shortcoming: it needs to allocate a single, contiguous block of memory to hold all the data. If your heap is fragmented, that could fail outright.

Assuming you do successfully allocate the memory, this should give faster access as a general rule. Instead of chasing through five levels of pointers to get to an object, it does everything on the CPU to figure out the address of an object, then uses that object directly.

Oh -- one minor detail: since this the addressing using an overload of operator() instead of operator[], you address it like m(1,2,3,4,5) instead of m[1][2][3][4][5]. You can support the latter if you really want to badly enough, but it's pretty ugly. I posted code for a 3D version of this in a previous answer, but it's ugly enough that you'd have to be really set on using square brackets instead of parentheses to bother (especially for 5D addressing).

Answer 3

Very minor point, but possibly still worth pointing out since you're using C++11.

In C++11, you no longer need to separate the right-angle brackets:

std::vector<std::vector<std::vector<std::vector<std::vector<float> > > > > votes;

You can now put them together:

std::vector<std::vector<std::vector<std::vector<std::vector<float>>>>> votes;

Answer 4

It's not entirely clearer whether the primary issue is speed or memory. 7.2G is a fair bit, but depending on your setup, my in itself be acceptable.

Firstly, memory considerations:

I think about 18.1% of the cells are occupied and I do not see a way to get an efficient sparse approach.

How do you use your data? Can you actually move the a loop out, and run trials for each a separately? That would immediately cut the memory usage by a factor of 8.

I think the idea of using 2-byte floats should also be good. Actually, for ease of implementation, I'd work with 2-byte integers (probably shorts), and then map back to a float as required.

Using more complex data structures than vector and array is inevitably going to cost you in some way. For example, using a map<> for this problem will result in a lot of dynamic memory allocation which will cripple performance.

On the speed side, I think there is a possible 5x speed up.

You run a very large number of trials, but only 20% of these are counted. Naively, reduce the outer loop from 200000 to 40000 and you'll get the same result. Well, not exactly:

The total number of events that are counted has mean 200000 * 8*10*30*30*0.2.

This may be enough for you. Alternatively, this is a binomial distribution, and the variance will be 200000 * 8*10*30*30*(0.2*0.8). The normal distribution to the binomial is valid here, so you could sample from:

normal(mean = 200000 * 8*10*30*30*0.2, variance = 200000 * 8*10*30*30*(0.2*0.8)) to get the number of events.

A small one on the speed side is that array look-up will be fractionally faster than vector, so one could use a mix of vectors and arrays.

Putting this together (have not done the 2 byte float!):

static const unsigned dimA = 8;
static const unsigned dimB = 10;
static const unsigned dimY = 30;
static const unsigned dimX = 30;
static const unsigned dimZ = 24000;

typedef std::vector<float> ZTable;
typedef std::vector<ZTable> XTable;
typedef XTable ATable[dimA][dimB][dimY];

void voting()
{
    ATable votes;
    for (size_t a = 0; a < dimA; ++a)
        for (size_t b = 0; b < 10; ++b)
            for (size_t y = 0; y < 30; ++y)
            {
                votes[a][b][y].resize(dimX);
                for (size_t x = 0; x < 30; ++x)
                    votes[a][b][y][x].resize(dimZ);
            }
    std::cout << "alloc complete" << std::endl;

    double mean = 200000.0 * 8 * 10 * 30 * 30 *0.2;
    double variance = 200000.0 * 8 * 10 * 30 * 30 * 0.2 * (1-0.2);
    double sd = sqrt(variance);

    std::default_random_engine generator;
    std::uniform_int_distribution<int> random_z(1, dimZ);
    std::uniform_int_distribution<int> random_y(1, dimX);
    std::uniform_int_distribution<int> random_x(1, dimY);
    std::uniform_int_distribution<int> random_a(1, dimA);
    std::uniform_int_distribution<int> random_b(1, dimB);
    std::uniform_real_distribution<float> random_vote(0.8, 1.0);
    std::normal_distribution<double> eventDistribution(mean, sd);

    double events = eventDistribution(generator);
    int loops = (int)(events / (8 * 10 * 30 * 30));
    double lostEvents = events - (8.0 * 10 * 30 * 30)*loops;
    std::cout << "Running " << loops << " loops" << std::endl;
    std::cout << "Lost events " << lostEvents << std::endl;

    for (int i = 0; i < loops; ++i) {
        int z = random_z(generator); // z in [1,24000]
        std::cout << i << " ";
        for (int a = 0; a < 8; ++a) 
            for (int b = 0; b < 10; ++b) 
                for (int x = 0; x < 30; ++x) 
                    for (int y = 0; y < 30; ++y) {
                        float this_vote = random_vote(generator);
                            votes[a][b][y][x][z-1] += this_vote;

                    }
    }
    // Still need to cast votes equal to `lostEvents`
    std::cout << "Lost events " << lostEvents << std::endl;
    for (unsigned i = 0; i < lostEvents; ++i)
    {
        int z = random_z(generator);
        int y = random_y(generator);
        int x = random_x(generator);
        int a = random_a(generator);
        int b = random_b(generator);
        float this_vote = random_vote(generator);
        votes[a-1][b-1][y-1][x-1][z-1] += this_vote;
    }
    std::cout << "votes complete" << std::endl;
}

EDIT: Corrected array indices to run from 0.

This runs in about 10 minutes on my machine (in debug mode).

Note that depending on your system , you can readily thread this as well. Doing this in release mode, and I get a run in less than minute.

Having done all this, some remarks on using 16 bits for the vote storage. As noted above, rather the using an actual 16-bit float, I'd just map into a short; effectively this is a fixed point with a maximum value of 16. Analysis of the table gives an actual maximum of 8.1 or so.

typedef std::vector<short> ZTable;

const unsigned short maxVote = 1 << 12;
float shortToFloat(unsigned short vote)
{
    return vote*1.0 / maxVote;
}
unsigned short floatToShort(float vote )
{
    float this_vote = vote * maxVote;
    unsigned short vote = (unsigned short)this_vote;
}