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;








16















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>.










share|improve this question



















  • 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 if i * 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 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





    If you are not already doing so, make sure to compile your code with compiler optimizations enabled before benchmarking.

    – Jesper Juhl
    10 hours ago


















16















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>.










share|improve this question



















  • 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 if i * 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 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





    If you are not already doing so, make sure to compile your code with compiler optimizations enabled before benchmarking.

    – Jesper Juhl
    10 hours ago














16












16








16








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>.










share|improve this question
















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






share|improve this question















share|improve this question













share|improve this question




share|improve this question








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 if i * 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 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





    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





    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 if i * 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 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





    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













3 Answers
3






active

oldest

votes


















18














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 type bool.




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.






share|improve this answer






























    13














    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.






    share|improve this answer
































      2














      I'd like to add some remarks to the good answers already posted.




      • The performance differences between std::vector<bool> and std::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;






      share|improve this answer

























      • 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











      • 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











      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
      );



      );













      draft saved

      draft discarded


















      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









      18














      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 type bool.




      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.






      share|improve this answer



























        18














        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 type bool.




        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.






        share|improve this answer

























          18












          18








          18







          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 type bool.




          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.






          share|improve this answer













          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 type bool.




          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.







          share|improve this answer












          share|improve this answer



          share|improve this answer










          answered 12 hours ago









          BlazeBlaze

          7,9691933




          7,9691933























              13














              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.






              share|improve this answer





























                13














                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.






                share|improve this answer



























                  13












                  13








                  13







                  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.






                  share|improve this answer















                  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.







                  share|improve this answer














                  share|improve this answer



                  share|improve this answer








                  edited 12 hours ago









                  Jesper Juhl

                  17.9k32647




                  17.9k32647










                  answered 12 hours ago









                  Marek RMarek R

                  13.8k22777




                  13.8k22777





















                      2














                      I'd like to add some remarks to the good answers already posted.




                      • The performance differences between std::vector<bool> and std::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;






                      share|improve this answer

























                      • 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











                      • 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















                      2














                      I'd like to add some remarks to the good answers already posted.




                      • The performance differences between std::vector<bool> and std::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;






                      share|improve this answer

























                      • 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











                      • 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













                      2












                      2








                      2







                      I'd like to add some remarks to the good answers already posted.




                      • The performance differences between std::vector<bool> and std::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;






                      share|improve this answer















                      I'd like to add some remarks to the good answers already posted.




                      • The performance differences between std::vector<bool> and std::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;







                      share|improve this answer














                      share|improve this answer



                      share|improve this answer








                      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 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











                      • 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











                      • @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

















                      draft saved

                      draft discarded
















































                      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.




                      draft saved


                      draft discarded














                      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





















































                      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







                      Popular posts from this blog

                      Isurus Índice Especies | Notas | Véxase tamén | Menú de navegación"A compendium of fossil marine animal genera (Chondrichthyes entry)"o orixinal"A review of the Tertiary fossil Cetacea (Mammalia) localities in wales port taf Museum Victoria"o orixinalThe Vertebrate Fauna of the Selma Formation of Alabama. Part VII. Part VIII. The Mosasaurs The Fishes50419737IDsh85068767Isurus2548834613242066569678159923NHMSYS00210535017845105743

                      Wolfenstein 3D Contents Availability Essential improvements Game data Video settings Input settings Audio settings Network VR support Issues fixed Other information System requirements NotesReferences    3D Realms Wolfenstein 3D pageGOG.com Community DiscussionsGOG.com Support PageSteam Community DiscussionsWolfenstein WikiOfficial websiteAmazon.comBethesda.netGamersGateGOG.comGreen Man GamingHumble StoreSteamweb browser versionWolfenstein 3D: Super UpgradesherehereUltraWolfhereWolfMenuECWolf Wolf4SDL WolfGL WinWolf3d NewWolf BetterWolf Sprite Fix and Rotation Project    Wolfenstein 3D VRSplitWolfWolfenstein 3D VRWolfenstein 3D VRWolfenstein 3D VR4DOS command shellFreeDOS's MORE.COMMacBin themthis shim fileWine regeditRELEASE: QUAKE II + III, WOLFENSTEIN 3D, RETURN TO CASTLE WOLFENSTEIN - GOG.com NewsMac Family - Wolfenstein Wiki - WikiaNerdly Pleasures: How many FPS? - DOS Games and Framerates

                      Король Коль Исторические данные | Стихотворение | Примечания | Навигацияверсии1 правкаверсии1 правкаA New interpretation of the 'Artognou' stone, TintagelTintagel IslandАрхивировано