Performance gap between vector and array Announcing the arrival of Valued Associate #679: Cesar Manara Planned maintenance scheduled April 23, 2019 at 00:00UTC (8:00pm US/Eastern) Data science time! April 2019 and salary with experience The Ask Question Wizard is Live!Is std::vector so much slower than plain arrays?Why aren't variable-length arrays part of the C++ standard?Using arrays or std::vectors in C++, what's the performance gap?Create ArrayList from arrayHow do I check if an array includes an object in JavaScript?How to append something to an array?Improve INSERT-per-second performance of SQLite?What is the difference between call and apply?Loop through an array in JavaScriptHow do I remove a particular element from an array in JavaScript?For-each over an array in JavaScript?Why is it faster to process a sorted array than an unsorted array?Replacing a 32-bit loop counter with 64-bit introduces crazy performance deviations
Putting class ranking in CV, but against dept guidelines
Question about debouncing - delay of state change
Can anything be seen from the center of the Boötes void? How dark would it be?
Why is my ESD wriststrap failing with nitrile gloves on?
Drawing without replacement: why is the order of draw irrelevant?
Using audio cues to encourage good posture
Is there any word for a place full of confusion?
Sum letters are not two different
Why weren't discrete x86 CPUs ever used in game hardware?
A term for a woman complaining about things/begging in a cute/childish way
If Windows 7 doesn't support WSL, then what does Linux subsystem option mean?
Dating a Former Employee
What initially awakened the Balrog?
What would you call this weird metallic apparatus that allows you to lift people?
How to install press fit bottom bracket into new frame
What is the font for "b" letter?
How often does castling occur in grandmaster games?
Chinese Seal on silk painting - what does it mean?
Is CEO the "profession" with the most psychopaths?
Has negative voting ever been officially implemented in elections, or seriously proposed, or even studied?
What do you call the main part of a joke?
How do I find out the mythology and history of my Fortress?
Why aren't air breathing engines used as small first stages?
What is this clumpy 20-30cm high yellow-flowered plant?
Performance gap between vector and array
Announcing the arrival of Valued Associate #679: Cesar Manara
Planned maintenance scheduled April 23, 2019 at 00:00UTC (8:00pm US/Eastern)
Data science time! April 2019 and salary with experience
The Ask Question Wizard is Live!Is std::vector so much slower than plain arrays?Why aren't variable-length arrays part of the C++ standard?Using arrays or std::vectors in C++, what's the performance gap?Create ArrayList from arrayHow do I check if an array includes an object in JavaScript?How to append something to an array?Improve INSERT-per-second performance of SQLite?What is the difference between call and apply?Loop through an array in JavaScriptHow do I remove a particular element from an array in JavaScript?For-each over an array in JavaScript?Why is it faster to process a sorted array than an unsorted array?Replacing a 32-bit loop counter with 64-bit introduces crazy performance deviations
.everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty,.everyoneloves__bot-mid-leaderboard:empty height:90px;width:728px;box-sizing:border-box;
I was trying to solve a coding problem in C++ which counts the number of prime numbers less than a non-negative number n
.
So I first came up with some code:
int countPrimes(int n)
vector<bool> flag(n+1,1);
for(int i =2;i<n;i++)
if(flag[i]==1)
for(long j=i;i*j<n;j++)
flag[i*j]=0;
int result=0;
for(int i =2;i<n;i++)
result+=flag[i];
return result;
which takes 88 ms and uses 8.6 MB of memory. Then I changed my code into:
int countPrimes(int n)
// vector<bool> flag(n+1,1);
bool flag[n+1] ;
fill(flag,flag+n+1,true);
for(int i =2;i<n;i++)
if(flag[i]==1)
for(long j=i;i*j<n;j++)
flag[i*j]=0;
int result=0;
for(int i =2;i<n;i++)
result+=flag[i];
return result;
which takes 28 ms and 9.9 MB. I don't really understand why there is such a performance gap in both the running time and memory consumption. I have read relative questions like this one and that one but I am still confused.
EDIT: I reduced the running time to 40 ms with 11.5 MB of memory after replacing vector<bool>
with vector<char>
.
c++ arrays performance vector std
|
show 1 more comment
I was trying to solve a coding problem in C++ which counts the number of prime numbers less than a non-negative number n
.
So I first came up with some code:
int countPrimes(int n)
vector<bool> flag(n+1,1);
for(int i =2;i<n;i++)
if(flag[i]==1)
for(long j=i;i*j<n;j++)
flag[i*j]=0;
int result=0;
for(int i =2;i<n;i++)
result+=flag[i];
return result;
which takes 88 ms and uses 8.6 MB of memory. Then I changed my code into:
int countPrimes(int n)
// vector<bool> flag(n+1,1);
bool flag[n+1] ;
fill(flag,flag+n+1,true);
for(int i =2;i<n;i++)
if(flag[i]==1)
for(long j=i;i*j<n;j++)
flag[i*j]=0;
int result=0;
for(int i =2;i<n;i++)
result+=flag[i];
return result;
which takes 28 ms and 9.9 MB. I don't really understand why there is such a performance gap in both the running time and memory consumption. I have read relative questions like this one and that one but I am still confused.
EDIT: I reduced the running time to 40 ms with 11.5 MB of memory after replacing vector<bool>
with vector<char>
.
c++ arrays performance vector std
6
How are you compiling your code? What compiler options? Also;vector<bool>
is special.
– Jesper Juhl
12 hours ago
12
be carfull, std::vector<bool> is a weird specialisation, more a bitset than a vector
– Martin m
12 hours ago
3
you may gain some time changing one loop a bit:for(int i = 2; i * i <n;i++)
since ifi * i >= n
then next loop does nothing.
– Marek R
12 hours ago
3
This doesn't address the question, but when you're dealing with boolean types, usetrue
andfalse
and not1
. So:vector<bool> flag(n+1, true);
andif (flag[i])
. That doesn't affect the result, but it makes it much clearer what you're doing.
– Pete Becker
11 hours ago
3
If you are not already doing so, make sure to compile your code with compiler optimizations enabled before benchmarking.
– Jesper Juhl
10 hours ago
|
show 1 more comment
I was trying to solve a coding problem in C++ which counts the number of prime numbers less than a non-negative number n
.
So I first came up with some code:
int countPrimes(int n)
vector<bool> flag(n+1,1);
for(int i =2;i<n;i++)
if(flag[i]==1)
for(long j=i;i*j<n;j++)
flag[i*j]=0;
int result=0;
for(int i =2;i<n;i++)
result+=flag[i];
return result;
which takes 88 ms and uses 8.6 MB of memory. Then I changed my code into:
int countPrimes(int n)
// vector<bool> flag(n+1,1);
bool flag[n+1] ;
fill(flag,flag+n+1,true);
for(int i =2;i<n;i++)
if(flag[i]==1)
for(long j=i;i*j<n;j++)
flag[i*j]=0;
int result=0;
for(int i =2;i<n;i++)
result+=flag[i];
return result;
which takes 28 ms and 9.9 MB. I don't really understand why there is such a performance gap in both the running time and memory consumption. I have read relative questions like this one and that one but I am still confused.
EDIT: I reduced the running time to 40 ms with 11.5 MB of memory after replacing vector<bool>
with vector<char>
.
c++ arrays performance vector std
I was trying to solve a coding problem in C++ which counts the number of prime numbers less than a non-negative number n
.
So I first came up with some code:
int countPrimes(int n)
vector<bool> flag(n+1,1);
for(int i =2;i<n;i++)
if(flag[i]==1)
for(long j=i;i*j<n;j++)
flag[i*j]=0;
int result=0;
for(int i =2;i<n;i++)
result+=flag[i];
return result;
which takes 88 ms and uses 8.6 MB of memory. Then I changed my code into:
int countPrimes(int n)
// vector<bool> flag(n+1,1);
bool flag[n+1] ;
fill(flag,flag+n+1,true);
for(int i =2;i<n;i++)
if(flag[i]==1)
for(long j=i;i*j<n;j++)
flag[i*j]=0;
int result=0;
for(int i =2;i<n;i++)
result+=flag[i];
return result;
which takes 28 ms and 9.9 MB. I don't really understand why there is such a performance gap in both the running time and memory consumption. I have read relative questions like this one and that one but I am still confused.
EDIT: I reduced the running time to 40 ms with 11.5 MB of memory after replacing vector<bool>
with vector<char>
.
c++ arrays performance vector std
c++ arrays performance vector std
edited 1 hour ago
isanae
2,55611437
2,55611437
asked 12 hours ago
Qin HeyangQin Heyang
30918
30918
6
How are you compiling your code? What compiler options? Also;vector<bool>
is special.
– Jesper Juhl
12 hours ago
12
be carfull, std::vector<bool> is a weird specialisation, more a bitset than a vector
– Martin m
12 hours ago
3
you may gain some time changing one loop a bit:for(int i = 2; i * i <n;i++)
since ifi * i >= n
then next loop does nothing.
– Marek R
12 hours ago
3
This doesn't address the question, but when you're dealing with boolean types, usetrue
andfalse
and not1
. So:vector<bool> flag(n+1, true);
andif (flag[i])
. That doesn't affect the result, but it makes it much clearer what you're doing.
– Pete Becker
11 hours ago
3
If you are not already doing so, make sure to compile your code with compiler optimizations enabled before benchmarking.
– Jesper Juhl
10 hours ago
|
show 1 more comment
6
How are you compiling your code? What compiler options? Also;vector<bool>
is special.
– Jesper Juhl
12 hours ago
12
be carfull, std::vector<bool> is a weird specialisation, more a bitset than a vector
– Martin m
12 hours ago
3
you may gain some time changing one loop a bit:for(int i = 2; i * i <n;i++)
since ifi * i >= n
then next loop does nothing.
– Marek R
12 hours ago
3
This doesn't address the question, but when you're dealing with boolean types, usetrue
andfalse
and not1
. So:vector<bool> flag(n+1, true);
andif (flag[i])
. That doesn't affect the result, but it makes it much clearer what you're doing.
– Pete Becker
11 hours ago
3
If you are not already doing so, make sure to compile your code with compiler optimizations enabled before benchmarking.
– Jesper Juhl
10 hours ago
6
6
How are you compiling your code? What compiler options? Also;
vector<bool>
is special.– Jesper Juhl
12 hours ago
How are you compiling your code? What compiler options? Also;
vector<bool>
is special.– Jesper Juhl
12 hours ago
12
12
be carfull, std::vector<bool> is a weird specialisation, more a bitset than a vector
– Martin m
12 hours ago
be carfull, std::vector<bool> is a weird specialisation, more a bitset than a vector
– Martin m
12 hours ago
3
3
you may gain some time changing one loop a bit:
for(int i = 2; i * i <n;i++)
since if i * i >= n
then next loop does nothing.– Marek R
12 hours ago
you may gain some time changing one loop a bit:
for(int i = 2; i * i <n;i++)
since if i * i >= n
then next loop does nothing.– Marek R
12 hours ago
3
3
This doesn't address the question, but when you're dealing with boolean types, use
true
and false
and not 1
. So: vector<bool> flag(n+1, true);
and if (flag[i])
. That doesn't affect the result, but it makes it much clearer what you're doing.– Pete Becker
11 hours ago
This doesn't address the question, but when you're dealing with boolean types, use
true
and false
and not 1
. So: vector<bool> flag(n+1, true);
and if (flag[i])
. That doesn't affect the result, but it makes it much clearer what you're doing.– Pete Becker
11 hours ago
3
3
If you are not already doing so, make sure to compile your code with compiler optimizations enabled before benchmarking.
– Jesper Juhl
10 hours ago
If you are not already doing so, make sure to compile your code with compiler optimizations enabled before benchmarking.
– Jesper Juhl
10 hours ago
|
show 1 more comment
3 Answers
3
active
oldest
votes
std::vector<bool>
isn't like any other vector. The documentation says:
std::vector<bool>
is a possibly space-efficient specialization of
std::vector
for the typebool
.
That's why it may use up less memory than an array, because it might represent multiple boolean values with one byte, like a bitset. It also explains the performance difference, since accessing it isn't as simple anymore. According to the documentation, it doesn't even have to store it as a contiguous array.
add a comment |
std::vector<bool>
is special case. It is specialized template. Each value is stored in single bit, so bit operations are needed. This memory compact but has couple drawbacks (like no way to have a pointer to bool
inside this container).
Now bool flag[n+1];
compiler will usually allocate same memory in same manner as for char flag[n+1];
and it will do that on stack, not on heap.
Now depending on page sizes, cache misses and i
values one can be faster then other. It is hard to predict (for small n
array will be faster, but for larger n
result may change).
As an interesting experiment you can change std::vector<bool>
to std::vector<char>
. In this case you will have similar memory mapping as in case of array, but it will be located at heap not a stack.
add a comment |
I'd like to add some remarks to the good answers already posted.
The performance differences between
std::vector<bool>
andstd::vector<char>
may vary (a lot) between different library implementations and different sizes of the vectors.See e.g. those quick benches: clang++ / libc++(LLVM) vs. g++ / libstdc++(GNU).
This:
bool flag[n+1];
declares a Variable Length Array, which (despites some performance advantages due to it beeing allocated in the stack) has never been part of the C++ standard, even if provided as an extension by some (C99 compliant) compilers.Another way to increase the performances could be to reduce the amount of calculations (and memory occupation) by considering only the odd numbers, given that all the primes except for 2 are odd.
If you can bare the less readable code, you could try to profile the following snippet.
int countPrimes(int n)
if ( n < 2 )
return 0;
// Sieve starting from 3 up to n, the number of odd number between 3 and n are
int sieve_size = n / 2 - 1;
std::vector<char> sieve(sieve_size);
int result = 1; // 2 is a prime.
for (int i = 0; i < sieve_size; ++i)
if ( sieve[i] == 0 )
// It's a prime, no need to scan the vector again
++result;
// Some ugly transformations are needed, here
int prime = i * 2 + 3;
for ( int j = prime * 3, k = prime * 2; j <= n; j += k)
sieve[j / 2 - 1] = 1;
return result;
Wow, 20 years after C99, and not even the most rudimentary VLAs... Looks like C++ is getting more and more behind C ;-) Afaik, there was once a proposal that would have madeint array[length];
legal in C++, but even that proposal did not allow for multidimensional arrays, neither on the stack (int array2d[height][width]
) nor on the heap (int (*array2d)[width] = new int[height][width];
). Apparently, that proposal was never approved, even though C goes as far as to allow the multidimensional case (int (*array2d)[width] = malloc(height * sizeof(*array2d));
) since 20 years ago...
– cmaster
8 hours ago
@cmaster Well, that's debatable ;)
– Bob__
8 hours ago
Yeah, I know. Especially since very few people actually understand the power of the C99 syntax - both of the top-scoring answers of the question you linked completely underestimate its value. Because, you see, C99 VLAs not just exist on the stack, they can also be allocated on the heap. I have already given an example of that, it's the last one. The real power comes from the fact that any C99 array type can have a runtime length, it can be pointed to or typedefed. And C99 does not care how many runtime length array types you nest, the indexing calculation comes out right.
– cmaster
4 hours ago
Long story short: I really enjoy working with C++ for the most part, but when it comes to manipulating multidimensional arrays of plain data, (images, volumes, simulations), I'll just fall back to C99 for its VLA syntax.
– cmaster
4 hours ago
add a comment |
Your Answer
StackExchange.ifUsing("editor", function ()
StackExchange.using("externalEditor", function ()
StackExchange.using("snippets", function ()
StackExchange.snippets.init();
);
);
, "code-snippets");
StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "1"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);
else
createEditor();
);
function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader:
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
,
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);
);
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f55745312%2fperformance-gap-between-vectorbool-and-array%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
3 Answers
3
active
oldest
votes
3 Answers
3
active
oldest
votes
active
oldest
votes
active
oldest
votes
std::vector<bool>
isn't like any other vector. The documentation says:
std::vector<bool>
is a possibly space-efficient specialization of
std::vector
for the typebool
.
That's why it may use up less memory than an array, because it might represent multiple boolean values with one byte, like a bitset. It also explains the performance difference, since accessing it isn't as simple anymore. According to the documentation, it doesn't even have to store it as a contiguous array.
add a comment |
std::vector<bool>
isn't like any other vector. The documentation says:
std::vector<bool>
is a possibly space-efficient specialization of
std::vector
for the typebool
.
That's why it may use up less memory than an array, because it might represent multiple boolean values with one byte, like a bitset. It also explains the performance difference, since accessing it isn't as simple anymore. According to the documentation, it doesn't even have to store it as a contiguous array.
add a comment |
std::vector<bool>
isn't like any other vector. The documentation says:
std::vector<bool>
is a possibly space-efficient specialization of
std::vector
for the typebool
.
That's why it may use up less memory than an array, because it might represent multiple boolean values with one byte, like a bitset. It also explains the performance difference, since accessing it isn't as simple anymore. According to the documentation, it doesn't even have to store it as a contiguous array.
std::vector<bool>
isn't like any other vector. The documentation says:
std::vector<bool>
is a possibly space-efficient specialization of
std::vector
for the typebool
.
That's why it may use up less memory than an array, because it might represent multiple boolean values with one byte, like a bitset. It also explains the performance difference, since accessing it isn't as simple anymore. According to the documentation, it doesn't even have to store it as a contiguous array.
answered 12 hours ago
BlazeBlaze
7,9691933
7,9691933
add a comment |
add a comment |
std::vector<bool>
is special case. It is specialized template. Each value is stored in single bit, so bit operations are needed. This memory compact but has couple drawbacks (like no way to have a pointer to bool
inside this container).
Now bool flag[n+1];
compiler will usually allocate same memory in same manner as for char flag[n+1];
and it will do that on stack, not on heap.
Now depending on page sizes, cache misses and i
values one can be faster then other. It is hard to predict (for small n
array will be faster, but for larger n
result may change).
As an interesting experiment you can change std::vector<bool>
to std::vector<char>
. In this case you will have similar memory mapping as in case of array, but it will be located at heap not a stack.
add a comment |
std::vector<bool>
is special case. It is specialized template. Each value is stored in single bit, so bit operations are needed. This memory compact but has couple drawbacks (like no way to have a pointer to bool
inside this container).
Now bool flag[n+1];
compiler will usually allocate same memory in same manner as for char flag[n+1];
and it will do that on stack, not on heap.
Now depending on page sizes, cache misses and i
values one can be faster then other. It is hard to predict (for small n
array will be faster, but for larger n
result may change).
As an interesting experiment you can change std::vector<bool>
to std::vector<char>
. In this case you will have similar memory mapping as in case of array, but it will be located at heap not a stack.
add a comment |
std::vector<bool>
is special case. It is specialized template. Each value is stored in single bit, so bit operations are needed. This memory compact but has couple drawbacks (like no way to have a pointer to bool
inside this container).
Now bool flag[n+1];
compiler will usually allocate same memory in same manner as for char flag[n+1];
and it will do that on stack, not on heap.
Now depending on page sizes, cache misses and i
values one can be faster then other. It is hard to predict (for small n
array will be faster, but for larger n
result may change).
As an interesting experiment you can change std::vector<bool>
to std::vector<char>
. In this case you will have similar memory mapping as in case of array, but it will be located at heap not a stack.
std::vector<bool>
is special case. It is specialized template. Each value is stored in single bit, so bit operations are needed. This memory compact but has couple drawbacks (like no way to have a pointer to bool
inside this container).
Now bool flag[n+1];
compiler will usually allocate same memory in same manner as for char flag[n+1];
and it will do that on stack, not on heap.
Now depending on page sizes, cache misses and i
values one can be faster then other. It is hard to predict (for small n
array will be faster, but for larger n
result may change).
As an interesting experiment you can change std::vector<bool>
to std::vector<char>
. In this case you will have similar memory mapping as in case of array, but it will be located at heap not a stack.
edited 12 hours ago
Jesper Juhl
17.9k32647
17.9k32647
answered 12 hours ago
Marek RMarek R
13.8k22777
13.8k22777
add a comment |
add a comment |
I'd like to add some remarks to the good answers already posted.
The performance differences between
std::vector<bool>
andstd::vector<char>
may vary (a lot) between different library implementations and different sizes of the vectors.See e.g. those quick benches: clang++ / libc++(LLVM) vs. g++ / libstdc++(GNU).
This:
bool flag[n+1];
declares a Variable Length Array, which (despites some performance advantages due to it beeing allocated in the stack) has never been part of the C++ standard, even if provided as an extension by some (C99 compliant) compilers.Another way to increase the performances could be to reduce the amount of calculations (and memory occupation) by considering only the odd numbers, given that all the primes except for 2 are odd.
If you can bare the less readable code, you could try to profile the following snippet.
int countPrimes(int n)
if ( n < 2 )
return 0;
// Sieve starting from 3 up to n, the number of odd number between 3 and n are
int sieve_size = n / 2 - 1;
std::vector<char> sieve(sieve_size);
int result = 1; // 2 is a prime.
for (int i = 0; i < sieve_size; ++i)
if ( sieve[i] == 0 )
// It's a prime, no need to scan the vector again
++result;
// Some ugly transformations are needed, here
int prime = i * 2 + 3;
for ( int j = prime * 3, k = prime * 2; j <= n; j += k)
sieve[j / 2 - 1] = 1;
return result;
Wow, 20 years after C99, and not even the most rudimentary VLAs... Looks like C++ is getting more and more behind C ;-) Afaik, there was once a proposal that would have madeint array[length];
legal in C++, but even that proposal did not allow for multidimensional arrays, neither on the stack (int array2d[height][width]
) nor on the heap (int (*array2d)[width] = new int[height][width];
). Apparently, that proposal was never approved, even though C goes as far as to allow the multidimensional case (int (*array2d)[width] = malloc(height * sizeof(*array2d));
) since 20 years ago...
– cmaster
8 hours ago
@cmaster Well, that's debatable ;)
– Bob__
8 hours ago
Yeah, I know. Especially since very few people actually understand the power of the C99 syntax - both of the top-scoring answers of the question you linked completely underestimate its value. Because, you see, C99 VLAs not just exist on the stack, they can also be allocated on the heap. I have already given an example of that, it's the last one. The real power comes from the fact that any C99 array type can have a runtime length, it can be pointed to or typedefed. And C99 does not care how many runtime length array types you nest, the indexing calculation comes out right.
– cmaster
4 hours ago
Long story short: I really enjoy working with C++ for the most part, but when it comes to manipulating multidimensional arrays of plain data, (images, volumes, simulations), I'll just fall back to C99 for its VLA syntax.
– cmaster
4 hours ago
add a comment |
I'd like to add some remarks to the good answers already posted.
The performance differences between
std::vector<bool>
andstd::vector<char>
may vary (a lot) between different library implementations and different sizes of the vectors.See e.g. those quick benches: clang++ / libc++(LLVM) vs. g++ / libstdc++(GNU).
This:
bool flag[n+1];
declares a Variable Length Array, which (despites some performance advantages due to it beeing allocated in the stack) has never been part of the C++ standard, even if provided as an extension by some (C99 compliant) compilers.Another way to increase the performances could be to reduce the amount of calculations (and memory occupation) by considering only the odd numbers, given that all the primes except for 2 are odd.
If you can bare the less readable code, you could try to profile the following snippet.
int countPrimes(int n)
if ( n < 2 )
return 0;
// Sieve starting from 3 up to n, the number of odd number between 3 and n are
int sieve_size = n / 2 - 1;
std::vector<char> sieve(sieve_size);
int result = 1; // 2 is a prime.
for (int i = 0; i < sieve_size; ++i)
if ( sieve[i] == 0 )
// It's a prime, no need to scan the vector again
++result;
// Some ugly transformations are needed, here
int prime = i * 2 + 3;
for ( int j = prime * 3, k = prime * 2; j <= n; j += k)
sieve[j / 2 - 1] = 1;
return result;
Wow, 20 years after C99, and not even the most rudimentary VLAs... Looks like C++ is getting more and more behind C ;-) Afaik, there was once a proposal that would have madeint array[length];
legal in C++, but even that proposal did not allow for multidimensional arrays, neither on the stack (int array2d[height][width]
) nor on the heap (int (*array2d)[width] = new int[height][width];
). Apparently, that proposal was never approved, even though C goes as far as to allow the multidimensional case (int (*array2d)[width] = malloc(height * sizeof(*array2d));
) since 20 years ago...
– cmaster
8 hours ago
@cmaster Well, that's debatable ;)
– Bob__
8 hours ago
Yeah, I know. Especially since very few people actually understand the power of the C99 syntax - both of the top-scoring answers of the question you linked completely underestimate its value. Because, you see, C99 VLAs not just exist on the stack, they can also be allocated on the heap. I have already given an example of that, it's the last one. The real power comes from the fact that any C99 array type can have a runtime length, it can be pointed to or typedefed. And C99 does not care how many runtime length array types you nest, the indexing calculation comes out right.
– cmaster
4 hours ago
Long story short: I really enjoy working with C++ for the most part, but when it comes to manipulating multidimensional arrays of plain data, (images, volumes, simulations), I'll just fall back to C99 for its VLA syntax.
– cmaster
4 hours ago
add a comment |
I'd like to add some remarks to the good answers already posted.
The performance differences between
std::vector<bool>
andstd::vector<char>
may vary (a lot) between different library implementations and different sizes of the vectors.See e.g. those quick benches: clang++ / libc++(LLVM) vs. g++ / libstdc++(GNU).
This:
bool flag[n+1];
declares a Variable Length Array, which (despites some performance advantages due to it beeing allocated in the stack) has never been part of the C++ standard, even if provided as an extension by some (C99 compliant) compilers.Another way to increase the performances could be to reduce the amount of calculations (and memory occupation) by considering only the odd numbers, given that all the primes except for 2 are odd.
If you can bare the less readable code, you could try to profile the following snippet.
int countPrimes(int n)
if ( n < 2 )
return 0;
// Sieve starting from 3 up to n, the number of odd number between 3 and n are
int sieve_size = n / 2 - 1;
std::vector<char> sieve(sieve_size);
int result = 1; // 2 is a prime.
for (int i = 0; i < sieve_size; ++i)
if ( sieve[i] == 0 )
// It's a prime, no need to scan the vector again
++result;
// Some ugly transformations are needed, here
int prime = i * 2 + 3;
for ( int j = prime * 3, k = prime * 2; j <= n; j += k)
sieve[j / 2 - 1] = 1;
return result;
I'd like to add some remarks to the good answers already posted.
The performance differences between
std::vector<bool>
andstd::vector<char>
may vary (a lot) between different library implementations and different sizes of the vectors.See e.g. those quick benches: clang++ / libc++(LLVM) vs. g++ / libstdc++(GNU).
This:
bool flag[n+1];
declares a Variable Length Array, which (despites some performance advantages due to it beeing allocated in the stack) has never been part of the C++ standard, even if provided as an extension by some (C99 compliant) compilers.Another way to increase the performances could be to reduce the amount of calculations (and memory occupation) by considering only the odd numbers, given that all the primes except for 2 are odd.
If you can bare the less readable code, you could try to profile the following snippet.
int countPrimes(int n)
if ( n < 2 )
return 0;
// Sieve starting from 3 up to n, the number of odd number between 3 and n are
int sieve_size = n / 2 - 1;
std::vector<char> sieve(sieve_size);
int result = 1; // 2 is a prime.
for (int i = 0; i < sieve_size; ++i)
if ( sieve[i] == 0 )
// It's a prime, no need to scan the vector again
++result;
// Some ugly transformations are needed, here
int prime = i * 2 + 3;
for ( int j = prime * 3, k = prime * 2; j <= n; j += k)
sieve[j / 2 - 1] = 1;
return result;
edited 9 hours ago
John Kugelman
249k54407460
249k54407460
answered 9 hours ago
Bob__Bob__
5,24331527
5,24331527
Wow, 20 years after C99, and not even the most rudimentary VLAs... Looks like C++ is getting more and more behind C ;-) Afaik, there was once a proposal that would have madeint array[length];
legal in C++, but even that proposal did not allow for multidimensional arrays, neither on the stack (int array2d[height][width]
) nor on the heap (int (*array2d)[width] = new int[height][width];
). Apparently, that proposal was never approved, even though C goes as far as to allow the multidimensional case (int (*array2d)[width] = malloc(height * sizeof(*array2d));
) since 20 years ago...
– cmaster
8 hours ago
@cmaster Well, that's debatable ;)
– Bob__
8 hours ago
Yeah, I know. Especially since very few people actually understand the power of the C99 syntax - both of the top-scoring answers of the question you linked completely underestimate its value. Because, you see, C99 VLAs not just exist on the stack, they can also be allocated on the heap. I have already given an example of that, it's the last one. The real power comes from the fact that any C99 array type can have a runtime length, it can be pointed to or typedefed. And C99 does not care how many runtime length array types you nest, the indexing calculation comes out right.
– cmaster
4 hours ago
Long story short: I really enjoy working with C++ for the most part, but when it comes to manipulating multidimensional arrays of plain data, (images, volumes, simulations), I'll just fall back to C99 for its VLA syntax.
– cmaster
4 hours ago
add a comment |
Wow, 20 years after C99, and not even the most rudimentary VLAs... Looks like C++ is getting more and more behind C ;-) Afaik, there was once a proposal that would have madeint array[length];
legal in C++, but even that proposal did not allow for multidimensional arrays, neither on the stack (int array2d[height][width]
) nor on the heap (int (*array2d)[width] = new int[height][width];
). Apparently, that proposal was never approved, even though C goes as far as to allow the multidimensional case (int (*array2d)[width] = malloc(height * sizeof(*array2d));
) since 20 years ago...
– cmaster
8 hours ago
@cmaster Well, that's debatable ;)
– Bob__
8 hours ago
Yeah, I know. Especially since very few people actually understand the power of the C99 syntax - both of the top-scoring answers of the question you linked completely underestimate its value. Because, you see, C99 VLAs not just exist on the stack, they can also be allocated on the heap. I have already given an example of that, it's the last one. The real power comes from the fact that any C99 array type can have a runtime length, it can be pointed to or typedefed. And C99 does not care how many runtime length array types you nest, the indexing calculation comes out right.
– cmaster
4 hours ago
Long story short: I really enjoy working with C++ for the most part, but when it comes to manipulating multidimensional arrays of plain data, (images, volumes, simulations), I'll just fall back to C99 for its VLA syntax.
– cmaster
4 hours ago
Wow, 20 years after C99, and not even the most rudimentary VLAs... Looks like C++ is getting more and more behind C ;-) Afaik, there was once a proposal that would have made
int array[length];
legal in C++, but even that proposal did not allow for multidimensional arrays, neither on the stack (int array2d[height][width]
) nor on the heap (int (*array2d)[width] = new int[height][width];
). Apparently, that proposal was never approved, even though C goes as far as to allow the multidimensional case (int (*array2d)[width] = malloc(height * sizeof(*array2d));
) since 20 years ago...– cmaster
8 hours ago
Wow, 20 years after C99, and not even the most rudimentary VLAs... Looks like C++ is getting more and more behind C ;-) Afaik, there was once a proposal that would have made
int array[length];
legal in C++, but even that proposal did not allow for multidimensional arrays, neither on the stack (int array2d[height][width]
) nor on the heap (int (*array2d)[width] = new int[height][width];
). Apparently, that proposal was never approved, even though C goes as far as to allow the multidimensional case (int (*array2d)[width] = malloc(height * sizeof(*array2d));
) since 20 years ago...– cmaster
8 hours ago
@cmaster Well, that's debatable ;)
– Bob__
8 hours ago
@cmaster Well, that's debatable ;)
– Bob__
8 hours ago
Yeah, I know. Especially since very few people actually understand the power of the C99 syntax - both of the top-scoring answers of the question you linked completely underestimate its value. Because, you see, C99 VLAs not just exist on the stack, they can also be allocated on the heap. I have already given an example of that, it's the last one. The real power comes from the fact that any C99 array type can have a runtime length, it can be pointed to or typedefed. And C99 does not care how many runtime length array types you nest, the indexing calculation comes out right.
– cmaster
4 hours ago
Yeah, I know. Especially since very few people actually understand the power of the C99 syntax - both of the top-scoring answers of the question you linked completely underestimate its value. Because, you see, C99 VLAs not just exist on the stack, they can also be allocated on the heap. I have already given an example of that, it's the last one. The real power comes from the fact that any C99 array type can have a runtime length, it can be pointed to or typedefed. And C99 does not care how many runtime length array types you nest, the indexing calculation comes out right.
– cmaster
4 hours ago
Long story short: I really enjoy working with C++ for the most part, but when it comes to manipulating multidimensional arrays of plain data, (images, volumes, simulations), I'll just fall back to C99 for its VLA syntax.
– cmaster
4 hours ago
Long story short: I really enjoy working with C++ for the most part, but when it comes to manipulating multidimensional arrays of plain data, (images, volumes, simulations), I'll just fall back to C99 for its VLA syntax.
– cmaster
4 hours ago
add a comment |
Thanks for contributing an answer to Stack Overflow!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f55745312%2fperformance-gap-between-vectorbool-and-array%23new-answer', 'question_page');
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
6
How are you compiling your code? What compiler options? Also;
vector<bool>
is special.– Jesper Juhl
12 hours ago
12
be carfull, std::vector<bool> is a weird specialisation, more a bitset than a vector
– Martin m
12 hours ago
3
you may gain some time changing one loop a bit:
for(int i = 2; i * i <n;i++)
since ifi * i >= n
then next loop does nothing.– Marek R
12 hours ago
3
This doesn't address the question, but when you're dealing with boolean types, use
true
andfalse
and not1
. So:vector<bool> flag(n+1, true);
andif (flag[i])
. That doesn't affect the result, but it makes it much clearer what you're doing.– Pete Becker
11 hours ago
3
If you are not already doing so, make sure to compile your code with compiler optimizations enabled before benchmarking.
– Jesper Juhl
10 hours ago