fmm's blog

c++ STL vector is too slow
By fmm, 11 years ago, In English

Today I got surprised getting TLE(s) for the problem C of the round #201 (http://mirror.codeforces.com/contest/346/problem/C) during practice. Looks like this problem was caused by stl-vector. Then, I decided to test using my own adjacency list (like the one I usually do for maxflow/mincost) and got ACC. Is it normal vector to be that slow?

stl-vector: http://mirror.codeforces.com/contest/346/submission/4525014

"my"-own-vector: http://mirror.codeforces.com/contest/346/submission/4524990

  • Vote: I like it
  • -3
  • Vote: I do not like it

»
11 years ago, # |
  Vote: I like it +13 Vote: I do not like it

One vector is not that slow. However, in your stl-vector code you allocate a million vectors! What happens then? Well, for each vector are allocated 3 pointers (begin, end and storage) as well as some elements for initial storage (this size doubles every time when reached). When you have a single vector that overhead is not that much, but when you have a million of them, it is terrifying.

Note: The same holds for other STL data structures as well — for example allocating a million priority_queues results in the same overhead.

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    For each vector exactly one pointer is allocated and deallocated. It's size not doubles (at least in MS VC++, and there are some issues why not to do doubling), but is new_size = size * 1.5;. Actually, there is no problems with having a million vectors [until app is under some debugger on Win and each memory deallocation is checked, like any run from MS VC++ IDE, including Release mode], but there is a problem that std::vector class is very slow on push_back while it's size is small.

    → Reply
»
11 years ago, # |
  Vote: I like it +13 Vote: I do not like it

OK with your code and STL vector: http://mirror.codeforces.com/contest/346/submission/4529404. You should add reserve to some small value if you're feeling that the worst test can got TLE, because there are too many reallocations on small vector sizes.

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Nice! Thank you for restoring my faith in vector again.

    → Reply
»
11 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

Thank you fmm! very nice.

Accidental today I read a text that related to your blog entry.I hope was attractive :

The sign of a mature professional is keeping the simple jobs simple. This is particularly challenging for those who are just learning a new subject. Medical students provide a classic example of this problem. After sitting through a few lectures on obscure tropical diseases, a young doctor worries that any patient with a sniffle and a rash might have the Ebola virus or bubonic plague, while a more experienced physician just sends them home with a bottle of aspirin.

Likewise, youmay have recently learned about balanced binary search trees, exception handling, parallel processing, and various models of object inheritance. These are all useful and important subjects. But they are not necessarily the best way to get a correct program working for a simple job.
→ Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

To expand on the reserve suggestion. The issue with this code is not std::vector, it is push_back. Your custom vector uses static memory, so adding elements is trivial because the memory is already-allocated. std::vectors were designed to allow dynamic memory usage and resizing them.

A vector has a bunch of space allocated for it. Using push_back when the space is already-allocated is similar to your custom vector. But when push_back would make the required space bigger than the allocated space, vector needs to reallocate memory. I think that what really happens is that it reallocates twice of the memory it needs, so that the next n push_backs don't cause it. Reallocations are very expensive. In your code you have plenty of vectors and each of them has to reallocate multiple times.

reserve() makes it so the reallocation happens only once per vector and in order. But it brings a new issue, the memory is now static. In order to keep memory dynamic and be able to add elements without this issue, you could use another data structure. std::vector needs all of this issue because it is supposed to allow random access. In your code it seems that you don't need random access because you just iterate through the vectors.

→ Reply