3

I'm creating an array of bitsets on the stack using this code:

int Rows = 800000;
int Columns = 2048;

bitset<Columns> data[Rows];

If I don't raise the stack size to hundreds of Megabytes, I get an stack overflow error.

Is there any way to allocate this code on the heap? for example with a code like this (I'm not even sure if this code is right):

bitset<Columns>* data[Rows] = new bitset<Columns>();

Edit: And more importantly, does this help memory usage or speed? Does it make any difference whether I use the Stack or the Heap for this? I really don't want to use any other libraries such as Boost too...

I come from a Java background and some C++ syntax is new for me, Sorry if the question seems kind of wrong.

Asteroids With Wings
  • 17,071
  • 2
  • 21
  • 35
Cypher
  • 2,374
  • 4
  • 24
  • 36
  • `bitset* data = new bitset[Rows];` – apple apple Nov 29 '17 at 13:13
  • 1
    You may use [`std::vector`](http://en.cppreference.com/w/cpp/container/vector_bool) instead. (It's specialized.) – Scheff's Cat Nov 29 '17 at 13:13
  • 2
    First of all `new bitset()` allocates and default-constructs *one* `bitset` object. You probably want something like `bitset* data = new bitset[Rows];`. [Any good beginners book](http://stackoverflow.com/questions/388242/the-definitive-c-book-guide-and-list) would have told you that. With that said, you should really be using [`std::vector`](http://en.cppreference.com/w/cpp/container/vector). – Some programmer dude Nov 29 '17 at 13:13
  • 1
    "do I have to allocate hundreds of Megabytes to the Heap also?" - well, `800,000 x 2,048 / 8` *is* `204,800,000` bytes no matter which was you look at it. – Rotem Nov 29 '17 at 14:05
  • 1
    @Someprogrammerdude but I read elsewhere (in Stackoverflow) that the bitset's performance is superior to the std::vector. I come from a Java background would you please elaborate more on this? – Cypher Nov 29 '17 at 14:05
  • @Rotem Actually I meant manually changing the default Heap size opposed to C++ automatically extending it. By the way is this possible or should I always change the Heap size by hand just like the Stack size? – Cypher Nov 29 '17 at 14:07
  • 1
    @Cypher You don't mention the platform or compiler you're working with but normally the heap will allocate more memory as required. – Rotem Nov 29 '17 at 14:10
  • @Rotem Thanks... I'm using Visual C++ 2015 by the way. – Cypher Nov 29 '17 at 14:12
  • 2
    I mean a vector *of* bitsets. Like `std::vector> data(rows);` – Some programmer dude Nov 29 '17 at 14:16

2 Answers2

2
#include<bitset>
#include<vector>

constexpr int Rows = 800000;
constexpr int Columns = 2048;

int your_function() {
  std::vector<std::bitset<Columns> > data (Rows);

  // do something with data
}

This will allocate the memory on the heap and it will still take whatever amount of memory it took before (plus a few bytes for bookkeeping). The heap however is not limited by a fixed size like the stack, but mainly limited by how much memory the system has, so on a reasonably modern PC you should be fine with a few hundred megabytes.

I am not sure if that was your concern, but bitset's memory usage is not inefficient- sizeof(std::bitset<2048>) == 256 on gcc so you do not waste a single bit there.

PaulR
  • 3,587
  • 14
  • 24
1

Storing this in the inverse way:

int Rows = 2048;
int Columns = 800000;

bitset<Columns> data[Rows];

Will save you almost 18Mb, and it is better for data locality.

In the first method If you calculate how much memory you are using:

A = (24 * 800000) + 800000 * (2048/8) = 224x10^6 bytes

In the other hand, it you swap the row size with the column size the memory you will be using is:

B = (24 * 2048) + 2048 * (800000/8) = 204,849x10^6 bytes

where 24 is the fixed size in bytes of a vector object in C++ in most systems. So in the second case you are reducing the memory usage by using less vectors.

A - B = 19150448 bytes = 18,26 Mb

This is not the answer but it can inderctly help you solve your problem.

magmine
  • 164
  • 2
  • 15