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
Amount of permutations on an NxNxN Rubik's Cube
How come Sam didn't become Lord of Horn Hill?
Can a new player join a group only when a new campaign starts?
If Windows 7 doesn't support WSL, then what does Linux subsystem option mean?
Why aren't air breathing engines used as small first stages?
Should I use a zero-interest credit card for a large one-time purchase?
Project Euler #1 in C++
Hangman Game with C++
Effects on objects due to a brief relocation of massive amounts of mass
How do living politicians protect their readily obtainable signatures from misuse?
How do I find out the mythology and history of my Fortress?
When a candle burns, why does the top of wick glow if bottom of flame is hottest?
What is this clumpy 20-30cm high yellow-flowered plant?
Multiple OR (||) Conditions in If Statement
A term for a woman complaining about things/begging in a cute/childish way
Most bit efficient text communication method?
How often does castling occur in grandmaster games?
Localisation of Category
Why wasn't DOSKEY integrated with COMMAND.COM?
Converted a Scalar function to a TVF function for parallel execution-Still running in Serial mode
The code below, is it ill-formed NDR or is it well formed?
Should I follow up with an employee I believe overracted to a mistake I made?
Why is my ESD wriststrap failing with nitrile gloves on?
Central Vacuuming: Is it worth it, and how does it compare to normal vacuuming?
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
11 hours ago
2
@Martinm @JesperJuhl Yes. I reduced the running time to 40 ms with 11.5 MB memory after replacingvector<bool>
withvector<char>
. Thank you.
– Qin Heyang
11 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
11 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
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
11 hours ago
2
@Martinm @JesperJuhl Yes. I reduced the running time to 40 ms with 11.5 MB memory after replacingvector<bool>
withvector<char>
. Thank you.
– Qin Heyang
11 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
11 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
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
11 hours ago
2
@Martinm @JesperJuhl Yes. I reduced the running time to 40 ms with 11.5 MB memory after replacingvector<bool>
withvector<char>
. Thank you.
– Qin Heyang
11 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
11 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
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
11 hours ago
be carfull, std::vector<bool> is a weird specialisation, more a bitset than a vector
– Martin m
11 hours ago
2
2
@Martinm @JesperJuhl Yes. I reduced the running time to 40 ms with 11.5 MB memory after replacing
vector<bool>
with vector<char>
. Thank you.– Qin Heyang
11 hours ago
@Martinm @JesperJuhl Yes. I reduced the running time to 40 ms with 11.5 MB memory after replacing
vector<bool>
with vector<char>
. Thank you.– Qin Heyang
11 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
11 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
11 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
10 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
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
7 hours ago
@cmaster Well, that's debatable ;)
– Bob__
7 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
3 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
3 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 11 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 11 hours ago
Jesper Juhl
17.9k32647
17.9k32647
answered 11 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
7 hours ago
@cmaster Well, that's debatable ;)
– Bob__
7 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
3 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
3 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
7 hours ago
@cmaster Well, that's debatable ;)
– Bob__
7 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
3 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
3 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 8 hours ago
John Kugelman
249k54407460
249k54407460
answered 8 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
7 hours ago
@cmaster Well, that's debatable ;)
– Bob__
7 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
3 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
3 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
7 hours ago
@cmaster Well, that's debatable ;)
– Bob__
7 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
3 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
3 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
7 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
7 hours ago
@cmaster Well, that's debatable ;)
– Bob__
7 hours ago
@cmaster Well, that's debatable ;)
– Bob__
7 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
3 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
3 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
3 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
3 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
11 hours ago
2
@Martinm @JesperJuhl Yes. I reduced the running time to 40 ms with 11.5 MB memory after replacing
vector<bool>
withvector<char>
. Thank you.– Qin Heyang
11 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
11 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
10 hours ago