Fastest way to reset every value of std::vector<int> to 0

Question

What's the fastest way to reset every value of a std::vector<int> to 0 and keeping the vectors initial size ?

A for loop with the [] operator ?

Vulgarity

std::fill – Portraiture

"Fastest" as in performance? Or as in easiest to implement/maintain? – Anklet

Answer 1

std::fill(v.begin(), v.end(), 0);

Nikolos

Looking at the assembly output, gcc actually unrolls this loop into using the mmx registers to dump in 16 bytes at a time until it gets close to the end. I'd say that's pretty fast. The memset version jumps to memset, which I'm guessing is about as fast. I'd use your method. – Inheritable

But, jumping to memset is a single instruction, so using it will result in a smaller binary size. – Sonasonant

this is not exactly what OP asked for, but simply reassigning your vector to a new one of the same size (v = std::vector<int>(vec_size,0)) seems slightly faster than fill on my machine – Vowel

This is the most idiomatic way of doing it, more idiomatic than using assign. – Crosscurrent

does assigning it to a new vector do heap allocation ? and then discard the allocation of the existing vector ? I could see that being slower than memset et al – Grand

Here it is the library and the compiler converting the std::fill(..., 0) into memset: godbolt.org/z/DcbH7d – Crosscurrent

std::fill(v.begin(), v.end(),(dataType) 0); std::fill and std::accumulate do not seem to work for me without type casting on GCC 7.5 – Polyphyletic

Answer 2

As always when you ask about fastest: Measure! Using the Methods above (on a Mac using Clang):

Method      |  executable size  |  Time Taken (in sec) |
            |  -O0    |  -O3    |  -O0      |  -O3     |  
------------|---------|---------|-----------|----------|
1. memset   | 17 kB   | 8.6 kB  | 0.125     | 0.124    |
2. fill     | 19 kB   | 8.6 kB  | 13.4      | 0.124    |
3. manual   | 19 kB   | 8.6 kB  | 14.5      | 0.124    |
4. assign   | 24 kB   | 9.0 kB  | 1.9       | 0.591    |

using 100000 iterations on an vector of 10000 ints.

Edit: If changeing this numbers plausibly changes the resulting times you can have some confidence (not as good as inspecting the final assembly code) that the artificial benchmark has not been optimized away entirely. Of course it is best to messure the performance under real conditions. end Edit

for reference the used code:

#include <vector>

#define TEST_METHOD 1
const size_t TEST_ITERATIONS = 100000;
const size_t TEST_ARRAY_SIZE = 10000;

int main(int argc, char** argv) {

   std::vector<int> v(TEST_ARRAY_SIZE, 0);

   for(size_t i = 0; i < TEST_ITERATIONS; ++i) {
   #if TEST_METHOD == 1 
      memset(&v[0], 0, v.size() * sizeof v[0]);
   #elif TEST_METHOD == 2
      std::fill(v.begin(), v.end(), 0);
   #elif TEST_METHOD == 3
      for (std::vector<int>::iterator it=v.begin(), end=v.end(); it!=end; ++it) {
         *it = 0;
      }
   #elif TEST_METHOD == 4
      v.assign(v.size(),0);
   #endif
   }

   return EXIT_SUCCESS;
}

Conclusion: use std::fill (because, as others have said its most idiomatic)!

Engler

+1. This particular benchmark isn't conclusive, but the point is absolutely correct, you should write a performance test of the alternatives as they will actually be used. If there's no performance difference then use whichever is the simplest source. – Curfew

"... not conclusive ..." IMO this inconclusiveness in itself is already a good point for doing benchmarks, more often than not the Optimizer already does a very good job for the kind of situations the OP asked about. And I'd modify your last sentence to read "If there's no significant performance difference ..." – Engler

By "not conclusive" I meant that just because they were all the same speed in this program doesn't necessarily mean they'll all be the same speed in the questioner's program. Aside from anything else, you'd need to be certain that the memory was actually zeroed - it could be the optimizer was smart enough to cheat the test. But since you don't have the questioner's program, that's not a failing of this answer :-) And you're absolutely right, it's very easy to spend time agonizing over a choice that actually makes no difference at all (or an insignificant difference) once optimized. – Curfew

+1: edited the answer to address your very relevant observations. – Engler

where's vector.assign, which exists expressly for this purpose? – Confectioner

UPDATE Using Nonius for benchmarks: clang3.6-libc++-c++1y-O3, gcc4.9-c++1y-O3 and gcc5-c++1y-O3 - TL;DR: assign is slower, except for small capacities on libc++. CODE coliru/paste – Interrupted

What about the new "for-each" syntax? for (auto& elem : v) elem = 0; My understanding is that compilers can take extreme liberties in optimizing these sorts of loops, it's still pretty idiomatic, and it doesn't rely on std::fill (in fact since it can be implemented in a template for any writeable iterable class, it doesn't even rely on the standard library). – Lutherlutheran

Also, wow, if you care about speed without optimizations (which might be plausible if you are deploying in 'debug' mode, which some teams do), fill looks terrible. It is two orders of magnitude slower in this test. – Lutherlutheran

assign seems to me more meaningful API and there's no reason it should be slower than fill, so I will consider that a problem in the implementation. And also it's faster than fill on debug so I prefer it anyway. – Girlhood

@ceztko, maybe .assign is slower because it contemplates (through conditionals) whether to resize the vector. In that sense std::fill is more idiomatic because it doesn't take an argument with the size. There should be an .assign(Value) function. – Crosscurrent

@alfC: a bound check can't cost almost 0.5 secs compared to the other methods, and of course the non resize case should be favoured in the implementation. – Girlhood

@ceztko, in the gcc implementation of STL, assign consists in two conditionals (comparing to size and capacity) and if the case is favorable, it calls std::fill_n and and internal erase_at_end (which surely entails an additional conditional). – Crosscurrent

@KyleStrand: It's not that fill is terrible, it is a template and the code is generated with -O0 inside your translation unit. When you use memset, you are using the libc code which was compiled with -O3 (even when you compile your code with -O0). If you care about speed in debug and you use templates, you will have to use explicit template instantiation in a separate file which you compile with -O3 – Airlie

Answer 3

How about the assign member function?

some_vector.assign(some_vector.size(), 0);

Clasping

The OP wanted to reset existing values, but your answer is better when wanting to resize and reset the values. Thanks! – Hoelscher

Answer 4

If it's just a vector of integers, I'd first try:

memset(&my_vector[0], 0, my_vector.size() * sizeof my_vector[0]);

It's not very C++, so I'm sure someone will provide the proper way of doing this. :)

Microanalysis

Since the standard (2003 TC1) guarantees that a std::vector is contiguous in memory, this should be fine. If your c++ library does not conform to the 2003 TC1, then don't use this. – Malawi

@Mario: I wouldn't have posted this unless that was true and assumed to be well-known, of course. :) But thanks. – Microanalysis

I checked the assembly. The ::std::fill method expands to something that's pretty darned fast, though a bit on the code-bloaty side since it's all inline. I'd still use it though because it's much nicer to read. – Inheritable

You'd better to add check if vector is empty and do nothing in this case. Calculating &buf[0] for empty vector can generate assertions in STL code. – Sharyl

Answer 5

I had the same question but about rather short vector<bool> (afaik the standard allows to implement it internally differently than just a continuous array of boolean elements). Hence I repeated the slightly modified tests by Fabio Fracassi. The results are as follows (times, in seconds):

            -O0       -O3
         --------  --------
memset     0.666     1.045
fill      19.357     1.066
iterator  67.368     1.043
assign    17.975     0.530
for i     22.610     1.004

So apparently for these sizes, vector<bool>::assign() is faster. The code used for tests:

#include <vector>
#include <cstring>
#include <cstdlib>

#define TEST_METHOD 5
const size_t TEST_ITERATIONS = 34359738;
const size_t TEST_ARRAY_SIZE = 200;

using namespace std;

int main(int argc, char** argv) {

    std::vector<int> v(TEST_ARRAY_SIZE, 0);

    for(size_t i = 0; i < TEST_ITERATIONS; ++i) {
#if TEST_METHOD == 1
        memset(&v[0], false, v.size() * sizeof v[0]);
#elif TEST_METHOD == 2
        std::fill(v.begin(), v.end(), false);
   #elif TEST_METHOD == 3
        for (std::vector<int>::iterator it=v.begin(), end=v.end(); it!=end; ++it) {
            *it = 0;
        }
   #elif TEST_METHOD == 4
      v.assign(v.size(),false);
   #elif TEST_METHOD == 5
      for (size_t i = 0; i < TEST_ARRAY_SIZE; i++) {
          v[i] = false;
      }
#endif
    }

    return EXIT_SUCCESS;
}

I used GCC 7.2.0 compiler on Ubuntu 17.10. The command line for compiling:

g++ -std=c++11 -O0 main.cpp
g++ -std=c++11 -O3 main.cpp

Monocycle

Answer 6

try

std::fill

and also

std::size siz = vec.size();
//no memory allocating
vec.resize(0);
vec.resize(siz, 0);

Dilator

resize is very nice – Meloniemelony

I timed vec.resize(0); vec.resize(siz); and found that with -O3 it performs the same as memset. – Breadwinner

note that resize does not reset the value of the elements unless the new size is greater than the original. – Dayfly

@Dayfly but since there is a vec.resize(0) ; at the beginning, it will resize no matter what right? – Bowshot

Answer 7

Have a vector of zeroes ready, then switch it with current vector when you need zeroes:

std::vector<int> zeroes(N,0);
std::vector<int> currentVec(N);
...
currentVec.swap(zeroes);

this effectively zeroes the currentVec in O(1) complexity. But until next time you need zeroing, you have to fill the other (zeroes) with zeroes, asynchronously. You can use a dedicated thread for this. Then during swapping, just an overhead of "mutex" will be there.

std::lock_guard<std::mutex> lg(mut);
currentVec.swap(zeroes);

while in another thread:

std::lock_guard<std::mutex> lg(mut);
std::fill(zeroes.begin(),zeroes.end(),0);

Womanizer