| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3823 |
| 3 | Benq | 3738 |
| 4 | Radewoosh | 3633 |
| 5 | jqdai0815 | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | ksun48 | 3390 |
| 10 | gamegame | 3386 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 167 |
| 2 | Um_nik | 163 |
| 2 | maomao90 | 163 |
| 4 | atcoder_official | 161 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 157 |
| 8 | TheScrasse | 154 |
| 9 | nor | 153 |
| 9 | Dominater069 | 153 |
Dear all,
I tried to write a program that called a function that used a temporary vector of size 10 10^6 times. This program ran for around 1 ~ 2 seconds. However, when I switched the vector to a bool array, it ran in 0.18 seconds. Why is there such a big difference?
in general vector is a little slower than array but not that much. but in your case you maybe trying to pass vector to function by value which takes a copy from the vector every time you call the function, maybe this is the problem, can you provide more details about what you are trying to do.
Creation of small temporary vector is very slow, because it uses dynamic memory allocation. Also access to the small local array is much faster because it is located on the stack.
Thank you! That explains a lot.
Auto comment: topic has been updated by le9018468 (previous revision, new revision, compare).
was that a
vector<bool>?https://en.cppreference.com/w/cpp/container/vector_bool
in libstdc++ (g++) at least,
vector<bool>is 8 times more space-efficient than it may seem to be, but storing each bool as a bit makesvector<bool>slower. usevector<char>for faster write-access.benchmarking: https://privatebin.net/?60dfb7b8ccbba335#1sAIKHl7q6epmIuSqYgASYc0Y6boMbgcDhfdY7tQhaY=
compiled with
g++ o.cpp -std=c++17, so all compiler optimizations are disabled to prevent compiler from breaking benchmark. my copy's of GCC version is8.2.0.these are average results on my PC:
is this a sufficient answer?
EDIT:
as people who answered to this comment said, bechmarking without compiler optimizations is a bad idea and it really is.
don't believe the numbers in this benchmark. in short,
vector<bool>(with-O1or more) is much faster than it is in this "benchmark" and compares well to (sometimes is faster than)vector<char>.making excuses, i must say that i didn't except the case of OP not using any optimizations. honestly, now i can't think of a better reason of OP's time difference than no optimizations +
vector<bool>.Very baaaad idea to do any benchmarks without compiler optimizations. STL implementation has a lot of temporary objects, iterators, proxy objects, allocator structures and function calls, and so on. And all this stuff is inlined or omitted with enabled optimizations.
You can see that at godbolt: Just look at generated asm code, then delete -O2 and you will see the difference =)
My main goal was to show the difference between
vector<bool>andvector<char>, and thatvector<char>results are comparable withbool []. So there seems to be no reason for me to mess with "benchmark"'s functions to make them work as intended with optimizations.-Onwhere n>=1 produces binary that seems to ignore f0() and f1() => breaks the "benchmark":-O1:-O2:-O3:If array is not used it can be removed (by optimization) but vector is not. Even more if you have small array it can be optimized to use registers (without memory allocation). But vector produces constructor/destructor calls (side effects) and can't be optimized as good as array. something like that ...
I really think that this is out of the initial question's scope.
This is where difference of execution speed come from.
I will break it down then.
The question was about why is
vectoraround 10 times slower thanbool [].Because normally the
vector<T>andT [](where T is some (possibly not) numeric type) working times are of the same order of magnitude, I thought that the OP was usingvector<bool>and provided an answer which took that almost as a fact.To prove the point, I made a simple "benchmark". The "benchmark" suffers from being able to be optimized by compiler, what would lead to "benchmarking" functions not doing what was intended. That's why I compiled the program without optimizations flags (what is equal to
-O0).vector<bool>execution time was >> thanvector<char>andbool []. Why are we talking about optimizations? In case of a real program (unlike this "benchmark"), optimizations wouldn't makevector<bool>as fast asvector<char>or well-comparing tobool []. (at least I hope so)If after optimization program not doing what was intended this is bad optimization. I think in your case this is not a bad optimization but bad benchmarks. Sorry.
I have never said compiler optimizations are bad. The "benchmark" is not perfect at all, but is sufficient to prove the point.
=======================================================================
This is what my previous comment was about. With
-O0you get7.5xfactor forvector<bool>vsvector<char>. And with-O2you get only2xfactor. And as I tried to show you, the compiler actually does a lot of optimization for thereal program. Benchmarking code with-O0is like benchmarking it in Python, that is the results do not reflect the real situation in any way for C++ real program (i.e. submission with -O2).In your case, the problem is that your test code is very week. Your code should calculate some check-value and return it. The math under calculations should be simple, but not too much, so that the compiler can not make O(1) from it. Some Fibonacci-like DP or simple algorithms like Eratosthenes sieve will help you to make a good benchmark =)
My "benchmark" giving 2x factor with
-O2is because of that weakness you mentioned.I only needed to prove that
vector<bool>is slower because of memory (not as in -On) optimization. There is no need for a stronger test period.As said above, you can prove nothing with
-O0. The results with optimization will be vastly different.Also, the statement "
vector<bool>is slower" is false. There are situations when it may be faster.Okay.
I made an Eratosthenes-sieve-like test (and readed some stuff on the internet). The factor between vectors changed to a much smaller one.
So, yeah you're right.
I'll update my answer accordingly.
Try to increase memory footprint for example take M=20 in your code and you will see vector bool "will shine". The performance depends on many factors and can't be checked with such naive benchmarks.