Strange (huge) performance difference between std::vector, QList and std::list

Question

While writing a program which handles a relativly large number of elements (~100k) i noticed a strange difference between std::list and QList. At first i used a std::vector, which performs well. But because the programm often needs to insert elements in a random position in the vector, i switched to std::list, which had a constant time for insertion, when the iterator is at the wanted position.

The problem is, std::list performed way worse than the std::vector with both the insert() and the push_back() method. Measured for adding 100 consequtive elements to a list with 100k elements i got:

~25ms for the std::vector (worst case when adding at the beginning)
over 600ms(!) for std::list (any position, even with push_back() or insert(list.begin()).

Please note, that the time to insert the elements does not include the time to reach the position with the iterator.

I know of the performance problems of lists because of the cache-misses a list causes but this seems to be way off the limits for a cache-miss. Also the time to insert an element(a simple struct with 5 constant length variables) increases with the size of the list. Even the operation to get the size of the list takes more time. This stands in total contrast to the time complexity guaranteed for both operations for the list: constant.

See: Here

Just out of curiosity a changed from std::list to QList and viola: Insertion time is constant and at between 0ms and 1ms.

Here's the code used to measure the time for insertion.

No other operations are performed between the two timepoints: WRONG: used the size() method

std::List:

    QTime time;
    time.start();

    for (int a = 1; a <= lineChange; a++)
    {
        listData.insert(listIterator, newElement); 
    }        
    int elapsed = time.restart();
    qDebug() << "elapsed: " << elapsed << "ms";

Result: elapsed: 662ms

QList:

    QTime time;
    time.start();

    for (int a = 1; a <= lineChange; a++)
    {
        QListData.insert(iteratorPos, newElement);
        position++;
    } 

    int elapsed = time.restart();
    qDebug() << "elapsed: " << elapsed << "ms";

Result: elapsed: 1ms

std::vector:

    QTime time;
    time.start();

    for (int a = 1; a <= lineChange; a++)
    {
        vectorData.insert(vectorIterator, newElement);

        /*update of the iterator when it was 
        invalidated due to resize of the vector*/
    }    

    int elapsed = time.restart();
    qDebug() << "elapsed: " << elapsed << "ms";

Result: elapsed: 27ms

So, why is there such a huge difference between between QList and std::list? Or better: Why is the performance if std::list so disastrous?

As a side information: Im using the QtEditor with gcc under Linux (Mint) with flags set to c++11

EDIT:

Datatypes and declarations:

typedef struct TOKELEMENT {
    unsigned int column;
    unsigned int lenght;
    unsigned int tType;
    std::string value;
} tokElement;

// the three lists
std::vector<okElement> vectorData;
std::list<tokElement> listData;
QList<tokElement> QListData;

tokElement newElement;

unsigned int iteratorPos;
std::vector<std::vector<tokElement> >::iterator vectorIterator;
std::list<std::vector<tokElement> >::iterator listIterator;

//lineChange is an unsigned int, given as function parameter
unsigned int lineChange;

Without the context (SSCCE), we can only *guess* what's going on. I could *guess* for example, that `QList` might store only a pointer (depending on the type of the element), whereas `list` and `vector` store by-value. I could *guess* furthermore, that `list` doesn't keep a "free list" and therefore has to allocate for each inserted element. — dyp, Mar 16 '14 at 00:15
Can you show enough of the code to see the declaration of all relevant variables, particularly `ElementList`, `actIterator`, and `lineChange`? — user2357112, Mar 16 '14 at 00:24
Also, note that QList is not a linked list. From the [docs](http://qt-project.org/doc/qt-4.8/qlist.html): "Internally, QList is represented as an array of pointers to items of type T. If T is itself a pointer type or a basic type that is no larger than a pointer, or if T is one of Qt's shared classes, then QList stores the items directly in the pointer array." — user2357112, Mar 16 '14 at 00:26
You mention size() is performing bad - that's probably due to gcc not maintaining the new standard in this case. See - http://stackoverflow.com/questions/19154205/should-stdlistsize-have-constant-complexity-in-c11 — Leeor, Mar 16 '14 at 00:49
We need at least the declarations and types. Also, are you compiling with at least `-O2` and `-DNDEBUG`? — Potatoswatter, Mar 16 '14 at 02:48
Sorry for the delay, i tried to create a SSCCE to show, but the error didn't appear there. I'll update the post with the declarations. But i think i found the problem. I hat a check for the size of the list in the *for*-loop to determine whether do use push_back() or insert(). As @Leeor said, it's time-complexity is not O(1). Sorry for the inconveniance — nils277, Mar 16 '14 at 02:56
I can't answer your question but out of curiosity: are you inserting in an already sorted list? — a.lasram, Mar 16 '14 at 03:38
@a.lasram When you mean if i ever called list::sort() on the list, then no. On the other hand the list is sorted in the meaning that the elements are inserted or removed from the positions they should occure. A sorting with list::sort() is not necessary. — nils277, Mar 16 '14 at 04:05

score 3 · Accepted Answer · answered Mar 16 '14 at 03:44

3

In contrast to what i mentionend in the question (shame on me), i had another check for the size of the std::list in the for-loop to determine whether to use insert() or push_back() on the list. Since this function doesn't have the time complexity of O(1) but O(n) this slowed down the whole insertion a lot. Thanks to Leeor for pointing this out.

After moving this check out of the for-loop the std::list performed as expetected and even faster than the QList.

answered Mar 16 '14 at 03:44

nils277

231
3
8

Note that a well written `std::vector` version would use a mass-insert algorithm to add elements (possibly as it traverses), instead of a loop. In order for the list to win "fairly", you have to *find* the insert location orders of magnitude less often than you *insert* at that position, and you need to use the container between the inserts (while wanting to maintain the insert position almost always). – Yakk - Adam Nevraumont Jun 29 '16 at 20:49

Strange (huge) performance difference between std::vector, QList and std::list

1 Answers1