Populating a list of integers is 100 times faster than populating a vector of integers

Question

I am comparing the times taken to populate a list of integers against a vector of integers .

Each vector & list is populated with 10 million random integers and this experiment is repeated 100 times to find the average .

To my amazement , populating a list is about 100 times quicker than populating a vector of integers . I would expect populating vector of integer to be much faster as vector are continuous in memory and insertions are much quicker .

How can populating a list be 100 times not 10 times quicker than populating a vector. I am sure I am missing some concept or idea which is causing this

This is my code used to generate the results

#include <iostream>
#include <sstream>
#include <list>
#include <vector>
#include <ctime>
#include <time.h>

using namespace std;



int main()
{
   list<int> mylist;
   vector<int> myvector;
   srand(time(NULL));
   int num;

   clock_t list_start;
   clock_t list_end;
   clock_t list_totaltime;

   for (int i=0;i<100;i++)
   {

    list_start = clock();

        for (int i = 0 ; i < 10000000 ; i++ ) // 10 million
        {    
            num = rand() % 10000000 ; 

            mylist.push_back(num);
         }

    list_end = clock();

    list_totaltime += difftime(list_end,list_start);

    mylist.clear();

   }

   cout << list_totaltime/CLOCKS_PER_SEC/100;

   cout <<" List is done ";

   cout << endl
        << endl;

   clock_t vector_start;  
   clock_t vector_end;
   clock_t vector_totaltime;

   for (int i=0;i<100;i++)
   {

    vector_start = clock();

        for (int i = 0 ; i < 10000000 ; i++ ) // 10 million times
        {    
            num = rand() % 10000000 ; 

            myvector.push_back(num);
        }

    vector_end = clock();

    vector_totaltime += difftime(vector_end,vector_start);

    myvector.clear();

    }

   cout << vector_totaltime/CLOCKS_PER_SEC/100;

   cout << " Vector is done " ;


}

Can someone explain to me why this is happening ???

You might try the test with `myvector.reserve(10000000)` before the loop. — nos, Feb 17 '14 at 11:32
You need to initialize `list_totaltime` and `vector_totaltime`. Crank up your compiler warning levels. — juanchopanza, Feb 17 '14 at 11:33
When list size increases is has no need to relocate what is already located, unlike vector (due to continuousness). — Cthulhu, Feb 17 '14 at 11:33
@juanchopanza Does initialising affect the time taken to populate the vector or list ?? — Computernerd, Feb 17 '14 at 11:34
You also have integer division. So, when I run your code, with the initialization problems fixed, I get `0` for both. — juanchopanza, Feb 17 '14 at 11:35
@juanchopanza what did you initialise list_totaltime and vector_totaltime to ??? — Computernerd, Feb 17 '14 at 11:39
@juanchopanza "...garbage" The word "worthless" popped into my head first, but that works =P — WhozCraig, Feb 17 '14 at 11:46
Because one of them results in a value >= 1, and is truncated to 1. The other is less than 1 and is truncated to 0. Try: `1.0 * list_totaltime/CLOCKS_PER_SEC/100` — Benjamin Lindley, Feb 17 '14 at 12:08
I initialized them to `0`. Fixing everything, and using an optimized build, I got `0.2067 List is done` and `0.0782 Vector is done`. — juanchopanza, Feb 17 '14 at 12:57

score 2 · Accepted Answer · answered Feb 17 '14 at 12:27

I tried with VS2013 C++ compiler, and std::vector is much faster than std::list (as I expected).

I got the following results:

Testing STL vector vs. list push_back() time
--------------------------------------------

Testing std::vector...done.
std::vector::push_back(): 89.1318 ms

Testing std::list...done.
std::list::push_back(): 781.214 ms

I used Windows high-resolution performance counters to measure times.
Of course, I did the tests in optimized release build.

I also refactored the random number generation out of the push-back loop, and used a more serious random number technique than rand().

Is your method of using clock() good to measure execution times?

What C++ compiler did you use? Did you test an optimized build?

The compilable test code follows:

// Testing push_back performance: std::vector vs. std::list

#include <algorithm>
#include <exception>
#include <iostream>
#include <list>
#include <random>
#include <vector>
#include <Windows.h>
using namespace std;

long long Counter() {
    LARGE_INTEGER li;
    QueryPerformanceCounter(&li);
    return li.QuadPart;
}

long long Frequency() {
    LARGE_INTEGER li;
    QueryPerformanceFrequency(&li);
    return li.QuadPart;
}

void PrintTime(const long long start, const long long finish, 
               const char * const s) {
    cout << s << ": " << (finish - start) * 1000.0 / Frequency() << " ms" << endl;
}

int main() {
    try {
        cout << endl
            << "Testing STL vector vs. list push_back() time\n"
            << "--------------------------------------------\n"
            << endl;

        const auto shuffled = []() -> vector<int> {
            static const int kCount = 10 * 1000 * 1000;

            vector<int> v;
            v.reserve(kCount);

            for (int i = 1; i <= kCount; ++i) {
                v.push_back((i % 100));
            }

            mt19937 prng(1995);
            shuffle(v.begin(), v.end(), prng);

            return v;
        }();

        long long start = 0;
        long long finish = 0;

        cout << "Testing std::vector...";
        start = Counter();
        vector<int> v;
        for (size_t i = 0; i < shuffled.size(); ++i) {
            v.push_back(shuffled[i]);
        }
        finish = Counter();
        cout << "done.\n";
        PrintTime(start, finish, "std::vector::push_back()");

        cout << endl;

        cout << "Testing std::list...";
        start = Counter();
        list<int> l;
        for (size_t i = 0; i < shuffled.size(); ++i) {
            l.push_back(shuffled[i]);
        }
        finish = Counter();
        cout << "done.\n";
        PrintTime(start, finish, "std::list::push_back()");
    } catch (const exception& ex) {
        cout << "\n*** ERROR: " << ex.what() << endl;
    }
}

I did it on a qunicy 2005 compiler , highly doubt theres a optmised built for this — Computernerd, Feb 17 '14 at 12:35

score 1 · Answer 2 · edited May 23 '17 at 12:10

Can someone explain to me why this is happening ???

The result is not real i.e., populating a list of integers is not 100 times faster than populating a vector of integers. What you see is a benchmark artifact due to errors in your code pointed out in the comments.

If you initialize the variables and avoid the integer division then you should see different result e.g., on my machine populating a vector is 3 times faster than populating a list (btw, calling vector::reserve() has no effect on the result).

Related: Fun with uninitialized variables and compiler (GCC).

Also, you shouldn't use difftime(time_t, time_t) with clock_t values.

score 1 · Answer 3 · answered Feb 17 '14 at 13:00

For the record, after fixing uninitialized variable problems and integer division, running an optimized build compiled with gcc 4.7.3 on x86_64 and the following flags

g++ -Wall -Wextra -pedantic-errors -pthread -std=c++11 -O3

I get

0.2 List is done 
0.07 Vector is done

So, the vector is faster, as I would have expected. This without any further change to the code.

score 0 · Answer 4 · answered Feb 17 '14 at 11:39

Elements in a vector are stored sequentially in consecutive memory locations. Initially some memory is allotted to the vector and as you keep adding more elements to a vector there has to a lot of memory operations to retain this property of vector. These memory operations take considerable time.

Whereas in case of a list the head stores the address of the second, the address of the third element is stored in third and so on. Here is there is no need of any memory re-allocation.

But lists take more storage memory compared to vectors.

score -1 · Answer 5 · answered Feb 17 '14 at 11:40

-1

If the size of the vector exceeds its capacity, the vector needs to be reallocated. In this case all the previous values have to be copied to the new storage. Try to increase the capacity with vector::reserve to reduce the needed reallocations.

answered Feb 17 '14 at 11:40

jpo234

34
2

Populating a list of integers is 100 times faster than populating a vector of integers

5 Answers5