### le9018468's blog

By le9018468, history, 3 months ago, ,

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?

•
• +11
•

 » 3 months ago, # |   +13 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.
 » 3 months ago, # |   +57 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.
•  » » 3 months ago, # ^ |   0 Thank you! That explains a lot.
 » 3 months ago, # |   0 Auto comment: topic has been updated by le9018468 (previous revision, new revision, compare).
 » 3 months ago, # | ← Rev. 7 →   +8 was that a vector?https://en.cppreference.com/w/cpp/container/vector_boolin libstdc++ (g++) at least, vector is 8 times more space-efficient than it may seem to be, but storing each bool as a bit makes vector slower. use vector for faster write-access.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 is 8.2.0. these are average results on my PC: bool a[10]: 0.22284 char a[10]: 0.20345 vector a(10): 3.44415 /* see EDIT */ vector a(10): 0.46760 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 (with -O1 or more) is much faster than it is in this "benchmark" and compares well to (sometimes is faster than) vector.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.
•  » » 3 months ago, # ^ |   +17 compiled with g++ o.cpp -std=c++17 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 =)
•  » » » 3 months ago, # ^ |   0 My main goal was to show the difference between vector and vector, and that vector results are comparable with bool []. So there seems to be no reason for me to mess with "benchmark"'s functions to make them work as intended with optimizations.-On where n>=1 produces binary that seems to ignore f0() and f1() => breaks the "benchmark":-O1: bool a[10]: 0.00000 char a[10]: 0.00000 vector a(10): 0.20992 vector a(10): 0.08911 -O2: bool a[10]: 0.00000 char a[10]: 0.00000 vector a(10): 0.15215 vector a(10): 0.08526 -O3: bool a[10]: 0.00000 char a[10]: 0.00000 vector a(10): 0.00995 vector a(10): 0.00000 
•  » » » » 3 months ago, # ^ | ← Rev. 2 →   +5 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 ...
•  » » » » » 3 months ago, # ^ |   0 I really think that this is out of the initial question's scope.
•  » » » » » » 3 months ago, # ^ |   0 This is where difference of execution speed come from.
•  » » » » » » » 3 months ago, # ^ |   0 I will break it down then.The question was about why is vector around 10 times slower than bool [].Because normally the vector and T [] (where T is some (possibly not) numeric type) working times are of the same order of magnitude, I thought that the OP was using vector 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 execution time was >> than vector and bool []. Why are we talking about optimizations? In case of a real program (unlike this "benchmark"), optimizations wouldn't make vector as fast as vector or well-comparing to bool []. (at least I hope so)
•  » » » » » » » » 3 months ago, # ^ |   0 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.
•  » » » » » » » » » 3 months ago, # ^ | ← Rev. 2 →   0 I have never said compiler optimizations are bad. The "benchmark" is not perfect at all, but is sufficient to prove the point.
•  » » » » » » » » 3 months ago, # ^ |   0 ======================================================================= In case of a real program (unlike this "benchmark"), optimizations wouldn't make vector bool as fast as vector char or well-comparing to bool []. (at least I hope so) This is what my previous comment was about. With -O0 you get 7.5x factor for vector vs vector. And with -O2 you get only 2x factor. And as I tried to show you, the compiler actually does a lot of optimization for the real program. Benchmarking code with -O0 is 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). The "benchmark" suffers from being able to be optimized by compiler. 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 =)
•  » » » » » » » » » 3 months ago, # ^ |   0 My "benchmark" giving 2x factor with -O2 is because of that weakness you mentioned.I only needed to prove that vector is slower because of memory (not as in -On) optimization. There is no need for a stronger test period.
•  » » » » » » » » » 3 months ago, # ^ |   0 As said above, you can prove nothing with -O0. The results with optimization will be vastly different.Also, the statement "vector is slower" is false. There are situations when it may be faster.
•  » » » » » » » » » 3 months ago, # ^ |   0 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. bool a[10]: 0.04205 char a[10]: 0.03920 vector a(10): 0.04339 vector a(10): 0.03941 So, yeah you're right.I'll update my answer accordingly.
•  » » » » » » » » 3 months ago, # ^ | ← Rev. 3 →   0 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.
•  » » » » » » » » » 3 months ago, # ^ |   0 bool a[20]: 0.44639 char a[20]: 0.40669 vector a(20): 7.01062 vector a(20): 0.89420