3. Store indices of std::vector elements in the vector itself

Store indices of std::vector elements in the vector itself


  • std::deque is seldomly a good alternative because in all implementations known to me it has a huge overhead per chunk. Thus std::deque needs a lot more memory than std::vector does. std::deque is viable for few elements only.
    Do you have to keep 50GB in RAM to access it all at once? Can´t you divide your data in small chunks and process them separately.
    Maybe a memory mapped file is an option?

    0
  • S

    DocShoe schrieb:

    std::deque is seldomly a good alternative because in all implementations known to me it has a huge overhead per chunk. Thus std::deque needs a lot more memory than std::vector does.

    What do you consider huge overhead per chunk?

    I have a special container that I use for lots of data - so I never used deque, but on paper it looks fine to me.

    0
  • Mod

    Shade Of Mine schrieb:

    DocShoe schrieb:

    std::deque is seldomly a good alternative because in all implementations known to me it has a huge overhead per chunk. Thus std::deque needs a lot more memory than std::vector does.

    What do you consider huge overhead per chunk?

    I have a special container that I use for lots of data - so I never used deque, but on paper it looks fine to me.

    std::deque is like std::list. It looks fine on paper but in practice they are both very cumbersome and often outperformed by a std::vector, because everything that they are not optimized for takes a lot of time. I.e. filling a deque is slightly faster than filling a vector (without using reserve) but you will lose that time later when accessing the elements.

    I do not see any advantage of using a deque over a vector in this case. A deque may be better if you have a fragmented heap and are you are almost out of memory as it can use smaller chunks of memory. But with a computer that can hold 50 GB of data at all, you are certainly on a 64-bit system with a huge virtual (and physical) address space and can easily allocate continous chunks of this size.

    edit: The real question is of course if you need the 50 GB at all. Novice programmers (for example those that do not know std::size_t 😉 ) often want to store all data in memory prematurely and then apply their algorithm to the data. Oftentimes you do not really need all the data at once and you can come up with an algorithm (or often even the same algorithm!) that works on a stream of data being read from disk bit by bit.

    0

  • The STLport and Dinkumware STL implemtation use map sizes depending on the size of the deque´s template parameter. I don´t remember the STLport details, but the Dinkumware uses a block size of max( sizeof( T ), 16 ). In addition, a pointer to each block is stored (4 additional bytes). The overhead is moderate for large (let´s say 100 bytes), but enormous for medium sized objects (20-40 bytes -> 20%/10% overhead).

    0
  • S

    DocShoe schrieb:

    uses a block size of max( sizeof( T ), 16 )

    OK, that's retarded.
    So deque is never usefull. Got it 🙂

    0
  • S

    The PC I use has 256GB of RAM; the code I writing will be executed just a few times to make classifier (~2MB of data) which will be used in production.

    Why I should worry about 40GB of data and invest months of time to make HDD-based algorithm (which will be slower and buggier) if I can get result in 2 weeks?

    P.S. There are no problems with std::vector containing large amount of data. There is some delay (~3 sec) in push_back when the size of underlying storage is doubled from, for example, 16 to 32 gigabytes, but this is totally acceptable since the software runs for ~20 hours.
    P.P.S: The part of code I asked here already works (and tested), thanks for std::size_t .

    0

  • SAn schrieb:

    The PC I use has 256GB of RAM; the code I writing will be executed just a few times to make classifier (~2MB of data) which will be used in production.

    Why I should worry about 40GB of data and invest months of time to make HDD-based algorithm (which will be slower and buggier) if I can get result in 2 weeks?

    P.S. There are no problems with std::vector containing large amount of data. There is some delay (~3 sec) in push_back when the size of underlying storage is doubled from, for example, 16 to 32 gigabytes, but this is totally acceptable since the software runs for ~20 hours.

    lol, nice. Only few people have such hardware at hand, that´s why I asked.

    0
  • ?

    SAn schrieb:

    P.S. There are no problems with std::vector containing large amount of data. There is some delay (~3 sec) in push_back when the size of underlying storage is doubled from, for example, 16 to 32 gigabytes, but this is totally acceptable since the software runs for ~20 hours.

    If you know the sinal size of the vector in advance or if you can make a rough estimate, you can allocate the memory in advance using std::vector::reserve().

    0
  • S

    We have successfully finished the project.

    After I corrected my code I realized that third party libraries also crash on big data, so I needed to correct them too. Int is used everywhere instead of std::size_t! So I am not the only one who did not use size_t. Surprisingly, standard C++ library (Visual Studio 10 in my case) has no problems with big data.

    Final version of program consumes 180GB of memory, but works on computer with only 128GB of RAM (just swapping).

    So, there is no need to rewrite code to use disk instead of RAM. Operating system will automatically "convert" your program from RAM to HDD version if needed.

    0
  • P

    asdfasd schrieb:

    But it is not guaranteed that std::size_t is big enough to hold indices for 50GB

    Well, std::vector<T>::size_type defaults to std::size_t, AND the maximum size of a vector is given by std::vector<T>::max_size() which returns an size_type. That means, std::size_t is big enough to express any index a vector element could possibly have.

    0
Anmelden zum Antworten